LeetCode汇总41-60

41. First Missing Positive

链接：https://leetcode.com/problems/first-missing-positive/

描述

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

1
2


Input: [1,2,0]
Output: 3

Example 2:

1
2


Input: [3,4,-1,1]
Output: 2

Example 3:

1
2


Input: [7,8,9,11,12]
Output: 1

Follow up:

Your algorithm should run in O(n) time and uses constant extra space.

题解

只需将每个元素放到它对应的下标处，即nums[i]==i+1，例如元素3放在第3个位置。再次扫描，找nums[i]!=i+1的位置即是所求的缺失值
使用swap实现元素的移动，对于每个i使用while，停止条件是：
- 或者在此处放置了正确的元素nums[i]==i+1
- 或者num[i]超出下标
- 使用while的目的是保证i处或者是正确的值，或者是越界的值，保证不会让一个应该被放置在别处的元素放在这里（防止这样的元素逃过for循环的搜索）
时间复杂度：虽然嵌套了循环，但被while正确放置的元素在for遍历到它时不会进行任何操作，即总交换次数仍是O(n)
空间复杂度：O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


// Runtime: 4 ms, faster than 79.52% of C++ online submissions for First Missing Positive.
// Memory Usage: 9.9 MB, less than 63.34% of C++ online submissions for First Missing Positive.
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        for(int i=0;i<nums.size();++i)
            while(nums[i]>0 && nums[i]<=nums.size() && nums[i]!=nums[nums[i]-1])
                std::swap(nums[i],nums[nums[i]-1]);
        for(int i=0;i<nums.size();++i)
            if(nums[i]!=i+1)
                return i+1;
        return nums.size()+1;
    }
};

42. Trapping Rain Water

链接：https://leetcode.com/problems/trapping-rain-water/

描述

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

LeetCode42

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

1
2


Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

题解

解法1：DP

扫描两趟：
- 第一趟从左往右，只考虑左侧水平面，计算每个位置处的水深left
- 第二趟从右往左，只考虑右侧水平面，计算每个位置处的水深right
扫描left和right，每个位置处取较小者即是实际水深
时间复杂度：O(n)
空间复杂度：O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


// Runtime: 8 ms, faster than 91.58% of C++ online submissions for Trapping Rain Water.
// Memory Usage: 14.5 MB, less than 6.39% of C++ online submissions for Trapping Rain Water.
class Solution {
public:
    int trap(vector<int>& height) {
        int N=height.size();
        vector<int> left(N,0),right(N,0);
        int left_max=0,right_max=0;
        int total=0;
        for(int i=0;i<N;++i){
            left_max=max(left_max,height[i]);
            left[i]=left_max-height[i];
        }
        for(int i=N-1;i>=0;--i){
            right_max=max(right_max,height[i]);
            right[i]=right_max-height[i];
        }
        for(int i=0;i<N;++i){
            total+=min(left[i],right[i]);
        }
        return total;
    }
};

解法2：双指针

使用left和right两个指针从左右两边向中间移动，同时记录左边和右边见过的最大值left_max和right_max
每次指针移动时：
- 判断哪个元素更小，元素更小的指针向中间移动（因为水平面取决于更小的一侧）
- 若左边元素更小，则：
  - 首先更新左边见过的最大值（即更新左侧水平面），若当前元素即为最大，则该处不会有水（水是两边高的夹住中间低的）
  - 若当前元素小于左侧最大的元素，则该处有水，且水深为左侧最大与当前元素之差（左侧最大元素代表左侧的水平面）
