SOUSIC

哈库呐玛塔塔

0%

Leetcode每日一题 - 2020年七月

发表于 更新于 分类于 Valine：
本文字数： 34k 阅读时长 ≈ 31 分钟
7月份每日一题

7月1日 718. 最长重复子数组（中等）

给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

示例：

1
2
3
4
5
6
输入：
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出：3
解释：
长度最长的公共子数组是 [3, 2, 1] 。

题解：

  1. 滑动窗口。主串从第一个开始，滑动匹配串直到与主串的当前元素相等，再看后面一共有几个元素相等。分别以 A 为主串和 B 为主串匹配一次取最大。比如A = {0,0,0,0,0,0,1,0,0,0}, B = {0,0,0,0,0,0,0,1,0,0}，以 A 为主串会得到6。

    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
    int findCore(vector<int>& A, vector<int>& B){
        int maxLen = 0;
        for (int i = 0; i < A.size(); i++)
        {
            int j = 0;

            while (j < B.size())
            {
                while(j<B.size() && B[j]!=A[i])//判断边界的一定要在前面
                    j++;
                if(j==B.size())
                    break;
                int cur = i;
                while(cur<A.size() && j<B.size() && A[cur]==B[j]){
                    cur++;
                    j++;
                }
                maxLen = max(maxLen, cur - i);
            }
        }
        return maxLen;
    }

    int findLength(vector<int>& A, vector<int>& B) {
        if(A.empty() || B.empty())
            return 0;

        int a = findCore(A, B);
        int b = findCore(B, A);
        return max(a, b);
    }

    时间复杂度：O((m+n) * min{n,m})。m、n为数组的长度。
    空间复杂度：O(1)

  2. 二维dp。dp[i][j]表示A[0:i) 和 B[0:i)最长公共字串长度。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    int findLength(vector<int>& A, vector<int>& B) {
        if(A.empty() || B.empty())
            return 0;

        int a = A.size(), b = B.size();
        vector<vector<int> > dp(a + 1, vector<int>(b + 1, 0));
        int maxLen = 0;
        for (int i = 1; i <= a; i++)
        {
            for (int j = 1; j <= b;j++){
                if(A[i - 1] == B[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                maxLen = max(maxLen, dp[i][j]);
            }
        }
        return maxLen;
    }

    时间复杂度：O(mn)
    空间复杂度：O(mn)

  3. 一维dp。
    因为只用到了上一行的dp，所以可以只用一维dp来做，但是j的更新就需要从后往前，因为更新当前的值需要上一行的前面的值。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    int findLength(vector<int>& A, vector<int>& B) {
        if(A.empty() || B.empty())
            return 0;

        int a = A.size(), b = B.size();
        vector<int> dp(b + 1, 0);
        int maxLen = 0;
        for (int i = 1; i <= a; i++)
        {
            for (int j = b; j > 0;j--){
                if(A[i - 1] == B[j - 1])
                    dp[j] = dp[j - 1] + 1;
                else
                    dp[j] = 0;
                maxLen = max(maxLen, dp[j]);
            }
        }
        return maxLen;
    }

    时间复杂度：O(mn)
    空间复杂度：O(m)

7月2日 378. 有序矩阵中第K小的元素（中等）

给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。

示例：

1
2
3
4
5
6
7
8
matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

返回 13。

题解：

  1. 把二维拉成一维，然后排序。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        vector<int> vec;
        for(int i=0;i<matrix.size();i++){
            for(int j=0;j<matrix[0].size();j++){
                vec.push_back(matrix[i][j]);
            }
        }
        sort(vec.begin(),vec.end());
        return vec[k-1];
    }

    时间复杂度：O(n^2 * log(n^2))
    空间复杂度：O(n^2)

  2. 类似与归并排序。到第k个就结束。本代码每次都遍历每一行的首位元素，找到最小值弹出。（其实可以用一个小根堆来求最小值，可以减少时间复杂度为O(k * logn)）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    int kthSmallest(vector<vector<int> >& matrix, int k) {
        int n = matrix.size();
        for (int i = 0; i < k;i++){
            int min = 0;
            for (int j = 0; j < n; j++)
            {
                while (matrix[min].empty())
                    min++;
                if (matrix[j].empty())
                    continue;
                min = matrix[min][0] <= matrix[j][0] ? min : j;
            }
            if(i==k-1)
                return matrix[min][0];
            matrix[min].erase(matrix[min].begin(), matrix[min].begin() + 1);
        }
        return 0;
    }

    时间复杂度：O(k * n)
    空间复杂度：O(1)

7月3日 108. 将有序数组转换为二叉搜索树（简单）

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

1
2
3
4
5
6
7
8
9
给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

题解：
递归。中序遍历，总是选择中间位置左边的数字作为根节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
TreeNode *buildTree(vector<int>& nums, int left, int right){
    if (left > right) {
        return nullptr;
    }
    // 总是选择中间位置左边的数字作为根节点
    int mid = (left + right) / 2;

    TreeNode* root = new TreeNode(nums[mid]);
    root->left = buildTree(nums, left, mid - 1);
    root->right = buildTree(nums, mid + 1, right);
    return root;
}

TreeNode* sortedArrayToBST(vector<int>& nums) {
    int L = 0, R = nums.size()-1;
    TreeNode *res = buildTree(nums, L, R);
    return res;
}

时间复杂度：O(n)
空间复杂度：O(logn)

7月4日 32. 最长有效括号（困难）

给定一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

1
2
3
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"

示例 2:

1
2
3
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

示例3:

1
2
3
输入: "()(())"
输出: 6
解释，都是有效的。

题解：

  1. 栈。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    int longestValidParentheses(string s) {
        stack<int> st1;
        st1.push(-1);
        int longest = 0;
        for (int i = 0; i < s.size(); i++)
        {
            if(s[i]=='(')
                st1.push(i);
            else{
                st1.pop();
                if(st1.empty())
                    st1.push(i);
                else
                    longest = max(longest, i - st1.top());
            }
        }
        return longest;
    }

    时间复杂度：O(n)
    空间复杂度：O(n)

  2. dp。

  • s[i]=‘)’ 且 s[i−1]=‘(’，也就是字符串形如 “……()”“……()”，我们可以推出：dp[i]=dp[i-2]+2
  • s[i]=‘)’ 且 s[i−1]=‘)’，也就是字符串形如 “……))”“……))”，我们可以推出：如果s[i−dp[i−1]−1]=‘(’，那么：dp[i]=dp[i−1]+dp[i−dp[i−1]−2]+2 
    1
    （代码略）

7月5日 44. 通配符匹配（困难）

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 ‘?’ 和 ‘*’ 的通配符匹配。

  1. ‘?’ 可以匹配任何单个字符。
  2. ‘*’ 可以匹配任意字符串（包括空字符串）。

两个字符串完全匹配才算匹配成功。

说明:

  1. s 可能为空，且只包含从 a-z 的小写字母。
  2. p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。

示例 1:

1
2
3
4
5
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

1
2
3
4
5
输入:
s = "aa"
p = "*"
输出: true
解释: '*' 可以匹配任意字符串。

示例 3:

1
2
3
4
5
输入:
s = "cb"
p = "?a"
输出: false
解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。

示例 4:

1
2
3
4
5
输入:
s = "adceb"
p = "*a*b"
输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".

示例 5:

1
2
3
4
输入:
s = "acdcb"
p = "a*c?b"
输出: false

题解：

  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
    bool matchCore(string s, string p, int idxS, int idxP){
        if(idxS == s.size() && idxP == p.size())
            return true;
        if(idxS >= s.size()){
            if(p[idxP] != '*')
                return false;
            else
                return matchCore(s, p, idxS, idxP + 1);
        }

        if(p[idxP]=='*'){
            if(idxP==p.size()-1)
                return true;
            while(p[idxP]=='*')//匹配连续的'*'
                idxP++;
            return matchCore(s, p, idxS + 1, idxP - 1) || matchCore(s, p, idxS, idxP);
        }
        if(p[idxP]=='?' || s[idxS]==p[idxP])
            return matchCore(s, p, idxS + 1, idxP + 1);
        else
            return false;
    }

    bool isMatch(string s, string p) {
        return matchCore(s, p, 0, 0);
    }

    时间复杂度：O(2^k)。k是‘*’串的个数。超时，941 / 1809 个通过测试用例。
    空间复杂度：O(2^k)，递归调用需要用到栈

  2. dp。
    dp[i][j]表示字符串s的前i个字符p的前j个字符是否能匹配。

  • 注意：s和p下标是从 0 开始的。
  • 当s[i-1]==p[j-1]或p[j-1]=='?'时：dp[i][j] = dp[i - 1][j - 1]。
  • 当p[j-1]=='*'时：如果使用’*‘，则dp[i][j] = dp[i-1][j]；如果不使用’*‘，则dp[i][j] = dp[i][j-1]。
  • 初始状态：dp[0][0] = true；dp[i][0] = false；如果直到p[i]前面都是”*“，dp[0][0～i] = true。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    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; i++) {
            if (p[i - 1] == '*')
                dp[0][i] = true;
            else
                break;
        }

        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n;j++){
                if(p[j-1]=='?' || p[j-1]==s[i-1])
                    dp[i][j] = dp[i - 1][j - 1];
                else if(p[j-1]=='*')
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
            }
        }
        return dp[m][n];
    }
    时间复杂度：O(mn)
    空间复杂度：O(mn)

