3月23日刷题笔记

本篇题目#

一、415. 字符串相加#

思路： 模拟竖式加法，从个位开始往高位算，每一位相加后记录进位。

对齐个位，从右往左：用 i、j 两个指针分别指向两个字符串末尾，每轮往左移一位
每一位做三件事：取出当前位的数字 → 加起来（含进位）→ 本位写入结果，进位留给下一轮
循环结束检查进位：如果最后还有进位（比如 999+1），在结果最前面补一个 "1"

1
class Solution:
2
    def addStrings(self, num1: str, num2: str) -> str:
3
        res = ""
4
        i, j, carry = len(num1) - 1, len(num2) - 1, 0
5

6
        # 只要其中一个指针还没有跳到边界外就继续执行这个循环
7
        while i >= 0 or j >= 0:
8
            n1 = int(num1[i]) if i >= 0 else 0
9
            n2 = int(num2[j]) if j >= 0 else 0
10

11
            tmp = n1 + n2 + carry  # 实际加起来得到的值
12
            carry = tmp // 10      # 用 // 得到要进位的数字，比如 9+5=14 写 4 进 1
13
            res = str(tmp % 10) + res  # tmp%10 是实际写在竖式下面的值
14

15
            i -= 1
16
            j -= 1
17

18
        # 如果两个指针都走完了且 carry 不等于 0，在最前面补 "1"
19
        return '1' + res if carry else res

CAUTION
注意点

i、j 从末尾往左移，模拟从个位开始的竖式加法

tmp // 10 取进位，tmp % 10 取本位

新结果拼在 res 前面，因为是从低位往高位算的

if carry 等价于 if carry != 0，数字 0 在 Python 中为 False

TIP

// 和 % 常用技巧

