- 1谷歌十年磨一剑，Jetpack Compose 从入门到精通，给出最美好的答案_jetpack compose accompnish
- 2在build.gradle下 使用 compile 时 gradle 下载很慢 解决办法_gradle compile太慢
- 3Python学习篇30-神经网络_python神经网络
- 4adb命令 查看运行APP当前页面的Activity名称_adb 查看当前activity name
- 5鸿蒙开发者公测邀请码,HarmonyOS 2.0鸿蒙第二期开发者Beta公测申请指南（05.09-05.17）...
- 6geogebra mac版【多平台的动态数学教育软件】_geogebro在线使用是动态的吗
- 7波形图数据提取_从图像提取波形
- 8HTML（二）——列表、表格_html列表怎么写
- 9Android权限分析_android 06755与00755
- 10C语言——PTA 统计素数并求和_c语言统计素数并求和pta
Leetcode热题Hot100+Top面试题-数组_leetcode top100和hot100
赞
踩
1-两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
提示：
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案
解题思路
两层遍历的方式，时间复杂度为O（n^2）。
C++实现
#include <iostream> #include <vector> using namespace std; class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { if(nums.size()<2||nums.size()>1e4||target<-1e9||target>1e9) { throw new std::invalid_argument("The list is out of range"); } vector<int> temp; for(int i=0;i<nums.size();++i) { for(int j=i+1;j<nums.size();++j) { if (nums[j]+nums[i]==target) { temp.push_back(i); temp.push_back(j); return temp; } } } return temp; } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
Python实现
class Solution(object): def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ result = [] for i, each in enumerate(nums): if abs(target-each) >=0 and i not in result: try: tmp = nums.index(target - each) if tmp != i: result.append(i) result.append(tmp) except: continue return result
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？
可以使用哈希表，也就是散列表，在C++中是map容器，Python就是字典。
C++实现
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { map<int,int> a;//提供一对一的hash vector<int> b(2,-1);//用来承载结果，初始化一个大小为2，值为-1的容器b for(int i=0;i<nums.size();i++) { if(a.count(target-nums[i])>0) { b[0]=a[target-nums[i]]; b[1]=i; break; } a[nums[i]]=i;//反过来放入map中，用来获取结果下标 } return b; } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
Python实现
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
if len(nums) <= 1:
return False
buff_dict = {}
for i in range(len(nums)):
if nums[i] in buff_dict:
return [buff_dict[nums[i]], i]
else:
buff_dict[target - nums[i]] = i
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
29-两数相除
给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
方法一：逻辑
越界问题只要对除数是1和-1单独讨论就可以
class Solution { public: int divide(int dividend, int divisor) { if(dividend == 0) return 0; if(divisor == 1) return dividend; if(divisor == -1){ if(dividend>INT_MIN) return -dividend;// 只要不是最小的那个整数，都是直接返回相反数就好啦 return INT_MAX;// 是最小的那个，那就返回最大的整数啦 } long a = dividend; long b = divisor; int sign = 1; if((a>0&&b<0) || (a<0&&b>0)){ sign = -1; } a = a>0?a:-a; b = b>0?b:-b; long res = div(a,b); if(sign>0)return res>INT_MAX?INT_MAX:res; return -res; } int div(long a, long b){ // 似乎精髓和难点就在于下面这几句 if(a<b) return 0; long count = 1; long tb = b; // 在后面的代码中不更新b while((tb+tb)<=a){ count = count + count; // 最小解翻倍 tb = tb+tb; // 当前测试的值也翻倍 } return count + div(a-tb,b); } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 时间复杂度：O（logC），其中C表示32位整数的范围
- 空间复杂度：O（1）
448-找到所有数组中消失的数字
给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。
方法一：原地修改
我们可以用一个哈希表记录数组nums 中的数字，由于数字范围均在[1,n] 中，记录数字后我们再利用哈希表检查[1,n] 中的每一个数是否出现，从而找到缺失的数字。
由于数字范围均在[1,n] 中，我们也可以用一个长度为 n 的数组来代替哈希表。这一做法的空间复杂度是 O(n) 的。我们的目标是优化空间复杂度到O(1)。
注意到nums 的长度恰好也为 n，能否让nums 充当哈希表呢？
由于nums 的数字范围均在[1,n] 中，我们可以利用这一范围之外的数字，来表达「是否存在」的含义。
具体来说，遍历nums，每遇到一个数 x，就让nums[x−1] 增加 n。由于 nums 中所有数均在 [1,n] 中，增加以后，这些数必然大于 n。最后我们遍历 nums，若 nums[i] 未大于 n，就说明没有遇到过数 i+1。这样我们就找到了缺失的数字。
注意，当我们遍历到某个位置时，其中的数可能已经被增加过，因此需要对 n 取模来还原出它本来的值。
class Solution { public: vector<int> findDisappearedNumbers(vector<int>& nums) { int n = nums.size(); for (auto& num : nums) { int x = (num - 1) % n; nums[x] += n; } vector<int> ret; for (int i = 0; i < n; i++) { if (nums[i] <= n) { ret.push_back(i + 1); } } return ret; } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 时间复杂度：O（n）
- 空间复杂度：O（1）
7-整数反转
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。
方法一：栈
class Solution { public: int reverse(int x) { int flag = 1, num = 0,index=0; string str = to_string(x); stack<char>stk; for (int i = 0; i < str.size(); ++i) { if (str[i] == '-') { flag = -1; continue; } stk.push(str[i]); } while (!stk.empty()) { if(stk.top()=='0') { stk.pop(); } else break; } index=stk.size()-1; while (!stk.empty()) { int s = stk.top()-'0'; stk.pop(); if(num>INT_MAX-s * pow(10,index)) return 0; num = num + s * pow(10,index); index--; } return num*flag; } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
1.时间复杂度：O（logx），x为十进制的位数
2. 空间复杂度：O（1）
方法二：数学
记 rev 为翻转后的数字，为完成翻转，我们可以重复「弹出」x 的末尾数字，将其「推入」rev 的末尾，直至 x 为 0。
要在没有辅助栈或数组的帮助下「弹出」和「推入」数字，我们可以使用如下数学方法：
// 弹出 x 的末尾数字 digit
digit = x % 10
x /= 10
// 将数字 digit 推入 rev 末尾
rev = rev * 10 + digit
- 1
- 2
- 3
- 4
- 5
- 6
题目需要判断反转后的数字是否超过 32 位有符号整数的范围 [-231,231-1]，例如 x=2123456789 反转后rev=9876543212>231 −1=2147483647，超过了 32 位有符号整数的范围。
因此我们需要在「推入」数字之前，判断是否满足
若该不等式不成立则返回 00。
但是题目要求不允许使用 6464 位整数，即运算过程中的数字必须在 3232 位有符号整数的范围内，因此我们不能直接按照上述式子计算，需要另寻他路。
考虑 x>0x>0 的情况，记 \textit{INT_MAX}=2^{31}-1=2147483647INT_MAX=2
31
−1=2147483647，由于
讨论该不等式成立的条件：
class Solution {
public:
int reverse(int x) {
int rev = 0;
while (x != 0) {
if (rev < INT_MIN / 10 || rev > INT_MAX / 10) {
return 0;
}
int digit = x % 10;
x /= 10;
rev = rev * 10 + digit;
}
return rev;
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 时间复杂度：O（logx），x为十进制的位数
- 空间复杂度：O（1）
4-寻找两个有序数组的中位数
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
解题思路
看到 log，很明显，我们只有用到二分的方法才能达到。我们不妨用另一种思路，题目是求中位数，其实就是求第 k 小数的一种特殊情况，而求第 k 小数有一种算法。
由于数列是有序的，其实我们完全可以一半儿一半儿的排除。假设我们要找第 k 小数，我们可以每次循环排除掉 k/2 个数。看下边一个例子。
假设我们要找第 7 小的数字。
我们比较两个数组的第 k/2 个数字，如果 k 是奇数，向下取整。也就是比较第 3个数字，上边数组中的 4 和下边数组中的 3，如果哪个小，就表明该数组的前 k/2 个数字都不是第 k 小数字，所以可以排除。也就是 1，2，3 这三个数字不可能是第 7 小的数字，我们可以把它排除掉。将 1349和 45678910两个数组作为新的数组进行比较。
更一般的情况 A[1] ，A[2] ，A[3]，A[k/2] … ，B[1]，B[2]，B[3]，B[k/2] … ，如果 A[k/2]<B[k/2] ，那么A[1]，A[2]，A[3]，A[k/2]都不可能是第 k 小的数字。
A 数组中比 A[k/2] 小的数有 k/2-1 个，B 数组中，B[k/2] 比 A[k/2] 小，假设 B[k/2] 前边的数字都比 A[k/2] 小，也只有 k/2-1 个，所以比 A[k/2] 小的数字最多有 k/1-1+k/2-1=k-2个，所以 A[k/2] 最多是第 k-1 小的数。而比 A[k/2] 小的数更不可能是第 k 小的数了，所以可以把它们排除。
橙色的部分表示已经去掉的数字。
由于我们已经排除掉了 3 个数字，就是这 3 个数字一定在最前边，所以在两个新数组中，我们只需要找第 7 - 3 = 4 小的数字就可以了，也就是 k = 4。此时两个数组，比较第 2 个数字，3 < 5，所以我们可以把小的那个数组中的 1 ，3 排除掉了。
我们又排除掉 2 个数字，所以现在找第 4 - 2 = 2 小的数字就可以了。此时比较两个数组中的第 k / 2 = 1 个数，4 == 4，怎么办呢？由于两个数相等，所以我们无论去掉哪个数组中的都行，因为去掉 1 个总会保留 1 个的，所以没有影响。为了统一，我们就假设 4 > 4 吧，所以此时将下边的 4 去掉。
由于又去掉 1 个数字，此时我们要找第 1 小的数字，所以只需判断两个数组中第一个数字哪个小就可以了，也就是 4。
所以第 7 小的数字是 4。
我们每次都是取 k/2 的数进行比较，有时候可能会遇到数组长度小于 k/2的时候。
此时 k / 2 等于 3，而上边的数组长度是 2，我们此时将箭头指向它的末尾就可以了。这样的话，由于 2 < 3，所以就会导致上边的数组 1，2 都被排除。造成下边的情况。
由于 2 个元素被排除，所以此时 k = 5，又由于上边的数组已经空了，我们只需要返回下边的数组的第 5 个数字就可以了。
从上边可以看到，无论是找第奇数个还是第偶数个数字，对我们的算法并没有影响，而且在算法进行中，k 的值都有可能从奇数变为偶数，最终都会变为 1 或者由于一个数组空了，直接返回结果。
所以我们采用递归的思路，为了防止数组长度小于 k/2，所以每次比较 min(k/2，len(数组) 对应的数字，把小的那个对应的数组的数字排除，将两个新数组进入递归，并且 k 要减去排除的数字的个数。递归出口就是当 k=1 或者其中一个数字长度是 0 了。
C++实现
class Solution() { double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int n=nums1.size();int m=nums2.size(); int left=(n+m+1)/2;int right=(n+m+2)/2; return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5; } int getKth(vector<int>& nums1, int start1,int end1,vector<int>& nums2,int start2,int end2,int k) { int len1=end1-start1+1; int len2=end2-start2+1; //让 len1 的长度小于 len2，这样就能保证如果有数组空了，一定是 len1 if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k); if (len1 == 0) return nums2[start2 + k - 1]; if (k == 1) return min(nums1[start1], nums2[start2]); int i = start1 + min(len1, k / 2) - 1; int j = start2 + min(len2, k / 2) - 1; if (nums1[i] > nums2[j]) { return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1)); } else { return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1)); } } int Min(int k,int length) { if(k<=length) return k; return length; } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
复杂度分析
- 时间复杂度：每进行一次循环，我们就减少 k/2 个元素，所以时间复杂度是 O(log(k)，而 k=(m+n)/2，所以最终的复杂也就是 O(log(m+n))
- 空间复杂度：虽然我们用到了递归，但是可以看到这个递归属于尾递归，所以编译器不需要不停地堆栈，所以空间复杂度为 O(1)
3-盛最多水的容器
给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器。
解题思路
我们有两种方法：即双层遍历与双指针，双层遍历的时间复杂度会超出时间限制，因此我们采用双指针法。
本题是一道经典的面试题，最优的做法是使用「双指针」。如果读者第一次看到这题，不一定能想出双指针的做法。
分析
我们先从题目中的示例开始，一步一步地解释双指针算法的过程。稍后再给出算法正确性的证明。
题目中的示例为：
[1, 8, 6, 2, 5, 4, 8, 3, 7]
在初始时，左右指针分别指向数组的左右两端，它们可以容纳的水量为min(1,7)∗8=8。
此时我们需要移动一个指针。移动哪一个呢？直觉告诉我们，应该移动对应数字较小的那个指针（即此时的左指针）。这是因为，由于容纳的水量是由
两个指针指向的数字中较小值 * 指针之间的距离
决定的。如果我们移动数字较大的那个指针，那么前者「两个指针指向的数字中较小值」不会增加，后者「指针之间的距离」会减小，那么这个乘积会减小。因此，我们移动数字较大的那个指针是不合理的。因此，我们移动 数字较小的那个指针。
有读者可能会产生疑问：我们可不可以同时移动两个指针？ 先别急，我们先假设 总是移动数字较小的那个指针 的思路是正确的，在走完流程之后，我们再去进行证明。
所以，我们将左指针向右移动：
[1, 8, 6, 2, 5, 4, 8, 3, 7]
此时可以容纳的水量为min(8,7)∗7=49。由于右指针对应的数字较小，我们移动右指针：
[1, 8, 6, 2, 5, 4, 8, 3, 7]
此时可以容纳的水量为min(8,3)∗6=18。由于右指针对应的数字较小，我们移动右指针：
[1, 8, 6, 2, 5, 4, 8, 3, 7]
此时可以容纳的水量为 min(8,8)∗5=40。两指针对应的数字相同，我们可以任意移动一个，例如左指针：
[1, 8, 6, 2, 5, 4, 8, 3, 7]
此时可以容纳的水量为min(6,8)∗4=24。由于左指针对应的数字较小，我们移动左指针，并且可以发现，在这之后左指针对应的数字总是较小，因此我们会一直移动左指针，直到两个指针重合。在这期间，对应的可以容纳的水量为：min(2,8)∗3=6，min(5,8)∗2=10，min(4,8)∗1=4。
在我们移动指针的过程中，计算到的最多可以容纳的数量为 49，即为最终的答案。
C++实现
class Solution() { int maxArea1(vector<int>& height) { //定义不断更新的最大值，左指针和右指针 int ans=0;int l=0,r=height.size()-1; while(l<r) { if(height[l]<height[r]) { ans=max(ans,min(height[r],height[l])*(r-l)); l++; } else { ans=max(ans,min(height[r],height[l])*(r-l)); r--; } } return ans; } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
复杂度分析
- 时间复杂度：O（n），n是数组的长度，两个指针总计最多遍历整个数组一次
- 空间复杂度：O（1），只需要额外的常数级别的空间
15-三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
解题思路
排序 + 双指针
本题的难点在于如何去除重复解。
算法流程：
- 特判，对于数组长度 n，如果数组为 null 或者数组长度小于 3，返回 []。
- 对数组进行排序。
- 遍历排序后数组：
若 nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于 0，直接返回结果。
对于重复元素：跳过，避免出现重复解
令左指针 L=i+1，右指针 R=n-1，当 L<R 时，执行循环：
当 nums[i]+nums[L]+nums[R]=0，执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 L,R移到下一位置，寻找新的解
若和大于 0，说明 nums[R] 太大，R 左移
若和小于 0，说明 nums[L]太小，L 右移
C++实现
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<int>ans1; vector<vector<int>>ans; if(nums.size()<3) return ans; sort(nums.begin(),nums.end()); int i=0; while(i<nums.size()-2) { if(nums[i]>0) return ans; int L=i+1,R=nums.size()-1; while (L<R) { if(nums[L]+nums[R]+nums[i]>0) { R--; } else if(nums[L]+nums[R]+nums[i]<0) { L++; } else { ans1.push_back(nums[i]); ans1.push_back(nums[L]); ans1.push_back( nums[R]); ans.push_back(ans1); //去除和左指针或右指针相等的元素 while (L<R&&nums[L]==nums[L+1]) { L++; } while (L<R&&nums[R]==nums[R-1]) { R--; } L++; R--; } } //去除和第一个位置一样的元素 while(nums[i]==nums[i+1]) i++; i++; } return ans; };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
复杂度分析
-
时间复杂度：O（n2）,数组排序O（NlogN）,遍历数组O（n2），双指针遍历O（n2），总体O（NlogN）+O（n）*O（n）=O(n2)
-
空间复杂度：O（n2）
31-下一个排列
实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列（即，组合出下一个更大的整数）。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须 原地 修改，只允许使用额外常数空间。
解题思路
前言
本题要求我们实现一个算法，将给定数字序列重新排列成字典序中下一个更大的排列。
以数字序列 [1,2,3] 为例，其排列按照字典序依次为：
[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]
- 1
- 2
- 3
- 4
- 5
- 6
这样，排列 [2,3,1] 的下一个排列即为 [3,1,2]。特别的，最大的排列 [3,2,1] 的下一个排列为最小的排列 [1,2,3]。
方法一：两遍扫描
思路及解法
注意到下一个排列总是比当前排列要大，除非该排列已经是最大的排列。我们希望找到一种方法，能够找到一个大于当前序列的新序列，且变大的幅度尽可能小。具体地：
我们需要将一个左边的「较小数」与一个右边的「较大数」交换，以能够让当前排列变大，从而得到下一个排列。
同时我们要让这个「较小数」尽量靠右，而「较大数」尽可能小。当交换完成后，「较大数」右边的数需要按照升序重新排列。这样可以在保证新排列大于原来排列的情况下，使变大的幅度尽可能小。
以排列[4,5,2,6,3,1] 为例：
我们能找到的符合条件的一对「较小数」与「较大数」的组合为 2 与 3，满足「较小数」尽量靠右，而「较大数」尽可能小。
当我们完成交换后排列变为 [4,5,3,6,2,1]，此时我们可以重排「较小数」右边的序列，序列变为 [4,5,3,1,2,6]。
具体地，我们这样描述该算法，对于长度为 n 的排列 a：
首先从后向前查找第一个顺序对(i,i+1)，满足 a[i] < a[i+1]。这样「较小数」即为 a[i]。此时[i+1,n) 必然是下降序列。
如果找到了顺序对，那么在区间 [i+1,n) 中从后向前查找第一个元素 j 满足a[i]<a[j]。这样「较大数」即为 a[j]。
交换 a[i]与 a[j]，此时可以证明区间 [i+1,n) 必为降序。我们可以直接使用双指针反转区间 [i+1,n) 使其变为升序，而无需对该区间进行排序。
注意
如果在步骤 1 找不到顺序对，说明当前序列已经是一个降序序列，即最大的序列，我们直接跳过步骤 2 执行步骤 3，即可得到最小的升序序列。
该方法支持序列中存在重复元素，且在 C++ 的标准库函数 next_permutation 中被采用。
解题思路
class Solution { public: void nextPermutation(vector<int>&nums) { int i=nums.size()-2; while(i>=0&&nums[i]>=nums[i+1]) i--; if(i>=0) { int j=nums.size()-1; while(j>=0&&nums[i]>=nums[j]) j--; swap(nums[i],nums[j]); } reverse(nums.begin()+i+1,nums.end());// 如果是最大的，会直接到-1 } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
复杂度分析
- 时间复杂度：O(N)，其中 N 为给定序列的长度。我们至多只需要扫描两次序列，以及进行一次反转操作。
- 空间复杂度：O(1)，只需要常数的空间存放若干变量。
33-搜索旋转排序数组
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
解题思路
思路和算法
二分查找
对于有序数组，可以使用二分查找的方法查找元素。
但是这道题中，数组本身不是有序的，进行旋转后只保证了数组的局部是有序的，这还能进行二分查找吗？答案是可以的。
可以发现的是，我们将数组从中间分开成左右两部分的时候，一定有一部分的数组是有序的。拿示例来看，我们从 6 这个位置分开以后数组变成了 [4, 5, 6] 和 [7, 0, 1, 2] 两个部分，其中左边 [4, 5, 6] 这个部分的数组是有序的，其他也是如此。
这启示我们可以在常规二分查找的时候查看当前 mid 为分割位置分割出来的两个部分 [l, mid] 和 [mid + 1, r] 哪个部分是有序的，并根据有序的那个部分确定我们该如何改变二分查找的上下界，因为我们能够根据有序的那部分判断出 target 在不在这个部分：
- 如果 [l, mid - 1] 是有序数组，且 target 的大小满足 [nums[l],nums[mid])，则我们应该将搜索范围缩小至 [l, mid - 1]，否则在 [mid + 1, r] 中寻找。
- 如果 [mid, r] 是有序数组，且 target 的大小满足 (nums[mid+1],nums[r]]，则我们应该将搜索范围缩小至 [mid + 1, r]，否则在 [l, mid - 1] 中寻找。
需要注意的是，二分的写法有很多种，所以在判断 target 大小与有序部分的关系的时候可能会出现细节上的差别
C++实现
class Solution { public: int search(vector<int>&nums,int target) { int n=(int)nums.size(); if(!n) return -1; if(n==1) return nums[0]==target?0:-1; int l=0,r=n-1; while(l<=r) { int mid=(l+r)/2; if(nums[mid]==target) return mid; //有序数组和无序数组的判断 if(nums[0]<=nums[mid]) { if(nums[l]<=target&&target<nums[mid]) r=mid-1; else l=mid+1; } else { if(nums[mid]<target&&target<=nums[r]) l=mid+1; else r=mid-1; } } } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
复杂度分析
- 时间复杂度：O(logn)，其中 n 为 nums 数组的大小。整个算法时间复杂度即为二分查找的时间复杂度 O(logn)。
- 空间复杂度： O(1) 。我们只需要常数级别的空间存放变量。
34-在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：
你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
解题思路
第一次完完整整Code出来的中等难度的题，把踩的坑和思路都记录一下，会越来越棒的。
我们基础框架采用二分法，使时间复杂度达到O（logN）。题中的关键词为排序数组，升序排列，且有重复的数字。我们可分为两步进行：
用基本二分法找到目标值，如果找不到，返回[-1,-1]
以找到的目标值为中心，向左向右查找与目标值相等的值
- 1
- 2
踩的坑：
for和while的差异，循环使用不熟练
if和else if只实现一个,是互斥的
数组中最后一个元素的索引为N-1
总结：基础差，明天恶补C++
代码比较冗杂，需继续优化
- 1
- 2
- 3
- 4
- 5
C++实现（自己实现）
#include<iostream> #include<vector> using namespace std; class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { int n = (int)nums.size();//后续修改 vector<int>vec(2, -1); //初始值 int midl = 0, midR = 0; //重复数字的初始位置和结束位置 //可省略 //if (!n) // return vec; int l = 0, r = n - 1; while (l <= r) { int mid = (l + r) / 2; midl = mid; midR = mid; if (nums[mid] == target) { if (mid >l) { for (int i = midl - 1; i >=0; i--) { if (nums[i] == target) midl--; } } if (mid < r) { for(int i=midR+1;i<=n-1;i++) { if (nums[i] == target) midR++; } } vec[0] = midl; vec[1] = midR; break; } else if (target > nums[mid]) l = mid + 1; else r = mid - 1; } return vec; } }; int main() { int nums[] = { 2,2 }; vector<int>num(nums, nums + 2); Solution s; vector<int>res=s.searchRange(num,2); for (auto it = res.begin(); it != res.end(); ++it) { std::cout << *it << " "; } system("pause"); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
补充：该算法时间复杂度没能达到题目要求，因为里面涉及两个循环，破坏了二分查找的独特性。
C++（官方）
class Solution { public: int binarySearch(vector<int>& nums, int target, bool lower) { int left = 0, right = (int)nums.size() - 1, ans = (int)nums.size(); while (left <= right) { int mid = (left + right) / 2; if (nums[mid] > target || (lower && nums[mid] >= target)) { right = mid - 1; ans = mid;//mid只存在右边 } else { left = mid + 1; } } return ans; } vector<int> searchRange(vector<int>& nums, int target) { int leftIdx = binarySearch(nums, target, true); int rightIdx = binarySearch(nums, target, false) - 1;//右边界-1 //leftIdx <= rightIdx包含了数组为空的情况，直接返回 if (leftIdx <= rightIdx && rightIdx < nums.size() && nums[leftIdx] == target && nums[rightIdx] == target) { return vector<int>{leftIdx, rightIdx}; } return vector<int>{-1, -1}; } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
复杂度分析
- 时间复杂度：O（logN）
- 空间复杂度：O（1），只需要常数空间存放若干变量
42-接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
解题思路
核心思想：不需要考虑如何处理整个字符串，而是去思考应该如何处理每一个字符。
这么一想，可以发现这道题的思路其实很简单。具体来说，仅仅对于位置 i，能装下多少水呢？
能装 2 格水，因为 height[i] 的高度为 0，而这里最多能盛 2 格水，2-0=2。
为什么位置 i 最多能盛 2 格水呢？因为，位置 i 能达到的水柱高度和其左边的最高柱子、右边的最高柱子有关，我们分别称这两个柱子高度为 l_max 和 r_max；位置 i 最大的水柱高度就是 min(l_max, r_max)。
更进一步，对于位置 i，能够装的水为：
water[i] = min(
# 左边最高的柱子
max(height[0..i]),
# 右边最高的柱子
max(height[i..end])
) - height[i]
- 1
- 2
- 3
- 4
- 5
- 6
1.暴力算法：超出时间限制
#include<iostream> #include <vector> using namespace std; class Solution { public: int trap(vector<int>& height) { int n = height.size(); int res = 0; for (int i = 1; i < n - 1; i++) { int l_max = 0, r_max = 0; // 找右边最高的柱子 for (int j = i; j < n; j++) r_max = max(r_max, height[j]); // 找左边最高的柱子 for (int j = i; j >= 0; j--) l_max = max(l_max, height[j]); // 如果自己就是最高的话， // l_max == r_max == height[i] res += min(l_max, r_max) - height[i]; } return res; } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
有之前的思路，这个解法应该是很直接粗暴的，时间复杂度 O(N^2)，空间复杂度 O(1)。但是很明显这种计算 r_max 和 l_max 的方式非常笨拙，一般的优化方法就是备忘录。
我们开两个数组 r_max 和 l_max 充当备忘录，l_max[i] 表示位置 i 左边最高的柱子高度，r_max[i] 表示位置 i 右边最高的柱子高度。预先把这两个数组计算好，避免重复计算：
2.备忘录优化
int trap(vector<int>& height) { if (height.empty()) return 0; int n = height.size(); int res = 0; // 数组充当备忘录 vector<int> l_max(n), r_max(n); // 初始化 base case l_max[0] = height[0]; r_max[n - 1] = height[n - 1]; // 从左向右计算 l_max for (int i = 1; i < n; i++) l_max[i] = max(height[i], l_max[i - 1]); // 从右向左计算 r_max for (int i = n - 2; i >= 0; i--) r_max[i] = max(height[i], r_max[i + 1]); // 计算答案 for (int i = 1; i < n - 1; i++) res += min(l_max[i], r_max[i]) - height[i]; return res; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
时间复杂度降低为O（n），但空间复杂度是O（n），有没有空间复杂度为O（1）的解法呢，这时候想起了双指针:
3.双指针
双指针边走边算，降低空间复杂度
需要注意的是：数组的第一个值和最后一个值不能接雨水。
int trap(vector<int>& height) { if (height.empty()) return 0; //防止下面的while出现死循环 int n = height.size(); int left = 0, right = n - 1; int res = 0; int l_max = height[0]; int r_max = height[n - 1]; while (left <= right) { l_max = max(l_max, height[left]); r_max = max(r_max, height[right]); // res += min(l_max, r_max) - height[i] if (l_max < r_max) { res += l_max - height[left]; left++; } else { res += r_max - height[right]; right--; } } return res; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 时间复杂度：O（n）
- 空间复杂度：O（1）
48-旋转图像
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
示例1
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]
- 1
- 2
解题思路
方法一：使用辅助数组
由于矩阵中的行列从 0 开始计数，因此对于矩阵中的元素 matrix[row][col]，在旋转后，它的新位置为matrixnew[col][n−row−1]。
这样一来，我们使用一个与 matrix 大小相同的辅助数组matrix new，临时存储旋转后的结果。我们遍历 matrix 中的每一个元素，根据上述规则将该元素存放到 matrixnew中对应的位置。在遍历完成之后，再将matrixnew 中的结果复制到原数组中即可。
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
// C++ 这里的 = 拷贝是值拷贝，会得到一个新的数组
auto matrix_new = matrix;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
matrix_new[j][n - i - 1] = matrix[i][j];
}
}
// 这里也是值拷贝
matrix = matrix_new;
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 时间复杂度：O(N^2)，其中 N 是matrix 的边长。
- 空间复杂度：O(N^2)。我们需要使用一个和 matrix 大小相同的辅助数组。
方法二：原地旋转
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
for (int i = 0; i < n / 2; ++i) {
for (int j = 0; j < (n + 1) / 2; ++j) {
int temp = matrix[i][j];
matrix[i][j] = matrix[n - j - 1][i];
matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
matrix[j][n - i - 1] = temp;
}
}
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 时间复杂度：O(N^2)，其中 N 是 matrix 的边长。我们需要枚举的子矩阵大小为 O(⌊n/2⌋×⌊(n+1)/2⌋)=O(N ^2)。
- 空间复杂度：O(1)。为原地旋转。
方法三：用翻转代替旋转
class Solution { public: void rotate(vector<vector<int>>& matrix) { int n = matrix.size(); // 水平翻转 for (int i = 0; i < n / 2; ++i) { for (int j = 0; j < n; ++j) { swap(matrix[i][j], matrix[n - i - 1][j]); } } // 主对角线翻转 for (int i = 0; i < n; ++i) { for (int j = 0; j < i; ++j) { swap(matrix[i][j], matrix[j][i]); } } } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 时间复杂度：O(N^2)，其中 N 是matrix 的边长。对于每一次翻转操作，我们都需要枚举矩阵中一半的元素。
- 空间复杂度：O(1)。为原地翻转得到的原地旋转。
。
75-颜色分类
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
解题思路
我们也可以考虑使用指针 p0来交换 0，p2来交换 2。此时，p0 的初始值仍然为 0，而 p2的初始值为 n−1。在遍历的过程中，我们需要找出所有的 0 交换至数组的头部，并且找出所有的 2 交换至数组的尾部。
注意：与p2交换时，数组中的数可能是2，也可能是0.
交换的数是2 的时候，需要不断与p2进行交换；
交换的数是0的时候，与p0进行交换；
交换的数是1的时候，不进行任何操作。
C++实现
class Solution { public: void sortColors(vector<int>& nums) { //sort(nums.begin(),nums.end()); int n=nums.size(); int ptr1=0,ptr2=n-1; for(int i=0;i<=ptr2;++i) { while(i<=ptr2&&nums[i]==2) { swap(nums[i],nums[ptr2]); --ptr2; } if(nums[i]==0) { swap(nums[i],nums[ptr1]); ptr1++; } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 时间复杂度：O（n）
- 空间复杂度：O（1）
128-最长连续序列
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
解题思路
我们考虑枚举数组中的每个数 x，考虑以其为起点，不断尝试匹配 x+1,x+2,⋯ 是否存在，假设最长匹配到了 x+y，那么以 x 为起点的最长连续序列即为 x,x+1,x+2,⋯,x+y，其长度为 y+1，我们不断枚举并更新答案即可。
对于匹配的过程，暴力的方法是 O(n) 遍历数组去看是否存在这个数，但其实更高效的方法是用一个哈希表存储数组中的数，这样查看一个数是否存在即能优化至 O(1) 的时间复杂度。
仅仅是这样我们的算法时间复杂度最坏情况下还是会达到 O(n^2)（即外层需要枚举 O(n) 个数，内层需要暴力匹配 O(n) 次），无法满足题目的要求。但仔细分析这个过程，我们会发现其中执行了很多不必要的枚举，如果已知有一个 x+1,x+2,⋯,x+y 的连续序列，而我们却重新从 x+1，x+2 或者是 x+y 处开始尝试匹配，那么得到的结果肯定不会优于枚举 x 为起点的答案，因此我们在外层循环的时候碰到这种情况跳过即可。
那么怎么判断是否跳过呢？由于我们要枚举的数 x 一定是在数组中不存在前驱数 x−1 的，不然按照上面的分析我们会从 x−1 开始尝试匹配，因此我们每次在哈希表中检查是否存在 x−1 即能判断是否需要跳过了。
C++实现
class Solution { public: int longestConsecutive(vector<int>& nums) { unordered_set<int> num_set; for (const int& num : nums) { num_set.insert(num); } int longestStreak = 0; for (const int& num : num_set) { if (!num_set.count(num - 1)) { int currentNum = num; int currentStreak = 1; while (num_set.count(currentNum + 1)) { currentNum += 1; currentStreak += 1; } longestStreak = max(longestStreak, currentStreak); } } return longestStreak; } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 时间复杂度：O（n），只有连续子序列的第一个数会进入内循环
- 空间复杂度：O（n），哈希表的大小
581-最短无序连续子数组
给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
请你找出符合题意的 最短 子数组，并输出它的长度。
方法一：排序
复制一个原数组，对其进行排序。查找第一个和最后一个元素不同的位置，即可找到对应的最短无序子数组。
class Solution { public: int findUnsortedSubarray(vector<int>& nums) { vector<int>nums1(nums); sort(nums1.begin(),nums1.end()); int left=0,n=nums.size(),right=n; for(int i=0;i<nums1.size();++i) { if(nums1[i]==nums[i]) left++; else break; } for(int i=n-1;i>=0;--i) { if(nums1[i]==nums[i]) right--; else break; } return right==0?0:right-left; } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 时间复杂度：O（nlogn）
- 空间复杂度：O（n）
方法二：一次遍历
利用数组中的最小元素的正确位置作为左边界，最大元素的正确位置作为右边界，即可找到最短无序子数组。
class Solution { public: int findUnsortedSubarray(vector<int>& nums) { int n = nums.size(); int maxn = INT_MIN, right = -1; int minn = INT_MAX, left = -1; for (int i = 0; i < n; i++) { if (maxn > nums[i]) { right = i; } else { maxn = nums[i]; } if (minn < nums[n - i - 1]) { left = n - i - 1; } else { minn = nums[n - i - 1]; } } return right == -1 ? 0 : right - left + 1; } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 时间复杂度：O（n）
- 空间复杂度：O（1）
621-任务调度器
给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。
然而，两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。
你需要计算完成所有任务所需要的 最短时间 。
方法一：模拟
我们按照时间顺序，依次给每一个时间单位分配任务。分为以下三步：
1.我们可以用二元组 (nextValidi ,resti) 表示第 i 个任务，其中 nextValidi表示其因冷却限制，最早可以执行的时间；resti表示其剩余执行次数。初始时，所有的inextValidi均为 1，而resti即为任务 i在数组tasks 中出现的次数。
2.我们用time 记录当前的时间。根据我们的策略，我们需要选择不在冷却中并且剩余执行次数最多的那个任务，也就是说，我们需要找到满足 nextValidi≤time 的并且resti最大的索引 i。因此我们只需要遍历所有的二元组，即可找到 i。在这之后，我们将 (nextValidi,resti) 更新为 (time+n+1,resti−1)，记录任务 i 下一次冷却结束的时间以及剩余执行次数。如果更新后的resti =0，那么任务 i 全部做完，我们在遍历二元组时也就可以忽略它了。
3.对于time 的更新，我们可以选择将其不断增加 1，模拟每一个时间片。但这会导致我们在 CPU 处于待命状态时，对二元组进行不必要的遍历。为了减少时间复杂度，我们可以在每一次遍历之前，将time 更新为所有 inextValidi中的最小值，直接「跳过」待命状态，保证每一次对二元组的遍历都是有效的。需要注意的是，只有当这个最小值大于 time 时，才需要这样快速更新。
class Solution { public: int leastInterval(vector<char>& tasks, int n) { unordered_map<char, int> freq; for (char ch : tasks) { ++freq[ch]; } // 任务总数 int m = freq.size(); vector<int> nextValid, rest; for (auto[_, v] : freq) { nextValid.push_back(1); rest.push_back(v); } int time = 0; for (int i = 0; i < tasks.size(); ++i) { ++time; int minNextValid = INT_MAX; for (int j = 0; j < m; ++j) { if (rest[j]) { minNextValid = min(minNextValid, nextValid[j]); } } time = max(time, minNextValid); int best = -1; //找到满足 nextValidi≤time 的并且resti最大的索引 j for (int j = 0; j < m; ++j) { if (rest[j] && nextValid[j] <= time) { if (best == -1 || rest[j] > rest[best]) { best = j; } } } nextValid[best] = time + n + 1; --rest[best]; } return time; } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 时间复杂度：O（n⋅∣Σ∣)，其中∣Σ∣ 是数组 task 中出现任务的种类，n为task的大小。
- 空间复杂度：O(∣Σ∣)。我们需要使用哈希表统计每种任务出现的次数，以及使用数组nextValid 和 test 帮助我们进行遍历得到结果，这些数据结构的空间复杂度均为O(∣Σ∣)。
394-字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
方法一：栈
本题中可能出现括号嵌套的情况，比如 2[a2[bc]]，这种情况下我们可以先转化成 2[abcbc]，在转化成 abcbcabcbc。我们可以把字母、数字和括号看成是独立的 TOKEN，并用栈来维护这些 TOKEN。具体的做法是，遍历这个栈：
1.如果当前的字符为数位，解析出一个数字（连续的多个数位）并进栈
2.如果当前的字符为字母或者左括号，直接进栈
3.如果当前的字符为右括号，开始出栈，一直到左括号出栈，出栈序列反转后拼接成一个字符串，此时取出栈顶的数字（此时栈顶一定是数字，想想为什么？），就是这个字符串应该出现的次数，我们根据这个次数和字符串构造出新的字符串并进栈
- 1
- 2
- 3
重复如上操作，最终将栈中的元素按照从栈底到栈顶的顺序拼接起来，就得到了答案。注意：这里可以用不定长数组来模拟栈操作，方便从栈底向栈顶遍历。
class Solution { public: string getDigits(string &s, size_t &ptr) { string ret = ""; while (isdigit(s[ptr])) { ret.push_back(s[ptr++]); } return ret; } string getString(vector <string> &v) { string ret; for (const auto &s: v) { ret += s; } return ret; } string decodeString(string s) { vector <string> stk; size_t ptr = 0; while (ptr < s.size()) { char cur = s[ptr]; if (isdigit(cur)) { // 获取一个数字并进栈 string digits = getDigits(s, ptr); stk.push_back(digits); } else if (isalpha(cur) || cur == '[') { // 获取一个字母并进栈 stk.push_back(string(1, s[ptr++])); //string(1, s[ptr++])构造字符串 } else { ++ptr; vector <string> sub; while (stk.back() != "[") { sub.push_back(stk.back()); stk.pop_back(); } reverse(sub.begin(), sub.end()); // 左括号出栈 stk.pop_back(); // 此时栈顶为当前 sub 对应的字符串应该出现的次数 int repTime = stoi(stk.back()); stk.pop_back(); string t, o = getString(sub);//t=“”，o= getString(sub) // 构造字符串 while (repTime--) t += o; //循环完成，repTime会变成-1 // 将构造好的字符串入栈 stk.push_back(t); } } return getString(stk); } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 时间复杂度：记解码后得出的字符串长度为 S，除了遍历一次原字符串 s，我们还需要将解码后的字符串中的每个字符都入栈，并最终拼接进答案中，故渐进时间复杂度为O(S+∣s∣)，即 O(S)。
- 空间复杂度：记解码后得出的字符串长度为 S，这里用栈维护 TOKEN，栈的总大小最终与 S 相同，故渐进空间复杂度为 O(S)。
有。
406-根据身高重建队列
假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。
方法一：排序+二维动态数组
核心思想：高个子的人是看不到矮个子的人
1.对数组进行排序，身高（hi）从高到矮，ki从小到大排序
2.遍历数组，从高到矮依次插入。
class Solution { public: vector<vector<int>> reconstructQueue(vector<vector<int>>& people) { sort(people.begin(), people.end(), [](const vector<int>& u, const vector<int>& v) { return u[0] > v[0] || (u[0] == v[0] && u[1] < v[1]); }); //cmp 判断函数 等价于上面的后半部分 //void cmp(const vector<int>& u, const vector<int>& v) { // return u[0] > v[0] || (u[0] == v[0] && u[1] < v[1]); //}; vector<vector<int>> ans; for (const vector<int>& person: people) { ans.insert(ans.begin() + person[1], person); } return ans; } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 时间复杂度：O（n^2），主要为二维动态数组的insert操作
- 空间复杂度：O（n）
方法二：排序+链表
使用vector是非常费时的，C++中vector（可以理解是一个动态数组，底层是普通数组实现的）如果插入元素大于预先普通数组大小，vector底部会有一个扩容的操作，即申请两倍于原先普通数组的大小，然后把数据拷贝到另一个更大的数组上。
所以使用vector（动态数组）来insert，是费时的，插入再拷贝的话，单纯一个插入的操作就是O(n^2)了，甚至可能拷贝好几次，就不止O(n2)了。
class Solution { public: // 身高从大到小排（身高相同k小的站前面） static bool cmp(const vector<int> a, const vector<int> b) { if (a[0] == b[0]) return a[1] < b[1]; return a[0] > b[0]; } vector<vector<int>> reconstructQueue(vector<vector<int>>& people) { sort (people.begin(), people.end(), cmp); list<vector<int>> que; // list底层是链表实现，插入效率比vector高的多 for (int i = 0; i < people.size(); i++) { int position = people[i][1]; // 插入到下标为position的位置 std::list<vector<int>>::iterator it = que.begin(); while (position--) { // 寻找在插入位置 it++; } que.insert(it, people[i]); } return vector<vector<int>>(que.begin(), que.end()); } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 时间复杂度：O（n^2），主要为insert操作，但比二维动态数组插入要快。
- 空间复杂度：O（n）