ps. 以后碰到这种题，直接用dp，递归基本都是时间复杂度比较高的。

7月6日 63. 不同路径 II（中等）

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

说明：m 和 n 的值均不超过 100。

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
输入:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

题解：

  1. 二维dp。
    dp[i][j] = dp[i-1][j] + dp[i][j-1]

注意初始化：

  • 当obstacleGrid[i][j]==1时dp[i][j] = 0；
  • 第一行和第一列，obstacleGrid[0][j]==1和obstacleGrid[i][0]==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
    27
    28
    29
    int uniquePathsWithObstacles(vector<vector<int> >& obstacleGrid) {
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        if(m==0 || obstacleGrid[0][0]==1)
            return 0;

        vector<vector<int> > dp(m,vector<int>(n,0));

        dp[0][0] = 1;
        for (int i = 1; i < m; i++){
            if(obstacleGrid[i][0]==1)
                break;
            dp[i][0] = 1;
        }
        for (int j = 1; j < n;j++){
            if(obstacleGrid[0][j]==1)
                break;
            dp[0][j] = 1;
        }

        for (int i = 1; i < m; i++)
        {
            for (int j = 1; j < n;j++){
                if(obstacleGrid[i][j]==1)
                    continue;
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
  1. 一维dp。
    因为只会用到上一行j之后（含j）的数据，所以可以优化为只用一维dp。
    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
    int uniquePathsWithObstacles(vector<vector<int> >& obstacleGrid) {
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        if(m==0 || obstacleGrid[0][0]==1)
            return 0;

        vector<int> dp(n+1,0);
        dp[0] = 1;
        for (int i = 1; i < n; i++){
            if(obstacleGrid[0][i]==1)
                break;
            dp[i] = 1;
        }

        for (int i = 1; i < m; i++)
        {
            if(dp[0]==1 && obstacleGrid[i][0]==0)
                dp[0] = 1;
            else
                dp[0] = 0;
            for (int j = 1; j < n; j++)
            {
                if(obstacleGrid[i][j]==1)
                    dp[j] = 0;
                else
                    dp[j] = dp[j] + dp[j - 1];
            }
        }
        return dp[n-1];
    }

7月7日 112. 路径总和（简单）

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树，以及目标和 sum = 22，

1
2
3
4
5
6
7
8
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

题解：

  1. dfs（递归）。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    bool hasPathSum(TreeNode* root, int sum) {
        if(root==nullptr)
            return false;
        if(root->left==nullptr && root->right==nullptr){
            return root->val==sum;
        }

        int curVal = root->val;
        return hasPathSum(root->left,sum-curVal) || hasPathSum(root->right,sum-curVal);
    }

    时间复杂度：O(n)
    空间复杂度：O(h)。h为树的高度，最坏情况下h = n。

  2. bfs。队列实现。时空复杂度都是O(n)

    1
    （代码略）

7月8日 程序员面试金典 面试题 16.11. 跳水板（简单）

你正在使用一堆木板建造跳水板。有两种类型的木板，其中长度较短的木板长度为shorter，长度较长的木板长度为longer。你必须正好使用k块木板。编写一个方法，生成跳水板所有可能的长度。
返回的长度需要从小到大排列。

示例：

1
2
3
4
5
输入：
shorter = 1
longer = 2
k = 3
输出： {3,4,5,6}

题解：
shorter的使用次数分别为0-k。
注意返回需要从小到大。

1
2
3
4
5
6
7
8
9
10
11
12
vector<int> divingBoard(int shorter, int longer, int k) {
    if(k==0)
        return {};
    if (shorter == longer) {
        return {shorter * k};
    }
    vector<int> res;
    for(int i=0;i<=k;i++){
        res.push_back(shorter*(k-i)+longer*i);
    }
    return res;
}

时间复杂度：O(k)
空间复杂度：O(k)

7月9日 程序员面试金典 面试题 17.13. 恢复空格（中等）

哦，不！你不小心把一个长篇文章中的空格、标点都删掉了，并且大写也弄成了小写。像句子”I reset the computer. It still didn’t boot!”已经变成了”iresetthecomputeritstilldidntboot”。在处理标点符号和大小写之前，你得先把它断成词语。当然了，你有一本厚厚的词典dictionary，不过，有些词没在词典里。假设文章用sentence表示，设计一个算法，把文章断开，要求未识别的字符最少，返回未识别的字符数。

注意：本题相对原题稍作改动，只需返回未识别的字符数

示例：

1
2
3
4
5
输入：
dictionary = ["looked","just","like","her","brother"]
sentence = "jesslookedjustliketimherbrother"
输出： 7
解释： 断句后为"jess looked just like tim her brother"，共7个未识别字符。

题解：
dp。
dp[i] 表示第 i 个之前字母（含i）之前未识别的最少字符数。

  • 当s[i-d:d)与字典中某一字符串匹配时： dp[i] = min(dp[i - d],dp[i])。需要枚举每一个字典中的字符串。
  • 当与所有不重合时： dp[i] = dp[i -1] + 1， 把 s[i-1] 当作一个未识别字符。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    int respace(vector<string>& dictionary, string sentence) {
        vector<int> dp(sentence.size() + 1,sentence.size());
        dp[0] = 0;
        for (int i = 1; i <= sentence.size(); i++) {
            for (string dict : dictionary) {
                int d = dict.size();
                if (i >= d && sentence.substr(i - d, d) == dict)
                    dp[i] = min(dp[i - d], dp[i]);
                else dp[i] = min(dp[i - 1] + 1,dp[i]);
            }
        }
        return dp[sentence.size()];
    }
    时间复杂度：O(n*k)。n 为字符串 s 的长度，k为字典的长度。
    空间复杂度：O(n)

7月10日 309. 最佳买卖股票时机含冷冻期（中等）

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

示例:

1
2
3
输入: [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

题解：
dp。
dp[i] 表示第 i 天结束之后的累计最大收益。
一共有三个状态：A观望，B持股，C冷却

1
2
3
4
5
状态转移图：A-(观望)->A,
        A-(买入｜-price)->B,
        B-(观望)->B,
        B-(卖出|+price)->C,
        C-(冷却)->A
  • 持有：用dp[i][0]表示
  • 冷却：用dp[i][1]表示
  • 观望：用dp[i][2]表示

根据状态转移图可以写出dp[i][j]的状态转移方程：

  • dp[i][0] = max(dp[i - 1][2] - prices[i], dp[i - 1][0]);
  • dp[i][1] = dp[i - 1][0] + prices[i];
  • dp[i][2] = max(dp[i - 1][1], dp[i - 1][2]);
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    int maxProfit(vector<int>& prices) {
        if(prices.empty())
            return 0;
        vector<vector<int> > dp(prices.size(), vector<int>(3));
        dp[0][0] = -prices[0];
        for (int i = 1; i < prices.size();i++){
            dp[i][0] = max(dp[i - 1][2] - prices[i], dp[i - 1][0]);
            dp[i][1] = dp[i - 1][0] + prices[i];
            dp[i][2] = max(dp[i - 1][1], dp[i - 1][2]);
        }
        return max(dp[prices.size() - 1][1], dp[prices.size() - 1][2]);
    }
    时间复杂度：O(n)
    空间复杂度：O(n)

7月11日 315. 计算右侧小于当前元素的个数（困难）

给定一个整数数组 nums，按要求返回一个新数组 *counts。数组 *counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

示例:

1
2
3
4
5
6
7
输入: [5,2,6,1]
输出: [2,1,1,0] 
解释:
5 的右侧有 2 个更小的元素 (2 和 1).
2 的右侧仅有 1 个更小的元素 (1).
6 的右侧有 1 个更小的元素 (1).
1 的右侧有 0 个更小的元素.

题解：

  1. 暴力。O(n^2)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> res(nums.size());
        for(int i = 0;i<nums.size();i++){
            int greater = 0;
            for(int j=i+1;j<nums.size();j++){
                if(nums[j]<nums[i])
                    greater++;
            }
            res[i] = greater;
        }
        return res;
    }
  2. 从后往前，维护一个升序数组。插入的序号就是比它小数字的个数。
    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
    int insertNums(vector<int> &sorted, int num){
        if(sorted.size()==1){
            if(num>sorted[0]){
                sorted.push_back(num);
                return 1;
            }
            else{
                sorted.insert(sorted.begin(),num);
                return 0;
            }
        }

        int l = 0, r = sorted.size()-1;
        int mid = (l + r) / 2;
        while (l <= r)
        {
            if(sorted[mid]<num)
                l = mid + 1;
            else
                r = mid - 1;
            mid = (l+r)/2;
        }
        sorted.insert(sorted.begin()+l, num);
        return l;
    }

    vector<int> countSmaller(vector<int>& nums) {
        if(nums.empty())
            return {};
        vector<int> sorted;
        vector<int> res(nums.size());
        sorted.push_back(nums[nums.size()-1]);
        for(int i=nums.size()-2;i>=0;i--){
            int idx = insertNums(sorted, nums[i]);
            res[i] = idx;
        }
        return res;
    }
    时间复杂度：O(nlogn)。每次插入二分查找需要O(logn)的复杂度。
    空间复杂度：O(n)

真题

给定两个长度为n，值不重复的数列 A & B ，将 A 这个数列进行入栈出栈操作，请问能否得到 B。

示例1：

1
2
3
4
5
输入：
A = [0,1,2,3,4]
B = [2,1,0,4,3]

输出： Y

示例2:

1
2
3
4
5
输入：
A = [0]
B = [1]

输出： 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
bool canGetB(vector<int> A, vector<int> B){
    stack<int> st;
    int idxA = 0, idxB = 0;
    for (; idxB < B.size(); idxB++)
    {
        if(idxA<A.size() && !st.empty() && st.top()==B[idxB]){
            st.pop();
            continue;
        }
        while (idxA<A.size() && A[idxA]!=B[idxB])
        {
            st.push(A[idxA]);
            idxA++;
        }
        if(idxA<A.size()){
            idxA++;
        }
        else
            break;
    }
    while(!st.empty() && idxB<B.size()){
        if(B[idxB]==st.top()){
            idxB++;
            st.pop();
        }else{
            break;
        }
    }
    if(idxA < A.size() || idxB < B.size())
        return false;
    return true;
}

时间复杂度：O(n)
空间复杂度：O(n)

7月12日 174. 地下城游戏（困难）

一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。

骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。

有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。

为了尽快到达公主，骑士决定每次只向右或向下移动一步。

编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。

例如，考虑到如下布局的地下城，如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7。

1
2
3
-2(K)  -3    3
-5	  -10    1
10	   30   -5(P)

说明:

  • 骑士的健康点数没有上限。
  • 任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。

题解：
反向dp。
因为正向dp需要维护两个重要变量：当 前HP 和 最大伤害。没办法做到无后效性。
dp[i][j] 表示从坐标 (i,j) 到终点所需的最小初始值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int calculateMinimumHP(vector<vector<int> >& dungeon) {
    if(dungeon.empty())
        return 0;
    int M = dungeon.size(), N = dungeon[0].size();
    vector<vector<int> > dp(M+1, vector<int>(N+1, INT_MAX));
    dp[M][N - 1] = dp[M - 1][N] = 1;
    for (int i = M - 1; i >= 0;i--){
        for (int j = N - 1; j >= 0;j--){
            int minn = min(dp[i + 1][j], dp[i][j + 1]);
            dp[i][j] = max(minn - dungeon[i][j], 1);
        }
    }
    return dp[0][0];
}

时间复杂度：O(MN)
空间复杂度：O(MN)

7月13日 350. 两个数组的交集 II（简单）

给定两个数组，编写一个函数来计算它们的交集。

示例 1：

1
2
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

示例 2:

1
2
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

题解：

  1. 双指针。但是需要先排序。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(),nums1.end());
        sort(nums2.begin(),nums2.end());

        vector<int> res;
        int idx1=0,idx2=0;
        while(idx1<nums1.size() && idx2<nums2.size()){
            if(nums1[idx1]==nums2[idx2]){
                res.push_back(nums1[idx1]);
                idx1++;
                idx2++;
            }else{
                if(nums1[idx1]<nums2[idx2])
                    idx1++;
                else
                    idx2++;
            }
        }
        return res;
    }

    时间复杂度：O(mlogmnlogn)。 排序需要 O(nlognmlogm)。
    空间复杂度：O(min{m,n})。

  2. 哈希表。遍历其中一个数组，存入哈希表。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        if(nums2.size()<nums1.size())
            return intersect(nums2, nums1);
        unordered_map<int,int> numMap;
        for (int n : nums1)
            numMap[n]++;

        vector<int> res;
        for (int n : nums2)
        {
            if(numMap.count(n)){
                res.push_back(n);
                numMap[n]--;
                if(numMap[n]==0)
                    numMap.erase(n);
            }
        }
        return res;
    }

    时间复杂度：O(m+n)。
    空间复杂度：O(min{m,n})。