- 若右边元素更小，同理
时间复杂度：O(n)
空间复杂度：O(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


// Runtime: 8 ms, faster than 91.75% of C++ online submissions for Trapping Rain Water.
// Memory Usage: 14.1 MB, less than 56.51% of C++ online submissions for Trapping Rain Water.
class Solution {
public:
    int trap(vector<int>& height) {
        int left=0,right=height.size()-1;
        int left_max=0,right_max=0;
        int ans=0;
        while(left<right){
            if(height[left]<height[right]){
                if(height[left]>=left_max)
                    left_max=height[left];
                else
                    ans+=(left_max-height[left]);
                ++left;
            }
            else{
                if(height[right]>=right_max)
                    right_max=height[right];
                else
                    ans+=(right_max-height[right]);
                --right;
            }
        }
        return ans;
    }
};

43. Multiply Strings

链接：https://leetcode.com/problems/multiply-strings/

描述

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Example 1:

1
2


Input: num1 = "2", num2 = "3"
Output: "6"

Example 2:

1
2


Input: num1 = "123", num2 = "456"
Output: "56088"

Note:

The length of both num1 and num2 is < 110.
Both num1 and num2 contain only digits 0-9.
Both num1 and num2 do not contain any leading zero, except the number 0 itself.
You must not use any built-in BigInteger library or convert the inputs to integer directly.

题解

两数相乘，结果的位数一定不会大于两数的位数之和。因此建立N1+N2长的数组存放中间结果，N1+N2长的字符串存放最终字符串结果
列竖式，使用i和j遍历两个输入的数，每次num1[i]*num2[j]的结果叠加到tmp[i+j+1]上，这里暂不考虑进位，每个位置存放的值可能大于10
考虑进位，从右往左扫描tmp数组，当tmp[i]>9时进位
最终结果字符串可能最前面有0，检测为0的长度跳过即可。但跳过的长度不能超过整个字符串，避免结果就是0的情况
时间复杂度：两层循环，O(n^2)
空间复杂度：O(n)

 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


// Runtime: 4 ms, faster than 98.19% of C++ online submissions for Multiply Strings.
// Memory Usage: 7 MB, less than 33.25% of C++ online submissions for Multiply Strings.
class Solution {
public:
    string multiply(string num1, string num2) {
        int N1=num1.size(),N2=num2.size();
        vector<int> tmp(N1+N2,0);
        string res(N1+N2,'0');
        for(int i=0;i<N1;++i)
            for(int j=0;j<N2;++j)
                tmp[i+j+1]+=(num1[i]-'0')*(num2[j]-'0');
        for(int i=N1+N2-1;i>0;--i){
            if(tmp[i]>9){
                tmp[i-1]+=tmp[i]/10;
                tmp[i]%=10;
            }
            res[i]=tmp[i]+'0';
        }
        res[0]=(tmp[0]!=0)?(tmp[0]+'0'):'0';
        int beg=0;
        while(res[beg]=='0' && beg<N1+N2-1)
            beg++;
        return res.substr(beg);
    }
};

44. Wildcard Matching

链接：https://leetcode.com/problems/wildcard-matching/submissions/

描述

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for ‘?’ and ‘*’.

1
2
3


'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).

Note:

s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like ? or *.

Example 1:

1
2
3
4
5


Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

1
2
3
4
5


Input:
s = "aa"
p = "*"
Output: true
Explanation: '*' matches any sequence.

Example 3:

1
2
3
4
5


Input:
s = "cb"
p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

Example 4:

1
2
3
4
5


Input:
s = "adceb"
p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".

Example 5:

1
2
3
4


Input:
s = "acdcb"
p = "a*c?b"
Output: false

题解

使用二维dp，原字符串s长度为m，模式串p长度为n，则建立(m+1)x(n+1)的dp矩阵，dp[i][j]代表s[0:i]和p[0:j]是否能匹配（左半开区间），dp矩阵的第一行和第一列分别处理s为空和p为空的情形
初始化：
- 由于s和p都为空时一定能匹配，故dp[0][0]=true
- 由于空p一定不能匹配非空s，故dp[1:m+2][0]=false
- 由于只有p为纯*时才能匹配非空的s，故dp[0][1:n+2]的值取决于该处的p是否为纯*
递推dp[i][j]：
- 当p[j-1]是*时：
  - 若dp[i-1][j]==True，则s增加一个时一定能被增加*的p匹配
  - 若dp[i][j-1]==True，则p增加一个*一定还能匹配到原来的s
- 当p[j-1]不是*时，必须保证dp[i-1][j-1]==True即s和p各减少一个字符时能匹配，否则s和p一定不匹配。以下两种情况是建立在s和p各减少一个字符时能匹配的基础上：
  - 若s和p新加的字符相同，则可以匹配
  - 若p新加的字符为?，则可以匹配
时间复杂度：O(n^2)
空间复杂度：O(n^2)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


// Runtime: 224 ms, faster than 32.88% of C++ online submissions for Wildcard Matching.
// Memory Usage: 11.5 MB, less than 30.83% of C++ online submissions for Wildcard Matching.
class Solution {
public:
    bool isMatch(string s, string p) {
        int m=s.size(),n=p.size();
        vector<vector<bool>> dp(m+1,vector<bool>(n+1,false));
        dp[0][0]=true;
        for(int i=1;i<n+1;++i)
            if(p[i-1]=='*')
                dp[0][i]=dp[0][i-1];
        for(int i=1;i<m+1;++i)
            for(int j=1;j<n+1;++j)
                if(p[j-1]=='*')
                    dp[i][j]=dp[i-1][j] || dp[i][j-1];
                else
                    dp[i][j]=dp[i-1][j-1] && (s[i-1]==p[j-1] || p[j-1]=='?');
        return dp[m][n];
    }
};

45. Jump Game II

链接：https://leetcode.com/problems/jump-game-ii/

描述

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example:

1
2
3
4


Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
    Jump 1 step from index 0 to 1, then 3 steps to the last index.

Note:

You can assume that you can always reach the last index.

题解

使用贪心法，但是每次不是贪当前一步能走的最远位置，而是贪后两步能走的最远位置
维护一个搜索变量i和当前的最远位置cur
每次走一步时，例如从i处跳到cur处，则下一个cur的选择策略是：遍历区间[i:cur]，每次i取一个值时有一个跳转的新cur，在这些新cur中选最大者，作为新的cur。这样就考虑到了所有可能的跳转情形。
时间复杂度：i需要扫描整个数组，O(n)
空间复杂度：O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


// Runtime: 16 ms, faster than 96.34% of C++ online submissions for Jump Game II.
// Memory Usage: 13.5 MB, less than 22.62% of C++ online submissions for Jump Game II.
class Solution {
public:
    int jump(vector<int>& nums) {
        int i=0,cnt=0,pre=0,cur=0;
        while(cur<nums.size()-1){
            cnt++;
            pre=cur;
            while(i<=pre){
                cur=max(cur,i+nums[i]);
                ++i;
            }
        }
        return cnt;
    }
};

46. Permutations

链接：https://leetcode.com/problems/permutations/

描述

Given a collection of distinct integers, return all possible permutations.

Example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

题解

回溯法，维护tmp数组作为一个排列，每次选一个数字加入到tmp数组中，直到dfs的深度等于数组长度时到达边界，将当前搜到的数组加入结果中。
去重手段：
- 用for循环保证一次搜索的数字不重复
- 用bool数组保证以前加入到tmp中的元素不会再被加入
时间复杂度：dfs的搜索树是高为n的n叉树，O(n^n)
空间复杂度：tmp数组和bool数组都长为n，且递归深度最大为n，故O(n)

 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


// Runtime: 4 ms, faster than 87.85% of C++ online submissions for Permutations.
// Memory Usage: 8.3 MB, less than 26.46% of C++ online submissions for Permutations.
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        see=vector<bool>(nums.size(),false);
        dfs(0,nums);
        return res;
    }
