Leetcode 刷题笔记

要开始刷题了，记录下那些思想比较绕的，一时半会想不起来怎么做的题目。

236. 二叉树的最近公共祖先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == p || root == q || !root) return root;
        TreeNode* l = lowestCommonAncestor(root->left, p, q);
        TreeNode* r = lowestCommonAncestor(root->right, p, q);
        // 情况 1，p、q在左右两边
        if (l && r) return root;
        if (!l && !r) return nullptr;// 两边都没有 p、q，那么直接返回
        // 情况 2 和 3
        return l ? l : r;
    }
};

问题描述：给定一颗树的根节点 root，找出节点 p 和 q 的最近的公共祖先节点。

这个分三种情况：

  1. 祖先节点正好在中间，而 p、q 节点在左右两边
  2. p、q 都在一边，且祖先节点为 p
  3. p、q 都在一边，且祖先节点为 q

递归地查找 p、q 位置，即到底是在左右两边，还是在同一边。

对于第一种情况，我们只要返回 root 节点就行了；对于第二种情况，返回 p；第三种情况，返回 q

395. 至少有 K 个重复字符的最长子串

这一题和 至多有K个重复字符的最长字串、无重复字符的最长字串 有类似的概念，可以一起训练。

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
class Solution {
public:
    int fz(const string& s, int l, int r, int k) {
        int a[26]{0};
        for (int i = l; i < r; ++i)
            a[s[i] - 'a']++;
        vector<vector<int>> pairs;
        int nl = l;
        int i;
        bool need_partation = false;
        for (i = l; i < r && nl < r; ++i) {
            if (a[s[i] - 'a'] < k) {
                need_partation = true;
                if (i - nl >= k)    pairs.push_back({nl, i});
                while (i < r && a[s[i] - 'a'] < k) ++i;
                nl = i;
            }
        }
        if (!need_partation) return r - l >= k ? r - l : 0;
        if (i - nl >= k)    pairs.push_back({nl, i});
        int ret = 0;
        for (auto p : pairs)
            ret = max(ret, fz(s, p[0], p[1], k));
        return ret;
    }
    int longestSubstring(string s, int k) {
        return fz(s, 0, s.size(), k);
    }
};

这道题的思想很重要，采用分治的思想：如果字符出现的次数少于 K 那么该字符比不可能出现在最长字串中，因此可以用该字符对字符串进行划分，划分成一个个的区间，然后对区间内的字符串再次采用分治思想。

举例如下：

1
2
3
4
5
6
7
8
9
//分治：对于一个字符串来说，如果要求子串最少出现k次，那么如果某些字母出现的次数小于k,
//这些字母一定不会出现在最长的子串中，并且这些字母将整个字符子串分割成小段，这些小段有可能是最长的
//但是由于被分割了，还是要检查这一小段，如果某些字母出现的次数小于k,会将小段继续分割下去,
//比如字符串"aacbbbdc"，要求最少出现2次,我们记录左右闭区间，，
//第一轮[0,7]，处理"aacbbbdc"，d只出现了一次不满足，于是递归解决区间[0,5]、[7,7]
//第二轮[0,5]，处理"aacbbb"，  c只出现了一次不满足，于是递归解决区间[0,1]、[3,4] 
//第二轮[7,7]，处理"c"，       c只出现了一次不满足，不继续递归
//第三轮[0,1]，处理"aa"，      满足出现次数>=2,ret=2
//第三轮[3,4]，处理"bbb"，     满足出现次数>=2 ret=3;

454. 四数相加 II

这题刚开始碰到是不会做的，感觉思想还是挺有意思的，记录下！

看下示例：

1
2
3
4
5
6
7
8
9
10
11
12
示例1：
输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0


示例2：
输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1

看下数据的范围：

  • n == nums1.length
  • n == nums2.length
  • n == nums3.length
  • n == nums4.length
  • 1 <= n <= 200
  • -228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228

n = 200，所以暴力肯定超时，最好想个 O(n*n) 的方法~

如果是两数相加要怎么做？两数相加很简单的：

target = a + b，只要在 map 中记录 a，然后查到 b 的时候，查以下 map 里面有没有 a 就行了。

其实四数相加完全可以转化成两数相加：

target = (a + b) + (c + d) ，那么我们先计算前两个数组之和，如示例1，a + b两两组合就会产生 4 个值 L1= [-1, 0, 0, 1]; c + d 两两组合就会产生 4 个值 L2 = [-1, 1, 2, 4];

