Leetcode Algorithm Notes

Chapter1 Sliding Window

424. 替换后的最长重复字符「Medium」

给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。

注意：字符串长度 和 k 不会超过 $10^4$。

示例 1：

1
2
3
输入：s = "ABAB", k = 2
输出：4
解释：用两个'A'替换为两个'B',反之亦然。

示例 2：

1
2
3
4
5
输入：s = "AABABBA", k = 1
输出：4
解释：
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。

算法分析：

​ 我们可以枚举字符串中的每一个位置作为右端点，然后找到其最远的左端点的位置，满足该区间内除了出现次数最多的那一类字符之外，剩余的字符（即非最长重复字符）数量不超过 $k$ 个。

​ 这样我们可以想到使用双指针维护这些区间，每次右指针右移，如果区间仍然满足条件，那么左指针不移动，否则左指针至多右移一格，保证区间长度不减小。

​ 虽然这样的操作会导致部分区间不符合条件，即该区间内非最长重复字符超过了 $k$ 个。但是这样的区间也同样不可能对答案产生贡献。当我们右指针移动到尽头，左右指针对应的区间的长度必然对应一个长度最大的符合条件的区间。

​ 实际代码中，由于字符串中仅包含大写字母，我们可以使用一个长度为 $26$ 的数组维护每一个字符的出现次数。每次区间右移，我们更新右移位置的字符出现的次数，然后尝试用它更新重复字符出现次数的历史最大值，最后我们使用该最大值计算出区间内非最长重复字符的数量，以此判断左指针是否需要右移即可。

变式「Medium 简单版」：1004. 最大连续1的个数 III

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int characterReplacement(string s, int k) {
        vector<int> num(26);
        int n = s.length();
        int maxn = 0;
        int left = 0, right = 0;
        while (right < n) {
            num[s[right] - 'A']++;
            maxn = max(maxn, num[s[right] - 'A']);
            if (right - left + 1 - maxn > k) {
                num[s[left] - 'A']--;
                left++;
            }
            right++;
        }
        return right - left;
    }
};

1423. 可获得的最大点数「Medium」

几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。

每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。

你的点数就是你拿到手中的所有卡牌的点数之和。

给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。

示例 1：

1
2
3
输入：cardPoints = [1,2,3,4,5,6,1], k = 3
输出：12
解释：第一次行动，不管拿哪张牌，你的点数总是 1 。但是，先拿最右边的卡牌将会最大化你的可获得点数。最优策略是拿右边的三张牌，最终点数为 1 + 6 + 5 = 12 。

示例 2：

1
2
3
输入：cardPoints = [2,2,2], k = 2
输出：4
解释：无论你拿起哪两张卡牌，可获得的点数总是 4 。

示例 3：

1
2
3
输入：cardPoints = [9,7,7,9,7,7,9], k = 7
输出：55
解释：你必须拿起所有卡牌，可以获得的点数为所有卡牌的点数之和。

示例 4：

1
2
3
输入：cardPoints = [1,1000,1], k = 1
输出：1
解释：你无法拿到中间那张卡牌，所以可以获得的最大点数为 1 。

算法分析：

我们考虑到每次拿牌都是从首尾拿一张，总共拿 k 张，与其去想拿首或者尾的一张，那么不妨逆向思维一下，拿走 k 张之后还剩下 n - k 张，我们只需要保证剩下的 n - 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
func maxScore(cardPoints []int, k int) int {
    n := len(cardPoints)
    sum := 0
    windowSize := n - k
    for _, val := range cardPoints[:windowSize] {
        sum += val
    }
    minSum := sum
    for i := windowSize; i < n; i++ {
        sum += cardPoints[i] - cardPoints[i - windowSize]
        minSum = min(minSum, sum)
    }
    total := 0
    for _, v := range cardPoints {
        total += v
    }
    return total - minSum
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

42. 接雨水「Hard」

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

picture

1
2
3
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

算法分析：

  1. 我们维护两个指针分别指向首尾两端 $\Rightarrow$ $left=0,~right=n-1$ 以及两个变量维护左边和右边的最大高度 $\Rightarrow$ $left_most$ 和 $right_most$.
  2. 此时我们依次遍历，可以分两种情况讨论：
    • 当 $left_most<right_most$ 时，当前位置能存储的水的最大高度取决于 $left_most$，无论中间的柱子情况如何，我们此时一定可以存储 $left_most-nums[i]$ 高度的水，直至在左边遇到高度大于 $left_most$ 的柱子，然后更新 $left_most$ 的值。
    • 当 $left_most>=right_most$ 时，当前位置能存储的水的最大高度取决于 $right_most$，无论中间的柱子情况如何，我们此时一定可以存储 $right_most-nums[i]$ 高度的水，直至在右边遇到高度大于 $right_most$ 的柱子，然后更新 $right_most$ 的值。
  3. 运行至 $left=right$ 结束。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int trap(vector<int>& height) {
        int left = 0, right = height.size() - 1;
        int left_most = 0, right_most = 0;
        int count = 0;
        while (left < right) {
            if (height[left] < height[right]) {
                height[left] >= left_most ? left_most = height[left] : count += left_most - height[left];
                ++left;
            } else {
                height[right] >= right_most ? right_most = height[right] : count += right_most - height[right];
                --right;
            }
        }
        return count;
    }
};

76. 最小覆盖子串「Hard」

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

1
2
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

算法分析：

本问题要求我们返回字符串 s 中包含字符串 t 的全部字符的最小窗口。我们称包含 t 的全部字母的窗口为「可行」窗口。

我们考虑使用滑动窗口来解决此问题，维护两个指针 $left$ 和 $right$，其中 $right$ 用来「延展」窗口，$left$ 用来 「收缩」窗口。

我们的遍历在字符串 s 中进行，会出现以下几种情况：

  • 首先，不断右移 $right$ 指针，直至目前的子串完全包含 t 中的所有字符.
  • 其次，我们开始收缩 $left$ 指针，直至 $[left,~right]$ 区间内不完全包含 t 中所有字符，其中我们使用变量 begin 保存答案字符串的开头位置，len 表示符合条件字符串的长度.
  • 当 $right$ 指针遍历至 s 的末尾，遍历结束.

Details：

我们使用两个哈希表 SFreq 和 TFreq 来存储各个出现字符的次数，check() 函数用于判断这两个哈希表之间是否具有包含关系.

算法缺陷：

每次左指针 $left$ 移动我们都需要判断两个哈希表之间的差异，造成了时间上的浪费，因此我们可以做一些优化.

优化算法：

我们使用一个变量 distant 来维护目前滑动窗口中出现了与 t 字符串中的匹配数目，当 distant = tlen 的时候，我们此时就可以移动 $left$ 指针了，移动的过程中更新答案字符串的开头和长度，直至 $[left,~right]$ 区间内不完全包含 t 中所有字符.

Details：

要清楚答案字符串的长度是 $right - left+1$ 还是 $right-left$，这个长度取决于 $right$ 的自加过程是在「收缩」阶段的前面或者后面，具体细节自己体会.

567. 字符串的排列 是本题的简单版，可以作为练习加深印象.

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
class Solution {
private:
    unordered_map<char, int> SFreq, TFreq;
public:
    bool check() {
        for (const auto &p: TFreq) {
            if (SFreq[p.first] < p.second) {
                return false;
            }
        }
        return true;
    }