private:
    vector<vector<int>> res;
    vector<int> tmp;
    vector<bool> see;
    void dfs(int depth,const vector<int> &nums){
        if(depth==nums.size()){
            res.push_back(tmp);
            return;
        }
        for(int i=0;i<nums.size();++i){
            if(see[i])
                continue;
            //选一个数字
            see[i]=true;
            tmp.push_back(nums[i]);
            //dfs
            dfs(depth+1,nums);
            //退回一步
            tmp.pop_back();
            see[i]=false;
        }
    }
};

47. Permutations II

链接：https://leetcode.com/problems/permutations-ii/

描述

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

1
2
3
4
5
6
7


Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

题解

仍用dfs做回溯，并用bool数组标记元素是否见过
相比无重复的输入，有重复输入时的去重手段：
- 将输入数组排序，使得重复数字聚在一起
- 对于重复的数字，若第一个数字已经搜过了，则在同一层for循环中不必再看后面的。例如[1,1,2,3]，第一个1的子节点可能是[1,2,3]，第二个1的子节点也可能是[1,2,3]，这两棵子树重复，剪掉一棵
- 在上一条剪枝的过程中，不能直接剪掉nums[i]==nums[i-1]的子树，只有在see[i-1]==false时才能剪。因为只能剪掉重复的兄弟节点，而see[i-1]==true意味着i-1的节点是i节点的祖先节点，不可剪掉i
时间复杂度：dfs的搜索树是高为n的n叉树，O(n^n)
空间复杂度：tmp数组和bool数组都长为n，且递归深度最大为n，故O(n)

 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


// Runtime: 8 ms, faster than 84.21% of C++ online submissions for Permutations II.
// Memory Usage: 9.1 MB, less than 54.55% of C++ online submissions for Permutations II.
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        std::sort(nums.begin(),nums.end());
        see=vector<bool>(nums.size(),false);
        dfs(0,nums);
        return res;
    }