接下来其实就是两数相加的内容了，

1
2
3
for x1 in L1, x2 in L2:
	if x1 + x2 == target
		ret++

这里还可以通过 map 进行优化，最终得到的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int, int> mp1, mp2;
        for (int i1 : nums1) {
            for (int i2 : nums2)
                mp1[i1+i2]++;
        }
        for (int i1 : nums3) {
            for (int i2 : nums4)
                mp2[i1+i2]++;
        }
        int ret = 0;
        for (auto it1 = mp1.begin(); it1 != mp1.end(); ++it1) {
            int target = 0 - it1->first;
            int times = it1->second;
            if (auto it2 = mp2.find(target); it2 != mp2.end()) {
                ret += it2->second * times;
            }
        }
        return ret;
    }
};

1109. 航班预定系统

这道题就是考察一个知识点，那就是：**差分数组**

其实一开始，我只是绝对对同一个区间进行相同的操作，没必要再遍历，但是就是找不出用什么别的方法，原来可以用差分。。。。。

差分数组的应用场景：对区间内 [l, r] 内的元素做同一类型的操作，那么就可以用差分数组。

由于差分数组是通过后一个减前一个的方式得到的即 d[i] = a[i] - a[i - 1]，i > 0。因此如果在区间 [l, r] 中进行 +val 操作，就会导致：

  • a[l] - a[l - 1] = d[l] + val
  • a[r + 1] - a[r] = d[r + 1] - val

因此只要改变差分数组中的两个元素就可以了，一个是 d[l]，一个是 d[r + 1]

接下来看下题目：

这里有 n 个航班，它们分别从 1 到 n 进行编号。

有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。

请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。

示例 1：

1
2
3
4
5
6
7
8
9
输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出：[10,55,45,25,25]
解释：
航班编号        1   2   3   4   5
预订记录 1 ：   10  10
预订记录 2 ：       20  20
预订记录 3 ：       25  25  25  25
总座位数：      10  55  45  25  25
因此，answer = [10,55,45,25,25]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> d(n + 1, 0);
        for (auto e : bookings) {
            int first = e[0];
            int last = e[1] + 1;
            int seats = e[2];
            d[first] += seats;
            if (last >= n + 1)   continue;
            d[last] -= seats;
        }
        for (int i = 2;i < n + 1;++i)
            d[i] = d[i] + d[i - 1];
        return {d.data() + 1, d.data()+d.size()};
    }
};

1004. 最大连续1的个数 III

给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。

示例 1：

1
2
3
4
输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。

示例 2：

1
2
3
4
输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出：10
解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。

这题用前缀和，v[i] 表示前面有几个 0。

但是这里的索引以及边界问题的使用很让人不解。。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> v(n + 1);
        for (int i = 1; i < n + 1; ++i) {
            v[i] = v[i - 1] + 1 - nums[i - 1];
        }
        int ret = 0;
        for (int i = 0; i < n; ++i) { // 这里为什么要从 0 开始遍历
            int left = lower_bound(v.begin(), v.end(), v[i + 1] - k) - v.begin();
            ret = max(ret, i - left + 1); // 为什么是 i - left + 1 而不是 i - left
        }
        return ret;
    }
};

5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

1
2
3
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

1
2
输入：s = "cbbd"
输出："bb"

提示：

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母组成

方法：中间扩散法！

首先确定回文串，就是找中心然后想两边扩散看是不是对称的就可以了。

在遍历中心点的时候，要注意中心点有两种情况。

一个元素可以作为中心点，两个元素也可以作为中心点。

所以我们在计算的时候，要注意一个元素为中心点和两个元素为中心点的情况。

这两种情况可以放在一起计算，但分别计算思路更清晰，我倾向于分别计算，代码如下：

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
class Solution {
public:
    string longestPalindrome(string s) {
        int l, r;
        int n = s.size();
        string ret;
        for (int i = 0;i < n; ++i) {
            l = r = i;
            while (l >=0 && r < n) {
                if (s[l] != s[r]) break;
                if (r - l + 1 > ret.size())
                    ret = s.substr(l, r - l + 1);
                --l;
                ++r;
            }
        }

        for (int i = 0;i < n; ++i) {
            l = r = i; r++;
            while (l >=0 && r < n) {
                if (s[l] != s[r]) break;
                if (r - l + 1 > ret.size())
                    ret = s.substr(l, r - l + 1);
                --l;
                ++r;
            }
        }
        return ret;
    }
};

