catalogue
34. Find the first and last position of an element in a sorted array
33. Search rotation sort array
31. Next arrangement
An arrangement of an integer array is to arrange all its members in sequence or linear order.
For example, arr = [1,2,3], the following can be regarded as the arrangement of arr: [1,2,3], [1,3,2], [3,1,2], [2,3,1].
The next permutation of an array of integers refers to the next lexicographically ordered permutation of its integers. More formally, if all permutations of an array are arranged in a container from small to large according to their dictionary order, the next permutation of the array is the one behind it in the ordered container. If there is no next larger permutation, the array must be rearranged to the least lexicographically ordered permutation (that is, its elements are arranged in ascending order).
For example, the next permutation of arr = [1,2,3] is [1,3,2].
Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
The next permutation of arr = [3,2,1] is [1,2,3], because there is no permutation with larger dictionary order in [3,2,1].
Give you an integer array nums and find the next arrangement of nums.
It must be modified in place and only additional constant space is allowed.
Example 1:
Input: num = [1,2,3]
Output: [1,3,2]
Example 2:
Input: num = [3,2,1]
Output: [1,2,3]
Example 3:
Input: num = [1,1,5]
Output: [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());
}
};-
Traverse the array in reverse order to find the number of num [I-1] < num [i],
-
Traverse the array in reverse order to find the number of num [k] > num [I-1]
-
Swap num[i-1] and num[k]
-
Number after reversing num[i-1]
32. Longest valid bracket
Give you a string containing only '(' and ')' and find the length of the longest valid (well formed and continuous) parenthesis substring.
Example 1:
Input: s = "(()"
Output: 2
Explanation: the longest valid bracket substring is "()"
Example 2:
Input: s = ") ()"
Output: 4
Explanation: the longest valid bracket substring is "() ()"
Example 3:
Input: s = ""
Output: 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. Find the first and last position of an element in a sorted array
Given an integer array nums arranged in ascending order and a target value target. Find the start and end positions of the given target value in the array.
If the target value target does not exist in the array, return [- 1, - 1].
Advanced:
Can you design and implement an algorithm with time complexity of {O(log n) to solve this problem?
Example 1:
Input: num = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
Input: num = [5,7,7,8,8,10], target = 6
Output: [- 1, - 1]
Example 3:
Input: num = [], target = 0
Output: [- 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};
}
};-
dichotomy
33. Search rotation sort array
The integer array nums is arranged in ascending order, and the values in the array are different from each other.
Before passing to the function, Num rotates on a previously unknown subscript k (0 < = k < num.length), making the array [num [k], Num [K + 1], nums[n-1], nums[0], nums[1], ..., Nums [k-1]] (subscript counts from 0). For example, [0,1,2,4,5,6,7] may become [4,5,6,7,0,1,2] after being rotated at subscript 3.
Give you the rotated array num and an integer target. If the target value target exists in num, return its subscript, otherwise return - 1.
Example 1:
Input: num = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: num = [4,5,6,7,0,1,2], target = 3
Output: - 1
Example 3:
Input: num = [1], target = 0
Output: - 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;
}
};-
Find the minimum segment first by dichotomy
-
When judging that the target is in that section, use dichotomy to find it
46. Full arrangement
Given an array nums without duplicate numbers, all possible permutations are returned. You can return answers in any order.
Example 1:
Input: num = [1,2,3]
Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
Example 2:
Input: num = [0,1]
Output: [[0,1], [1,0]]
Example 3:
Input: num = [1]
Output: [[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 + backtracking
39. Combination sum
Give you an array of integers with no duplicate elements, @ candidates, and a target integer, @ target. Find out all the different combinations of numbers and targets in ， candidates ， and return them in the form of a list. You can return these combinations in any order.
The same number in candidates can be selected repeatedly without limit. If the selected number of at least one number is different, the two combinations are different.
For a given input, ensure that the number of different combinations with sum target is less than 150.
Example 1:
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3], [7]]
Explanation:
2 and 3 can form a set of candidates, 2 + 2 + 3 = 7. Note 2 can be used multiple times.
7 is also a candidate, 7 = 7.
There are only two combinations.
Example 2:
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2], [2,3,3], [3,5]]
Example 3:
Input: candidates = [2], target = 1
Output: []
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();
}
}
};-
Set begin to de duplication
77. Portfolio
Given two integers n and k, returns the combination of all possible k numbers in the range [1, n].
You can return answers in any order.
Example 1:
Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
Example 2:
Input: n = 1, k = 1
Output: [[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. Subset
Give you an integer array {nums. The elements in the array are different from each other. Returns all possible subsets (power sets) of the array.
The solution set cannot contain duplicate subsets. You can return the solution set in any order.
Example 1:
Input: num = [1,2,3]
Output: [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]
Example 2:
Input: num = [0]
Output: [[], [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();
}
}
};-
There is no need to find an end condition
48. Rotate image
Given an n × The two-dimensional matrix of N represents an image. Please rotate the image 90 degrees clockwise.
You have to rotate the image in place, which means you need to modify the input two-dimensional matrix directly. Do not use another matrix to rotate the image.
Example 1:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1], [8,5,2], [9,6,3]]
Example 2:
Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Output: [[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]);
}
}
}
};-
First reverse the numbers by column, and then exchange the numbers diagonally
49. Grouping of acronyms
Here is an array of strings. Please combine the letters and words together. You can return a list of results in any order.
An alphabetic ectopic word is a new word obtained by rearranging the letters of the source word. The letters in all the source words are usually used just once.
Example 1:
Input: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
Output: ["bat"],["nat","tan"],["ate","eat","tea"]]
Example 2:
Input: strs = [""]
Output: [""]]
Example 3:
Input: strs = ["a"]
Output: ["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;
}
};-
Strings with the same letters are exactly the same after sorting
-
Sort first and then enter the hash table
56. Consolidation interval
An array of intervals is used to represent a set of several intervals, in which a single interval is intervals[i] = [starti, endi]. Please merge all overlapping intervals and return} a non overlapping interval array, which needs to cover all the intervals in the input exactly.
Example 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6], [8,10], [15,18]]
Explanation: the interval [1,3] and [2,6] overlap and merge them into [1,6]
Example 2:
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Interpretation: intervals [1,4] and [4,5] can be considered overlapping intervals.
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]) //Normally, there is intersection but not subset [1,4] [3,6]
{
vec[index][1]=a[i][1];
}
else if(a[i][0]<=vec[index][1] && a[i][1]<vec[index][1]) // On the left is a large interval [1,4] [2,3]
{
continue;
}
else if((a[i][0]==vec[index][0] && a[i][1]==vec[index][1])) //Exactly equal [1,4] [1,4]
{
continue;
}
else if((a[i][0]<=vec[index][1] && a[i][0]>vec[index][0])) //On the right is a large interval [1,4] [0,8]
{
continue;
}
else // No intersection
{
vec.push_back(a[i]);
index++;
}
}
return vec;
}
};-
Sort first
-
Add the first and interval into the array and traverse from the second to judge the situation of the two intervals.
-
There are five cases in the two intervals, see the note
-
When sorting two-dimensional arrays:
-
Sort according to the first digit size or ASCII size of each array, and compare the second if equal
-
62. Different paths
A robot is located in the upper left corner of an m x n# grid (the starting point is marked "Start" in the figure below).
The robot can only move down or right one step at a time. The robot attempts to reach the lower right corner of the grid (marked "Finish" in the figure below).
How many different paths are there altogether?
Example 1:
Input: m = 3, n = 7
Output: 28
Example 2:
Input: m = 3, n = 2
Output: 3
Explanation:
Starting from the upper left corner, there are three paths to the lower right corner.
1. Right - > down - > down
2. Down - > down - > right
3. Down - > right - > down
Example 3:
Input: m = 7, n = 3
Output: 28
Example 4:
Input: m = 3, n = 3
Output: 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];
}
};-
dynamic programming
75. Color classification
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++;
}
}
};
-
Hash table time complexity O (n) space complexity 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--;
}
}
}
};-
Double finger needling
-
Time complexity O(n) space complexity O(1)
-
i traversal, 0 and left pointer exchange, left pointer + +, 2 and existing pointer exchange, right pointer--
-
If nums[i] is 0 or 2 after I and r are replaced, I -- needs to be traversed again, otherwise this result will be missed
-
The judgment of nums[i]=0 must be placed before the judgment of nums[i]=2 to prevent the first number from being 2. After operation, I will fall back to 1, resulting in boundary crossing