7月14日 120. 三角形最小路径和（中等）

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。

例如，给定三角形：

1
2
3
4
5
6
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

说明：
如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

题解：

  1. 普通dp。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    int minimumTotal(vector<vector<int> >& triangle) {
        if(triangle.empty())
            return 0;
        int n = triangle.size();
        vector<vector<int> > dp(n,vector<int>(n));
        dp[0][0] = triangle[0][0];
        for (int i = 1; i < n; i++)
        {
            dp[i][0] = dp[i - 1][0] + triangle[i][0];
            for (int j = 1; j < i;j++){
                dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];
            }
            dp[i][i] = dp[i - 1][i - 1] + triangle[i][i];
        }
        return *min_element(dp[n - 1].begin(), dp[n - 1].end());
    }
    时间复杂度：O(n^2)。
    空间复杂度：O(n^2)。

7月15日 96. 不同的二叉搜索树（中等）

给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

示例:

1
2
3
4
5
6
7
8
9
10
11
输入: 3
输出: 5

解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

题解：

  1. dp。
    设需要求 n 个节点。以一个节点为根节点，左子树的数量加右子树的数量就是以这个节点为根节点的数量。遍历不同的根节点（0~n）累加。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    int numTrees(int n) {
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j <= i; ++j) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
  2. 数学。
    数学上被称为卡塔兰数。
    1
    2
    3
    4
    5
    6
    7
    nt numTrees(int n) {
        long long C = 1;
        for (int i = 0; i < n; ++i) {
            C = C * 2 * (2 * i + 1) / (i + 2);
        }
        return (int)C;
    }