215. 数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

1
2
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:

1
2
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

提示：

  • 1 <= k <= nums.length <= 104
  • -104 <= nums[i] <= 104

这一题实际上就是考察快排会不会，以及对快排进行优化，即随机取一个数作为比较数，而不是呆呆得永远取第一个数，

代码如下：

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
class Solution {
public:
    int findK(vector<int>& nums, int l, int r, int k) {
        int t_l = l, t_r = r;
        if (r > l) { // 引入随机性，防止退化到 O(n*n)
            int idx = rand()%(r - l) + l; // 注意 r - l = 0 时会发生计算错误
            swap(nums[l], nums[idx]);
        }
        int cmp_num = nums[l];
        while (l < r) {
            while (r > l && nums[r] <= cmp_num) --r;
            swap(nums[l], nums[r]);
            while (l < r && nums[l] >= cmp_num) ++l;
            swap(nums[l], nums[r]);
        }

        if (l + 1 == k) return nums[l];
        return l + 1 < k ? findK(nums, l + 1, t_r, k) :
            findK(nums, t_l, r - 1, k);
    }
    int findKthLargest(vector<int>& nums, int k) {
        // 用快排的思想
        return findK(nums, 0, nums.size() - 1, k);
    }
};

295. 数据流的中位数

中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

  • void addNum(int num) - 从数据流中添加一个整数到数据结构中。
  • double findMedian() - 返回目前所有元素的中位数。

示例：

1
2
3
4
5
addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3)
findMedian() -> 2

进阶:

  1. 如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？
  2. 如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？

方法：

中位数，只要记住用

  1. 大顶堆 + 小顶堆
  2. 大顶堆 < 小顶堆

因此就相当于把整个有序列表划分成两部分，前面的部分在大顶堆，后面部分在小顶堆，只要保持 |大顶堆.size() - 小顶堆.size()| <= 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
class MedianFinder {
private:
    priority_queue<int, vector<int>, greater<int>> min_pq;
    priority_queue<int, vector<int>, less<int>> max_pq;
public:
    MedianFinder()
        : min_pq()
        , max_pq()
    {}

    void addNum(int num) {
        if (min_pq.empty() || min_pq.top() <= num) {
            min_pq.push(num);
        } else max_pq.push(num);

        if (min_pq.size() > max_pq.size() + 1) {
            max_pq.push(min_pq.top());
            min_pq.pop();
        } else if(1 + min_pq.size() < max_pq.size()) {
            min_pq.push(max_pq.top());
            max_pq.pop();
        }
    }

    double findMedian() {
        double ret;
        if (min_pq.size() == max_pq.size()) {
            ret = (min_pq.top() + max_pq.top()) * 1.0 /2;
        } else if(min_pq.size() > max_pq.size()) {
            ret = min_pq.top() * 1.0;
        } else ret = max_pq.top() * 1.0;
        return ret;
    }
};

动态规划之子序列问题

  1. 300.最长递增子序列
  2. 674.最长连续递增序列
  3. 718.最长重复子数组
  4. 1143.最长公共子序列
  5. 1035.不相交的线
  6. 53.最大子序和
  7. 392.判断子序列
  8. 115.不同的子序列
  9. 583.两个字符串的删除操作
  10. 72.编辑距离
  11. 为了绝杀编辑距离，我做了三步铺垫，你都知道么？
  12. 647.回文子串
  13. 516.最长回文子序列
  14. 动态规划总结篇

300.最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

1
2
3
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

1
2
输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

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

提示：

  • 1 <= nums.length <= 2500
  • -104 <= nums[i] <= 104

注意项：

  • 注意这里说的是子序列而不是子串

  • 只需要返回长度，不需要具体的子序列

  • 严格递增

用 dp[n] 表示 n 个元素的数组中，以 nums[n - 1] 元素结尾的最长严格递增子序列的长度 为 dp[n]，那么

dp[n + 1] = max(dp[i] + 1)，其中必须满足 nums[i] < nums[n + 1]，i = 0~n

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp(nums.size(), 1);
        int ret = 1;
        for (int i = 1;i < nums.size(); ++i) {
            for (int j = 0;j < i;++j) {
                if (nums[j] < nums[i])
                    dp[i] = max(dp[i], dp[j] + 1);
            }
            ret = max(ret, dp[i]);
        }
        return ret;
    }
};