    string minWindow(string s, string t) {
        for (auto& c : t) {
            ++TFreq[c];
        }
        int begin = -1, slen = (int)s.size();
        int len = INT_MAX;
        int left = 0, right = -1;
        while (right < slen) {
           if (TFreq.count(s[++right])) {
                ++SFreq[s[right]];
            }

            while (check() and left <= right) {
                if (right - left + 1 < len) {
                    len = right - left + 1;
                    begin = left;
                }
               if (TFreq.count(s[left])) {
                    --SFreq[s[left]];
                }
                ++left;
            }
        }
        return begin *** -1 ? string() : s.substr(begin, len);
    }
};

优化代码：

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
class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> SFreq, TFreq;
        int slen = (int)s.size(), tlen = (int)t.size();
        if (slen *** 0 || tlen *** 0 || slen < tlen) {
            return "";
        }
        
        for (const auto& c : t) {
            ++TFreq[c];
        }
        
        int distant = 0;
        int len = slen + 1;
        int left = 0, right = 0;
        int begin = 0;
        
        // [left, right)
        while (right < slen) {
            if (TFreq[s[right]] *** 0) {
                ++right;
                continue;
            }
            
            if (SFreq[s[right]] < TFreq[s[right]]) {
                distant++;
            }
            
            SFreq[s[right]]++;
            right++;
            
            while (distant *** tlen) {
                if (right - left < len) {
                    len = right - left;
                    begin = left;
                }
                
                if (TFreq[s[left]] *** 0) {
                    ++left;
                    continue;
                }
                
                if (SFreq[s[left]] *** TFreq[s[left]]) {
                    distant--;
                }
                
                SFreq[s[left]]--;
                left++;
            }
        }
        
        return len *** slen + 1 ? "" : s.substr(begin, len);
    }
};

992. K 个不同整数的子数组「Hard」

给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定独立的子数组为好子数组。

( 例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。)

返回 A 中好子数组的数目。

示例 1：

1
2
3
输入：A = [1,2,1,2,3], K = 2
输出：7
解释：恰好由 2 个不同整数组成的子数组：[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].

示例 2：

1
2
3
输入：A = [1,2,1,3,4], K = 3
输出：3
解释：恰好由 3 个不同整数组成的子数组：[1,2,1,3], [2,1,3], [1,3,4].

提示：

  • 1 <= A.length <= 20000
  • 1 <= A[i] <= A.length
  • 1 <= K <= A.length

算法分析：

滑动窗口的思维定势：

我们一般考虑滑动窗口的时候都是每轮循环使 $right$ 向右移动一位，然后固定 $right$，然后「收缩」$left$，但是考虑本题，$right$ 指针其实并不固定：

对于一个固定的左边界来说，满足「恰好存在 K 个不同整数的子区间」的右边界 不唯一，且形成区间。

示例：左边界固定的时候，恰好存在 $2$ 个不同整数的子区间为 [1, 2], [1, 2, 1], [1, 2, 1, 2]，总数为 $3$。

picture

但是本题是「恰好存在 K 个不同整数的子区间」，所以我们需要找到左边界固定的情况下，满足「恰好存在 K 个不同整数的子区间」最小右边界和最大右边界。

对比以前我们做过的，使用「滑动窗口」解决的问题的问法基本都会出现「最小」、「最大」这样的字眼。那么这题如何解决呢？对此，我们可以进行一定的转换：

把「恰好」改成「最多」就可以使用双指针一前一后交替向右的方法完成，这是因为 对于每一个确定的左边界，最多包含 $K$ 种不同整数的右边界是唯一确定的，并且在左边界向右移动的过程中，右边界或者在原来的地方，或者在原来地方的右边。

而「最多存在 $K$ 个不同整数的子区间的个数」与「恰好存在 K 个不同整数的子区间的个数」的差恰好等于「最多存在 $K-1$ 个不同整数的子区间的个数」。

picture

因此原问题就可以转换为求解「最多存在 $K$ 个不同整数的子区间的个数」和 「最多存在 $K-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
// 主求解函数
func subarraysWithKDistinct(A []int, K int) int {
    return atMostKDistinct(A, K) - atMostKDistinct(A, K - 1)
}

func atMostKDistinct(A []int, K int) int {
    n := len(A)
    // count 代表 [left, right) 里不同整数的个数
    res, count, left, right := 0, 0, 0, 0
    freq := make([]int, n + 1)
    
    // [left, right) 包含不同整数的个数小于等于 K
    for right < n {
        if freq[A[right]] *** 0 {
            count++
        }
        
        freq[A[right]]++
        right++
        
        for count > K {
            freq[A[left]]--
            if freq[A[left]] *** 0 {
                count--
            }
            left++
        }
        
        // [left, right) 区间的长度就是对结果的贡献
        res += right - left
    }
    
    return res
}

995. K 连续位的最小翻转次数「Hard」

在仅包含 0 和 1 的数组 A 中，一次 K 位翻转包括选择一个长度为 K 的（连续）子数组，同时将子数组中的每个 0 更改为 1，而每个 1 更改为 0。

返回所需的 K 位翻转的最小次数，以便数组没有值为 0 的元素。如果不可能，返回 -1。

示例 1：

1
2
3
输入：A = [0,1,0], K = 1
输出：2
解释：先翻转 A[0]，然后翻转 A[2]。

示例 2：

1
2
3
4
5
6
输入：A = [0,0,0,1,0,1,1,0], K = 3
输出：3
解释：
翻转 A[0],A[1],A[2]: A变成 [1,1,1,1,0,1,1,0]
翻转 A[4],A[5],A[6]: A变成 [1,1,1,1,1,0,0,0]
翻转 A[5],A[6],A[7]: A变成 [1,1,1,1,1,1,1,1]

提示：

  1. 1 <= A.length <= 30000
  2. 1 <= K <= A.length

算法分析：

方法一：差分数组

由于对同一个子数组执行两次翻转操作不会改变该子数组，所以对每个长度为 $K$ 的子数组，应至多执行一次翻转操作。

对于若干个 $K$ 位翻转操作，改变先后顺序并不影响最终翻转的结果。不妨从 $A[0]$ 开始考虑，若 $A[0]=0$，则必定要翻转从位置 $0$ 开始的子数组；若 $A[0]=1$，则不翻转从位置 $0$ 开始的子数组。

按照这一策略，我们从左到右地执行这些翻转操作。由于翻转操作是唯一的，若最终数组元素均为 $1$，则执行的翻转次数就是最小的。

若直接模拟上述过程，复杂度将会是 $O(NK)$ 的。考虑优化问题：

考虑不去翻转数字，而是统计每个数字需要翻转的次数。对于一次翻转操作，相当于把子数组中所有数字的翻转次数加 $1$.

这启发我们用差分数组的思想来计算当前数字需要翻转的次数。我们可以维护一个差分数组 $diff$，其中 $diff[i]$ 表示两个相邻元素 $A[i-1]$ 和 $A[i]$ 的翻转次数的差，对于区间 $[l,r]$，将其元素全部加 $1$，只会影响到 $l$ 和 $r+1$ 处的差分值，故 diff[l]++ && diff[r + 1]--.

通过累加差分数组可以得到当前位置需要翻转的次数，我们用变量 $revCnt$ 来表示这一累加值。