7月16日 785. 判断二分图（中等）

给定一个无向图graph，当这个图为二分图时返回true。

如果我们能将一个图的节点集合分割成两个独立的子集A和B，并使图中的每一条边的两个节点一个来自A集合，一个来自B集合，我们就将这个图称为二分图。

graph将会以邻接表方式给出，graph[i]表示图中与节点i相连的所有节点。每个节点都是一个在0到graph.length-1之间的整数。这图中没有自环和平行边： graph[i] 中不存在i，并且graph[i]中没有重复的值。

示例 1:

1
2
3
4
5
6
7
8
9
输入: [[1,3], [0,2], [1,3], [0,2]]
输出: true
解释: 
无向图如下:
0----1
|    |
|    |
3----2
我们可以将节点分成两组: {0, 2} 和 {1, 3}。

示例 2:

1
2
3
4
5
6
7
8
9
输入: [[1,2,3], [0,2], [0,1,3], [0,2]]
输出: false
解释: 
无向图如下:
0----1
| \  |
|  \ |
3----2
我们不能将节点分割成两个独立的子集。

题解：
bfs或者dfs，把经过的点分别标上交替的记号。

1
（代码待补全）

7月17日 35. 搜索插入位置（简单）

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:

1
2
输入: [1,3,5,6], 5
输出: 2

