目录
31. 下一个排列
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。
必须 原地 修改，只允许使用额外常数空间。
示例 1：
输入：nums = [1,2,3]
输出：[1,3,2]
示例 2：
输入：nums = [3,2,1]
输出：[1,2,3]
示例 3：
输入：nums = [1,1,5]
输出：[1,5,1]
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int n=nums.size();
int i;
for(i=n-1;i>0;i--)
{
if(nums[i-1]<nums[i])
{
break;
}
}
if(i<=0)
{
reverse(nums.begin(),nums.end());
return;
}
for(int k=n-1;k>=i;k--)
{
if(nums[k]>nums[i-1])
{
swap(nums[k], nums[i-1]);
break;
}
}
reverse(nums.begin()+i,nums.end());
}
};-
倒序遍历数组找到num[i-1]<num[i]的数,
-
倒序遍历数组找到num[k]>nums[i-1]的数
-
交换num[i-1]和num[k]
-
反转num[i-1]后的数
32. 最长有效括号
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
示例 2：
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
示例 3：
输入：s = ""
输出：0
class Solution {
public:
int longestValidParentheses(string s) {
stack<int> sk;
sk.push(-1);
int maxlen=0;
for(int i=0;i<s.size();i++)
{
if(s[i]=='(') sk.push(i);
else
{
sk.pop();
if(sk.empty())
{
sk.push(i);
}
else
{
maxlen=max(maxlen,i-sk.top());
}
}
}
return maxlen;
}
};34. 在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：
你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int l=0,r=nums.size()-1;
if(nums.empty()) return{-1,-1};
while(l<r)
{
int mid=l+(r-l)/2;
if(nums[mid]>=target) r=mid;
else l=mid+1;
}
if(nums[l]!=target) return {-1,-1};
int start=l;
l=0,r=nums.size()-1;
while(l<r)
{
int mid=l+(r-l)/2+1;
if(nums[mid]<=target) l=mid;
else r=mid-1;
}
int end=l;
return {start,end};
}
};-
二分法
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 。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
示例 3：
输入：nums = [1], target = 0
输出：-1
class Solution {
public:
int search(vector<int>& nums, int target) {
int l=0,r=nums.size()-1;
while(l<r)
{
int mid=l+(r-l)/2;
if(nums[mid]<=nums.back()) r=mid;
else l=mid+1;
}
int minIndex=r;
if(target<=nums.back())
{
r=nums.size()-1;
}
else
{
l=0;
r--;
}
while(l<r)
{
int mid=l+(r-l)/2;
if(nums[mid]>=target) r=mid;
else l=mid+1;
}
if(nums[l]!=target) return-1;
return l;
}
};-
用二分法先找最小值分段
-
在判断target在那段，再用二分法找
46. 全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1]
输出：[[1]]
class Solution {
public:
vector<int>v;
vector<vector<int>> ans;
vector<bool> av;
vector<vector<int>> permute(vector<int>& nums) {
av=vector<bool>(nums.size(),false);
dfs(nums,0);
return ans;
}
void dfs(vector<int> &nums,int n)
{
if(n==nums.size())
{
ans.push_back(v);
return;
}
for(int i=0;i<nums.size();i++)
{
if(av[i]==false)
{
v.push_back(nums[i]);
av[i]=true;
dfs(nums,n+1);
v.pop_back();
av[i]=false;
}
}
}
};-
dfs+回溯
39. 组合总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
示例 2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：
输入: candidates = [2], target = 1
输出: []
class Solution {
public:
vector<int> vec,judge;
vector<vector<int>> ans;
vector<vector<int>> combinationSum(vector<int>& c, int target) {
dfs(c,target,0);
return ans;
}
void dfs(vector<int>&nums,int target,int begin)
{
int sum=0;
for(int i:vec)
{
sum+=i;
}
if(sum==target)
{
ans.push_back(vec);
return;
}
else if(sum>target) return;
for(int i=begin;i<nums.size();i++)
{
vec.push_back(nums[i]);
dfs(nums,target,i);
vec.pop_back();
}
}
};-
设置begin为去重
77. 组合
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1：
输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
示例 2：
输入：n = 1, k = 1
输出：[[1]]
class Solution {
public:
vector<int> vec;
vector<vector<int>> ans;
vector<vector<int>> combine(int n, int k) {
dfs(n,k,1);
return ans;
}
void dfs(int n,int k,int index)
{
if(vec.size()==k)
{
ans.push_back(vec);
return;
}
for(int i=index;i<=n;i++)
{
vec.push_back(i);
dfs(n,k,i+1);
vec.pop_back();
}
}
};78. 子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
class Solution {
public:
vector<vector<int>> ans;
vector<int> vec;
vector<vector<int>> subsets(vector<int>& nums) {
dfs(nums,0);
return ans;
}
void dfs(vector<int> &nums,int n)
{
ans.push_back(vec);
for(int i=n;i<nums.size();i++)
{
vec.push_back(nums[i]);
dfs(nums,i+1);
vec.pop_back();
}
}
};-
无需找结束条件
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]]
示例 2：
输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
class Solution {
public:
void rotate(vector<vector<int>>& m) {
int line=m.size();
int col=m[0].size();
for(int j=0;j<col;j++)
{
for(int i=0;i<line/2;i++)
{
swap(m[i][j],m[line-1-i][j]);
}
}
for(int i=1;i<line;i++)
{
for(int j=0;j<i;j++)
{
swap(m[i][j],m[j][i]);
}
}
}
};-
先按列反转数字，再以对角线交换数字
49. 字母异位词分组
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:
输入: strs = [""]
输出: [[""]]
示例 3:
输入: strs = ["a"]
输出: [["a"]]
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string,vector<string>> um;
vector<vector<string>> vec;
for(auto &i:strs)
{
string s=i;
sort(s.begin(),s.end());
um[s].push_back(i);
}
for(auto ite=um.begin();ite!=um.end();ite++)
{
vec.push_back(ite->second);
}
return vec;
}
};-
有相同字母的字符串排序完后完全相同
-
则先排序，再入哈希表
56. 合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& a) {
sort(a.begin(),a.end());
vector<vector<int>> vec;
vec.push_back(a[0]);
int index=0;
for(int i=1;i<a.size();i++)
{
if(a[i][0]<=vec[index][1] && a[i][1]>vec[index][1]) //正常情况，有交集但非子集 [1,4] [3,6]
{
vec[index][1]=a[i][1];
}
else if(a[i][0]<=vec[index][1] && a[i][1]<vec[index][1]) // 左为大区间 [1,4] [2,3]
{
continue;
}
else if((a[i][0]==vec[index][0] && a[i][1]==vec[index][1])) //完全相等 [1,4] [1,4]
{
continue;
}
else if((a[i][0]<=vec[index][1] && a[i][0]>vec[index][0])) //右为大区间 [1,4] [0,8]
{
continue;
}
else // 无交集
{
vec.push_back(a[i]);
index++;
}
}
return vec;
}
};-
先排序
-
把第一个、区间加入数组，从第二个开始遍历，判断两个区间情况。
-
两个区间共有五种情况，见注释
-
二维数组排序时：
-
按照每个数组第一个数字大小或ASCII大小排序，若相等则比较第二个
-
62. 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7
输出：28
示例 2：
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
示例 3：
输入：m = 7, n = 3
输出：28
示例 4：
输入：m = 3, n = 3
输出：6
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m,vector<int>(n));
dp[0][0]=1;
int i,j;
for(i=1;i<m;i++)
{
dp[i][0]=1;
}
for(j=1;j<n;j++)
{
dp[0][j]=1;
}
for(int i=1;i<m;++i)
{
for(int j=1;j<n;++j)
{
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
return dp[i-1][j-1];
}
};-
动态规划
75. 颜色分类
class Solution {
public:
void sortColors(vector<int>& nums) {
unordered_map<int,int> um;
um[0]=0;
um[1]=0;
um[2]=0;
for(auto i:nums)
{
um[i]++;
}
int i=0;
while(um[0]--)
{
nums[i]=0;
i++;
}
while(um[1]--)
{
nums[i]=1;
i++;
}
while(um[2]--)
{
nums[i]=2;
i++;
}
}
};
-
哈希表时间复杂度 O（n）空间复杂度O（n）
class Solution {
public:
void sortColors(vector<int>& nums) {
int l=0;
int r=nums.size()-1;
for(int i=0;i<=r;i++)
{
if(nums[i]==0)
{
swap(nums[i],nums[l]);
l++;
}
if(nums[i]==2)
{
swap(nums[i],nums[r]);
r--;
if(nums[i]!=1) i--;
}
}
}
};-
双指针法
-
时间复杂度 O(n) 空间复杂度O(1)
-
i遍历，0与左指针交换，左指针++，2与有指针交换，右指针--
-
如果i与r换完数字后nums[i]是0或2，需要i--重新遍历，不然就会漏掉这个结果
-
判断nums[i]=0必须放在判断nums[i]=2之前，防止第一个数字为2，运行后i会回退到1造成越界