遍历到 $A[i]$ 时，若 $A[i]+revCnt$ 是偶数，则说明当前元素的实际值为 $0$，需要翻转区间 $[i,i+K-1]$ ，我们可以直接将 $revCnt$ 增加 $1$，$diff[i+K]$ 减少 $1$.

注意到若 $i+K>n$ 则无法执行翻转操作，此时应返回 $-1$.

方法二：滑动窗口

我们考虑能否将空间复杂度简化为 $O(1)$ ?

回顾方法一的代码，当遍历到位置 $i$ 时，若能知道位置 $i-K$ 上发生了翻转操作，便可以直接修改 $revCnt$ 从而去掉 $diff$ 数组。

注意到 $0≤A[i]≤1$，我们可以用 $A[i]$ 范围之外的数来表达「是否翻转过」的含义**。

具体来说，若要翻转从位置 $i$ 开始的子数组，可以将 $A[i]$ 加 $2$，这样当遍历到位置 $i’$ 时，若有 $A[i’-K]>1$，则说明在位置 $i’-K$ 上发生了翻转操作。

方法一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func minKBitFlips(A []int, K int) (ans int) {
    n := len(A)
    diff := make([]int, n + 1)
    revCnt := 0
    for i, v := range A {
        revCnt += diff[i]
        if (v + revCnt) % 2 *** 0 {
            if i + K > n {
                return -1
            }
            ans++
            revCnt++
            diff[i + K]--
        }
    }
    return
}

由于模 $2$ 意义下的加减法与异或等价，我们也可以用异或改写上面的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func minKBitFlips(A []int, K int) (ans int) {
    n := len(A)
    diff := make([]int, n + 1)
    revCnt := 0
    for i, v := range A {
        revCnt ^= diff[i]
        if v *** revCnt { // v ^ revCnt *** 0
            if i + K > n {
                return -1
            }
            ans++
            revCnt ^= 1
            diff[i + K] ^= 1
        }
    }
    return
}

方法二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func minKBitFlips(A []int, K int) (ans int) {
    n := len(A)
    revCnt := 0
    for i, v := range A {
        if i >= K && A[i - K] > 1 {
            revCnt ^= 1
            A[i - K] -= 2 // 复原数组元素，若允许修改数组 A，则可以省略
        }
        if v *** revCnt {
            if i + K > n {
                return -1
            }
            ans++
            revCnt ^= 1
            A[i] += 2
        }
    }
    return
}

220. 存在重复元素 III「Medium」

给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k.

如果存在则返回 true，不存在返回 false.

示例 1：

1
2
输入：nums = [1,2,3,1], k = 3, t = 0
输出：true

示例 2：

1
2
输入：nums = [1,0,1,1], k = 1, t = 2
输出：true

算法分析：

方法一：滑动窗口 & 有序集合

根据题意，对于任意一个位置 $i$ ( 假设其值为 $u$ )，我们其实是希望在下标范围为 $[max(0,~i-k),i]$ 内找到值范围在 $[u-t,u+t]$ 的数.

因此我们可以使用一个「有序集合」去维护长度为 $k$ 的滑动窗口内的数.

每次都在「有序集合」中应用「二分查找」，找到「小于等于 $u$ 的最大值」和「大于等于 $u$ 的最小值」，即「有序集合」中的最接近 $u$ 的数。然后判断两值是否落在 $[u-t,u+t]$ 范围内.

由于我们希望对「有序集合」应用「二分」，找到最接近 $u$ 的数，因此我们需要使用 $TreeSet$ 数据结构（基于红黑树，因此查找和插入都具有折半的效率），并且由于 $nums$ 中的数较大，会存在 $int$ 溢出问题，我们需要使用 $long$ 来存储.

  • 时间复杂度： $TreeSet$ 基于红黑树，查找和插入都是 $O(\log k)$ 复杂度。整体复杂度为 $O(n\log k)$.
  • 空间复杂度：$O(k)$.

方法二：桶排序

上述解法无法做到线性的原因是：我们需要在大小为 $k$ 的滑动窗口所在的「有序集合」中找到与 $u$ 接近的数.

如果我们能够将 $k$ 个数字分到 $k$ 个桶的话，那么我们就能 $O(1)$ 的复杂度确定是否有 $[u-t,u+t]$ 的数字 ( 检查目标桶是否有元素 ).

具体的做法为：令桶的大小为 $size = t+1$，根据 $u$ 计算所在桶编号：

  • 如果已经存在该桶，说明前面已有 $[u-t,u+t]$ 的数字，返回 $true$.
  • 如果不存在该桶，则检查相邻两个桶的元素是有 $[u-t,u+t]$ 的数字，如有返回 $true$.
  • 建立目标桶，并删除下标范围不在 $[max(0,~i-k),i]$ 内的桶

方法一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        set<long> st;
        for (int i = 0; i < nums.size(); ++i) {
            auto lb = st.lower_bound((long)nums[i] - t);
            if (lb != st.end() and *lb <= (long)nums[i] + t) {
                return true;
            }
            st.insert(nums[i]);
            if (i >= k) {
                st.erase(nums[i - k]);
            }
        }
        return false;
    }
};

方法二：

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:
    long size;
  
    bool containsNearbyAlmostDuplicate(vector <int> & nums, int k, int t) {
        int n = nums.size();
        map<long, long> m;
        size = t + 1L;
        for (int i = 0; i < n; i++) {
            long u = nums[i] * 1L;
            long idx = getIdx(u);
            // 目标桶已存在（桶不为空），说明前面已有 [u - t, u + t] 范围的数字
            if (m.find(idx) != m.end()) return true;
            // 检查相邻的桶
            long l = idx - 1, r = idx + 1;
            if (m.find(l) != m.end() && abs(u - m[l]) <= t) return true;
            if (m.find(r) != m.end() && abs(u - m[r]) <= t) return true;
            // 建立目标桶
            m.insert({idx, u});
            // 移除下标范围不在 [max(0, i - k), i) 内的桶
            if (i >= k) m.erase(getIdx(nums[i - k]));
        }
        return false;
    }
  
    long getIdx(long u) {
        return u >= 0 ? u / size : (u + 1) / size - 1;
    }
};

Chapter2 Dynamic Programming

5. 最长回文子串「Medium」

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void optimize(vector<vector<bool>>& dp, string& s) {
    int len = (int)s.length();
    for (int i = 0; i < len; i++) {
        dp[i][i] = true;
    }
    for (int j = 1; j < len; j++) {
        for (int i = 0; i < j; i++) {
            if (s[i] *** s[j]) {
                if (j - i < 3) dp[i][j] = true;
                else dp[i][j] = dp[i + 1][j - 1];
            } else dp[i][j] = false;
        }
    }
}

72. 编辑距离「Hard」

给你两个单词 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')