示例 2:

1
2
输入: [1,3,5,6], 2
输出: 1

示例 3:

1
2
输入: [1,3,5,6], 7
输出: 4

示例 4:

1
2
输入: [1,3,5,6], 0
输出: 0

题解：
二分查找。可以用O(n)的复杂度顺序遍历。但是一看到排好序，就想到了二分查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int searchInsert(vector<int>& nums, int target) {
    if(nums.empty())
        return 0;
    int L=0,R=nums.size()-1;
    int mid;
    while(L<=R){
        mid = (L+R)/2;
        if(nums[mid]>target)
            R = mid - 1;
        else if(nums[mid]<target)
            L = mid + 1;
        else
            return mid;
    }
    return L;
}

时间复杂度：O(logn)。
空间复杂度：O(1)。

7月18日 97. 交错字符串（困难）

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。

示例 1:

1
2
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出: true

示例 2:

1
2
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出: false

题解：

  1. 双指针递归。（超时）99 / 101 个通过测试用例
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    bool isInterleaveCore(string s1,string s2,string s3,int idx1,int idx2,int idx3){
        if(idx1==s1.size())
            return s2.substr(idx2,s2.size()-idx2+1)==s3.substr(idx3,s3.size()-idx3+1);
        if(idx2==s2.size())
            return s1.substr(idx1,s1.size()-idx1+1)==s3.substr(idx3,s3.size()-idx3+1);
        if(s1[idx1]==s3[idx3]){
            if(s2[idx2]==s3[idx3])
                return isInterleaveCore(s1,s2,s3,idx1+1,idx2,idx3+1) || isInterleaveCore(s1,s2,s3,idx1,idx2+1,idx3+1);
            else
                return isInterleaveCore(s1,s2,s3,idx1+1,idx2,idx3+1);
        }else{
            if(s2[idx2]==s3[idx3])
                return isInterleaveCore(s1,s2,s3,idx1,idx2+1,idx3+1);
            else
                return false;
        }
    }

    bool isInterleave(string s1, string s2, string s3) {
        if(s3.size() != s1.size()+s2.size())
            return false;
        return isInterleaveCore(s1,s2,s3,0,0,0);
    }
  2. 二维dp。
    dp[i][j] 表示字符串 s3[0:i+j] 能否由 s1[0:i] 和 s2[0:j] 组成。
    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
    bool isInterleave(string s1, string s2, string s3) {
        if(s3.size() != s1.size()+s2.size())
            return false;
        vector<vector<bool> > dp(s1.size()+1,vector<bool>(s2.size()+1,false));

        dp[0][0] = true;
        for(int i=1;i<=s1.size();i++){
            if(s1[i-1]==s3[i-1])
                dp[i][0] = true;
            else
                break;
        }
        for(int i=1;i<=s2.size();i++){
            if(s2[i-1]==s3[i-1])
                dp[0][i] = true;
            else
                break;
        }

        for(int i=1;i<=s1.size();i++){
            for(int j=1;j<=s2.size();j++){
                dp[i][j] = (s1[i-1]==s3[i+j-1] && dp[i-1][j]) || (s2[j-1]==s3[i+j-1] && dp[i][j-1]);
            }
        }
        return dp[s1.size()][s2.size()];
    }
    时间复杂度：O(mn)。m 为s1的长度，n 为s2的长度。
    空间复杂度：O(mn)。

ref. leetcode题解

  1. 一维dp。
    因为dp在计算时只用到了上一行，所以可以优化为只用一维数组。
    1
    代码略

7月19日 312. 戳气球（困难）

有 n 个气球，编号为0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

现在要求你戳破所有的气球。如果你戳破气球 i ，就可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。

求所能获得硬币的最大数量。

说明:

  • 你可以假设 nums[-1] = nums[n] = 1，但注意它们不是真实存在的所以并不能被戳破。
  • 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

示例:

1
2
3
4
输入: [3,1,5,8]
输出: 167 
解释: nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
     coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167

题解：
dp。
dp[i][j]表示(i:j)开区间内所能得到的最大值。外层循环要倒序，因为子问题dp[k][j]要在父问题dp[i][j]（i<=k<=j）之前。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int maxCoins(vector<int>& nums) {
    int n = nums.size();
    vector<vector<int> > dp(n + 2, vector<int>(n + 2, 0));
    nums.insert(nums.begin(), 1);
    nums.push_back(1);
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i + 2; j <= n + 1; j++) {
            for (int k = i + 1; k < j; k++) {
                dp[i][j] = max(
                        dp[i][j],
                        (dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j]));
            }
        }
    }
    return dp[0][n + 1];
}

时间复杂度：O(n^3)。
空间复杂度：O(n^2)。

7月20日 167. 两数之和 II - 输入有序数组（简单）

给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

说明:

  • 返回的下标值（index1 和 index2）不是从零开始的。
  • 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

示例:

1
2
3
输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

题解：

  1. 哈希表。
    哈希表保存每个元素，再遍历一次即可。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    vector<int> twoSum(vector<int>& numbers, int target) {
        unordered_map<int, int> numMap;
        for (int i = 0; i < numbers.size();i++)
            numMap[numbers[i]] = i;

        for (int i = 0; i < numbers.size();i++){
            auto it = numMap.find(target - numbers[i]);
            if (it != numMap.end())
                return {i + 1, it->second+1};
        }
        return {};
    }

    时间复杂度：O(n)。
    空间复杂度：O(n)。

  2. 二分查找。时间复杂度：O(nlogn)。空间复杂度：O(1)。

    1
    代码略

  3. 双指针。
    初始时两个指针分别指向第一个元素位置和最后一个元素的位置。每次计算两个指针指向的两个元素之和，并和目标值比较。如果两个元素之和等于目标值，则发现了唯一解。如果两个元素之和小于目标值，则将左侧指针右移一位。如果两个元素之和大于目标值，则将右侧指针左移一位。移动指针之后，重复上述操作，直到找到答案。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    vector<int> twoSum(vector<int>& numbers, int target) {
        int L = 0, R = numbers.size() - 1;
        while (L < R) {
            int sum = numbers[L] + numbers[R];
            if (sum == target) {
                return {L + 1, R + 1};
            } else if (sum < target) {
                ++L;
            } else {
                --R;
            }
        }
        return {-1, -1};
    }

    时间复杂度：O(n)。
    空间复杂度：O(1)。