718.最长重复子数组

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

示例 1：

1
2
3
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。

示例 2：

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

提示：

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 100

这一题明显和前面的那种有较大的差别了，因为它涉及两个数组，而前面的都是在一个数组里面折腾的。

这种两个数组的优先考虑二维 DP。再结合 一维时候的思想：dp[i] 表示 第 i 个元素结尾的最长xxx子串。

最后可以想到：用 dp[i][j] 表示以 nums1[i] 和 nums2[j] 结尾的最长公共子串的长度，那么

  • 如果 nums1[i] == nums2[j]，dp[i][j] = dp[i - 1][j - 1] + 1
  • 如果 nums1[i] != nums2[j]，dp[i][j] = 0

只要找到最大的那个 dp[i][j] 就可以了

这里还需要一个小技巧，由于依赖于 i - 1 和 j - 1 因此，遍历的 i，j 要从 1 开始。那么我们就多加一行一列，下标 1 实际上对应于数组中的下标 0，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int n1 = nums1.size();
        int n2 = nums2.size();
        int ret;
        vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1, 0));
        ret = dp[0][0];
        for (int i = 1;i < n1 + 1;++i) {
            for (int j = 1;j < n2 + 1;++j) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    ret = max(ret, dp[i][j]);
                } else dp[i][j] = 0;
            }
        }
        return ret;
    }
};

1143.最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

1
2
3
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace" ，它的长度为 3 。

示例 2：

1
2
3
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。

示例 3：

1
2
3
输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。

提示：

  • 1 <= text1.length, text2.length <= 1000
  • text1 和 text2 仅由小写英文字符组成。

这里也是出现了两个字符串，毫无疑问，继续二维 DP，与上一题不同的是，这里要求的是子序列而非子串，子序列可以是不连续的。

用 dp[i][j] 表示以 text1[i]、text2[j] 结尾的字符串的最长公共子序列长度，那么会遇到两种情况：

  1. text1[i] == text2[j]，此时 dp[i][j] = dp[i - 1][j - 1] + 1;
  2. text1[i] != text2[j]，此时取两组字符串中公共子序列最长的值，其一为 (text1[i - 1], text2[j])，其二为 (text1[i], text2[j - 1])，因此 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        // dp[i][j] 表示字符串 text1[i]、text2[j] 的最长公共子序列长度
        // 如果 text1[i] == text2[j], dp[i][j] = dp[i - 1][j - 1] + 1
        // 如果 text1[i] != text2[j], dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        int n1 = text1.size(), n2 = text2.size();
        vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1));
        for (int i = 1;i < n1 + 1; ++i) {
            for (int j = 1;j < n2 + 1; ++j) {
                if (text1[i - 1] == text2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[n1][n2];
    }
};

给出表格更好理解：

a b c d e

a 1 1 1 1 1

c 1 1 2 2 2

e 1 1 2 2 3

1035. 不相交的线

这一题其实就是最长公共子序列的长度，也就是和 1143 这一题一样，无非是两个字符串变成了两个数组。

53.最大子串和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：

1
2
3
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

提示：

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

这题很简单啊，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // dp[i] 表示以 nums[i] 结尾的数组子串的最大和
        // 那么 dp[i] = max(nums[i], nums[i] + dp[i - 1]);
        int ret = nums[0];
        vector<int> dp(nums.size());
        dp[0] = nums[0];
        for (int i = 1;i < nums.size();++i) {
            dp[i] = max(nums[i], nums[i] + dp[i - 1]);
            ret = max(ret, dp[i]);
        }
        return ret;
    }
};

392.判断子序列

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

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

示例 1：

1
2
输入：s = "abc", t = "ahbgdc"
输出：true

提示：

  • 0 <= s.length <= 100
  • 0 <= t.length <= 10^4
  • 两个字符串都只由小写字符组成。

这一题也是 相当于判断 s 和 t 的最长公共子序列的长度是否等于 t 的长度，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int func(const string& s, const string& t) {
        int n1 = s.size(), n2 = t.size();
        vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1));
        for (int i = 1; i < n1 + 1; ++i) {
            for (int j = 1; j < n2 + 1; ++j) {
                dp[i][j] = s[i - 1] == t[j - 1] ?
                    dp[i - 1][j - 1] + 1 : dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[n1][n2];
    }
    bool isSubsequence(string s, string t) {
        // 相当于是判断 s 和 t 的最长公共子序列的长度是否等于 t 的长度
        return func(s, t) == s.size();
    }
};