private:
    vector<vector<int>> res;
    vector<int> tmp;
    vector<bool> see;
    void dfs(int depth,const vector<int> &nums){
        if(depth==nums.size()){
            res.push_back(tmp);
            return;
        }
        for(int i=0;i<nums.size();++i){
            if(see[i])
                continue;
            //剪枝
            if(i>=1 && !see[i-1] && nums[i]==nums[i-1])
                continue;
            //选一个数字
            see[i]=true;
            tmp.push_back(nums[i]);
            //dfs
            dfs(depth+1,nums);
            //退回一步
            tmp.pop_back();
            see[i]=false;
        }
    }
};

48. Rotate Image

链接：https://leetcode.com/problems/rotate-image/

描述

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

LeetCode48_1

1
2


Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]

Example 2:

LeetCode48_2

1
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]]

Example 3:

1
2


Input: matrix = [[1]]
Output: [[1]]

Example 4:

1
2


Input: matrix = [[1,2],[3,4]]
Output: [[3,1],[4,2]]

Constraints:

matrix.length == n
matrix[i].length == n
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000

题解

顺时针旋转90度，等价于先沿对角线反转再左右反转。
时间复杂度：O(n^2)
空间复杂度：O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


// Runtime: 0 ms, faster than 100.00% of C++ online submissions for Rotate Image.
// Memory Usage: 7.4 MB, less than 31.10% of C++ online submissions for Rotate Image.
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int N=matrix.size();
        for(int i=0;i<N;++i){
            for(int j=i;j<N;++j)
                swap(matrix[i][j],matrix[j][i]);
            reverse(matrix[i].begin(),matrix[i].end());
        }
    }
};

49. Group Anagrams

链接：https://leetcode.com/problems/group-anagrams/

描述

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

1
2


Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2:

1
2


Input: strs = [""]
Output: [[""]]

Example 3:

1
2


Input: strs = ["a"]
Output: [["a"]]

Constraints:

1 <= strs.length <= 10^4
0 <= strs[i].length <= 100
strs[i] consists of lower-case English letters.

题解

同一组Anagram排序后相同，因此建立字典，每个单词排序后作为key，value是容纳这些单词的vector
时间复杂度：O(n)
空间复杂度：O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


// Runtime: 64 ms, faster than 79.56% of C++ online submissions for Group Anagrams.
// Memory Usage: 20.9 MB, less than 37.83% of C++ online submissions for Group Anagrams.
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string,vector<string>> m;
        for(auto &s:strs){
            string sc=s;
            sort(sc.begin(),sc.end());
            if(m.find(sc)==m.end())
                m[sc]={};
            m[sc].push_back(s);
        }
        vector<vector<string>> res;
        for(auto p:m)
            res.push_back(p.second);
        return res;
    }
};

50. Pow(x, n)

链接：https://leetcode.com/problems/powx-n/

描述

Implement pow(x, n), which calculates x raised to the power n (i.e. xn).

Example 1:

1
2


Input: x = 2.00000, n = 10
Output: 1024.00000

Example 2:

1
2


Input: x = 2.10000, n = 3
Output: 9.26100

Example 3:

1
2
3


Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2^-2 = 1/2^2 = 1/4 = 0.25

Constraints:

-100.0 < x < 100.0
-2^31 <= n <= 2^31-1
-10^4 <= x^n <= 10^4

题解

当n为偶数时，x^n=(x^(n/2))^2，即类似二分查找。
当n为正奇数时，x^n=(x^((n-1)/2))^2*n，也可转为n-1偶数利用二分法。
当n为负奇数时，x^n=(x^((n-1)/2))^2/n
n为偶数时不需讨论正负，是因为只需递归调用，不需手动乘上x或1/x，而n为奇数时需要。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


// Runtime: 0 ms, faster than 100.00% of C++ online submissions for Pow(x, n).
// Memory Usage: 6 MB, less than 59.72% of C++ online submissions for Pow(x, n).
class Solution {
public:
    double myPow(double x, int n) {
        if(n==0)
            return 1;
        double half=myPow(x,n/2);
        if(n%2==0)
            return half*half;
        else
            return (n>0)?(half*half*x):(half*half/x);
    }
};

51. N-Queens

链接：https://leetcode.com/problems/n-queens/

描述

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

LeetCode51

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.

Example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