算法分析：

  1. 状态：dp[i][j] 表示 word1 的前 i 个字母和 word2 的前 j 个字母之间的编辑距离。

  2. 状态转移方程：

    • 当 word1[i - 1] *** word2[j - 1] 时，不需要转换，编辑距离为 dp[i] [j] = dp[i - 1] [j - 1].
    • 当 word1[i - 1] != word2[j - 1] 时，分三种情况讨论：
      • 插入一个字符，***dp[i] [j - 1]***：为 A 的前 i 个字符和 B 的前 j - 1 个字符编辑距离的子问题。即对于 B 的第 j 个字符，我们在 A 的末尾添加了一个相同的字符
      • 删除一个字符，***dp[i - 1] [j]***：为 A 的前 i - 1 个字符和 B 的前 j 个字符编辑距离的子问题。即对于 A 的第 i 个字符，我们在 B 的末尾添加了一个相同的字符
      • 替换一个字符，***dp[i - 1] [j - 1]***：为 A 前 i - 1 个字符和 B 的前 j - 1 个字符编辑距离的子问题。即对于 B 的第 j 个字符，我们修改 A 的第 i 个字符使它们相同
    • 对于这三种情况，我们去其中编辑距离的最小值再加一，即 dp[i][j] = min(dp[i - 1] [j - 1], dp[i - 1] [j], dp[i] [j - 1]) + 1.

  3. 边界条件：

    image-20210206201135253
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int minDistance(string word1, string word2) {
        // dp[i][j] 表示 word1 的前 i 个字母和 word2 的前 j 个字母之间的编辑距离。
        int len1 = (int)word1.length(), len2 = (int)word2.length();
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1));
        for (int i = 0; i < len1 + 1; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j < len2 + 1; j++) {
            dp[0][j] = j;
        }
        for (int i = 1; i < len1 + 1; i++) {
            for (int j = 1; j < len2 + 1; j++) {
                if (word1[i - 1] *** word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {    //dp[i-1][j-1] 表示替换操作，dp[i-1][j] 表示删除操作，dp[i][j-1] 表示插入操作
                    dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
                }
            }
        }
        return dp[len1][len2];
    }
};

338. 比特位计数「Medium」

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

示例 1:

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

示例 2:

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

算法分析：

  1. 状态：bit[i] 表示 i 的「比特数」
  2. 状态转移方程：对于正整数 $x$，如果可以知道最大的正整数 $y$ 使得 $y≤x$ 且 $y$ 是 $2$ 的整数次幂，则 $y$ 的二进制表示中只有最高位是 $1$，其余都是 $0$，此时称 $y$ 为 $x$ 的「最高有效位」。也就是说 bit[x] = bit[y - x] + 1
  3. 边界条件：判断「最高有效位」看上题，(i & (i - 1)) *** 0.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> bits(num + 1);
        int highBit = 0;
        for (int i = 1; i <= num; i++) {
            if ((i & (i - 1)) *** 0) {
                highBit = i;
            }
            bits[i] = bits[i - highBit] + 1;
        }
        return bits;
    }
};

132. 分割回文串 II「Hard」

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。

返回符合要求的 最少分割次数

示例 1：

1
2
3
输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

算法分析：

Step1：定义状态

设 $f[i]$ 表示字符串的前缀 $s[0…i]$ 的最少分割次数。

Step2：状态转移方程

要想得出 $f[i]$ 的值，我们可以考虑枚举 $s[0…i]$ 分割出的最后一个回文串，这样我们就可以写出状态转移方程：

$f[i]=min_{0≤j<i}(f[j])+1$，其中 $s[j+1,i]$ 是一个回文串.

即我们枚举最后一个回文串的起始位置 $j+1$，保证 $s[j+1,i]$ 是一个回文串，那么 $f[i]$ 就可以从 $f[j]$ 转移而来，附加 $1$ 次额外的分割次数。

Step3：边界情况

注意到上面的状态转移方程中，我们还少考虑了一种情况，即 $s[0…i]$ 本身就是一个回文串。此时其不需要进行任何分割，即：$f[i]=0$.

那么我们如何知道 $s[j+1,i]$ or $s[0…i]$ 是否为回文串呢？我们可以使用 $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
30
31
32
33
34
35
class Solution {
public:
    void optimize(vector<vector<bool>>& dp, string& s) {
        int len = (int)s.length();
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        for (int j = 1; j < len; j++) {
            for (int i = 0; i < j; i++) {
                if (s[i] *** s[j]) {
                    if (j - i < 3) dp[i][j] = true;
                    else dp[i][j] = dp[i + 1][j - 1];
                } else dp[i][j] = false;
            }
        }
    }
    
    int minCut(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n));
        optimize(dp, s);
        vector<int> f(n, n);
        for (int i = 0; i < n; ++i) {
            if (dp[0][i]) f[i] = 0;
            else {
                for (int j = 0; j < i; ++j) {
                    if (dp[j + 1][i]) {
                        f[i] = min(f[i], f[j] + 1);
                    }
                }
            }
        }
        return f.back();
    }
};

115. 不同的子序列「Hard」

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

字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串.

( 例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是 )

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

示例 1：

1
2
3
4
5
6
7
8
9
10
11
输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下图所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
(上箭头符号 ^ 表示选取的字母)
rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^

示例 2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入：s = "babgbag", t = "bag"
输出：5
解释：
如下图所示, 有 5 种可以从 s 中得到 "bag" 的方案。 
(上箭头符号 ^ 表示选取的字母)
babgbag
^^ ^
babgbag
^^    ^
babgbag
^    ^^
babgbag
  ^  ^^
babgbag
    ^^^

算法分析：

Preface：

假设字符串 s 和 t 的长度分别为 m 和 n，只有当 m ≥ n 的时候才有意义，当 m < n 时返回 0.

  1. 定义状态

    创建二维数组 dp，其中 dp[i][j] 表示 s[i:] 的子序列中 t[j:] 出现的个数.

  2. 状态转移方程

    当 i < m 且 j < n 时， 我们考虑 dp[i][j] 的计算.

    • 当 s[i] = t[j] 时，dp[i][j] 由两部分组成：

      • 如果 s[i] 和 t[j] 匹配，则考虑 t[j + 1:] 作为 s[i + 1:] 的子序列，

        子序列数为 dp[i + 1][j + 1].

      • 如果 s[i] 不和 t[j] 匹配，则考虑 t[j:] 作为 s[i + 1:] 的子序列，

        子序列数为 dp[i + 1][j].

      因此当 s[i] = t[j] 时，有 dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j].

    • 当 s[i] ≠ t[j] 时，s[i] 不和 t[j] 匹配，因此只考虑 t[j:] 作为 s[i + 1:] 的子序列，

      子序列数为 dp[i + 1][j].

      因此当 s[i] ≠ t[j] 时，dp[i][j] = dp[i + 1][j].

    最终计算得到 dp[0][0] 即为在 s 的子序列中 t 出现的个数.

  3. 边界情况

    • 当 j = n 时，t[j:] 为空字符串，由于空字符串是任何字符串的子序列，因此对任意 0 ≤ i ≤ m，有 dp[i][n] = 1.
    • 当 i = m 且 j < n 时，s[i:] 为空字符串，t[j:] 为非空字符串，由于非空字符串不是空字符串的子序列，因此对任意 0 ≤ j < n，有 dp[m][j] = 0.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func numDistinct(s, t string) int {
    m, n := len(s), len(t)
    if m < n {
        return 0
    }
    dp := make([][]int, m + 1)
    for i := range dp {
        dp[i] = make([]int, n + 1)
        dp[i][n] = 1
    }
    for i := m - 1; i >= 0; i-- {
        for j := n - 1; j >= 0; j-- {
            if s[i] *** t[j] {
                dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j]
            } else {
                dp[i][j] = dp[i + 1][j]
            }
        }
    }
    return dp[0][0]
}

53. 最大子序和「Easy」

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

示例 1：

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