115.不同的子序列

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，”ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是）

题目数据保证答案符合 32 位带符号整数范围。

示例 1：

1
2
输入：s = "rabbbit", t = "rabbit"
输出：3

示例 2：

1
2
输入：s = "babgbag", t = "bag"
输出：5

这一题属实有难度了，做了好久，主要是状态方程找不出来。思路其实还是挺类似的，这种两个字符串的，大概率就是二维 DP 了，并且一般来说 dp[i][j] 就表示以 s[i]、t[j] 结尾的字符串xxxxxx。然后比较 s[i] == t[j] 和 s[i] != t[j] 两种情况就可以了。

但是关键在于，状态方程该怎么写？最终状态方程是这样的：

  • 如果 s[i] == t[j]，dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]
  • 如果 s[i] != t[j]，dp[i][j] = dp[i - 1][j]

解释如下：

先看s[i] == t[j] 时，以s = “rara” t = “ra” 为例，当i = 3, j = 1时，s[i] == t[j]。

此时分为2种情况，s串用最后一位的a + 不用最后一位的a。

如果用s串最后一位的a,那么t串最后一位的a也被消耗掉，此时的子序列其实=dp[i-1][j-1]

如果不用s串最后一位的a，那就得看”rar”里面是否有”ra”子序列的了，就是dp[i-1][j]

所以 dp[i][\j] = dp[i-1][j-1] + dp[i-1][j]

再看s[i] != t[j] 比如 s = “rarb” t = “ra” 还是当i = 3, j = 1时，s[i] != t[j]

此时显然最后的b想用也用不上啊。所以只能指望前面的”rar”里面是否有能匹配”ra”的

所以此时dp[i][j] = dp[i-1][j]

代码如下：

1

583.两个字符串的删除操作

给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。

每步 可以删除任意一个字符串中的一个字符。

示例 1：

1
2
3
输入: word1 = "sea", word2 = "eat"
输出: 2
解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"

示例 2:

1
2
输入：word1 = "leetcode", word2 = "etco"
输出：4

这一题就是 最长公共子序列的长度 的变形

设 n1 = word1.size(), n2 = word2.size(), n = 最长公共子序列的长度，所以 ret = n1 - n + n2 - n

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int minDistance(string word1, string word2) {
        int n1 = word1.size(), n2 = word2.size();
        vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1));
        for (int i = 1; i < n1 + 1; ++i) {
            for (int j = 1; j < n2 + 1; ++j) {
                if (word1[i - 1] == word2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return n1 + n2 - 2*dp[n1][n2];
    }
};

72.编辑距离

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

示例 1：

1
2
3
4
5
6
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2：

1
2
3
4
5
6
7
8
输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

提示：

  • 0 <= word1.length, word2.length <= 500
  • word1 和 word2 由小写英文字母组成

这道题太难了，看了题解也模模糊糊的，见 为了绝杀编辑距离，我做了三步铺垫，你都知道么？

代码如下：

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
class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.length();
        int n = word2.length();

        vector<vector<int>> cost(m+1, vector<int>(n+1));

        for (int i = 0; i <= m; ++i) {
            cost[i][0] = i;
        }
        for (int j = 0; j <= n; ++j) {
            cost[0][j] = j;
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (word1[i-1] == word2[j-1]) {
                    cost[i][j] = cost[i-1][j-1];
                } else {
                    cost[i][j] = 1 + min(cost[i-1][j-1], min(cost[i][j-1], cost[i-1][j]));
                }
            }
        }
        return cost[m][n];
    }
};

647.回文子串

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

1
2
3
输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

这一题可以用中心拓展发做，也可以用动态规划做。

动态规划：

用 dp[i][j] 表示由字符 s[i]s[i + 1]…s[j - 1]s[j] 构成的子串是否为 回文串

  • 如果 s[i] == s[j], dp[i][j] = dp[i + 1][j - 1]

  • 如果 s[i] != s[j], dp[i][j] = false

这一题的矩阵 dp 是按对角线的方向进行赋值计算的，这种遍历方式在动态规划题目中比较常见，需要掌握：