Input: 4
Output: [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

题解

使用dfs结合回溯，搜索每一行中可能在哪里放皇后，tmp数组记录每一行的哪个位置放皇后，搜到一个结果就存入res
dfs的一层就是一行，在这一行中搜索哪里能放皇后时，要根据之前放的tmp数组来排除不能放皇后的位置
时间复杂度：dfs搜索树是n叉树，每搜索一个节点时都要遍历tmp数组来排除不能放皇后的位置即O(n)，故总复杂度为O(n^n*n)=O(n^(n+1))
空间复杂度：递归深度是O(n)，若不考虑多解导致res变大，总空间复杂度O(n)

 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


// Runtime: 8 ms, faster than 83.90% of C++ online submissions for N-Queens.
// Memory Usage: 7.7 MB, less than 58.21% of C++ online submissions for N-Queens.
class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        dfs(0,n);
        vector<vector<string>> visu(res.size(),vector<string>(n,string(n,'.')));
        // 输出到结果中
        for(int i=0;i<res.size();++i){
            for(int j=0;j<n;++j)
                visu[i][j][res[i][j]]='Q';
        }
        return visu;
    }
private:
    vector<int> tmp;
    vector<vector<int>> res;
    void dfs(int depth,int n){
        if(depth==n){
            res.push_back(tmp);
            return;
        }
        for(int i=0;i<n;++i){
            // 根据前面已放的皇后来判断这一行的这个位置能否放皇后
            bool flag=true;
            for(int j=0;j<tmp.size();++j){
                if(i==tmp[j] || i==tmp[j]+(depth-j) || i==tmp[j]-(depth-j)){
                    flag=false;
                    break;
                }
            }
            // 这里不能放皇后就continue
            if(!flag)
                continue;
            tmp.push_back(i);
            dfs(depth+1,n);
            tmp.pop_back();
        }
    }
};

52. N-Queens II

链接：https://leetcode.com/problems/n-queens-ii/

描述

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

LeetCode51

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


Input: 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.
[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

题解

参见上一题，只需返回解的数量即可。

 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


// Runtime: 4 ms, faster than 89.14% of C++ online submissions for N-Queens II.
// Memory Usage: 6.8 MB, less than 30.55% of C++ online submissions for N-Queens II.
class Solution {
public:
    int totalNQueens(int n) {
        dfs(0,n);
        return res.size();
    }
private:
    vector<int> tmp;
    vector<vector<int>> res;
    void dfs(int depth,int n){
        if(depth==n){
            res.push_back(tmp);
            return;
        }
        for(int i=0;i<n;++i){
            // 根据前面已放的皇后来判断这一行的这个位置能否放皇后
            bool flag=true;
            for(int j=0;j<tmp.size();++j){
                if(i==tmp[j] || i==tmp[j]+(depth-j) || i==tmp[j]-(depth-j)){
                    flag=false;
                    break;
                }
            }
            // 这里不能放皇后就continue
            if(!flag)
                continue;
            tmp.push_back(i);
            dfs(depth+1,n);
            tmp.pop_back();
        }
    }
};

53. Maximum Subarray

链接：https://leetcode.com/problems/maximum-subarray/

描述

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Example 1:

1
2
3


Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

1
2


Input: nums = [1]
Output: 1

Example 3:

1
2


Input: nums = [0]
Output: 0

Example 4:

1
2


Input: nums = [-1]
Output: -1

Example 5:

1
2


Input: nums = [-2147483647]
Output: -2147483647

Constraints:

1 <= nums.length <= 2 * 10^4
-2^31 <= nums[i] <= 2^31 - 1

题解

使用dp，dp数组第i位的含义是以i为结尾的连续子数组的最大和
递推时只需考虑是否要另起一个数组，即当前dp=max(过去的最大连续子数组+当前值，当前值)
时间复杂度：O(n)
空间复杂度：O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


// Runtime: 4 ms, faster than 99.90% of C++ online submissions for Maximum Subarray.
// Memory Usage: 13.6 MB, less than 9.19% of C++ online submissions for Maximum Subarray.
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> dp(nums.size(),0);
        dp[0]=nums[0];
        for(int i=1;i<nums.size();++i)
            dp[i]=max(dp[i-1]+nums[i],nums[i]);
        return *max_element(dp.begin(),dp.end());
    }
};

54. Spiral Matrix

链接：https://leetcode.com/problems/spiral-matrix/

描述

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

Example 1:

1
2
3
4
5
6
7


Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]

Example 2:

1
2
3
4
5
6
7


Input:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

题解