算法分析：

  1. 定义状态

    我们令 $f(i)$ 为以第 $i$ 个数结尾的「连续子数组的最大和」，那么很显然我们要求的答案就是：$max_{0≤i<n}f(i)$.

  2. 状态转移方程

    $f(i)=max(f(i-1)+nums[i],nums[i])$.

  3. 无边界情况

$DP$ 算法优化：

​ 每一次的状态只与前一次的状态有关，所以可以利用「滚动数组」思想优化空间，设置一个变量 $pre$ 表示前一个解的值.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func maxSubArray(nums []int) int {
    pre, maxn := 0, nums[0]
    for _,v := range nums {
        pre = max(pre + v, v)
        maxn = max(maxn, pre)
    }
    return maxn
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

198. 打家劫舍「Medium」

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

1
2
3
4
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

1
2
3
4
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

算法分析：

  1. 定义状态：

    由于当前考虑的房屋有两种选择：「偷」和「不偷」。我们用 0 表示「不偷」，用 1 表示「偷」，即：

    • dp[i][0] 表示：考虑区间 [0..i] ，并且下标为 i 的这个房间不偷，能够偷窃到的最高金额；
    • dp[i][1] 表示：考虑区间 [0..i] ，并且下标为 i 的这个房间偷，能够偷窃到的最高金额。

  2. 状态转移方程：

    • 不偷：dp[i][0] = max(dp[i - 1][0], dp[i - 1][i])
    • 偷：dp[i][1] = dp[i - 1][0] + nums[i]

  3. 边界情况：

    • dp[0][0] = 0
    • dp[0][1] = nums[0]

算法优化：

每层算法只与其上一层的状态有关，所以可以使用「滚动数组」来节省空间.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int rob(vector<int>& nums) {
        int len = nums.size();
        if (len *** 0) {
            return 0;
        }
        if (len *** 1) {
            return nums[0];
        }
        int norob = 0, rob = nums[0];
        for (int i = 1; i < len; ++i) {
            int temp = norob;
            norob = max(norob, rob);
            rob = temp + nums[i];
        }
        return max(norob, rob);
    }
};

0-1 背包问题

有 n 种物品，物品 i 的体积为 $v_i$ ，价值为 $w_i$，有一个体积限制 $V$，每种物品只有 1 个，只有选或者不选，而没有选几个的问题，此问题称为 01 背包问题。

  1. 状态：

    dp[i][j] := 考虑了 [0..i] 里的物品，占用了 j 空间，所能取得的最大价值.

  2. 状态转移方程：

    转移方式有两种，一种是放入，一种是不放入。

    如果放，则区间 [0...i-1] 只能占 j - v[i] 空间；

    如果不放，则区间 [0...i-1] 的物品还是占了 j 空间。

    1
    2
    dp[i][j] = dp[i - 1][j] 当前物品不选
               dp[i - 1][j - v[i]] + w[i] 当前物品选，j - v[i] 要大于等于 0

  3. 边界情况：

    初始化时将所有状态置为 $0$ 即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int ZeroOnePack(vector<int>& weights, vector<int>& values, int capacity) {
    int n = (int)weights.size();
    vector<vector<int>> dp(n, vector<int>(capacity + 1, 0));
    
    for (int i = 0; i < n; ++i) {
        for (int j = 1; j <= capacity; ++j) {
            if (i *** 0) {
                dp[i][j] = j < weights[i] ? 0 : values[i];
            } else if (j < weights[i]) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i]);
            }
        }
    }
    return dp.back().back();
}

32. 最长有效括号「Hard」

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：

1
2
3
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：

1
2
3
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

算法分析：

  1. 状态：

    dp[i] 表示以下标 i 为字符结尾的最长有效字符串的长度.

  2. 状态转移方程：

    • 以 ( 结尾的子字符串不考虑，因为不可能构成合法括号

    • if s[i] *** ')'

      • s[i - 1] *** '('，也就是字符串形如 “……()”，我们可以推出：dp[i] = dp[i − 2] + 2.

      • s[i - 1] *** ')'，也就是字符串形如 “.......))”，我们可以推出：

        if s[i - dp[i - 1] - 1] *** '('，dp[i] = dp[i − 1] + dp[i − dp[i − 1] − 2] + 2

        因为如果倒数第二个 )是一个有效子字符串的一部分（记为subs），我们此时需要判断 subs 前面一个符号是不是 ( ，如果恰好是(，我们就用 subs 的长度( dp[i - 1] ) 加上 2 去更新dp[i]。除此以外，我们也会把子字符串 subs 前面的有效字符串的长度加上，也就是 dp[i − dp[i − 1] − 2].

  3. 边界情况：

    • i - 2 有可能小于零越界了，这种情况下就是只有 () ，前面记为 0 就好了.
    • i - dp[i - 1] - 1 和 i - dp[i - 1] - 2 都可能越界，越界了当成 0 来计算就可以了.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int longestValidParentheses(string s) {
        int maxLen = 0;
        vector<int> dp(s.length());
        for (int i = 1; i < s.length(); i++) {
            if (s[i] *** ')') {
                if (s[i - 1] *** '(') {
                    dp[i] = (i - 2 >= 0 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] - 1 >= 0 and s[i - dp[i - 1] - 1] *** '(') {
                    dp[i] = (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0) + dp[i - 1] + 2;
                }
            }
            maxLen = fmax(dp[i], maxLen);
        }
        return maxLen;
    }
};

1143. 最长公共子序列「Medium」

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

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

  • 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

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

注：本题过于经典，算法比较简单，不多赘述了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func longestCommonSubsequence(text1 string, text2 string) int {
    m, n := len(text1), len(text2)
    dp := make([][]int, m + 1)x2
    for i, _ := range dp {
        dp[i] = make([]int, n + 1)
    }
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; 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[m][n]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

91. 解码方法「Medium」

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

1
2
3
4
'A' -> 1
'B' -> 2
...
'Z' -> 26

要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：

  • "AAJF" ，将消息分组为 (1 1 10 6)
  • "KJF" ，将消息分组为 (11 10 6)

注意，消息不能分组为 (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。

给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。

  • s 只包含数字，并且可能包含前导零。

示例 1：

1
2
3
输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2：

1
2
3
输入：s = "226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

算法分析：

  1. 状态：

    $dp[i]$ 表示字符串的前 $i$ 个字符可能的组合数.

  2. 状态转移方程：

    对于当前位 $i≠0$，则可以对前一项进行转移：dp[i] += dp[i - 1].

    考虑 $i$ 和 $i - 1$ 能否组成合法数字，如果可以的话也可以转移：dp[i] += dp[i - 2].

  3. 边界情况：

    第 $i - 1$ 位的时候要考虑是否字符 '0'，若是，则此项不进行转移；同理，第 $i - 2$ 位的时候亦是如此.

    细节点：我们如何判断不合法的字符到最后一定是 $0$ 呢？

    若是当前字符为 '0'，我们就不会考虑前一项了，若是前一项与当前项组成的数字也是不合法的，我们也不会做加法，因此迭代下去则会一直是零.

  4. 优化：

    使用变量来代替迭代元素

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
class Solution {
public:
    int numDecodings(string s) {
        int n = (int)s.size();
        vector<int> dp(n + 1);
        dp[0] = 1;
        for (int i = 1; i <= n; ++i) {
            if (s[i - 1] != '0') {
                dp[i] += dp[i - 1];
            }
            if (i > 1 and s[i - 2] != '0' and ((s[i - 2] - '0') * 10 + s[i - 1] - '0' <= 26)) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }
};

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        // a = dp[i - 2], b = dp[i - 1], c = dp[i]
        int a = 0, b = 1, c;
        for (int i = 1; i <= n; ++i) {
            c = 0;
            if (s[i - 1] != '0') {
                c += b;
            }
            if (i > 1 && s[i - 2] != '0' && ((s[i - 2] - '0') * 10 + (s[i - 1] - '0') <= 26)) {
                c += a;
            }
            tie(a, b) = {b, c};
        }
        return c;
    }
};

Chapter3 Binary Search

33. 搜索旋转排序数组「Medium」

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，

使数组变为 [nums[k], nums[k + 1], ..., nums[n - 1], nums[0], nums[1], ...,nums[k - 1]]（下标 从 0 开始 计数）

例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

示例 1：

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

示例 2：

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

算法分析：

对于有序数组，可以使用二分查找的方法查找元素。

但是这道题中，数组本身不是有序的，进行旋转后只保证了数组的局部是有序的，这还能进行二分查找吗？答案是可以的。

可以发现的是，我们将数组从中间分开成左右两部分的时候，一定有一部分的数组是有序的。拿示例来看，我们从 6 这个位置分开以后数组变成了 [4, 5, 6] 和 [7, 0, 1, 2] 两个部分，其中左边 [4, 5, 6] 这个部分的数组是有序的，其他也是如此。

这启示我们可以在常规二分查找的时候查看当前 mid 为分割位置分割出来的两个部分 [l, mid] 和 [mid + 1, r] 哪个部分是有序的，并根据有序的那个部分确定我们该如何改变二分查找的上下界，因为我们能够根据有序的那部分判断出 target 在不在这个部分：

  • 如果 [l, mid - 1] 是有序数组，且 target 的大小满足 [nums[l], nums[mid]) 则我们应该将搜索范围缩小至 [l, mid - 1]，否则在 [mid + 1, r] 中寻找。
  • 如果 [mid, r] 是有序数组，且 target 的大小满足 (nums[mid], nums[r]] 则我们应该将搜索范围缩小至 [mid + 1, r]，否则在 [l, mid - 1] 中寻找。

picture

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
int search(int* nums, int numsSize, int target){
    if (!numsSize) return -1;
    if (numsSize *** 1) return nums[0] *** target ? 0 : -1;
    
    int left = 0, right = numsSize - 1;
    
    // 本题的二分是只在有序数组那一边的范围里找 target
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] *** target) return mid;
        
        if (nums[left] <= nums[mid]) { // 左边为升序排序数组
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else { // 右边为升序数组
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;
}

变式： 数组中的值可以重复

算法分析：

对于数组中有重复元素的情况，二分查找时可能会有 nums[l] = nums[mid] = nums[right] 此时无法判断区间 [left, mid] 和区间 [mid + 1, right] 哪个是有序的。

对于这种情况，我们只能将当前二分区间的左边界加一，右边界减一，然后在新区间上继续二分查找。

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
bool search(int* nums, int numsSize, int target){
    if (!numsSize) return false;
    if (numsSize *** 1) return nums[0] *** target ? true : false;
    
    int left = 0, right = numsSize - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] *** target) return true;
        if (nums[left] *** nums[mid] && nums[mid] *** nums[right]) {
            ++left;
            --right;
        } else if (nums[left] <= nums[mid]) { 
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else { 
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return false;
}

153. 寻找旋转排序数组中的最小值「Medium」

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

  • 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
  • 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]]

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