7月21日 95. 不同的二叉搜索树 II（中等）

给定一个整数 n，生成所有由 1 … n 为节点所组成的 二叉搜索树 。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
输入：3
输出：
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
解释：
以上的输出对应以下 5 种不同结构的二叉搜索树：

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

提示：0 <= n <= 8

题解：
递归。

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
vector<TreeNode*> generateSubTree(int L, int R){
    if(L>R)
        return {nullptr};

    vector<TreeNode*> Trees;
    for(int i=L;i<=R;i++){
        vector<TreeNode*> leftTree = generateSubTree(L,i-1);
        vector<TreeNode*> rightTree = generateSubTree(i+1,R);

        for(auto lTree:leftTree){
            for(auto rTree:rightTree){
                TreeNode* root = new TreeNode(i);
                root->left = lTree;
                root->right = rTree;
                Trees.push_back(root);
            }
        }
    }
    return Trees;
}
vector<TreeNode*> generateTrees(int n) {
    if(n==0)
        return {};
    return generateSubTree(1,n);
}

7月22日 剑指 Offer 11. 旋转数组的最小数字（简单）

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

示例 1：

1
2
输入：[3,4,5,1,2]
输出：1

示例 2：

1
2
输入：[2,2,2,0,1]
输出：0

题解：

  1. 暴力。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    int minArray(vector<int>& numbers) {
        if(numbers.empty())
            return 0;
        for(int i=1;i<numbers.size();i++){
            if(numbers[i]<numbers[i-1])
                return numbers[i];
        }
        return numbers[0];
    }

    时间复杂度：O(n)
    空间复杂度：O(1)

  2. 二分。
    注意：当numbers[mid]==numbers[R]时，由于重复元素的存在，我们并不能确定numbers[mid]究竟在最小值的左侧还是右侧，因此我们不能忽略某一部分的元素。但是由于它们的值相同，所以可以忽略二分查找区间的右端点numbers[R]。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    int minArray(vector<int>& numbers) {
        if(numbers.empty())
            return 0;
        int L=0,R=numbers.size()-1;
        while(L<R){
            int mid = (L+R)/2;
            if(numbers[mid]<numbers[R])
                R=mid;
            else if(numbers[mid]>numbers[R])
                L=mid+1;
            else{
                R--;
            }
        }
        return numbers[R];
    }

    时间复杂度：O(logn)
    空间复杂度：O(1)

7月23日 64. 最小路径和（中等）

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:

1
2
3
4
5
6
7
8
输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

题解：

  1. 二维dp。
    dp[i][j]表示走到第i行第j列格子时的最小值。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    int minPathSum(vector<vector<int>>& grid) {
        if(grid.empty())
            return 0;
        int m = grid.size(),n=grid[0].size();
        vector<vector<int> > dp(m+1,vector<int>(n+1,INT_MAX));
        dp[1][1] = grid[0][0];
        for(int i = 1;i<=m;i++){
            for(int j = 1;j<=n;j++){
                if(i==1&&j==1)
                    continue;
                dp[i][j] = min(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1];
            }
        }
        return dp[m][n];
    }

    时间复杂度：O(mn)
    空间复杂度：O(mn)

  2. 一维dp。
    因为只用到了上一行的dp，所以二维dp可以优化为一维。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    int minPathSum(vector<vector<int>>& grid) {
        if(grid.empty())
            return 0;
        int m = grid.size(),n=grid[0].size();
        vector<int> dp(n,0);
        
        dp[0] = grid[0][0];
        for(int i = 1;i<n;i++)
            dp[i] = grid[0][i]+dp[i-1];
        
        for(int i = 1;i<m;i++){
            for(int j = 0;j<n;j++){
                if(j==0)
                    dp[j] = dp[j]+grid[i][0];
                else
                    dp[j] = min(dp[j-1],dp[j])+grid[i][j];
            }
        }
        return dp[n-1];
    }

    时间复杂度：O(mn)
    空间复杂度：O(n)

7月24日 1025. 除数博弈（简单）

爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。

最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作：

选出任一 x，满足 0 < x < N 且 N % x == 0 。
用 N - x 替换黑板上的数字 N 。
如果玩家无法执行这些操作，就会输掉游戏。

只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 false。假设两个玩家都以最佳状态参与游戏。

示例 1：

1
2
3
输入：2
输出：true
解释：爱丽丝选择 1，鲍勃无法进行操作。

示例 2：

1
2
3
输入：3
输出：false
解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。