使用四个坐标pair<int,int>来描述边界的4个点，打印完一圈后收缩边界
为处理“只有一行”/“只有一列”等边界条件，打印一圈时应该优先打完一行/一列，过程：
- 打完第一行（首尾元素都打）
- 若不止一行，则打完最后一列（不打首元素，打尾元素）
- 若不止一行且不止一列，则打完最后一行（打首元素，不打尾元素）
- 若不止一行且不止一列，则打完第一列（首尾元素都不打）
打完一圈后分x和y两个方向收缩边界
停止条件是：
- 或者坐标界定的矩形框为负，此时直接返回
- 或者坐标界定的矩形框只有一个元素，此时打印完该元素再返回
时间复杂度：O(m*n)
空间复杂度：O(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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48


// Runtime: 0 ms, faster than 100.00% of C++ online submissions for Spiral Matrix.
// Memory Usage: 7.2 MB, less than 100.00% of C++ online submissions for Spiral Matrix.
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if(matrix.empty()) return {};
        int m=matrix.size(),n=matrix[0].size();
        // {x,y}
        vector<pair<int,int>> points{{0,0},{n-1,0},{n-1,m-1},{0,m-1}};
        operate(matrix,points);
        return res;
    }
private:
    vector<int> res;
    void operate(const vector<vector<int>>& matrix,vector<pair<int,int>> &p){
        if(p[0].first>p[1].first || p[1].second>p[2].second)
            return;
        if(p[0].first==p[1].first && p[1].second==p[2].second){
            res.push_back(matrix[p[0].second][p[0].first]);
            return;
        }
        for(int i=p[0].first;i<=p[1].first;++i)
            res.push_back(matrix[p[0].second][i]);
        if(p[1].second<p[2].second){
            for(int j=p[1].second+1;j<=p[2].second;++j)
                res.push_back(matrix[j][p[1].first]);
            if(p[0].first<p[1].first){
                for(int i=p[2].first-1;i>=p[3].first;--i)
                    res.push_back(matrix[p[2].second][i]);
                for(int j=p[3].second-1;j>p[0].second;--j)
                    res.push_back(matrix[j][p[3].first]);
            }
        }
        if(p[0].first<=p[1].first){
            p[0].first++;
            p[1].first--;
            p[2].first--;
            p[3].first++;
        }
        if(p[1].second<=p[2].second){
            p[0].second++;
            p[1].second++;
            p[2].second--;
            p[3].second--;
        }
        operate(matrix,p);
    }
};

55. Jump Game

链接：https://leetcode.com/problems/jump-game/

描述

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

1
2
3


Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

1
2
3


Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Constraints:

1 <= nums.length <= 3 * 10^4
0 <= nums[i][j] <= 10^5

题解

同第45题，贪心法搜索后两步能走的最远位置。若后两部能走的最远位置和后一步能走的最远位置相同，则不能走到末尾。
时间复杂度：实际i只扫描了整个数组，O(n)
空间复杂度：O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


// Runtime: 16 ms, faster than 94.59% of C++ online submissions for Jump Game.
// Memory Usage: 13.1 MB, less than 100.00% of C++ online submissions for Jump Game.
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int cur=0,pre=0,i=0;
        bool res=true;
        while(cur<nums.size()-1){
            pre=cur;
            while(i<=pre){
                cur=max(cur,i+nums[i]);
                ++i;
            }
            if(cur==pre){
                res=false;
                break;
            }
        }
        return res;
    }
};

56. Merge Intervals

链接：https://leetcode.com/problems/merge-intervals/

描述

Given a collection of intervals, merge all overlapping intervals.

Example 1:

1
2
3


Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

1
2
3


Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

Constraints:

intervals[i][0] <= intervals[i][1]

题解

新建一个数组保存合并后的区间，每看到一个输入区间就和合并后的结果对比，看是否需要合并
合并前将输入区间排序，解决两个问题：
- 合并时按顺序合并，避免出现“合并结果中A B本不相连但输入区间C后合并为一个区间”的情况，即对于每个输入区间，只需要同时考虑一个合并后的区间与它是否相交
- 将一个输入区间合并到最终合并的区间中时，由于该输入区间靠后，故不需要遍历所有合并后的区间，只需要和最后一个比较即可
判断两个区间[a,b]和[c,d]是否相交，只需看(a-d)*(b-c)的符号，小于等于0则相交
时间复杂度：排序花时间O(nlogn)，最后合并只需O(n)，总复杂度O(nlogn)
空间复杂度：O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