示例 1：

1
2
3
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

算法分析：

一个不包含重复元素的升序数组在经过旋转之后，可以得到下面可视化的折线图：

picture

其中横轴表示数组元素的下标，纵轴表示数组元素的值。图中标出了最小值的位置，是我们需要查找的目标.

我们考虑**数组中的最后一个元素** $x$：在最小值右侧的元素 ( 不包括最后一个元素本身 )，它们的值一定都严格小于 $x$ 而在最小值左侧的元素，它们的值一定都严格大于 $x$. 因此，我们可以根据这一条性质，通过二分查找的方法找出最小值.

在二分查找的每一步中，左边界为 $low$，右边界为 $high$，区间的中点为 $pivot$，最小值就在该区间内. 我们将中轴元素 $nums[pivot]$ 与右边界元素 $nums[high]$ 进行比较，可能会有以下的三种情况：

第一种情况是 $nums[pivot]<nums[high]$. 如下图所示，这说明 $nums[pivot]$ 是最小值右侧的元素，因此我们可以忽略二分查找区间的右半部分.

picture

第二种情况是 $nums[pivot]>nums[high]$. 如下图所示，这说明 $nums[pivot]$ 是最小值左侧的元素，因此我们可以忽略二分查找区间的左半部分.

picture

由于数组不包含重复元素，并且只要当前的区间长度不为 $1$，$pivot$ 就不会与 $high$ 重合；而如果当前的区间长度为 $1$ ，这说明我们已经可以结束二分查找了。因此不会存在 $nums[pivot]=nums[high]$ 的情况.

当二分查找结束时，我们就得到了最小值所在的位置.

1
2
3
4
5
6
7
8
9
10
11
12
13
int findMin(int* nums, int numsSize) {
    int low = 0;
    int high = numsSize - 1;
    while (low < high) {
        int pivot = low + (high - low) / 2;
        if (nums[pivot] < nums[high]) {
            high = pivot;
        } else {
            low = pivot + 1;
        }
    }
    return nums[low];
}

Chapter5 Greedy Algorithm

1749. 任意子数组和的绝对值的最大值「Medium」

给你一个整数数组 nums 。一个子数组 $[nums_l, nums_{l+1}\cdots,nums_{r-1},nums_r]$ 的 和的绝对值 为 $abs(nums_l+nums_{l+1}+\cdots+nums_{r-1}+nums_r)$.

请你找出 nums 中 和的绝对值 最大的任意子数组（可能为空），并返回该 最大值 。

示例 1：

1
2
3
输入：nums = [1,-3,2,3,-4]
输出：5
解释：子数组 [2,3] 和的绝对值最大，为 abs(2+3) = abs(5) = 5 。

算法分析：

我们使用一个 $sum$ 数组来保存前缀和，然后使用 $maxn$ 和 $minn$ 来保存遍历过程中前缀和的最大值和最小值，这样相当于丢弃 $maxn$ 或 $minn$ 前面的子数组，可以使得目前的 $sum[i]-maxn$ 可能得到一个较大的负值 ( 也许是正值 )，$sum[i] - minn$ 可能得到一个较大的正值 ( 也许是负值 )，然后更新答案变量即可.

值得注意的细节：

前缀和数组 $sum$ 我们申请多一个空间，这样就不需要单独判断 $0$ 这个可能溢出的点了，子区间 $[i,j]$ 的和为 $sum[j + 1]-sum[i]$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxAbsoluteSum(vector<int>& nums) {
        int ans = 0;
        int n = (int) nums.size();
        vector<int> sum(n + 1);
        for (int i = 1; i <= n; ++i) {
            sum[i] = sum[i - 1] + nums[i - 1];
        }
        for (int i = 1, maxn = 0, minn = 0; i <= n; ++i) {
            ans = max(ans, abs(sum[i] - maxn));
            ans = max(ans, abs(sum[i] - minn));
            maxn = max(maxn, sum[i]);
            minn = min(minn, sum[i]);
        }
        return ans;
    }
};