1
a = (a // b) * b + (a % b)   # 验算公式
2

3
n // 10       # 去掉个位
4
n % 10        # 取个位
5
n % 2         # 判断奇偶（0偶1奇）
6
i % len(arr)  # 循环索引，超出边界自动绕回

二、54. 螺旋矩阵#

#54螺旋矩阵

Medium

思路： 用 top、bottom、left、right 四条边界标记还没读过的区域，顺时针依次读完每条边后把对应边界往内收缩一格，不断循环直到区域为空。

1
class Solution:
2
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
3
        if not matrix or not matrix[0]:
4
            return []
5

6
        res = []
7

8
        # 初始化四个边界指针
9
        top, bottom = 0, len(matrix) - 1
10
        left, right = 0, len(matrix[0]) - 1
11

12
        while top <= bottom and left <= right:
13

14
            # 1. 上边：从左到右
15
            for j in range(left, right + 1):
16
                res.append(matrix[top][j])
17
            top += 1
18

19
            # 2. 右边：从上到下
20
            for i in range(top, bottom + 1):
21
                res.append(matrix[i][right])
22
            right -= 1
23

24
            # 3. 下边：从右到左（需要判断 top <= bottom，防止重复读）
25
            if top <= bottom:
26
                for j in range(right, left - 1, -1):
27
                    res.append(matrix[bottom][j])
28
                bottom -= 1
29

30
            # 4. 左边：从下到上（需要判断 left <= right，防止重复读）
31
            if left <= right:
32
                for i in range(bottom, top - 1, -1):
33
                    res.append(matrix[i][left])
34
                left += 1
35

36
        return res

CAUTION
注意点

读完上边和右边后，top 和 right 已经改变，while 不会在中途重新检查，所以读下边和左边前需要手动 if 判断，防止单行或单列时重复读

反向循环 range(right, left-1, -1) 中 stop 写 left-1，是因为 range 取不到 stop，多减一才能让 left 本身被包含

四个方向：上边 j 增，右边 i 增，下边 j 减，左边 i 减

三、5. 最长回文子串#

#5最长回文子串

Medium

思路一：中心扩展 O(n²)#

以每个字符为中心向两边扩展，奇偶回文分开处理。

1
class Solution:
2
    def longestPalindrome(self, s: str) -> str:
3
        n = len(s)
4
        ans_left = ans_right = 0
5

6
        for i in range(n):
7
            # 设置两个指针
8
            # 左指针向左走 右指针向右走
9
            l = r = i
10
            # 只要左右指针没越界，同时左指针指向的元素等于右指针指向元素的时候就循环
11
            while l >= 0 and r < n and s[l] == s[r]:
12
                l -= 1
13
                r += 1
14

15
            # 注意这时候跳出循环了，证明左右指针现在指向的两个元素不相同了
16
            # 那么现在这两个指针的上一个位置形成的区间就是一个回文串
17
            # 所以左指针 l 要 +1，右指针 r 要 -1，然后判断回文串是否比之前记录的长
18
            # 当前回文的长度是 (r-1) - (l+1) + 1 = r - l - 1
19
            if r - l - 1 > ans_right - ans_left:
20
                ans_left, ans_right = l + 1, r
21

22
        # 这里要n-1 因为r是从i+1开始的
23
        for i in range(n - 1):      # 偶回文
24
            l, r = i, i + 1
25
            while l >= 0 and r < n and s[l] == s[r]:
26
                l -= 1
27
                r += 1
28
            # 当前回文的长度是 (r-1) - (l+1) + 1 = r - l - 1
29
            if r - l - 1 > ans_right - ans_left:
30
                ans_left, ans_right = l + 1, r
31

32
        return s[ans_left: ans_right]

TIP
循环结束时 l 和 r 各多走了一步，真正的回文是 s[l+1..r-1]，长度为 r - l - 1。用左闭右开区间 [l+1, r) 存储，最后 s[ans_left:ans_right] 直接切片。

奇回文示例： 以 "babad" 为例，i=2，中心是 'b'

1
扩展过程：
2
  l=2, r=2  →  s[2]='b' == s[2]='b'  ✓  继续
3
  l=1, r=3  →  s[1]='a' == s[3]='a'  ✓  继续
4
  l=0, r=4  →  s[0]='b' != s[4]='d'  ✗  停止
5

6
停止后：l=0, r=4
7

8
  b  a  b  a  d
9
  ↑           ↑
10
  l           r   ← 这两个已经不匹配了，各多走了一步
11

12
真正的回文是 l+1 到 r-1：
13
  b  a  b  a  d
14
     ↑     ↑
15
    l+1   r-1  →  "aba"

偶回文示例： s = "abba"，n=4

1
i=0: l=0,r=1  s[0]='a' != s[1]='b'  扩展失败，长度 2
2
i=1: l=1,r=2  s[1]='b' == s[2]='b'  继续扩展
3
     l=0,r=3  s[0]='a' == s[3]='a'  继续扩展
4
     l=-1,r=4 越界，停止
5
     长度 = r - l - 1 = 4 - (-1) - 1 = 4  → "abba"
6
i=2: l=2,r=3  s[2]='b' != s[3]='a'  扩展失败，长度 2

思路二：Manacher 算法 O(n)#

利用回文的对称性，避免重复计算，把时间复杂度从 O(n²) 降到 O(n)。

核心步骤：

插入 # 消除奇偶差异：s = "bab" → t = "^#b#a#b#$"，所有回文都变成奇回文
half_len[i] 记录以 t[i] 为中心的最长回文半径
用 box_m（当前右边界最远的回文中心）和 box_r（其右边界）复用已知结果
每次扩展都会让 box_r 右移，总扩展次数为 O(n)

IMPORTANT
Manacher 时间复杂度为 O(n) 的原因
box_r 只会单调右移，每次 while 扩展都让 box_r 增加，所以整个算法的总扩展次数不超过 len(t)，即 O(n)。利用镜像对称性跳过已知结果是关键。

1
class Solution:
2
    def longestPalindrome(self, s: str) -> str:
3

4
        # 第一步：改造字符串，消除奇偶差异
5
        # 在每个字符之间插入 #，首尾加哨兵 ^ 和 $
6
        # 例：s = "bab" → t = "^#b#a#b#$"
7
        t = "#".join("^" + s + "$")
8

9
        # 第二步：初始化 half_len 数组
10
        # half_len[i] = 以 t[i] 为中心的最长回文的半径
11
        half_len = [0] * (len(t) - 2)
12
        half_len[1] = 1
13

14
        # 第三步：初始化 box
15
        # box_m = 右边界最靠右的回文中心
16
        # box_r = 该回文的右边界（不含）
17
        box_m = box_r = max_i = 0
18

19
        # 第四步：遍历每个位置，计算 half_len[i]
20
        for i in range(2, len(half_len)):
21
            hl = 1
22

23
            if i < box_r:
24
                # i 在 box 内，利用镜像对称性初始化
25
                # i' = box_m * 2 - i（i 关于 box_m 的镜像）
26
                hl = min(half_len[box_m * 2 - i], box_r - i)
27

28
            # 暴力扩展，哨兵保证不越界
29
            while t[i - hl] == t[i + hl]:
30
                hl += 1
31
                box_m, box_r = i, i + hl
32

33
            half_len[i] = hl
34

35
            if hl > half_len[max_i]:
36
                max_i = i
37

38
        # 第五步：还原回 s 的下标
39
        hl = half_len[max_i]
40
        return s[(max_i - hl) // 2 : (max_i + hl) // 2 - 1]