// Runtime: 44 ms, faster than 70.74% of C++ online submissions for Merge Intervals.
// Memory Usage: 14.7 MB, less than 12.51% of C++ online submissions for Merge Intervals.
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        std::sort(intervals.begin(),intervals.end());          
        vector<vector<int>> res;
        if(!intervals.empty())
            res.push_back(intervals[0]);
        for(const auto &pair:intervals){
            // 取最后一个合并后的区间
            auto &p=res[res.size()-1];
            // 比较这两个区间是否相交
            if((pair[0]-p[1])*(pair[1]-p[0])<=0)
                p={min(pair[0],p[0]),max(pair[1],p[1])};
            else
                res.push_back(pair);
        }
        return res;
    }
};

57. Insert Interval

链接：https://leetcode.com/problems/insert-interval/

描述

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:

1
2


Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

1
2
3


Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

Example 3:

1
2


Input: intervals = [], newInterval = [5,7]
Output: [[5,7]]

Example 4:

1
2


Input: intervals = [[1,5]], newInterval = [2,3]
Output: [[1,5]]

Example 5:

1
2


Input: intervals = [[1,5]], newInterval = [2,7]
Output: [[1,7]]

Constraints:

0 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= intervals[i][0] <= intervals[i][1] <= 10^5
intervals is sorted by intervals[i][0] in ascending order.
newInterval.length == 2
0 <= newInterval[0] <= newInterval[1] <= 10^5

题解

用一个指针遍历intervals，分三段：
- 第一段是左侧与newInterval不相交的区间，判定标准是该区间的右端点小于newInterval的左端点
- 第二段是与newInterval相交的区间，判断标准是该区间的左端点小于等于newInterval的右端点，由于左侧与newInterval不相交的区间已在第一段中处理，故这里只考虑右侧边界即可
- 第三段是剩下的部分
时间复杂度：O(n)
空间复杂度：O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


// Runtime: 20 ms, faster than 99.22% of C++ online submissions for Insert Interval.
// Memory Usage: 17.3 MB, less than 5.25% of C++ online submissions for Insert Interval.
class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int n=intervals.size(),cur=0;
        vector<vector<int>> ans;
        while(cur<n && intervals[cur][1]<newInterval[0])
            ans.push_back(intervals[cur++]);
        while(cur<n && intervals[cur][0]<=newInterval[1]){
            newInterval[0]=min(newInterval[0],intervals[cur][0]);
            newInterval[1]=max(newInterval[1],intervals[cur][1]);
            ++cur;
        }
        ans.push_back(newInterval);
        while(cur<n)
            ans.push_back(intervals[cur++]);
        return ans;
    }
};

58. Length of Last Word

链接：https://leetcode.com/problems/length-of-last-word/

描述

Given a string s consists of upper/lower-case alphabets and empty space characters ' ‘, return the length of last word (last word means the last appearing word if we loop from left to right) in the string.

If the last word does not exist, return 0.

Note: A word is defined as a maximal substring consisting of non-space characters only.

Example:

1
2


Input: "Hello World"
Output: 5

题解

跳过末尾的空格，开始往前走同时计数增加。往前走到第一个空格处停止
时间复杂度：O(n)
空间复杂度：O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


// Runtime: 4 ms, faster than 89.37% of C++ online submissions for Length of Last Word.
// Memory Usage: 6.7 MB, less than 78.58% of C++ online submissions for Length of Last Word.
class Solution {
public:
    int lengthOfLastWord(string s) {
        int cnt=0,last=s.size()-1;
        while(s[last]==' ')
            last--;
        for(int i=last;i>=0;--i){
            if(s[i]!=' ')
                cnt++;
            else
                break;
        }
        return cnt;
    }
};

59. Spiral Matrix II

链接：https://leetcode.com/problems/spiral-matrix-ii/

描述

Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

Example:

1
2
3
4
5
6
7


Input: 3
Output:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

题解

设置一个变量，每次填充一个值时+1
用四个坐标来维护当前填充的一圈，每次填完一圈后矩形收缩
边界条件有两种：
- 第一种是填完某一圈后刚好填满整个矩阵，直接返回
- 第二种是填完最后一圈后最中心还剩下一个元素，填充该元素后返回
时间复杂度：O(n^2)
空间复杂度：O(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
34
35
36
37
38
39


// Runtime: 0 ms, faster than 100.00% of C++ online submissions for Spiral Matrix II.
// Memory Usage: 7.1 MB, less than 82.47% of C++ online submissions for Spiral Matrix II.
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        res=vector<vector<int>>(n,vector<int>(n));
        vector<pair<int,int>> p{{0,0},{n-1,0},{n-1,n-1},{0,n-1}};
        generate(p);
        return res;
    }