179. 最大数

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

示例 1：

1
2
输入：nums = [10,2]
输出："210"

示例 2：

1
2
输入：nums = [3,30,34,5,9]
输出："9534330"

算法分析：

由题意，我们可以知道，开头位越大的数字拼接起来越大，我们可以使用排序来解决此问题.

字符串拼接容易理解，但是题目中给出的是 int 型的数据类型，这样就涉及一个基础的问题了，如何实现整数拼接？

我们可以将两个数的位数分别拉长，再将对方的数加上，最后再比大小.

举个例子： $(x=442,y=4)\Rightarrow~~ (x=4420,y=4000)\Rightarrow(x=4424,y=4442)$.

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:
    string largestNumber(vector<int> &nums) {
        sort(nums.begin(), nums.end(), [](const int &x, const int &y) {
            long sx = 10, sy = 10;
            while (sx <= x) {
                sx *= 10;
            }
            while (sy <= y) {
                sy *= 10;
            }
            return sy * x + y > sx * y + x;
        });
        if (nums[0] *** 0) {
            return "0";
        }
        string ret;
        for (int &x : nums) {
            ret += to_string(x);
        }
        return ret;
    }
};

Chapter6 Bit Manipulation

1680. 连接连续二进制数字「Medium」

给你一个整数 n ，请你将 1 到 n 的二进制表示连接起来，并返回连接结果对应的 十进制 数字对 10^9 + 7 取余的结果。

示例 1：

1
2
3
输入：n = 1
输出：1
解释：二进制的 "1" 对应着十进制的 1 。

示例 2：

1
2
3
4
输入：n = 3
输出：27
解释：二进制下，1，2 和 3 分别对应 "1" ，"10" 和 "11" 。
将它们依次连接，我们得到 "11011" ，对应着十进制的 27 。

示例 3：

1
2
3
4
5
输入：n = 12
输出：505379714
解释：连接结果为 "1101110010111011110001001101010111100" 。
对应的十进制数字为 118505380540 。
对 109 + 7 取余后，结果为 505379714 。

算法分析：

由于我们需要将「十进制转换成二进制」「进行运算」「将结果转换回十进制」这三个步骤，因此我们不妨直接将整个问题在十进制的角度下进行考虑。

假设我们当前处理到了数字 $i$，并且前面 $[1,i-1]$ 的二进制连接起来对应的十进制数为 $x$，那么我们如何将数字 $i$ 进行连接呢？

观察二进制连接的过程，我们可以将这一步运算抽象为两个步骤：

  1. 将之前 $[1,i-1]$ 的二进制数左移若干位，这个位数就是 $i$ 的二进制表示的位数；
  2. 将 $i$ 通过加法运算与左移的结果进行相加。

这样，我们可以得到 $x$ 的递推式：$x=x\times2^{len(i)}+i$.

我们可以知道 $len(i)$ 和 $len(i-1)$ 要么相等，要么相差 $1$.

$x$ 是 $(100\cdots)_2$ 的形式存储，而 $x-1$ 是以 $(111\cdots)_2$ 的形式存在，所以当一个数 $x$ 为 $2$ 的倍数次的时候，那么它比 $x-1$ 多一位，因此***当 x & (x - 1) *** 0 的时候，移位的位数就需要加 $1$***，答案就显而易见了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
private:
    const unsigned int mod = 1e9 + 7;
public:
    int concatenatedBinary(int n) {
        int times = 1;
        int ans = 1;
        for (int i = 2; i <= n; ++i) {
            if ((i & (i - 1)) *** 0) ++times;
            for (int j = 0; j < times; ++j) {
                ans <<= 1;
                ans %= mod;
            }
            ans += i;
            ans %= mod;
        }
        return ans;
    }
};

剑指 Offer 56 - I. 数组中数字出现的次数「Medium」

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是 $O(n)$，空间复杂度是 $O(1)$.

示例 1：

1
2
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]

算法分析：

设两个只出现一次的数字为 $x,y$，由于 $x≠y$，则 $x$ 和 $y$ 二进制至少有一位不同（即分别为 $0$ 和 $1$ ），根据此位可以将 $nums$ 拆分为分别包含 $x$ 和 $y$ 的两个子数组。

易知两子数组都满足 「除一个数字之外，其他数字都出现了两次」。因此，仿照以上简化问题的思路，分别对两子数组遍历执行异或操作，即可得到两个只出现一次的数字 $x,y$.

算法流程：

  1. 遍历 $nums$ 执行异或：

    • 设整型数组 $nums=[a,a,b,b\cdots,x,y]$，对 $nums$ 中所有数字进行异或，得到的结果为 $x\bigoplus y$.

  2. 循环左移计算 m:

    • 根据异或运算定义，若整数 $x\bigoplus y$ 某二进制位为 $1$，则 $x$ 和 $y$ 的此二进制位一定不同。换言之，找到 $x\bigoplus y$ 某位为 $1$ 的二进制位，即可将数组 $nums$ 拆分为上述的两个子数组。根据与运算特点，可知对于任意整数 $a$ 有：

      • 若 $a$ & $0001=1$，则 $a$ 的第一位为 $1$ ；
      • 若 $a$ & $0010=1$，则 $a$ 的第二位为 $1$ ；
      • 以此类推…

    • 因此，初始化一个辅助变量 $m=1$，通过与运算从右向左循环判断，可 获取整数 $x\bigoplus y$ 首位 $1$，记录于 $m$ 中，代码如下：

      1
      2
      while(z & m *** 0) // m 循环左移一位，直到 z & m ！= 0
          m <<= 1

  3. 拆分 $nums$ 为两个子数组；

  4. 分别遍历两个子数组执行异或；

    • 通过遍历判断 $nums$ 中各数字和 $m$ 做与运算的结果，可将数组拆分为两个子数组，并分别对两个子数组遍历求异或，则可得到两个只出现一次的数字

picture

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int x = 0, y = 0, n = 0, m = 1;
        for(int num : nums)         // 1. 遍历异或
            n ^= num;
        while((n & m) *** 0)         // 2. 循环左移，计算 m
            m <<= 1;
        for(int num : nums) {       // 3. 遍历 nums 分组
            if(num & m) x ^= num;   // 4. 当 num & m != 0
            else y ^= num;          // 4. 当 num & m *** 0
        }
        return vector<int> {x, y};  // 5. 返回出现一次的数字
    }
};

剑指 Offer 56 - II. 数组中数字出现的次数 II「Medium」

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

示例 1：

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

算法分析：

方法一：有限状态自动机

各二进制位的 位运算规则相同 ，因此只需考虑一位即可。如下图所示，对于所有数字中的某二进制位 $1$ 的个数，存在 $3$ 种状态，即对 $3$ 余数为 $0, 1, 2$.

  • 若输入二进制位 $1$，则状态按照 $0\rightarrow1\rightarrow2\rightarrow0\rightarrow\cdots$ 顺序转换；
  • 若输入二进制位 $0$，则状态不变.

picture

如下图所示，由于二进制只能表示 $0,1$，因此需要使用两个二进制位来表示 $3$ 个状态。设此两位分别为 $two,one$，则状态转换变为：$00\rightarrow01\rightarrow10\rightarrow00\rightarrow\cdots$

![image-20210304232713519](/Users/wanglei/Library/Application Support/typora-user-images/image-20210304232713519.png)

