日拱两卒（一）

Leetcode的考察点和ACM不太一样，之前面试也有几次尴尬写不出的经历。

从2026.07.04开始把Hot100过一遍，因为前面几题其实很久以前提交过，所以这次倒着刷。

这轮试着用Python而不是C++！

每天两题写完差不多正好是9月日常实习。某一天的题太简单的话就多做几道！

100#

有n + 1个整数，值域是[1, n]，找出唯一的重复的数。

假设这个重复的数是x。定义cnt[i]为小于等于i的数的个数。

cnt[i] <= i 当 i <= x - 1时。

cnt[i] > i 当 i >= x 时。

所以二分出最小的满足cnt[i] > i的i就可以了。

1
class Solution:
2
    def findDuplicate(self, nums: List[int]) -> int:
3
        l = 1
4
        r = len(nums) - 1
5
        while l < r:
6
            mid = (l + r) >> 1;
7

8
            cnt = 0
9
            for num in nums:
10
                cnt += num <= mid
11

12
            if cnt > mid:
13
                r = mid
14
            else:
15
                l = mid + 1
16

17
        return l

99#

按字典序找出下一个排列。

比如[1, 2, 3]的下一个是[1, 3, 2]，再下一个是[2, 1, 3]。

[1, 3, 5, 4, 2] -> [1, 4, 5, 3, 2] -> [1, 4, 2, 3, 5]。这是一个一般化过程。

从后往前看，如果有一个数破坏了递增，说明这个数移到后面去是可以提升字典序的（因为后面有比它大的数）。

那么把哪个数和它调换？因为要求下一个排列，肯定是比它大的最小的数。

换完以后容易发现现在递减的部分可以倒过来，进一步缩小字典序。

1
class Solution:
2
    def nextPermutation(self, nums: List[int]) -> None:
3
        n = len(nums)
4

5
        i = n - 2
6
        while i >= 0 and nums[i] >= nums[i + 1]:
7
            i -= 1
8

9
        if i >= 0:
10
            j = n - 1
11
            while nums[j] <= nums[i]:
12
                j -= 1
13
            nums[i], nums[j] = nums[j], nums[i]
14

15
        nums[i+1:] = nums[i+1:][::-1]

98#

不用sort排序一个只含有0, 1, 2的数组。

这个问题叫荷兰国旗问题（名字加深印象）！

p0维护下一个0的位置，它的左边都是0。p2维护下一个2的位置，它的右边都是2。i是当前检查的位置。

循环的不变量：[0, p0)都是 0，(p2, n - 1]都是 2，中间[p0, i)都是 1。

把2交换到后面去的时候要再检查一次当前位置，因为被换到前面来的数可能是0或2。

在这个算法里，一个数最多会被搬两次。

1
class Solution:
2
    def sortColors(self, nums: List[int]) -> None:
3
        p0, i, p2 = 0, 0, len(nums) - 1
4
        while i <= p2:
5
            if nums[i] == 0:
6
                nums[i], nums[p0] = nums[p0], nums[i]
7
                p0 += 1
8
                i += 1
9
            elif nums[i] == 2:
10
                nums[i], nums[p2] = nums[p2], nums[i]
11
                p2 -= 1
12
            else:
13
                i += 1

97#

求一个数组里的绝对众数。

擂台法。同一个数字想成同一个门派，同门派就加一战斗力，不同门派就减一战斗力。绝对众数的门派肯定能站到最后。

1
class Solution:
2
    def majorityElement(self, nums: List[int]) -> int:
3
        ans, cnt = 0, 0
4
        for num in nums:
5
            if cnt == 0:
6
                ans = num
7
                cnt += 1
8
            else:
9
                cnt += 1 if num == ans else -1
10
        return ans

96#

找出只出现一次的数字，保证其他数字都是两次。

老生常谈的异或。

1
class Solution:
2
    def singleNumber(self, nums: List[int]) -> int:
3
        ans = 0
4
        for num in nums:
5
            ans = ans ^ num
6
        return ans

95#

编辑距离。

dp[n][m]代表只考虑word1前n个字母，word2前m个字母的答案。

第n个和第m个字母相等时，只需要考虑dp[n - 1][m - 1]这个子问题。

不相等时，插入、删除、替换对应三个子问题。

@cache起到记忆化搜索的作用，Python把这个功能内置了。

1
class Solution:
2
    def minDistance(self, word1: str, word2: str) -> int:
3
        n = len(word1)
4
        m = len(word2)
5

6
        @cache
7
        def dfs(x, y):
8
            if x < 0:
9
                return y + 1
10
            if y < 0:
11
                return x + 1
12
            if word1[x] == word2[y]:
13
                return dfs(x - 1, y - 1)
14

15
            return min(dfs(x - 1, y), dfs(x, y - 1), dfs(x - 1, y - 1)) + 1
16

17
        return dfs(n - 1, m - 1)

94#

最长公共子序列。

熟悉Python的多维列表初始化和enumerate。

1
class Solution:
2
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
3
        n, m = len(text1), len(text2)
4
        dp = [[0] * (m + 1) for _ in range(n + 1)]
5

6
        for i, x in enumerate(text1):
7
            for j, y in enumerate(text2):
8
                dp[i + 1][j + 1] = dp[i][j] + 1 if x == y else max(dp[i][j + 1], dp[i + 1][j])
9

10
        return dp[n][m]

93#

最长回文子串。

经典的区间DP。

1
class Solution:
2
    def longestPalindrome(self, s: str) -> str:
3
        n = len(s)
4
        dp = [[False] * n for _ in range(n)]
5

6
        for i in range(n):
7
            dp[i][i] = True
8

9
        for i in range(n - 1):
10
            dp[i][i + 1] = True if s[i] == s[i + 1] else False
11

12
        for length in range(3, n + 1):
13
            for l in range(n):
14
                r = l + length - 1
15
                if r > n - 1:
16
                    break
17
                if s[l] == s[r]:
18
                    dp[l][r] = dp[l + 1][r - 1]
19

20
        ans = 0
21
        st = 0
22
        for i in range(n):
23
            for j in range(i, n):
24
                if dp[i][j] and j - i + 1 > ans:
25
                    ans = j - i + 1
26
                    st = i
27

28
        return s[st:st + ans]

92#

从左上角走到右下角的最小权重和，只能向下和向右。

经典的简单DP。

1
class Solution:
2
    def minPathSum(self, grid: List[List[int]]) -> int:
3
        n, m = len(grid), len(grid[0])
4
        dp = [[0] * m for _ in range(n)]
5

6
        dp[0][0] = grid[0][0]
7
        for j in range(1, m):
8
            dp[0][j] = dp[0][j - 1] + grid[0][j]
9

10
        for i in range(1, n):
11
            dp[i][0] = dp[i - 1][0] + grid[i][0]
12

13
        for i in range(1, n):
14
            for j in range(1, m):
15
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
16

17
        return dp[n - 1][m - 1]

91#

从左上角走到右下角的不同路径数，只能向下和向右。

可以是简单DP。

也可以是组合数学，m行n列，因为只能向下和向右，肯定是走m - 1 + n - 1步，这些步数里有m - 1步是向下走。

数据量小的时候Python有现成的comb函数，数据量大的时候还是得上预处理阶乘和逆元的写法。

1
class Solution:
2
    def uniquePaths(self, m: int, n: int) -> int:
3
        return comb(m + n - 2, m - 1)