题解：

  1. dp。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    bool divisorGame(int N) {
        vector<bool> dp(N+1,false);
        dp[1] = false;
        dp[2]= true;
        int n=N;
        for(int i=3;i<=N;i++){
            for(int j=1;j<i;j++){
                if(i % j == 0 && !dp[i - j]){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[N];
    }

    时间复杂度：O(N^2)
    空间复杂度：O(N)

  2. 归纳法。N 为奇数的时候 Alice（先手）必败，N 为偶数的时候 Alice 必胜。

    1
    2
    3
    bool divisorGame(int N) {
        return N % 2 == 0;
    }

    时间复杂度：O(1)
    空间复杂度：O(1)

7月25日 410. 分割数组的最大值（困难）

给定一个非负整数数组和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。

注意:
数组长度 n 满足以下条件:

  • 1 ≤ n ≤ 1000
  • 1 ≤ m ≤ min(50, n)

示例:

1
2
3
4
5
6
7
8
9
10
11
输入:
nums = [7,2,5,10,8]
m = 2

输出:
18

解释:
一共有四种方法将nums分割为2个子数组。
其中最好的方式是将其分为[7,2,5] 和 [10,8]，
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。

题解：

  1. dp。dp[i][j]表示前i个数被分成j段的答案。dp[i][j]的状态转移方程为：
    • dp[i][j] = min(max(dp[k][j-1],subSum(k+1,i)))

其中min里需要枚举k=[0,i)，subSum(k+1,i)表示nums[k+1]到nums[i]的和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int splitArray(vector<int>& nums, int m) {
    vector<vector<long long> > dp(nums.size() + 1, vector<long long>(m + 1, LLONG_MAX));

    vector<long long> preSum(nums.size() + 1, 0);

    for (int i = 1; i <= nums.size();i++)
        preSum[i] = preSum[i - 1] + nums[i-1];

    dp[0][0] = 0;
    for (int i = 1; i <= nums.size(); i++)
    {
        for (int j = 1; j <= min(m, i); j++)
        {
            for (int k = 0; k < i; k++)
                dp[i][j] = min(dp[i][j], max(dp[k][j - 1], preSum[i] - preSum[k]));
        }
    }
    return (int)dp[nums.size()][m];
}

时间复杂度：O(m * n^2)
空间复杂度：O(mn)

7月26日 329. 矩阵中的最长递增路径（困难）

给定一个整数矩阵，找出最长递增路径的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。

示例 1:

1
2
3
4
5
6
7
8
输入: nums = 
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
] 
输出: 4 
解释: 最长递增路径为 [1, 2, 6, 9]。

示例 2:

1
2
3
4
5
6
7
8
输入: nums = 
[
  [3,4,5],
  [3,2,6],
  [2,2,1]
] 
输出: 4 
解释: 最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。

题解：
有记忆的dfs。
普通dfs会超时，所以加了二位矩阵来记录已经得到的最长序列。

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
vector<vector<int> > dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

int dfs(vector<vector<int> > &matrix, int i, int j, vector<vector<int> > &memo){
    if(memo[i][j]!=0)
        return memo[i][j];
    memo[i][j] = 1;
    for(auto d:dirs){
        if (i + d[0] >= 0 && i + d[0] < matrix.size() 
            && j + d[1] >= 0 && j + d[1] < matrix[0].size() 
            && matrix[i + d[0]][j + d[1]] > matrix[i][j])
            memo[i][j] = max(memo[i][j], dfs(matrix, i + d[0], j + d[1], memo) + 1);
    }
    return memo[i][j];
}

int longestIncreasingPath(vector<vector<int> >& matrix) {
    if(matrix.empty())
        return 0;
    int m = matrix.size(), n = matrix[0].size();
    vector<vector<int> > memo(m, vector<int>(n, 0));
    int res = 0;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            res = max(res, dfs(matrix, i, j, memo));
        }
    }
    return res;
}

时间复杂度：O(mn)
空间复杂度：O(mn)

7月27日 392. 判断子序列（简单）

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，”ace”是”abcde”的一个子序列，而”aec”不是）。

示例 1:

1
2
s = "abc", t = "ahbgdc"
返回 true.

示例 2:

1
2
s = "axc", t = "ahbgdc"
返回 false.

后续挑战：
如果有大量输入的 S，称作S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

题解：
双指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool isSubsequence(string s, string t) {
    if(t.empty()){
        if(s.empty())
            return true;
        else
            return false;
    }
    
    int idxS=0,idxT=0;
    while(idxS<s.size() && idxT<t.size()){
        if(s[idxS]==t[idxT])
            idxS++;
        idxT++;
    }
    return idxS==s.size();
}

时间复杂度：O(m+n)
空间复杂度：O(1)

7月28日 104. 二叉树的最大深度（简单）

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]， 3 / \ 9 20 / \ 15 7 返回它的最大深度 3 。

题解：

  1. 层序遍历（BFS）。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    int maxDepth(TreeNode* root){
        if(root==nullptr)
            return 0;
        queue<TreeNode*> que;
        que.push(root);
        int hight = 0;
        while(!que.empty()){
            hight++;
            int n = que.size();
            for (int i = 0; i < n; i++)
            {
                TreeNode *curNode = que.front();
                que.pop();
                if(curNode->left!=nullptr)
                    que.push(curNode->left);
                if(curNode->right!=nullptr)
                    que.push(curNode->right);
            }
        }
        return hight;
    }

    时间复杂度：O(n)
    空间复杂度：O(n)

  2. 递归。

    1
    2
    3
    4
    5
    int maxDepth(TreeNode* root){
        if(root==nullptr)
            return 0;
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }

    时间复杂度：O(n)
    空间复杂度：O(hight)

7月29日 LCP 13. 寻宝（困难）

我们得到了一副藏宝图，藏宝图显示，在一个迷宫中存在着未被世人发现的宝藏。

迷宫是一个二维矩阵，用一个字符串数组表示。它标识了唯一的入口（用 ‘S’ 表示），和唯一的宝藏地点（用 ‘T’ 表示）。但是，宝藏被一些隐蔽的机关保护了起来。在地图上有若干个机关点（用 ‘M’ 表示），只有所有机关均被触发，才可以拿到宝藏。

要保持机关的触发，需要把一个重石放在上面。迷宫中有若干个石堆（用 ‘O’ 表示），每个石堆都有无限个足够触发机关的重石。但是由于石头太重，我们一次只能搬一个石头到指定地点。

迷宫中同样有一些墙壁（用 ‘#’ 表示），我们不能走入墙壁。剩余的都是可随意通行的点（用 ‘.’ 表示）。石堆、机关、起点和终点（无论是否能拿到宝藏）也是可以通行的。

我们每步可以选择向上/向下/向左/向右移动一格，并且不能移出迷宫。搬起石头和放下石头不算步数。那么，从起点开始，我们最少需要多少步才能最后拿到宝藏呢？如果无法拿到宝藏，返回 -1 。

示例 1：

1
2
3
4
5
输入： ["S#O", "M..", "M.T"]

输出：16

解释：最优路线为： S->O, cost = 4, 去搬石头 O->第二行的M, cost = 3, M机关触发 第二行的M->O, cost = 3, 我们需要继续回去 O 搬石头。 O->第三行的M, cost = 4, 此时所有机关均触发 第三行的M->T, cost = 2，去T点拿宝藏。 总步数为16。

示例 2：

1
2
3
4
5
输入： ["S#O", "M.#", "M.T"]

输出：-1

解释：我们无法搬到石头触发机关

示例 3：

1
2
3
4
5
输入： ["S#O", "M.T", "M.."]

输出：17

解释：注意终点也是可以通行的。

限制：

1
2
3
4
5
6
1 <= maze.length <= 100
1 <= maze[i].length <= 100
maze[i].length == maze[j].length
S 和 T 有且只有一个
0 <= M的数量 <= 16
0 <= O的数量 <= 40，题目保证当迷宫中存在 M 时，一定存在至少一个 O 。