接下来，需要通过状态转换表导出状态转换的计算公式。首先回忆一下位运算特点，对于任意二进制位 $x$，有：

  • 异或运算：x ^ 0 = x ， x ^ 1 = ~x
  • 与运算：x & 0 = 0 ， x & 1 = x

计算 $one$ 方法：

设当前状态为 $two,one$，此时输入二进制位 $n$。如下图所示，通过对状态表的情况拆分，可推出 $one$ 的计算方法为：

1
2
3
4
5
6
7
if two *** 0:
  if n *** 0:
    one = one
  if n *** 1:
    one = ~one
if two *** 1:
    one = 0

引入 异或运算 ，可将以上拆分简化为：

1
2
3
4
if two *** 0:
    one = one ^ n
if two *** 1:
    one = 0

引入 与运算 ，可继续简化为：

1
one = one ^ n & ~two

p

计算 $two$ 方法：

由于是先计算 $one$ ，因此应在新 $one$ 的基础上计算 $two$.

如下图所示，修改为新 $one$ 后，得到了新的状态图。观察发现，可以使用同样的方法计算 $two$，即：

1
two = two ^ n & ~one

picture

返回值：

以上是对数字的二进制中 “一位” 的分析，而 int 类型的其他 $31$ 位具有相同的运算规则，因此可将以上公式直接套用在 $32$ 位数上。

遍历完所有数字后，各二进制位都处于状态 $00$ 和状态 $01$ ( 取决于 “只出现一次的数字” 的各二进制位是 $0$ 还是 $1$ )，而此两状态是由 $one$ 来记录的 ( 此两状态下 $twos$ 恒为 $0$ )，因此返回 $ones$ 即可.

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ones = 0, twos = 0;
        for(int &num : nums){
            ones = ones ^ num & ~twos;
            twos = twos ^ num & ~ones;
        }
        return ones;
    }
};

剑指 Offer 65. 不用加减乘除做加法「Easy」

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

示例:

1
2
输入: a = 1, b = 1
输出: 2

提示：

  • a, b 均可能是负数或 $0$
  • 结果不会溢出 $32$ 位整数

算法分析：

观察发现，无进位和 与 异或运算 规律相同，进位 和 与运算 规律相同 ( 并需左移一位 ) 。因此，无进位和 $n$ 与进位 $c$ 的计算公式如下：
$$
\left{
\begin{aligned}
&n=a\bigoplus b & 非进位和：异或运算\
&c=a&b~<<1 & 进位：与运算+左移一位\
\end{aligned}
\right.
$$
和 ( $s$ ）=（非进位和 $n$ ）+（进位 $c$ ）。即可将 $s=a+b$ 转化为：$s=a+b\Rightarrow s=n+c$.

循环求 $n$ 和 $c$，直至进位 $c=0$；此时 $s=n$，返回 $n$ 即可.

picture

Q ： 若数字 $a$ 和 $b$ 中有负数，则变成了减法，如何处理？
A ： 在计算机系统中，数值一律用 补码 来表示和存储。补码的优势： 加法、减法可以统一处理（CPU只有加法器）。因此，以上方法 同时适用于正数和负数的加法 。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int add(int a, int b) {
        while (b != 0) { // 当进位为 0 时跳出
            int c = (unsigned int)(a & b) << 1;  // c = 进位
            a ^= b; // a = 非进位和
            b = c; // b = 进位
        }
        return a;
    }
};

Chapter7 BackTrack

51. N 皇后「Hard」

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：

picture

1
2
3
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

算法分析：

方法一：基于集合的回溯

为了判断一个位置所在的列和两条斜线上是否已经有皇后，使用三个集合 $columns,diagonals1,diagonals2$ 分别记录每一列以及两个方向的每条斜线上是否有皇后。

列的表示法很直观，一共有 $N$ 列，每一列的下标范围从 $0$ 到 $N-1$，使用列的下标即可明确表示每一列。

如何表示两个方向的斜线呢？对于每个方向的斜线，需要找到斜线上的每个位置的行下标与列下标之间的关系。

方向一的斜线为从左上到右下方向，同一条斜线上的每个位置满足行下标与列下标之差相等，例如 $(0,0)$ 和 $(3,3)$ 在同一条方向一的斜线上。因此使用行下标与列下标之差即可明确表示每一条方向一的斜线。

picture

方向二的斜线为从右上到左下方向，同一条斜线上的每个位置满足行下标与列下标之和相等，例如 $(3,0)$ 和 $(1,2)$ 在同一条方向二的斜线上。因此使用行下标与列下标之和即可明确表示每一条方向二的斜线。

picture

每次放置皇后时，对于每个位置判断其是否在三个集合中，如果三个集合都不包含当前位置，则当前位置是可以放置皇后的位置。

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
class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        auto solutions = vector<vector<string>>();
        auto queens = vector<int>(n, -1);
        auto columns = unordered_set<int>();
        auto diagonals1 = unordered_set<int>();
        auto diagonals2 = unordered_set<int>();
        backtrack(solutions, queens, n, 0, columns, diagonals1, diagonals2);
        return solutions;
    }

    void backtrack(vector<vector<string>> &solutions, vector<int> &queens, int n, int row, unordered_set<int> &columns, unordered_set<int> &diagonals1, unordered_set<int> &diagonals2) {
        if (row *** n) {
            vector<string> board = generateBoard(queens, n);
            solutions.push_back(board);
        } else {
            for (int i = 0; i < n; i++) {
                if (columns.find(i) != columns.end()) {
                    continue;
                }
                int diagonal1 = row - i;
                if (diagonals1.find(diagonal1) != diagonals1.end()) {
                    continue;
                }
                int diagonal2 = row + i;
                if (diagonals2.find(diagonal2) != diagonals2.end()) {
                    continue;
                }
                queens[row] = i;
                columns.insert(i);
                diagonals1.insert(diagonal1);
                diagonals2.insert(diagonal2);
                backtrack(solutions, queens, n, row + 1, columns, diagonals1, diagonals2);
                queens[row] = -1;
                columns.erase(i);
                diagonals1.erase(diagonal1);
                diagonals2.erase(diagonal2);
            }
        }
    }

    vector<string> generateBoard(vector<int> &queens, int n) {
        auto board = vector<string>();
        for (int i = 0; i < n; i++) {
            string row = string(n, '.');
            row[queens[i]] = 'Q';
            board.push_back(row);
        }
        return board;
    }
};

90. 子集 II「Hard」

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：

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

示例 2：

1
2
输入：nums = [0]
输出：[[],[0]]
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:
    vector<int> t;
    vector<vector<int>> ans;

    void dfs(bool choosePre, int cur, vector<int> &nums) {
        if (cur *** nums.size()) {
            ans.push_back(t);
            return;
        }
        dfs(false, cur + 1, nums);
        if (!choosePre && cur > 0 && nums[cur - 1] *** nums[cur]) {
            return;
        }
        t.push_back(nums[cur]);
        dfs(true, cur + 1, nums);
        t.pop_back();
    }

    vector<vector<int>> subsetsWithDup(vector<int> &nums) {
        sort(nums.begin(), nums.end());
        dfs(false, 0, nums);
        return ans;
    }
};
#Programming #Algorithm
Leetcode Algorithm Notes
https://www.mementos.top/1976/04/01/Leetcode Algorithm Notes/
作者
Natsumi
发布于
1976年4月1日
许可协议