把 i 表示当前需要遍历哪一条对角线，i = 1 表示当前需要遍历第 i 条对角线，总共遍历 n - 1 条对角线，因为 i = 0 这条对角线已经初始化过了。j 表示当前在第 j 行，总共遍历 n - i 行。因此 dp[i][j] 中的 i 对应代码中的 j，dp[i][j] 中的 j 对应代码中的 j + i

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int countSubstrings(string s) {
        // 用 dp[i][j] 表示由字符 s[i]s[i + 1]...s[j - 1]s[j] 构成的子串是否为 回文串
        // 如果 s[i] == s[j], dp[i][j] = dp[i + 1][j - 1]
        // 如果 s[i] != s[j], dp[i][j] = false
        int n = s.size();
        int ret = s.size();
        vector<vector<int>> dp(n, vector<int>(n, 1));
        for (int i = 1; i < n; ++i) {
            for(int j = 0; j < n - i; ++j) {
                if (s[j] == s[j + i])
                    dp[j][j + i] = dp[j + 1][j + i - 1];
                else
                    dp[j][j + i] = 0;
                ret += dp[j][j + i];
            }
        }
        return ret;
    }
};

中心拓展法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    int num = 0;
    public int countSubstrings(String s) {
        for (int i=0; i < s.length(); i++){
            count(s, i, i);//回文串长度为奇数
            count(s, i, i+1);//回文串长度为偶数
        }
        return num;
    }

    public void count(String s, int start, int end){
        while(start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)){
            num++;
            start--;
            end++;
        }
    }
}

516.最长回文子序列

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：

1
2
3
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。

示例 2：

1
2
3
输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。

提示：

  • 1 <= s.length <= 1000
  • s 仅由小写英文字母组成

这一题让我有点无从下手了，因为如果单单是一维数组，dp[i] 表示 xxx的最长回文子序列的长度，那么 s[i] 的加入对判断 能否使 回文子序列长度变长 没有帮助，因为你都不知道这个前面的回文子序列具体是什么；

因此考虑用二维 DP 试试。用 dp[i][j] 表示以 s[i] ~ s[j] 表示的子串的 最长回文子序列的长度，因此

  • 如果 s[i] == s[j]，那么 dp[i][j] = dp[i + 1][j - 1] + 2
  • 如果 s[i] != s[j]，那么 dp[i][j] = max( dp[i + 1][j], dp[i][j - 1] )，注意 s[i + 1] ~s[j - 1] 构成的子串是 max 中的任意一个字符串的子串

这一题填二维数组的方向也和之前的不太一样，因为 dp[i][j] 依赖于 dp[i + 1][j - 1] ，也就是它斜下方的那个元素，因此是 45° 斜着填二维数组。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n));
        for (int i = 0;i < n; ++i)
            dp[i][i] = 1;
        for (int i = 1;i < n; ++i) {
            for (int j = 0;j < n - i; ++j) {
                if (s[j] == s[j + i]) {
                    // 斜着填二维数组，本质是差分从 0 ~ n-1，起始点 j 从 0 ~ n - i - 1
                    // 例如 n = 5 差分为 1, 起始点从 1 ~ 3: (0, 1),(1, 2),(2, 3),(3, 4)
                    dp[j][j + i] = dp[j + 1][j + i - 1] + 2;
                } else {
                    dp[j][j + i] = max(dp[j + 1][j + i], dp[j][j + i - 1]);
                }
            }
        }
        return dp[0][n - 1];
    }
};

128. 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

1
2
3
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

1
2
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

172. 阶乘后的零

给定一个整数 n ，返回 n! 结果中尾随零的数量。

提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1

示例 1：

1
2
3
输入：n = 3
输出：0
解释：3! = 6 ，不含尾随 0

示例 2：

1
2
输入：n = 0
输出：0

提示：

  • 0 <= n <= 10000

n! 尾零的数量即为 n! 中因子 10 的个数，而 10=2×5，因此转换成求 n! 中质因子 2 的个数和质因子 5 的个数的较小值。

由于质因子 5 的个数不会大于质因子 2 的个数（具体证明见方法二），我们可以仅考虑质因子 5 的个数。

而 n! 中质因子 5 的个数等于 [1,n] 的每个数的质因子 5 的个数之和，我们可以通过遍历 [1,n] 的所有 5 的倍数求出。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int trailingZeroes(int n) {
        int ans = 0;
        for (int i = 5; i <= n; i += 5) {
            for (int x = i; x % 5 == 0; x /= 5)
                ++ans;
        }
        return ans;
    }
};