题解：

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int n, m;

bool inBound(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}

vector<vector<int>> bfs(int x, int y, vector<string>& maze) {
    vector<vector<int>> ret(n, vector<int>(m, -1));
    ret[x][y] = 0;
    queue<pair<int, int>> Q;
    Q.push({x, y});
    while (!Q.empty()) {
        auto p = Q.front();
        Q.pop();
        int x = p.first, y = p.second;
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k], ny = y + dy[k];
            if (inBound(nx, ny) && maze[nx][ny] != '#' && ret[nx][ny] == -1) {
                ret[nx][ny] = ret[x][y] + 1;
                Q.push({nx, ny});
            }
        }
    }
    return ret;
}

int minimalSteps(vector<string>& maze) {
    n = maze.size(), m = maze[0].size();
    // 机关 & 石头
    vector<pair<int, int>> buttons, stones;
    // 起点 & 终点
    int sx, sy, tx, ty;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (maze[i][j] == 'M') {
                buttons.push_back({i, j});
            }
            if (maze[i][j] == 'O') {
                stones.push_back({i, j});
            }
            if (maze[i][j] == 'S') {
                sx = i, sy = j;
            }
            if (maze[i][j] == 'T') {
                tx = i, ty = j;
            }
        }
    }
    int nb = buttons.size();
    int ns = stones.size();
    vector<vector<int>> start_dist = bfs(sx, sy, maze);

    // 边界情况：没有机关
    if (nb == 0) {
        return start_dist[tx][ty];
    }
    // 从某个机关到其他机关 / 起点与终点的最短距离。
    vector<vector<int>> dist(nb, vector<int>(nb + 2, -1));
    // 中间结果
    vector<vector<vector<int>>> dd(nb);
    for (int i = 0; i < nb; i++) {
        vector<vector<int>> d = bfs(buttons[i].first, buttons[i].second, maze);
        dd[i] = d;
        // 从某个点到终点不需要拿石头
        dist[i][nb + 1] = d[tx][ty];
    }

    for (int i = 0; i < nb; i++) {
        int tmp = -1;
        for (int k = 0; k < ns; k++) {
            int mid_x = stones[k].first, mid_y = stones[k].second;
            if (dd[i][mid_x][mid_y] != -1 && start_dist[mid_x][mid_y] != -1) {
                if (tmp == -1 || tmp > dd[i][mid_x][mid_y] + start_dist[mid_x][mid_y]) {
                    tmp = dd[i][mid_x][mid_y] + start_dist[mid_x][mid_y];
                }
            }
        }
        dist[i][nb] = tmp;
        for (int j = i + 1; j < nb; j++) {
            int mn = -1;
            for (int k = 0; k < ns; k++) {
                int mid_x = stones[k].first, mid_y = stones[k].second;
                if (dd[i][mid_x][mid_y] != -1 && dd[j][mid_x][mid_y] != -1) {
                    if (mn == -1 || mn > dd[i][mid_x][mid_y] + dd[j][mid_x][mid_y]) {
                        mn = dd[i][mid_x][mid_y] + dd[j][mid_x][mid_y];
                    }
                }
            }
            dist[i][j] = mn;
            dist[j][i] = mn;
        }
    }

    // 无法达成的情形
    for (int i = 0; i < nb; i++) {
        if (dist[i][nb] == -1 || dist[i][nb + 1] == -1) return -1;
    }
    
    // dp 数组， -1 代表没有遍历到
    vector<vector<int>> dp(1 << nb, vector<int>(nb, -1));
    for (int i = 0; i < nb; i++) {
        dp[1 << i][i] = dist[i][nb];
    }
    
    // 由于更新的状态都比未更新的大，所以直接从小到大遍历即可
    for (int mask = 1; mask < (1 << nb); mask++) {
        for (int i = 0; i < nb; i++) {
            // 当前 dp 是合法的
            if (mask & (1 << i)) {
                for (int j = 0; j < nb; j++) {
                    // j 不在 mask 里
                    if (!(mask & (1 << j))) {
                        int next = mask | (1 << j);
                        if (dp[next][j] == -1 || dp[next][j] > dp[mask][i] + dist[i][j]) {
                            dp[next][j] = dp[mask][i] + dist[i][j];
                        }
                    }
                }
            }
        }
    }

    int ret = -1;
    int final_mask = (1 << nb) - 1;
    for (int i = 0; i < nb; i++) {
        if (ret == -1 || ret > dp[final_mask][i] + dist[i][nb + 1]) {
            ret = dp[final_mask][i] + dist[i][nb + 1];
        }
    }

    return ret;
}

7月30日 343. 整数拆分（中等）

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

示例 1:

1
2
3
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

1
2
3
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

说明: 你可以假设 n 不小于 2 且不大于 58。

题解：

  1. dp。
    dp[i]表示数字i分解后能达到的最大积。可以分为两种情况：
  • 1）i分解为j和i-j两个数；
  • 2）i分解为j和i-j后，i-j还可以再分解，其最大积为dp[i-j]。
  • 枚举1~i-1每一个点，看哪个点分解后的积最大
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    int integerBreak(int n) {
        vector<int> dp(n+1,0);
        for (int i = 2; i <= n; i++)
        {
            for (int j = 1; j < i; j++)
            {
                dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }
    时间复杂度：O(n^2)
    空间复杂度：O(n)

7月31日 程序员面试金典 面试题 08.03. 魔术索引（简单）

魔术索引。 在数组A[0…n-1]中，有所谓的魔术索引，满足条件A[i] = i。给定一个有序整数数组，编写一种方法找出魔术索引，若有的话，在数组A中找出一个魔术索引，如果没有，则返回-1。若有多个魔术索引，返回索引值最小的一个。

示例1:

1
2
3
输入：nums = [0, 2, 3, 4, 5]
输出：0
说明: 0下标的元素为0

示例2:

1
2
输入：nums = [1, 1, 1]
输出：1

提示: nums长度在[1, 1000000]之间

题解：

1
2
3
4
5
6
7
int findMagicIndex(vector<int>& nums) {
    for(int i=0;i<nums.size();i++){
        if(nums[i]==i)
            return i;
    }
    return -1;
}

时间复杂度：O(n)
空间复杂度：O(1)