给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
示例 1：
输入：s = “3[a]2[bc]”
输出：“aaabcbc”
这题用递归或栈都可以，我用的是栈来写，准备两个栈，一个数字栈sta_num，一个字符串栈sta_str，再准备一个字符串变量str和整型num，开始遍历字符串s，每次先判断s[i]是否是数字字符，如果是，转换成数字类型加到num上，如果是字母，就加到str上，当遍历到左括号时，说明要记录重复的字符串了，我们把要重复的次数num存入栈sta_num中，把之前遍历好的字符串str先保存起来存入字符串栈sta_str中，然后把num和str清空，准备记录下次的数据，在没遇到右括号前，操作都和上述一样，当遇到右括号后，我们按照sta_num的栈顶元素，重复sta_num.top()次当前的字符串str，重复完后把这个栈顶元素出栈，把当前的str接到字符串栈的栈顶元素后面。重复操作，最后返回str即可。
class Solution {
public:
string decodeString(string s) {
stacksta_num;
stacksta_str;
string str;
int num = 0;
int n = s.size();
for (int i = 0; i < n; i++)
{
if (s[i] >= '0' && s[i] <= '9')
num = num * 10 + s[i] - '0';
else if (s[i] == '[')
{
sta_num.push(num);
num = 0;
sta_str.push(str);
str.clear();
}
else if (s[i] == ']')
{
string tmp = str;
for (int j = 1; j < sta_num.top(); j++)
str += tmp;
sta_num.pop();
str = sta_str.top() + str;
sta_str.pop();
}
else
{
str += s[i];
}
}
return str;
}
};
力扣——每日一题
2022. 将一维数组转变成二维数组
给你一个下标从 0 开始的一维整数数组 original 和两个整数 m 和 n 。你需要使用 original 中 所有 元素创建一个 m 行 n 列的二维数组。
original 中下标从 0 到 n - 1 （都 包含 ）的元素构成二维数组的第一行，下标从 n 到 2 * n - 1 （都 包含 ）的元素构成二维数组的第二行，依此类推。
请你根据上述过程返回一个 m x n 的二维数组。如果无法构成这样的二维数组，请你返回一个空的二维数组。
示例 1：
输入：original = [1,2,3,4], m = 2, n = 2
输出：[[1,2],[3,4]]
解释：
构造出的二维数组应该包含 2 行 2 列。
original 中第一个 n=2 的部分为 [1,2] ，构成二维数组的第一行。
original 中第二个 n=2 的部分为 [3,4] ，构成二维数组的第二行。
先判断一下一维数组的元素是否等于m*n，如果不等于就返回一个空的二维数组。如果相等，就把二维数组开辟出m行n列的空间，再用for循环把一维数组的值一个个赋值进去即可。
class Solution {
public:
vector> construct2DArray(vector& original, int m, int n) {
int num=original.size();
vector>v;
if(num!=m*n)return v;
v.resize(m,vector(n));
int l=0;
for(int i=0;i
用一个快速for循环也可以，速度更快。
class Solution {
public:
vector> construct2DArray(vector& original, int m, int n) {
int num=original.size();
vector>v;
if(num!=m*n)return v;
v.resize(m,vector(n));
int k=0,j=0;
for(auto i:original)
if(j
912. 排序数组
给你一个整数数组 nums，请你将该数组升序排列。
示例 1：
输入：nums = [5,2,3,1]
输出：[1,2,3,5]
快速排序。
class Solution {
public:
void quick_sort(vector&nums,int l,int r)
{
if(l>=r)return;
int x=nums[(l+r)/2],i=l-1,j=r+1;
while(ix);
if(i sortArray(vector& nums) {
quick_sort(nums,0,nums.size()-1);
return nums;
}
};
169. 多数元素
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：[3,2,3]
输出：3
进阶：
- 尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
这题可以用哈希表记录各个元素的出现次数，然后找到次数最大的那个元素，这种解法的时间复杂度是O(n)，空间复杂度也是O(n)。
class Solution {
public:
int majorityElement(vector& nums) {
unordered_mapmymap;
int ans=0,num=0;
for(auto i:nums)
{
if(ans<++mymap[i])
{
ans=mymap[i];
num=i;
}
}
return num;
}
};
但进阶要求空间复杂度为O(1)，所以我们要找个操作更骚的解法，这里就学到一个新的知识点：摩尔投票。
摩尔投票的意思是这样的：假如几个国家之间相互打仗，每个国家都有着一部分兵力，每一个兵都可以和另一个国家的兵一换一，战争结束后哪个国家还剩有兵，哪个国家就获胜，此时如果有一个国家的兵比其它所有国家的兵总和还多，那么这个国家必然会胜出。因为哪怕其它几个国家联手对付他，兵也不够它一换一的。
在这道题里，国家就是各个不同的数，兵的数量就是这些数的出现次数。我们可以从第一个数开始，准备一个数记录当前的胜者num，一个数记录兵力ans。开始遍历nums，如果num和nums[i]相同，那么兵力ans++，如果不相同，说明遭遇敌人，ans–，当ans<0时，新的胜者就是nums[i]，用num记录下来，这样，最后胜出的必然是那个数占有一大半的数，遍历完后，返回num即可。时间复杂度是O(n)，空间复杂度是O(1)。
class Solution {
public:
int majorityElement(vector& nums) {
int ans=1,num=nums[0],n=nums.size();
for(int i=1;i
378. 有序矩阵中第 K 小的元素
给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。
示例 1：
输入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
输出：13
解释：矩阵中的元素为 [1,5,9,10,11,12,13,13,15]，第 8 小元素是 13
题目说了，每行每列都是升序的，那我们就把所有的行都用归并排序整合在一起，最后返回下标为k-1的元素即可。
class Solution {
public:
void merge_sort(vector&v,vector&num)
{
int n=v.size(),m=num.size(),i=0,j=0;
vectorarr;
while(i>& matrix, int k) {
vectorv;
v=matrix[0];
int n=matrix.size();
for(int i=1;i 