private:
    int cnt=0;
    vector<vector<int>> res;
    void generate(vector<pair<int,int>> &p){
        if(p[0].first>p[1].first || p[0].second>p[3].second)
            return;
        if(p[0].first==p[1].first && p[0].second==p[3].second){
            res[p[0].second][p[0].first]=++cnt;
            return;
        }
        for(int i=p[0].first;i<=p[1].first;++i)
            res[p[0].second][i]=++cnt;
        for(int j=p[1].second+1;j<=p[2].second;++j)
            res[j][p[1].first]=++cnt;
        for(int i=p[2].first-1;i>=p[3].first;--i)
            res[p[2].second][i]=++cnt;
        for(int j=p[3].second-1;j>p[0].second;--j)
            res[j][p[3].first]=++cnt;
        p[0].first++;
        p[0].second++;
        p[1].first--;
        p[1].second++;
        p[2].first--;
        p[2].second--;
        p[3].first++;
        p[3].second--;
        generate(p);
    }
};

60. Permutation Sequence

链接：https://leetcode.com/problems/permutation-sequence/

描述

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

“123”
“132”
“213”
“231”
“312”
“321”

Given n and k, return the kth permutation sequence.

Note:

Given n will be between 1 and 9 inclusive.
Given k will be between 1 and n! inclusive.

Example 1:

1
2


Input: n = 3, k = 3
Output: "213"

Example 2:

1
2


Input: n = 4, k = 9
Output: "2314"

题解

全排列中，从低到高第i位上一个数字重复出现的次数是(i-1)!，因此从最高位入手，逐位向后推。计算次高位时固定最高位取出一段排列，将k置为原本的k在这一段中的偏移，继续递推
若最高位上一个数字重复出现的次数是multip，则：
- 第k个排列的最高位数字是(k-1)/multip+1（由于不可重复，故用bool数组记录哪些数字已被取过，这里求的是第(k-1)/multip+1个未被取过的数字）
- 取最高位固定下来的一段排列，下一次递推的k（即在这一段内的偏移量）是(k-1)%multip+1
- 固定最高位，取这一段排列作为剩余数字的全排列，继续递推
时间复杂度：确定每一位时都要遍历bool数组找第(k-1)/multip+1个false，故O(n^2)
空间复杂度：使用了vector保存阶乘，并用了bool数组，O(n)

 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


// Runtime: 0 ms, faster than 100.00% of C++ online submissions for Permutation Sequence.
// Memory Usage: 6.1 MB, less than 100.00% of C++ online submissions for Permutation Sequence.
class Solution {
public:
    string getPermutation(int n, int k) {
        get_multip(n);
        string s;
        for(int i=1;i<=n;++i)
            s.push_back('0'+i);
        vector<bool> visit(n,false);
        string res;
        for(int i=n-1;i>=0;--i){
            int multip=multiplier[i];
            // 这一次应该取第(k-1)/multip+1个未被取过的数字
            int index=find_kth_unseen(visit,(k-1)/multip+1);
            visit[index]=true;
            res.push_back(s[index]);
            k=(k-1)%multip+1;
        }
        return res;
    }
private:
    // 快速计算多个数的阶乘
    vector<int> multiplier{1};
    void get_multip(int n){
        int cur=0;
        for(int i=1;i<=n;++i)
            multiplier.push_back(i*multiplier[cur++]);
    }
    // 找出bool数组中第k个false的下标
    int find_kth_unseen(const vector<bool> &visit,int k){
        int cur=0;
        while(k>0)
            if(!visit[cur++])
                --k;
        return cur-1;
    }
};

文章目录

41. First Missing Positive

描述

题解

42. Trapping Rain Water

描述

题解

解法1：DP

解法2：双指针

43. Multiply Strings

描述

题解

44. Wildcard Matching

描述

题解

45. Jump Game II

描述

题解

46. Permutations

描述

题解

47. Permutations II

描述

题解

48. Rotate Image

描述

题解

49. Group Anagrams

描述

题解

50. Pow(x, n)

描述

题解

51. N-Queens

描述

题解

52. N-Queens II

描述

题解

53. Maximum Subarray

描述

题解

54. Spiral Matrix

描述

题解

55. Jump Game

描述

题解

56. Merge Intervals

描述

题解

57. Insert Interval

描述

题解

58. Length of Last Word

描述

题解

59. Spiral Matrix II

描述

题解

60. Permutation Sequence

描述

题解