小试身手

2025-09-10 罗马数字转整数

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

  • I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
  • C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个罗马数字，将其转换成整数。

代码思路如下：

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
import re

class Solution:
    def romanToInt(self, s: str) -> int:
	    """
		    首先需要罗马数字和阿拉伯数的映射，以及特殊罗马数字和和普通罗马数字和
	    """
        roman_normal_num = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
        roman_special_num = {'IV': 4, 'IX': 9, 'XL': 40, 'XC': 90, 'CD': 400, 'CM': 900}
        special_num_sum = 0
        normal_num_sum = 0
        
		"""
		    findall匹配特殊罗马数字的个数，并全部转换为数字和 special_num_sum
		    replace将特殊罗马数字从原字符串删除，该循环结束后只剩下正常罗马数字
		"""
        for k, v in roman_special_num.items():
            #special_num_count = s.count(k)
            special_num_count = len(re.findall(k, s))
            special_num_sum += (special_num_count * v)
            s = s.replace(k, '')

		"""
			计算正常罗马数字，求出数字和normal_num_sum
		"""
        for k, v in roman_normal_num.items():
            #normal_num_count = s.count(k)
            normal_num_count = len(re.findall(k, s))

            normal_num_sum += (normal_num_count * v)
            
		"""
			将special_num_sum和normal_num_sum结果相加
		"""
        return special_num_sum + normal_num_sum

思考：如何找到特殊罗马数字是解决该题的关键。熟悉字符串匹配的方法使用：count，findall 等。

2025-09-11 最长公共前缀

如果不存在公共前缀，返回空字符串 ""。

示例 1：
输入：strs = [“flower”,”flow”,”flight”]
输出：“fl”

示例 2：
输入：strs = [“dog”,”racecar”,”car”]
输出：“”
解释：**输入不存在公共前缀。

**提示：

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] 如果非空，则仅由小写英文字母组成

代码思路如下：

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
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
	    """
	    选择一个比较基准字符串，使用一个 pos 指针从左到右遍历基准字符，同时和字符数组的每个字符串的同位置字符进行比较，【如果当前pos值=某个字符串s的长度，说明s长度不足基准字符串，不再进行后续比较，或者当前位置字符均不相同】，返回当前baseline[:pos]，否则返回整个baseline字符
	    
	    备注：pos指针可以通过将基准字符串枚举化或者列表化获得，下面分别是两种实现代码
	    """
        # baseline = strs[0]
        # for pos, c in enumerate(baseline):
        #     for s in strs:
        #         if pos == len(s) or c != s[pos]:
        #             return baseline[:pos]
        # return baseline

        baseline = list(strs[0])
        for pos in range(0, len(baseline)):
            for s in strs:
                if pos == len(s) or baseline[pos] != s[pos]:
                    return ''.join(baseline[:pos])
        return ''.join(baseline)```
思考：相比于列表化，枚举化更加方便。列表化最后还需要join方法连接字符。
# 2025-09-12 三数之和
给你一个整数数组 `nums` ，判断是否存在三元组 `[nums[i], nums[j], nums[k]]` 满足 `i != j`、`i != k` 且 `j != k` ，同时还满足 `nums[i] + nums[j] + nums[k] == 0` 。请你返回所有和为 `0` 且不重复的三元组。
注意：**答案中不可以包含重复的三元组。

**示例 1：**

输入：**nums = [-1,0,1,2,-1,-4]
输出：**[[-1,-1,2],[-1,0,1]]
**解释：**
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

**示例 2：**

输入：**nums = [0,1,1]
输出：**[]
解释：**唯一可能的三元组和不为 0 。

**示例 3：**

输入：**nums = [0,0,0]
输出：**[[0,0,0]]
解释：**唯一可能的三元组和为 0 。

**提示：**

- `3 <= nums.length <= 3000`
- `-105 <= nums[i] <= 105`

## 代码思路如下：
```python
class Solution:
	"""
	1. 先将数组从小到大排序 sorted
	2. for遍历数组，从第一个一直到倒数第三个数，下标记为current
	3. 初始化left指针和right指针，分别指向current的下一个数和最后一个数
	4. 除了从第一个数开始，后面都要判断并跳过和current一样的数
    5. 当left＜right时，循环执行以下步骤：
	   5.1 对current, left, right对应下标的数字求和，记为total_sum
	   
	   5.2 if判断total_sum 的值
	   
		   5.2.1 等于0（满足条件）
			   5.2.1.1 append这三个数到result列表
			   5.2.1.2 循环指针右移，跳过和sorted_nums[left]一样的数：当left < right 时，同时sorted_nums[left] == sorted_nums[left + 1]，left += 1
			   5.2.1.3 循环指针左移，跳过和sorted_nums[right]一样的数:逻辑类似 4.2.2
			   5.2.1.4 分别再次移动left和right，这一步才是真正跳过重复的数，因为前两步的指针最后落点还是重复的数，最后还需要再移动一次才能跳出，指向才正确
			   
			5.2.2 小于0
				left指针右移（这样能使和越大，越有可能靠近0）
				
			5.2.3 大于0
				right指针左移（这样能使和越小，越有可能靠近0）
	"""
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        sorted_nums = sorted(nums)
        nums_len = len(sorted_nums)
        result = []
        for current in range(nums_len - 2):
            left = current + 1
            right = nums_len - 1
			
			# 跳过和current一样的数
            if current > 0 and sorted_nums[current] == sorted_nums[current - 1]:
                continue
                
            while (left < right):
                total_sum = sorted_nums[current] + sorted_nums[left] + sorted_nums[right]
                if total_sum == 0:
                    result.append([sorted_nums[current], sorted_nums[left], sorted_nums[right]])
                    while left < right and (sorted_nums[left] == sorted_nums[left + 1]):
                        left += 1
                    while left < right and (sorted_nums[right] == sorted_nums[right - 1]):
                        right -= 1

                    left += 1
                    right -= 1
                elif total_sum < 0:
                    left += 1
                else:
                    right -= 1
        return result

思考：一开始有考虑使用枚举组合数求解，但是数一多就容易超时，复杂度爆炸。于是使用双指针。加深了滑动双指针的理解，确定指针的边界。对于怎么跳过重复的数，不知道会有几个数有重复，应该使用while循环。

2025-09-13 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  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
25
26
27
class Solution:
	"""
	判断有效括号，总是从最里面的左括号开始匹配
	但是最外面的符号是最先输入的，又是最后匹配的。这一特性很容易联想到用栈存储（先进后出）左括号
	
	遍历每个字符：
		如果是一个左括号，将其压入栈stack
		如果是一个右括号，先判断栈是否为空
			如果不为空，从栈顶弹出一个左括号，并判断是否是一对。另外使用字典来映射成对的括号关系，左括号为key，右括号为value。
			否则，说明没有左括号可以匹配了，返回False
			
	遍历结束后，如果栈的容量不为0，说明还有左括号没有匹配，返回False
	
	"""
    def isValid(self, s: str) -> bool:
        mapping = {'(': ')', '{': '}', '[': ']'}
        stack = []
        
        for bracket in s:
            if bracket in mapping:
                stack.append(bracket)
            elif len(stack) != 0:
                if mapping[stack.pop()] != bracket:
                    return False
            else:
                return False
        return len(stack) == 0

思考：最早输入的左括号最晚判断，联想到栈中数据先进后出的性质。

2025-09-14 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

代码思路如下：

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
	"""
	使用pointer指针指向伪头节点result_list
	
	当list1和list2均不为空时，比较两者val值：
		如果list1.val 大于等于 list2.val
			将pointer.next指向list2（后继结点）
			list2向后移动一步
		否则
			将pointer.next指向list1（后继结点）
			list1向后移动一步
		pointer向后移动一步
		
	当list1或list2为空时，将pointer.next指向非空的那个list
	"""
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        result_list = ListNode()
        pointer = result_list
        
        while(list1 and list2):
            if (list1.val >= list2.val):
                pointer.next = list2
                list2 = list2.next
            else:
                pointer.next = list1
                list1 = list1.next
            pointer = pointer.next

        if list1 == None:
            pointer.next = list2
        else:
            pointer.next = list1
        return result_list.next

2025-09-15 找出字符串中第一个匹配项的下标

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。

示例 1：

输入：haystack = “sadbutsad”, needle = “sad”
输出：0
解释：“sad” 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：

输入：haystack = “leetcode”, needle = “leeto”
输出：-1
解释：“leeto” 没有在 “leetcode” 中出现，所以返回 -1 。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
	"""
	重点是构造一个滑动窗口，从haystack左往右逐一和needle比较，匹配到则返回第一个匹配项下标
	关键是找到窗口的左边界的下标，左边界的位置在倒数第len_needle，通过归纳总结可以得出：
	倒数第一的元素下标 ---> len(haystack) -1
	倒数第二的元素下标 ---> len(haystack) -2
	倒数第三的元素下标 ---> len(haystack) -3
	...
	倒数第n的元素下标 ---> len(haystack) -n
	倒数第len_needle的元素下标 ---> len(haystack) - len_needle
	但由于range函数取值是左闭右开，所以最后还需要+1才能取到对应下标，因此边界判断条件为：
	range(0, len_haystack - len_needle + 1)
	"""
    def strStr(self, haystack: str, needle: str) -> int:
        len_needle = len(needle)
        len_haystack = len(haystack)

        for i in range(0, len_haystack - len_needle + 1):
            if haystack[i:i + len_needle] == needle:
                return i
        return -1

思考：如何确定边界？一步想不到，枚举几个简单例子，归纳总结。

2025-09-15加练：搜索插入位置

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

请必须使用时间复杂度为 O(log 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
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
class Solution:
	"""
	根据要求的时间复杂度，首先想到二分查找
	初始化left和right指针
	
	考虑输入数组的长度
		当长度为1，也就是只有一个数nums[left]（left == right）
			如果target小于等于nums[left]，说明target的索引排在其前面或者说等于，即0
			否则为1
			
		当长度不为2，使用二分查找比较（while循环条件：只要数组长度＞2，这意味着left和right会慢慢靠近，极限情况是left和right相邻，即left + 1 == right）
			如果找到中间值nums[middle] = target，直接返回middle
			不然如果nums[middle] < target，left向middle移动
			否则right向middle移动
			
		如果没在while循环提前返回，此时的比较数组长度一定为2，接下来需要和比较数组各部分比较
			1. 如果target = nums[left]，返回left
			2. 如果target = nums[right]，返回right
			3. 如果target > nums[right]，返回right + 1
			4. 如果target < nums[right] and target > nums[left]（夹在中间）,返回 left + 1
			5. 如果target＜nums[left]，如果直接返回left - 1，会出现错误（假如比较数组恰巧为原数组的第一和第二个元素），因此还需要再判断left？= 0，为0则返回0，否则才返回left - 1
		
		
	
		
	"""
    def searchInsert(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1

        if(left == right):
            if(target <= nums[left]):
                return 0
            else:
                return 1

        while(left + 1 != right):
            middle = floor((right + left) / 2)
            if(nums[middle] < target):
                left = middle
            elif(nums[middle] > target):
                right = middle
            else:
                return middle
        
        if(target == nums[left]):
            return left
        elif(target == nums[right]):
            return right
        elif(target > nums[right]):
            return right + 1
        elif(target < nums[right] and target > nums[left]):
            return left + 1
        else:
            if(left == 0):
                return 0
            else:
                return left - 1

思考：二分查找的实现。以及对特殊情况的分类讨论，边界判定等。尤其是涉及到指针移动，while 循环后的指针指向。

2025-09-16 二进制求和

给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

示例 1：

输入:a = “11”, b = “1”
输出：“100”

示例 2：

输入：a = “1010”, b = “1011”
输出：“10101”

提示：

  • 1 <= a.length, b.length <= 104
  • a 和 b 仅由字符 '0' 或 '1' 组成
  • 字符串如果不是 "0" ，就不含前导零

代码思路如下：

无脑版

1
2
3
4
5
6
7
8
9
10
11
12
def addBinary(self, a: str, b: str) -> str:
 """
 先将二进制字符串转换成十进制
 得到十进制加和的结果
 将结果转换成二进制字符串
 """
    a_int = int(a, 2)
    b_int = int(b, 2)

    result_int = a_int + b_int
    
    return bin(result_int)[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
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
class Solution:
	"""
	editedString方法主要作用是将较短的二进制字符串用0补齐，如果两个字符串长度一样则不修改，原样返回，用一个数组列表返回
	"""
    def editedString(self, a:str, b:str) -> List[str]:
        len_a = len(a)
        len_b = len(b)
        edited_str = ''
        if (len_a < len_b):
            for i in range(len_b - len_a):
                edited_str += '0'
            edited_str += a
            return [edited_str, b]
        elif (len_a > len_b):
            for i in range(len_a - len_b):
                edited_str += '0'
            edited_str += b
            return [edited_str, a]
        else:
            return [a, b]
            
	"""
	将二进制字符串，从后往前遍历，按位比较，同时引入进位变量carry，考虑是否进位情况。
	用result_int记录结果
	
	每次加和都考虑如下六种情况：
		如果1 + 1，且carry为0，那么该位的加和结果为0，同时修改carry为1
		如果1 + 1，且carry为1，那么该位的加和结果为1，carry不变
		
		如果0 + 0，且carry为0，那么该位的加和结果为0，carry不变
		如果0 + 0，且carry为1，那么该位的加和结果为1，同时修改carry为1
		
		如果0 + 1，且carry为0，那么该位的加和结果为1，carry不变
		如果0 + 1，且carry为1，那么该位的加和结果为0，carry 不变
		
	需要注意的是，当所有位都按照上面计算完后，还需要判断最高位是否有进位（看循环结束后的carry是否为1），有则在最高位的左边再加一个1
	最后将结果字符串反向输出即为最终答案（因为result_int存储的是低位到高位的计算结果）
	"""
    def addBinary(self, a: str, b: str) -> str: 
        result_int = ''
        carry = 0
        edited_str = self.editedString(a, b)

        for i in range(len(edited_str[0])-1, -1, -1):
            if (edited_str[0][i] == edited_str[1][i] and edited_str[0][i] == '1'):
                if (carry == 0):
                    carry = 1
                    result_int += '0'
                else:
                    result_int += '1'
            elif (edited_str[0][i] == edited_str[1][i] and edited_str[0][i] == '0'):
                if (carry == 0):
                    result_int += '0'
                else:
                    result_int += '1'
                    carry = 0
            else:
                if (carry == 0):
                    result_int += '1'
                else:
                    result_int += '0'

        if (carry == 1):
            result_int += '1'
        
        return result_int[::-1]

思考：怎么将自然语言的加法算法翻译成代码？考虑各个位的相加的结果是否需要进位。什么时候对进位变量修改？

2025-09-17 x的平方根

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：**不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：**x = 4
输出：2

示例 2：

输入：**x = 8
输出：2
解释：8 的算术平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。

代码思路如下：

简单版，但耗时

1
2
3
4
5
6
7
8
9
10
11
class Solution:
	
	"""
	一旦找到最小的大于等于x的数（i的平方），返回（它的平方根）- 1
	"""
    def mySqrt(self, x: int) -> int:
         i = 0
         while(i * i <= x):
             i += 1
             if(i * i > x):
                 return i - 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
class Solution:
	
	"""
	初始化平方根区间[left, right]，包含x的平方根
	构造区间中点mid = (left + right) // 2
	
	while循环，不断缩减区间，终止条件为：left和right相邻：（(left + right) // 2 != left）
		如果mid的平方 <= x，说明，当前left较小，离x的平方根较远，令left = mid
		反之说明，当前right 较大，离x的平方根较远，令right = mid
	
	循环结束后，返回left，因为x的平方根的整数部分一定会落在left
	举例：x = 8时，循环结束后left = 2，right = 3
	"""
    def mySqrt(self, x: int) -> int:
        left = 1
        right = x
        mid = 0
        while((left + right) // 2 != left):
            mid = (left + right) // 2
            if(mid * mid <= x):
                left = mid
            else:
                right = mid
        return left

2025-09-18 删除排序链表中的重复元素

给定一个已排序的链表的头 head ， 删除所有重复的元素，每个元素只出现一次 。返回已排序的链表。
示例 1：
输入：head = [1,1,2]
输出：[1,2]

示例 2：
输入：**head = [1,1,2,3,3]
输出：[1,2,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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
	"""
	首先判断链表是否为空，空则原路返回
	
	初始化双指针cur_left和cur_right（分别为 head 和 head.next），不断向后移动，用于寻找重复的元素
	
	while 循环，循环条件：cur_left 和 cur_right 均不为 None
		if两指针的val不一样，两指针向后移动一步
		
		else再while循环判断：在cur_right还未到达链表末端时：
			如果cur_right.val == cur_right.next.val，说明有重复元素，cur_right 向后移动一步
			否则 break
			
		此时cur_left 和 cur_right 分别位于重复元素的开头和结尾，只需要将 cur_left.next 指向 cur_right.next，删除重复元素；同时 cur_right = cur_left.next，更新 cur_left 和 cur_right 的位置
		
	最后返回 head
	"""
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head == None:
            return head

        cur_left = head
        cur_right = head.next

        while(cur_left != None and cur_right != None):
            if(cur_left.val != cur_right.val):
                cur_left = cur_left.next
                cur_right = cur_right.next
            else:
                while(cur_right.next != None):
                    if(cur_right.val == cur_right.next.val):
                        cur_right = cur_right.next
                    else:
                        break

                cur_left.next = cur_right.next
                cur_right = cur_left.next
                
        return head

思考：双指针移动扫描重复元素，要注意指针的判空操作，尤其是右指针！

2025-09-19 合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 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
class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
		"""
		循环从后往前遍历，比较末尾两个数大小，较大的数插入尾端
		需要三个指针，一个确定 nums1 的位置，一个确定 nums2 的位置，最后一个确定尾插的位置
		
		退出循环后，检查 nums2 的数是否全部插入 nums1，没有的话，将剩余的插入
		"""
        nums1_cur = m - 1
        nums2_cur = n - 1

        index = m + n - 1

        while(nums1_cur >= 0 and nums2_cur >= 0):
            if(nums1[nums1_cur] > nums2[nums2_cur]):
                nums1[index] = nums1[nums1_cur]
                nums1_cur -= 1
            else:
                nums1[index] = nums2[nums2_cur]
                nums2_cur -= 1
            index -= 1

        while(nums2_cur >= 0):
            nums1[index] = nums2[nums2_cur]
            nums2_cur -= 1
            index -= 1

思考：错误的思路是从前往后顺序比较，这样会涉及到数组的移动。相反，可以从后往前比较数组元素，尾插较大的值。

2025-09-20 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

代码思路如下

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
	"""
	分解问题：先遍历左子树，然后添加节点值，然后遍历右子树
	递归终止条件：节点为 None
	"""
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        self.inorder(result, root)

        return result


    def inorder(self, result, root):
        if root is None:
            return result
        
        self.inorder(result, root.left)
        result.append(root.val)
        self.inorder(result, root.right)

2025-09-21 相同的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

代码思路如下：

非递归版本

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
import queue
class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
		
		"""
		如果都为空树，返回 True
		"""
        if(p == None and q == None):
            return True
        
        """
        如果都有根节点，将根节点加入队列，对两个树使用广度优先遍历
        当两个列表非空时，进行如下判断：
	        取出两个队列的节点，当前节点值是否相等？相等则继续，否则返回 False
	        
	        接下来比较当前节点的左节点
		        先判断是否全为非空
			        是，继续比较值大小
					    不相等则返回 False
						相等则将左节点
				接着判断左节点是否全为空？
					是，则 pass
				既不是全空，也不是全非空，那结果就是一个空，一个非空，这类直接返回 False
			
			右节点的判断逻辑与左节点类似
		
		while 循环中途没有结束，说明两棵树完全相同，返回 True
        """
        elif(p != None and q != None):

            list_p = queue.Queue()
            list_p.put(p)

            list_q = queue.Queue()
            list_q.put(q)

            while((not list_p.empty()) and (not list_q.empty())):
                temp_p = list_p.get()
                temp_q = list_q.get()

                if(temp_p.val != temp_q.val):
                    return False
                

                if(temp_p.left != None and temp_q.left != None):
                    if(temp_p.left.val != temp_q.left.val):
                        return False
                    else:
                        list_p.put(temp_p.left)
                        list_q.put(temp_q.left)
                elif(temp_p.left == None and temp_q.left == None):
                    print("pass1")
                    pass
                else:
                    return False



                if(temp_p.right != None and temp_q.right != None):
                    if(temp_p.right.val != temp_q.right.val):
                        return False
                    else:
                        list_p.put(temp_p.right)
                        list_q.put(temp_q.right)
                elif(temp_p.right == None and temp_q.right == None):
                    pass
                else:
                    return False

            return True
            
		"""
		如果只有一个有根节点，那后面就无需比较了
		"""
        else:
            return False

递归版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
	"""
	终止条件：如果 p 和 q 均为空返回 true，否则返回 false
	
	否则开始递归：判断两根节点是否相等，然后左子树和右子树是否相等
	"""
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:        
        if(p == None or q == None):
            return p == q
            
        return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

2025-09-22 对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

代码思路如下：

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
	"""
	终止条件：
		左右节点均为空，返回 Ture
		其中有一个为空，返回 False
		比较左右节点值，相等返回 True，反之 false
	
	递归：
		分别比较左子树和右子树
			比较 left 是否等于 right，不等的话直接返回就可以了。
			如果相当，比较 left 的左节点和 right 的右节点，再比较 left 的右节点和 right 的左节点

	"""
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        L = root.left
        R = root.right

        if(root == None):
            return True
        
        return self.recur(L, R)


    def recur(self, L: Optional[TreeNode], R: Optional[TreeNode]):
        if not (L or R):
            return True
        if not (L and R):
            return False
        if L.val!=R.val:
            return False

        return  self.recur(L.left, R.right) and self.recur(L.right, R.left)

2025-09-23 二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
	"""
	终止条件：节点为空返回 0
	递归调用： 返回（左右子树的最大深度，再加1）
	"""
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if(root == None):
            return 0

        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

2025-09-24 将有序数组转换为二叉搜索树

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。

代码思路如下：

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
	"""
	由于数组已经升序
	
	终止条件：
		数组长度为 0，返回空
		数组长度为 1，返回该节点
	
	切割数组：只需要找到数组中间项索引 root_index 的值 nums[root_index]作为 root
	
	递归调用：将中间项左边部分（小于根节点的值）传给左子树，右边部分传给右子树
	
	最后返回这棵树

	"""
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        
        if(len(nums) == 0):
            return None
        if(len(nums) == 1):
            return TreeNode(nums[0], None, None)

        root = TreeNode()
        root_index  = len(nums) // 2
        root.val = nums[root_index]

        root.left = self.sortedArrayToBST(nums[0:root_index])
        root.right = self.sortedArrayToBST(nums[root_index + 1:]) 

        return root

思考：构建平衡二叉搜索树，先确定根节点 root，然后用大于等于 root 的值构建右子树，反之为左子树，左右子树的构建采用递归

2025-09-25 平衡二叉树

给定一个二叉树，判断它是否是平衡二叉树（是指该树所有节点的左右子树的高度相差不超过 1）

代码思路如下：

不用保存每个节点的左右子树高度差，直接在递归中比较，如果差值绝对值大于 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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        if(root == None):
            return True

        return self.treeDepth(root) != -1
        
    def treeDepth(self, root: Optional[TreeNode]) -> int:
        if(root == None):
            return 0

        left_depth = self.treeDepth(root.left)
        right_depth = self.treeDepth(root.right)

        if left_depth == -1 or right_depth == -1 or abs(left_depth - right_depth) > 1:
            return -1
  
        return max(left_depth, right_depth) + 1

2025-09-26 二叉树的最小深度

给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：**叶子节点是指没有子节点的节点。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
	"""
	基本思路和求解最大深度类似，只是最后返回的时候可能会有如下几种情况：
	如果左右子树有一个为空，返回（非空子树的深度 + 1）
	否则返回（较小的深度 + 1）
	"""
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if(root == None):
            return 0

        left = self.minDepth(root.left)
        right = self.minDepth(root.right)

        if(left == 0 or right == 0):
            return max(left, right) + 1
        else:
            return min(left, right) + 1

2025-09-27 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 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
30
31
32
33
34
35
36
37
38
39
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
	"""
	用先序遍历递归获得每条根节点到叶子节点的路径
	使用 current_sum 变量记录路径和
	
	递归方法 pathSum
		终止条件：
			1. root为None
			
			2. 累加 current_sum：current_sum += root.val
				判断 累计路径和是否等于目标和，同时还是判断该节点是否为叶子节点（左右子树均为空）
					如果是，则返回 True
					否则 False
		
		递归调用：
			递归左子树和右子树，只要左右子树有一边能找得到该路径即可
	"""
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if(root == None):
            return False
        current_sum = 0
        return self.pathSum(root, targetSum, current_sum)

    def pathSum(self, root: Optional[TreeNode], targetSum: int, current_sum: int) :
        if(root != None):
            current_sum += root.val
            
            if(current_sum == targetSum and root.left == None and root.right == None):
                return True
                
            return self.pathSum(root.left, targetSum, current_sum) or self.pathSum(root.right, targetSum, current_sum)

        return False

2025-09-27加练：杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。

代码思路如下

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
class Solution:
	"""
	主方法用于传递前 numRows 行
	"""
    def generate(self, numRows: int) -> List[List[int]]:
        if(numRows == 1):
            return [[1]]
        
        return self.triangle(numRows)
	
	"""
	递归方法 triangle
		终止条件：numRows = 1，也就是只有一个数
		
		递归调用（原问题拆解成子问题）：
			所求当前行 = 在上一个当前行last_rows，插入一个新的list
			该 list 的构造方法可以归纳得到（略）
			返回新的 new_rows
	"""
    def triangle(self, numRows: int) -> List[List[int]]:
        if(numRows == 1):
            return [[1]]

        last_rows = self.triangle(numRows - 1)
        result_list = []

        if(last_rows == [[1]]):
            last_rows.append([1, 1])
            return last_rows

        result_list.append(1)
        for i in range(len(last_rows[-1]) - 1):
            result_list.append(last_rows[-1][i] + last_rows[-1][i + 1])
        result_list.append(1)
        last_rows.append(result_list)
        
        new_rows = last_rows
        return new_rows

2025-09-28 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
	"""
	时间倒序遍历价格，找到 buy 买入日期后的最大的股价sell_max
	因此在这一天买入的利润为 sell_max - prices[buy]
	更新 max_profit， 保留上一步求的最大的买入利润
	
	"""
    def maxProfit(self, prices: List[int]) -> int:
        sell_max = 0
        max_profit = 0

        for buy in reversed(range(len(prices))):
            sell_max = max(sell_max, prices[buy])
            max_profit = max(max_profit, sell_max - prices[buy])
        return max_profit

2025-09-29 验证回文串

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

示例 1：

输入: s = “A man, a plan, a canal: Panama”
输出：true
解释：“amanaplanacanalpanama” 是回文串。

示例 2：

**输入：s = “race a car”
输出：false
解释：”raceacar” 不是回文串。

示例 3：

**输入：s = “ “
输出：true
解释：在移除非字母数字字符之后，s 是一个空字符串 “” 。
由于空字符串正着反着读都一样，所以是回文串。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
	"""
	处理空串情况
	
	处理大小写，保留小写字母以及数字
	
	回文字符串特点：正反顺序一样
	"""
    def isPalindrome(self, s: str) -> bool:
        if(s == ' '):
            return True
        lower_s = s.lower()
        result = ''.join([char for char in lower_s if char.isalpha() or char.isdigit()])
        return result == result[::-1]

2025-09-29加练：只出现一次的数字

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

代码思路如下：

时间复杂度为 NlogN 的解法（空间复杂度 1）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
	"""
	只有一个元素的时候，返回该元素
	
	先将数组排序
	然后从头开始，两两比较 nums[i] 和 nums[i + 1]，如果不相等，则返回靠左的数
	如果指针 i 移动到了最后一个元素，说明前面的数都是出现了两次，则返回 nums[i]
	"""
    def singleNumber(self, nums: List[int]) -> int:
        if(len(nums) == 1):
            return nums[0]
        nums.sort()
        
        for i in range(0, len(nums), 2):
            if(i + 1 == len(nums)):
                return nums[i]
            if(nums[i] != nums[i + 1]):
                return nums[i]

时间复杂度为 N 的解法（空间复杂度 N）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
	"""
	字典记录每个数字的出现次数（key 为数，value 为出现次数）
	然后遍历字典，返回出现次数为 1 的那个数
	"""
    def singleNumber(self, nums: List[int]) -> int:
        
        hash_table = dict()
        for i in nums:
            hash_table[i] = hash_table.get(i, 0) + 1
            
        for k, v in hash_table.items():
            if(v == 1):
                return k

在时间复杂度不变的情况下，空间复杂度能否继续优化？

有的！那就是位运算，直接在原数组上计算，只需要一个 res 变量接收结果

1
2
3
4
5
6
7
8
9
10
11
 class Solution:
"""
异或运算的精髓在于，两个相同的数异或结果为 0，任意一个数和0️异或，结果不变
那么，这个数组里重复的数都是成对的，那么对所有的数都异或计算，相等的数都变成了0
最后剩下 未重复的数 和 0 异或，那结果就是要求的答案
"""
   def singleNumber(self, nums: List[int]) -> int:
       res = 0
       for num in nums:
           res ^= num
       return res

思考：怎么想到要使用位运算 -> 想要以”消消乐“的形式消除相同的数 -> 使用集合？占空间 ->尝试转换成二进制，使用异或运算，利用性质：两个相同的数异或结果为 0，任意一个数和0️异或，结果不变。

2025-09-30 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
	"""
	node_address 列表用于记录节点地址
	
	用一个指针从头遍历链表，当指针不为空时：
		如果指向的节点的地址不在列表中，则记录，并且指针后移一位
		否则检测到环，返回 True
		
	如果没在循环中返回，说明该链表没有环，返回 False
	"""
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        node_address = []
        pointer = head
        while(pointer != None):
            if(pointer not in node_address):
                node_address.append(pointer)
                pointer = pointer.next
            else:
                return True
        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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
	"""
	使用快慢指针，如果存在环，那么快指针一定会在后续”追“上慢指针
	否则，快指针一定会先到达末尾，快指针的 next 为空则说明无环
	"""
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if(head is None):
            return False

        first = head
        second = head.next

        if(second is None):
            return False
        
        while(second != None):
            if(second.next is None):
                return False
            if(first == second):
                return True
            first = first.next
            second = second.next.next

2025-10-01 二叉树的先序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        self.traversal(root, res)
        return res
    def traversal(self, root: Optional[TreeNode], res: List[int]):
        if(root is None):
            return
        res.append(root.val)
        self.traversal(root.left, res)
        self.traversal(root.right, res)

2025-10-02 二叉树的后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        self.postOrder(root, res)
        return res

    def postOrder(self, root: Optional[TreeNode], res: List[int]):
        if(root is None):
            return
        self.postOrder(root.left, res)
        self.postOrder(root.right,res)
        res.append(root.val)

2025-10-03 相交链表

代码思路如下：

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
	"""
	A,B 两个指针分别从 headA 和 headB 指针遍历
	当 A 和 B 不相等时，一直循环以下操作：
		A 不为空，一直移动 A，否则将 A 指向 headB
		B 不为空，一直移动 B，否则将 B 指向 headA
	退出循环的时候，AB 一定相等，要么都为空，要么指向同一个节点
	"""
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        A = headA
        B = headB
        while(A is not B ):
            if (A is not None ):
                A = A.next 
            else:
                A = headB
                
            if (B is not None):
                B = B.next
            else:
                B = headA
                
        return A

2025-10-04 Excel 表列名称

给你一个整数 columnNumber ，返回它在 Excel 表中相对应的列名称。

例如：

A -> 1
B -> 2
C -> 3
…
Z -> 26
AA -> 27
AB -> 28
…

代码思路如下：

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:
	"""
	一开始的思路是26 进制转换，但是发现 A-Z 是从 1 开始的，而非 0（坑的很，一直没注意）
	所以需要从 0 重新映射，构建一下词典
	且每次计算都需要将columnNumber 减 1
	
	最后倒序输出结果
	"""
    def convertToTitle(self, columnNumber: int) -> str:
        num_col = {0: 'A', 1: 'B', 2: 'C', 3: 'D', 4: 'E', 5: 'F', 6: 'G', 7: 'H', 8: 'I', 9: 'J', 10: 'K', 11: 'L', 12: 'M', 13: 'N', 14: 'O', 15: 'P', 16: 'Q', 17: 'R', 18: 'S', 19: 'T', 20: 'U', 21: 'V', 22: 'W', 23: 'X', 24: 'Y', 25: 'Z'}
        
        if(columnNumber < 26):
            columnNumber -= 1
            return num_col[columnNumber]

        ans = ''
        while(columnNumber > 0):
            columnNumber -= 1
            remainder = columnNumber % 26
            columnNumber //= 26
            ans += num_col[remainder]
            
        return ans[::-1]

2025-10-05 多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：

**输入：nums = [3,2,3]
输出：3

示例 2：

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

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
	"""
	简单的数字统计问题
	"""
    def majorityElement(self, nums: List[int]) -> int:
        dict = {}
        len_nums = len(nums) / 2
        res = 0
        for n in nums:
            dict[n] = dict.get(n, 0) + 1
        
        for k, v in dict.items():
            if(v > len_nums):
                res = k
        return res

有没有空间复杂度为O(1)的算法？有的，使用摩尔投票法

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

摩尔投票法

可以把整个过程想象成一场投票和战争：

  • 如果此时票数为 0，说明是刚开始或者此前的票数都已经抵消，需要选出新的 candidate。
  • 每个相同的数字都是给 candidate 的赞成票（vote++）。
  • 每个不同的数字都是反对票（vote--），它会和一张赞成票同归于尽。
  • 因为目标数字的数量超过了所有其他数字数量的总和，所以即使经历了一场惨烈的“内战”（互相抵消），最后剩下的也一定是这个目标数字。

2025-10-06 Excel 表列序号

给你一个字符串 columnTitle ，表示 Excel 表格中的列名称。返回 该列名称对应的列序号 。
例如：
A -> 1
B -> 2
C -> 3
…
Z -> 26
AA -> 27
AB -> 28
…

代码思路如下：

1
2
3
4
5
6
7
8
9
class Solution:
    def titleToNumber(self, columnTitle: str) -> int:
        power = len(columnTitle) - 1
        mapping = {'A':1, 'B':2, 'C':3, 'D':4, 'E':5, 'F':6, 'G':7, 'H':8, 'I':9,'J':10, 'K':11, 'L':12, 'M':13, 'N':14, 'O':15, 'P':16, 'Q':17, 'R':18, 'S':19, 'T':20, 'U':21, 'V':22, 'W':23, 'X':24, 'Y':25, 'Z':26}
        res = 0
        for letter in columnTitle:
            res += mapping[letter] * (26 ** power)
            power -= 1
        return res

2025-10-07 颠倒二进制

颠倒给定的 32 位有符号整数的二进制位。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
class Solution:
	"""
	转换成二进制字符串，反转字符串
	"""
    def reverseBits(self, n: int) -> int:
        bin_n = bin(n)[2:]
        zeros = 32 - len(bin_n)
        for i in range(zeros):
            bin_n = '0' + bin_n
        res = int(bin_n[::-1], 2)
        return res

2025-10-08 位1 的个数

给定一个正整数 n，编写一个函数，获取一个正整数的二进制形式并返回其二进制表达式中 设置位 的个数（也被称为汉明重量）。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
	"""
	转换成二进制字符串，对设置位为 1 的位置 count 计数
	"""
    def hammingWeight(self, n: int) -> int:
        bin_n = bin(n)[2:]
        length = len(bin_n)
        count = 0
        for i in range(length):
            if(bin_n[i] == '1'):
                count += 1
        return count

是否有更简单的算法？位运算

每次都与整数 n 的最后一位进行与运算，记录结果为1 的次数

1
2
3
4
5
6
7
class Solution:
    def hammingWeight(self, n: int) -> int:
        res = 0
        while n:
            res += n & 1
            n >>= 1
        return res

邪修：消除二进制末尾的 1

res 记录了进行了多少次消除操作。在二进制中，对整数 n 减 1 得到的 n-1，能把 n 的末尾 1 变成 0，同时末尾 1 的右边部分全变成 0，对 n 和 n-1 与运算能够消除末尾 1 及其右边的部分（每次都丢掉一部分）。循环计算直到 n 等于 0。

1
2
3
4
5
6
7
class Solution(object):
    def hammingWeight(self, n):
        res = 0
        while n:
            res += 1
            n &= n - 1
        return res

2025-10-09 移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

代码思路如下：

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
	"""
	设置 left 和 right 双指针从 head 和 head.next 开始
	如果 right 指针不为空，循环执行下面操作：
		如果left 的 val 等于目标值：
			头结点向后移动一步
			左右指针移动一步
		如果 right 的 val 等于目标值：
			断开链表，重新连接 left.next = right.next
		否则
			左右指针移动一步
			
	当退出循环时，如果最后只有一个节点时，还需要判断该节点是否等于目标值
		等于则删除该节点，也就是返回空节点（head.next）
	
	"""
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        if(head == None):
            return head

        left = head
        right = head.next

        while(right != None):
            if(left.val == val):
                head = head.next
                left = left.next
                right = right.next
            elif(right.val == val):
                left.next = right.next
            else:
                left = left.next
                right = right.next
                
        if(head.val == val):
            return head.next
            
        return head

2025-10-10 同构字符串

给定两个字符串 s 和 t ，判断它们是否是同构的。
如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。
每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

代码思路如下：

字典法

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:
	"""
	一列一列的逐个字符检查 s 到 t 的映射
	如果 s 没出现在字典里，则加入
	如果出现则比较 t 的值是否等于 s 的映射，不等于说明不是唯一映射，返回 False
	
	t 到 s 的映射同理
	"""
    def isIsomorphic(self, s: str, t: str) -> bool:

        mapping_a_to_b = {}
        for i in range(len(s)):
            if(mapping_a_to_b.get(s[i]) is None):
                mapping_a_to_b[s[i]] = t[i]
            elif(mapping_a_to_b.get(s[i]) != t[i]):
                return False

        mapping_b_to_a = {}
        for i in range(len(s)):
            if(mapping_b_to_a.get(t[i]) is None):
                mapping_b_to_a[t[i]] = s[i]
            elif(mapping_b_to_a.get(t[i]) != s[i]):
                return False
    
        return True

2025-10-11 反转链表

代码思路如下：

递归

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        return self.reverseList_with_tail(head)[0]
    def reverseList_with_tail(self, head):
        """
        反转链表并同时返回头节点和尾节点
        基本情况：空链表
        基本情况：只有一个节点
        递归反转剩余部分
        将当前节点连接到尾部
        新头节点不变，新尾节点变成当前节点
        """
        if not head:
            return None, None
            
        if not head.next:
            return head, head
        
        new_head, new_tail = self.reverseList_with_tail(head.next)
        
        new_tail.next = head
        head.next = None
        
        return new_head, head

迭代（头插法）

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
	"""
	创建一个空链表res_list_head
	pointer从头遍历原链表
	先保存 pointer 后面的节点（temp = pointer.next），现在要将 pointer 从原链表断开
	每次选一个节点插入res_list_head的头结点
	将新的头节左移（res_list_head = pointer）
	移动 pointer
	"""
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        res_list_head = None
        pointer = head

        if(pointer is None):
            return None

        while(pointer):
            temp = pointer.next
            pointer.next = res_list_head
            res_list_head = pointer
            pointer = temp
            
        return res_list_head

2025-10-12 存在重复元素

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

代码思路如下：

但是很耗时。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
	"""
	字典统计，如果频次大于等于 2 就返回 True
	"""
    def containsDuplicate(self, nums: List[int]) -> bool:
        if(len(nums) == 1):
            return False

        count = {}
        for i in range(len(nums)):
            count[nums[i]] = count.get(nums[i], 0) + 1
            if(count[nums[i]] >= 2):
                return True
        return False

能否继续优化？答案是没有，不过另外一种思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
	"""
	数组排序
	重复出现的元素一定相邻，只需要用两个相邻指针扫描比较即可
	"""
    def containsDuplicate(self, nums: List[int]) -> bool:
        length = len(nums)
        if(length == 1):
            return False

        sorted_nums = sorted(nums)
        left = 0
        right = 1
        while(right != length):
            if(sorted_nums[left] == sorted_nums[right]):
                return True
            left += 1
            right += 1
        return False

2025-10-13 存在重复元素（进阶版）

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
	"""
	只需要在排序的时候记录原数组的索引顺序，然后在比较的时候判断是否满足条件即可
	"""
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        if(k == 0):
            return False

        length = len(nums)
        indexed_nums = enumerate(nums)
        sorted_nums = sorted(indexed_nums, key = lambda x: x[1])

        left = 0
        right = 1
        while(right != length):
            abs_index = abs(sorted_nums[left][0] - sorted_nums[right][0])
            if((sorted_nums[left][1] == sorted_nums[right][1]) and abs_index <= k):
                return True
            left += 1
            right += 1
        return False

但是上述方法的运行时间较长（300ms），是否能优化？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
	"""
	count字典：
		键：当前数字
		值：数字的索引 list
		
	统计数字的索引，同时 list 的长度表示出现频次，≥2 即为重复元素
	当出现重复元素时，判断条件是否成立，成立返回 true, 否则删除第一个索引
	"""
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        if(len(nums) == 1):
            return False

        count = {}
        for i in range(len(nums)):
            count[nums[i]] = count.get(nums[i], [])
            count[nums[i]].append(i)
            if(len(count[nums[i]]) >= 2):
                if(abs(count[nums[i]][0] - count[nums[i]][1]) <= k):
                    return True
                del count[nums[i]][0]
        return False

为什么要条件不成立的时候都要删除第一个索引？因为如果存在重复数字的索引差值≤k，这意味着，两个数字的距离是最近的（距离为 k），也就是说我们每次要从左至右遍历，当前数字 x 的索引和 x 上一次出现的索引进行比较。

上述方法的运行时间降到了 100ms，还能优化么？

这次我们直接使用哈希表来存储每个数字 x 的上一次出现的位置的索引：last_index，符合条件返回 true，不符合则更新 x 的 last_index。

1
2
3
4
5
6
7
8
9
class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        last_index = {}

        for index, x in enumerate(nums):
            if(x in last_index and index - last_index[x] <= k):
                return True
            last_index[x] = index
        return False

思考：其实这两次优化的思想都是一样的，从左往右比较 当前 x 的索引和上一次最近 x 的索引的距离是否≤k，最后代码的执行速度有差异，是因为第一个优化，需要对 list 反复删除元素。第二个优化直接使用哈希表，效率自然高。

2025-10-14 完全二叉树的节点个数

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（从第 0 层开始），则该层包含 1~ 2h 个节点。

代码思路如下：

最简单的递归法

1
2
3
4
5
6
7
8
9
10
11
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if(root == None):
            return 0
        return self.countNodes(root.left) + self.countNodes(root.right) + 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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
	"""
	这是一个计算子树高度的方法，因为完全二叉树的性质，只需要一直检查 root 的 left 节点的状态来计算子树高度
	"""
    def height(self, root: Optional[TreeNode]) -> int:
        height = 0
        while(root):
            height += 1
            root = root.left
        return height
    """
	每次都需要判断左右子树的高度关系，对非满二叉树的子树继续递归，满二叉树的子树直接计算节点数。
    """
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if(root == None):
            return 0
        
        left_tree_height = self.height(root.left)
        right_tree_height = self.height(root.right)

        if(left_tree_height > right_tree_height):
            return self.countNodes(root.left) + 2 ** right_tree_height
        else:
            return self.countNodes(root.right) + 2 ** left_tree_height

那么优化后的递归的时间复杂度是多少呢？

首先每层都要计算左右子树高度，这一部分时间为 logn，一共要递归 logn 次（也就是树的高度），所以时间复杂的是 logn 的平方。
思考：理解完全二叉树的性质，才能优化递归，减少调用次数，从而降低时间复杂度。

2025-10-15 用队列模拟栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class MyStack:

    def __init__(self):
        self.assist_list = []
        self.major_list = []
	"""
	只需要一个辅助队列，用于保存 push 进来的元素，然后将辅助队列和主队列相加即可（注意辅助队列在加号前面，其实正常来讲应该用队列的pop 方法一个一个弹出元素，并加入到辅助队列，然后再将两个队列的引用互换。
	"""
    def push(self, x: int) -> None:
        self.assist_list.append(x)
        self.major_list = self.assist_list + self.major_list
        self.assist_list = []
        return self.major_list
    def pop(self) -> int:
        return self.major_list.pop(0)
    def top(self) -> int:
        return self.major_list[0]

    def empty(self) -> bool:
        return len(self.major_list) <= 0

2025-10-16 翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

代码思路如下：

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
	"""
	递归，递归左右子树，得到翻转的子树
	然后将左右子节点交换
	返回节点
	"""
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if (root is None ):
            return None
        #temp = root.left 
        #root.left = root.right 
        #root.right = temp 
        
        #self.invertTree(root.left)
        #self.invertTree(root.right)
        
        left = self.invertTree(root.left)
        right = self.invertTree(root.right)
        root.left = right 
        root.right = left 
        
        return root

2025-10-17 汇总区间

给定一个  无重复元素 的 有序 整数数组 nums 。
区间 [a,b] 是从 a 到 b（包含）的所有整数的集合。
返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个区间但不属于 nums 的数字 x 。
列表中的每个区间范围 [a,b] 应该按如下格式输出：

  • "a->b" ，如果 a != b
  • "a" ，如果 a == b

示例 1：
输入：nums = [0,1,2,4,5,7]
输出：[“0->2”,”4->5”,”7”]
**解释：区间范围是：
[0,2] –> “0->2”
[4,5] –> “4->5”
[7,7] –> “7”

示例 2：
输入：nums = [0,2,3,4,6,8,9]
输出：[“0”,”2->4”,”6”,”8->9”]
**解释：区间范围是：
[0,0] –> “0”
[2,4] –> “2->4”
[6,6] –> “6”
[8,9] –> “8->9”

代码思路如下：

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:
	"""
	双指针 left，right 滑动确定汇总区间，只要右区间nums[right - 1] + 1 == nums[right]，一直移动右区间；区间类型有两种，一种是只有一个数字，这种情况满足 left + 1 == right；另外一种则是多个连续的数字。while 循环里的 if 语句分别对应上述指针滑动逻辑以及判断区间类型
	在 while 循环结束后，还需要对最后指针的停留位置再判断，区间类型是一个数字还是多个数字
	"""
    def summaryRanges(self, nums: List[int]) -> List[str]:
        left = 0
        right = 1
        nums_length = len(nums) 
        result_list = []
        
        if (nums_length == 0):
            return result_list 
        
        while (right < nums_length):
            if (nums[right - 1] + 1 == nums[right]):
                right += 1
            elif(left + 1 == right):
                result_list.append(str(nums[left]))
                left = right
                right = right + 1
            else:
                result_list.append(str (nums[left])  + "->" + str(nums[right - 1]))
                left = right 
                right = right + 1
        if (left + 1 == right):
            result_list.append(str(nums[left]))
        else:
            result_list.append(str (nums[left])  + "->" + str(nums[right - 1]))
        return result_list

2025-10-18 二的幂

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。
如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。

代码思路如下：

1
2
3
4
5
6
7
8
9
class Solution:
	"""
	转换成二进制字符串，然后判断是否满足最高位为 1，且其他位均为 0。该方法执行速度较慢，因为涉及字符串的拼接
	"""
    def isPowerOfTwo(self, n: int) -> bool:
        bin_num = bin(n)[2:]
        if(bin_num[0] == "1" and bin_num[1:] == (len(bin_num) - 1) * "0"):
            return  True 
        return False

超快的位运算！

1
2
3
4
5
6
7
class Solution:
	"""
	只需要判断 n 是否大于零，以及 n 和 n-1 的 且运算 是否为0
	原理：如果 n 是 2 的幂，那么 n - 1 的二进制会和 n 的二进制完全相反，此时按位做&运算结果一定为 0
	"""
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and n & n - 1 == 0

2025-10-19 用栈实现队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class MyQueue:

    def __init__(self):
        self.A, self.B = [], []

    def push(self, x: int) -> None:
        self.A.append(x)

    def pop(self) -> int:
        peek = self.peek()
        self.B.pop()
        return peek

    def peek(self) -> int:
        if self.B: return self.B[-1]
        if not self.A: return -1
        # 将栈 A 的元素依次移动至栈 B
        while self.A:
            self.B.append(self.A.pop())
        return self.B[-1]

    def empty(self) -> bool:
        return not self.A and not self.B

2025-10-20 判断该链表是否为回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 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
30
31
32
33
34
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
	"""
	先使用快慢指针寻找链表的中间节点
	然后使用头插法得到原链表的后半段的翻转链表reversed_list_head
	只需要比较原链表的前半段是否和reversed_list_head相等即可，全部相等即为回文链表
	"""
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        fast = head
        slow = head

        while(fast and fast.next):
            fast = fast.next.next
            slow = slow.next
        mid = slow

        reversed_list_head = None

        while(mid is not None):
            temp = mid.next
            mid.next = reversed_list_head
            reversed_list_head = mid
            mid = temp
        
        while(reversed_list_head):
            if reversed_list_head.val != head.val:
                return False
            head = head.next
            reversed_list_head = reversed_list_head.next
        return True

2025-10-21 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的 字母异位词（字母异位词是通过重新排列不同单词或短语的字母而形成的单词或短语，并使用所有原字母一次。）。

代码思路如下：

1
2
3
4
5
6
7
8
9
class Solution:
	"""
	朴素的方法，比较字母的排序
	"""
    def isAnagram(self, s: str, t: str) -> bool:
        ss = "".join(sorted(s))
        tt = "".join(sorted(t))

        return ss == tt

更优的方法

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:
	"""
	使用字典记录字母的出现次数，在 s 中出现一次就+1，在 t 中出现就-1。如果满足字母异位，那么最后字典中所有字母的出现字数应该均为 0
	"""
    def isAnagram(self, s: str, t: str) -> bool:
        letter_count = {}

        if(len(s) != len(t)):
            return False

        for char in s:
            if(letter_count.get(char) is None):
                letter_count[char] = 1
                continue
            letter_count[char] += 1

        for char in t:
            if(letter_count.get(char) is None):
                letter_count[char] = 1
                continue
            letter_count[char] -= 1
        
        for val in letter_count.values():
            if(val != 0):
                return False
        return True

2025-10-22 二叉树的所有路径

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。

代码思路如下：

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        res = []
        self.findAllPaths(root, '', res)
        return res
	
	"""
	如果节点为空则返回
	
	否则构建路径，将当前节点加入
	
	再判断当前节点是否为叶子节点，是则将路径添加至 res，否则在路径末尾添加 ->
	
	递归左子树和右子树
	"""
    def findAllPaths(self, root: Optional[TreeNode], path: str, res: List[str]) -> None:
        if(root is None):
            return

        path += str(root.val)

        if(root.left is None and root.right is None):
            return res.append(path)

        path += '->'

        self.findAllPaths(root.left, path, res)
        self.findAllPaths(root.right, path, res)

2025-10-23 各位相加

给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。返回这个结果。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
	"""
	不断分解各个位数，各位加和判断是否满足条件
	"""
    def addDigits(self, num: int) -> int:
        while(num >= 10):
            next_num = 0
            while(num != 0):
                next_num = next_num + (num % 10)
                num //= 10
            num = next_num
        return num

O(1)时间复杂度的解法，数学法

1
2
3
4
5
6
7
8
class Solution:
	"""
	涉及到数学推导。。。
	通过找规律和归纳可以发现对一个数模 9 就是结果
	但是如果是9的倍数，最后取余的结果会是 0 而不是 9，因此需要把数 -1 取余再 +1，这样才正确
	"""
    def addDigits(self, num: int) -> int:
        return (num - 1) % 9 + 1 if num else 0

2025-10-24 丢失的数字

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

示例 1：

输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。

示例 2：

输入：nums = [0,1]
输出：2
解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
class Solution:
	"""
	先求出区间数总和nums_sum，然后循环减去所有出现的数，最后的结果就是没有出现的数
	"""
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        nums_sum = ((1 + n) * n) // 2
        result = 0
        for i in range(0, n):
            nums_sum -= nums[i]
        return nums_sum

异或法（用于寻找非重复元素）

按位异或运算 ⊕ 满足交换律和结合律，且对任意整数 x 都满足 x⊕x=0 和 x⊕0=x。那么可以，在原数组后面再加入[0, n]区间的所有数，这样数组一共有 2n + 1个数，其中重复的数通过异或均变为 0，剩下的就是丢失的数。这里使用枚举，用索引表示[0, n]区间的所有数（除了 n），然后将 nums 的每个数和索引进行异或，最后返回时还需要和 n 异或，因为索引最大值为 n - 1。

1
2
3
4
5
6
7
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        xor = 0
        n = len(nums)
        for i, num in enumerate(nums):
            xor ^= i ^ num
        return xor ^ n

2025-10-25 第一个错误的版本

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

代码思路如下：

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
# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
	"""
	为了减少调用 api 次数，首先想到二分法。
	初始化：
		left 为第一个版本
		right 为最后一个版本
		
	循环：
		取中间版本mid_version
		如果mid_version为错误版本，说明最后一个正确版本在mid_version之前，更新 right
		如果mid_version为正确版本，说明第一个错误版本在mid_version之后，更新 left
	
	left 和 right 距离不断缩小，退出循环后，最后 left 指向首个错误版本
	"""
    def firstBadVersion(self, n: int) -> int:
        left = 1
        right = n
        while(left <= right):
            mid_version = (left + right) // 2
            if(isBadVersion(mid_version)):
                right = mid_version - 1
            else:
                left = mid_version + 1
        return left

2025-10-26 单词规律

给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。

这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。具体来说：

  • pattern 中的每个字母都 恰好 映射到 s 中的一个唯一单词。
  • s 中的每个唯一单词都 恰好 映射到 pattern 中的一个字母。
  • 没有两个字母映射到同一个单词，也没有两个单词映射到同一个字母。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
	"""
	如果模式长度和单词个数不一致，直接返回 False
	
	如果模式匹配，那么单词的去重集合长度=模式的去重集合长度=模式和单词的匹配的去重集合长度
	"""
    def wordPattern(self, pattern: str, s: str) -> bool:
        s_list = s.split()

        if(len(pattern) != len(s_list)):
            return False

        return len(set(zip(pattern, s_list))) == len(set(pattern)) == len(set(s_list))

2025-10-27 区域和检索 - 数组不可变

给定一个整数数组  nums，处理以下类型的多个查询:

  1. 计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的 和 ，其中 left <= right
    实现 NumArray 类：
  • NumArray(int[] nums) 使用数组 nums 初始化对象
  • int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的 总和 ，包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + ... + nums[right] )

示例 1：
输入：
[“NumArray”, “sumRange”, “sumRange”, “sumRange”]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出：
[null, 1, -1, -3]
解释：
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1))
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class NumArray:
	"""
	最直接的方法，直接累加，但是耗时很长
	"""
    def __init__(self, nums: List[int]):
        self.nums = nums

    def sumRange(self, left: int, right: int) -> int:
        s = self.nums
        res = 0
        
        for i in range(left, right):
            res += s[i]
        res += s[right]
        return res

# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(left,right)

更优化的方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class NumArray:
	"""
	区间[left, right]的元素和 可以转换为 前 right + 1 个元素和 - 前 left 个元素和
	
	那么只需要求出数组长度为 n 的 nums 的前0，1，2 。。。， n 个元素和（一张表）：
		前 n 个元素和 =  前 n - 1 个元素和 + 当前元素
	
	根据给定区间查表即可
	"""
    def __init__(self, nums: List[int]):
        top_n_sum = [0] * (len(nums) + 1)

        for i in range(len(nums)):
            top_n_sum[i + 1] = top_n_sum[i] + nums[i]
        self.top_n_sum = top_n_sum

    def sumRange(self, left: int, right: int) -> int:
        return self.top_n_sum[right + 1] - self.top_n_sum[left]


# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(left,right)

2025-10-28 3 的幂

给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。
整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3x

代码思路如下：

1
2
3
4
5
6
7
class Solution:
	找到数据范围内最大的 3 的幂，然后判断 n 是否大于0 且最大的 3 幂次方 % n 为 0 
    def isPowerOfThree(self, n: int) -> bool:
        i = 0
        while(3 ** i <= 2 ** 31 -1):
            i += 1
        return n > 0 and (3 ** i) % n == 0

2025-10-29 比特位计数

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def countBits(self, n: int) -> List[int]:
        ans = [0, 1]

        if(n == 0):
            return [ans[0]]
        elif(n == 1):
            return ans

        i = 2
        while(i <= n):
            if(i % 2 == 0):
                temp = ans[i // 2]
                ans.append(temp)
            else:
                ans.append(ans[i - 1] + 1)
            i += 1
        return ans

这题有点 tricky，首先需要写出几个数观察一下：

数字 比特位为1的个数（记为A）
0 0
1 1
2 1
3 2
4 1
5 2
6 2
7 3
8 1
可以发现，一个偶数的 A 值等于它除以2的那个数的 A 值，比如 6 的 A 值就是 3 的 A 值，均为 2，以此类推；一个奇数的 A 值就是它上一个偶数的 A 值再加一 ，比如 5 的 A 值等于 4 的 A 值 + 1，也就是 2。运用动态规划思想，能够从 0 逐步求出直到 n 的 A 值。只需要简单判断当前数的奇偶性即可。

2025-10-30 4的幂

代码思路如下：

1
2
3
4
5
6
7
8
9
10
class Solution:
	"""
	如果 4 的幂首先一定是 2 的幂：(n & (n - 1) == 0)
	其次最高位 1 的位置一定要在奇数位
	和二进制数0xaaaaaaaa（这个数奇数位均为 0，偶数位均为 1） &运算，如果结果为 0 说明 1 在奇数位，反之在偶数位
	"""
    def isPowerOfFour(self, n: int) -> bool:
        if(n < 0):
            return False
        return n > 0 and (n & (n - 1) == 0) and (n & 0xaaaaaaaa == 0)

2025-10-31 反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
	"""
	双指针交换 head 和 tail，循环终止条件为head >= tail
	"""
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        temp = ''
        head = 0
        tail = len(s) - 1
        while(head < tail):
            temp = s[tail]
            s[tail] = s[head]
            s[head] = temp
            head += 1
            tail -= 1

单指针写法：

头尾指针的值相加一定等于len(s) - 1，那么如果 head 为 i，则 tail 为 -i-1，上述代码可改写为如下形式：

1
2
3
4
class Solution:
    def reverseString(self, s: List[str]) -> None:
        for head in range(len(s) // 2):
            s[head], s[-head - 1] = s[-head - 1], s[head]

2025-11-01 反转字符串中的元音字母

给你一个字符串 s ，仅反转字符串中的所有元音字母，并返回结果字符串。
元音字母包括 'a'、'e'、'i'、'o'、'u'，且可能以大小写两种形式出现不止一次。

代码思路如下：

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:
	"""
	vowels记录大小写的元音字母
	两个 while 循环：left 和 right 双指针分别从头和尾寻找元音字母（注意下标越界！）
	
	退出循环时对应两种情况：
		left < right，可以交换
		left >= right，可能不存在可交换的元音字母 或者 在交换完最后一对元音字母后两个指针第一次“错”开，此时直接退出整个循环
		
	每找到一对就交换位置
	
	然后双指针各自移动
	"""
    def reverseVowels(self, s: str) -> str:
        vowels = ['A', 'a', 'E', 'e', 'I', 'i', 'O', 'o', 'U', 'u']
        res = list(s)
        left = 0
        right = len(res) - 1

        while(left < right):
            while(res[left] not in vowels):
                left += 1
                if(left == len(res)):
                    break
            while(res[right] not in vowels):
                right -= 1
                if(right == -1):
                    break
            if(left >= right):
                break
            temp = res[left]
            res[left] = res[right]
            res[right] = temp

            left += 1
            right -= 1
        return ''.join(res)

2025-11-02 两个数组的交集

给定两个数组 nums1 和 nums2 ，返回 它们的 交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

代码思路如下：

暴力遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
	"""
	两个数组的数两两比较，如果相等且此前出现在结果集，则加入结果集
	
	但是如果遇到数组有大量重复，代码执行时间会很久
	"""
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        res = []
        for n1 in nums1:
            for n2 in nums2:
                if(n1 == n2 and n1 not in res):
                    res.append(n1)
        return res

利用集合，实现一次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
	"""
	选择一个参考数组 nums1，转换为 set1
	
	遍历 nums2，如果其在 set1 中，将该数加入结果列表 res，同时在 set1 移除该数，这样子能避免重复
	"""
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        set1 = set(nums1)
        res = []
        for n2 in nums2:
            if(n2 in set1):
                res.append(n2)
                set1.remove(n2)
        return res

2025-11-03 两个数组的交集②

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

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

示例 2:
**输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
	"""
	统计 nums1 所有元素的个数
	
	遍历 nums2，如果 nums2 的元素出现在 nums1 中且个数＞0：
		加入结果集，同时其元素个数 - 1
	
	如果个数变为 0，说明后续某元素出现次数已经大于原先 nums1 统计的个数了，之后便不再添加进结果集
	"""
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        num1_cnt = Counter(nums1)
        res = []
        for num in nums2:
            if(num1_cnt[num] > 0):
                res.append(num)
                num1_cnt[num] -= 1
        return res

2025-11-04 有效的完全平方数

给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。
不能使用任何内置的库函数，如  sqrt 。

提示：

  • 1 <= num <= 231 - 1

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
	"""
	二分法
	"""
    def isPerfectSquare(self, num: int) -> bool:
        if(num == 1):
            return True

        left = 1
        right = num

        while(left <= right):
            mid = (left + right) // 2
            sq = mid * mid
            if(sq == num):
                return True
            elif(sq < num):
                left = mid + 1
            else:
                right = mid - 1
        return False

2025-11-05 猜数字大小

我们正在玩猜数字游戏。猜数字游戏的规则如下：

我会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。（我选的数字在整个游戏中保持不变）。

如果你猜错了，我会告诉你，我选出的数字比你猜测的数字大了还是小了。

你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有三种可能的情况：

  • -1：你猜的数字比我选出的数字大 （即 num > pick）。
  • 1：你猜的数字比我选出的数字小 （即 num < pick）。
  • 0：你猜的数字与我选出的数字相等。（即 num == pick）。

返回我选出的数字。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# The guess API is already defined for you.
# @param num, your guess
# @return -1 if num is higher than the picked number
#          1 if num is lower than the picked number
#          otherwise return 0
# def guess(num: int) -> int:

class Solution:
	"""
	二分法，但是时间较长。。。
	"""
    def guessNumber(self, n: int) -> int:
        left = 1
        right = 2 ** 31 -1
        while(left <= right):
            mid = (left + right) // 2
            if(guess(mid) == 0):
                return mid
            elif(guess(mid) == -1):
                right = mid - 1
            else:
                left = mid + 1

2025-11-06 赎金信

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
	"""
	与题目：两个数组的交集②的思路类似
	"""
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        magazine_cnt = Counter(magazine)
        for letter in ransomNote:
            if(magazine_cnt[letter]):
                if(magazine_cnt[letter] < 0):
                    return False
                magazine_cnt[letter] -= 1
            else:
                return False
        return True

2025-11-07 字符串中的第一个唯一字符

给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
	"""
	用字典 char_cnt 按照字符出现的顺序 记录各个字符的 首次索引位置 和 累计出现次数
	
	遍历 char_cnt，如果累计出现次数为 1，返回第一个唯一字符的索引位置
	
	否则最后返回-1
	
	"""
    def firstUniqChar(self, s: str) -> int:
        char_cnt = {}
        index = 0
        for char in s:
            if(char in char_cnt):
                char_cnt[char][1] += 1
            else:
                char_cnt[char] = [index, 1]
            index += 1
        for char in char_cnt:
            if(char_cnt[char][1] == 1):
                return char_cnt[char][0]
        return -1

更优雅的写法（参考某大神）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
	"""
	第一遍遍历：
		将只出现过一次的字符标记为 True
		出现过两次以上的均标记为 False
	
	第二次遍历：
		找到第一个标记为 True 的字符，并且返回其索引
	"""
    def firstUniqChar(self, s: str) -> int:
        dic = {}
        for letter in s:
            dic[letter] = not letter in dic
        for index, letter in (enumerate(s)):
            if(dic[letter]):
                return index
        return -1

思考：

学习到了一个新的写法：

1
dic[letter] = not letter in dic

这一句表示，如果 letter 这个键没有在 dic出现，则创建该键，并且标记成 True，反之标记为 False。因此能区分只出现一次和多次的字符。

2025-11-08 判断子序列

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

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

代码思路如下：

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
class Solution:
	"""
	双指针
	遍历 t 字符串：
		如果字符匹配，则双指针各向后移动，否则只移动 t 的指针
		如果 s 已经遍历完了（s_index == s_len），说明 s 是 t 的子序列，直接返回 True
	否则返回 False
	"""
    def isSubsequence(self, s: str, t: str) -> bool:
        s_len = len(s)
        t_len = len(t)

        s_index = 0
        t_index = 0

        if(s_len > t_len):
            return False
        if(s_len == 0):
            return True
        while(t_index < t_len):
            if(s[s_index] == t[t_index]):
                s_index += 1
                t_index += 1
            else:
                t_index += 1
            if(s_index == s_len):
                return True
        return False

2025-11-09 左叶子之和

给定二叉树的根节点 root ，返回所有左叶子之和。

代码思路如下：

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
	"""
	先判断当前节点的左子树是否为叶子节点，如果是则将值加入 left_sum
	否则递归左子树
	然后递归右子树
	
	返回左右子树的左叶子之和
	"""
    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        return self.recursive(root)

    def recursive(self, root: Optional[TreeNode]) -> int:
        if(root is None):
            return 0
        
        left_sum = 0
        if(root.left is not None and root.left.left is None and root.left.right is None):
            left_sum = root.left.val
        else:
            left_sum = self.recursive(root.left)

        right_sum = self.recursive(root.right)

        return left_sum + right_sum

2025-11-10 最长回文串

给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的 回文串 的长度。

在构造过程中，请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。

代码思路如下：

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
class Solution:
	"""
	回文字符串特点：除了中间字符会出现奇数次或者偶数次，两边的字符均出现偶数次
	
	那么可以统计每个字符的次数，然后（ans 保存加和结果）偶数次全部加和，对于奇数次的字符，应该先 -1 再加和，并且用 odd_count 标记是否出现奇数次的字符
	
	经过上面的计算，剩下就是全部奇数次字符多出来的字符，每个字符都剩一个，可以随便选一个放在回文串中间。（odd_count）
	
	最后返回加和结果 ans + odd_count
	"""
    def longestPalindrome(self, s: str) -> int:
        letter_count = {}
        for letter in s:
            if(letter in letter_count):
                letter_count[letter] += 1
            else:
                letter_count[letter] = 1
        odd_count = 0
        ans = 0
        for count in letter_count.values():
            if(count % 2 != 0):
                odd_count = 1
                ans += (count - 1)
            else:
                ans += count

        return ans + odd_count

2025-11-11 Fizz Buzz

给你一个整数 n ，返回一个字符串数组 answer（下标从 1 开始），其中：

  • answer[i] == "FizzBuzz" 如果 i 同时是 3 和 5 的倍数。
  • answer[i] == "Fizz" 如果 i 是 3 的倍数。
  • answer[i] == "Buzz" 如果 i 是 5 的倍数。
  • answer[i] == i （以字符串形式）如果上述条件全不满足。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def fizzBuzz(self, n: int) -> List[str]:
        res = []
        for i in range(n):
            if((i + 1) % 15 == 0):
                res.append('FizzBuzz')
            elif((i + 1) % 3 == 0):
                res.append('Fizz')
            elif((i + 1) % 5 == 0):
                res.append('Buzz')
            else:
                res.append(str(i + 1))
        return res

2025-11-12 第三大的数

给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。

代码思路如下（时间复杂度 n 方）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
	"""
	先获取原数组最大的数 max_num
	
	然后循环两次数组，剔除第一大和第二大的数
	如果在循环没结束时候数组为空了，说明没有第三大的数，则返回 max_num
	
	否则循环结束后返回修改后的数组的最大数
	"""
    def thirdMax(self, nums: List[int]) -> int:
        nums_list = nums
        max_num = max(nums_list)

        for i in range(2):
            temp_max_num = max(nums_list)
            while(temp_max_num in nums_list):
                nums_list.remove(temp_max_num)
            if(nums_list == []):
                return max_num
                
        return max(nums_list)

时间复杂度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
33
34
35
36
37
38
39
class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        nums_list = nums

        if(len(nums_list) == 1):
            return nums_list[0]
        if(len(nums_list) == 2):
            return max(nums_list)
            
	"""
	top_3_nums:一个大小为3且不重复的【升序】数组。（前三大的数）
	"""
        pointer = 0
        top_3_nums = []
        while(len(top_3_nums) < 3 and pointer < len(nums_list)):
            if(nums_list[pointer] not in top_3_nums):
                top_3_nums.append(nums_list[pointer])
            pointer += 1
        top_3_nums.sort()
	"""
	接着遍历剩下的数，根据大小关系更新这个三元组：新元素替换最小值、中间值或依次替换所有值。
	"""
        for i in range(pointer, len(nums_list)):
            if(top_3_nums[0] < nums_list[i] < top_3_nums[1]):
                top_3_nums[0] = nums_list[i]

            elif(top_3_nums[1] < nums_list[i] < top_3_nums[2]):
                top_3_nums[0] = top_3_nums[1]
                top_3_nums[1] = nums_list[i]
            elif(top_3_nums[2] < nums_list[i]):
                top_3_nums[0] = top_3_nums[1]
                top_3_nums[1] = top_3_nums[2]
                top_3_nums[2] = nums_list[i]
	"""
	最终若不足三个不同数字则返回最大值，否则返回列表中的第一个数即第三大的数。
	"""
        if(len(top_3_nums) < 3):
            return max(top_3_nums)
        return top_3_nums[0]

2025-11-13 字符串相加

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。

代码思路如下：

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
class Solution:
	"""
	第一步，将位数较短的数前面用 0 补齐
	第二步（循环），从个位开始，依次计算结果位（按位相加）和 进位
	第三步，第二步结束后需要判断最高位是否有进位产生，carry 为 1 说明有进位，否则无
	"""
    def addStrings(self, num1: str, num2: str) -> str:
        num1_len = len(num1)
        num2_len = len(num2)
        
        if(num1_len > num2_len):
            num2 = '0' * (num1_len - num2_len) + num2
        else:
            num1 = '0' * (num2_len - num1_len) + num1
        
        pointer = len(num1) - 1
        carry = 0
        ans = ''
        
        while(pointer >= 0):
            n1 = int(num1[pointer])
            n2 = int(num2[pointer])

            temp_sum = n1 + n2 + carry

            carry = temp_sum // 10
            res = temp_sum % 10
            
            ans = str(res) + ans
            pointer -= 1
        return '1' + ans if carry else ans

不补齐 0 的写法

在循环中，指针索引小于 0 的时候说明，较短的数的高位需要补 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        num1_len = len(num1)
        num2_len = len(num2)
        
        n1_pointer = len(num1) - 1
        n2_pointer = len(num2) - 1
        carry = 0
        ans = ''
        while(n1_pointer >= 0 or n2_pointer >= 0):
            n1 = int(num1[n1_pointer]) if n1_pointer >= 0 else 0
            n2 = int(num2[n2_pointer]) if n2_pointer >= 0 else 0

            temp_sum = n1 + n2 + carry

            carry = temp_sum // 10
            res = temp_sum % 10
            ans = str(res) + ans
            n1_pointer -= 1
            n2_pointer -= 1
        return '1' + ans if carry else ans

2025-11-14 排列硬币

你总共有 n 枚硬币，并计划将它们按阶梯状排列。对于一个由 k 行组成的阶梯，其第 i 行必须正好有 i 枚硬币。阶梯的最后一行 可能 是不完整的。

给你一个数字 n ，计算并返回可形成 完整阶梯行 的总行数。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
	"""
	完整阶梯行 rows 初始为 0
	硬币数量不为 0 时，依次减去与行数相同的硬币数（rows + 1）
	如果剩余数≥0，则完整阶梯行 +1
	"""
    def arrangeCoins(self, n: int) -> int:
        coins = n
        rows = 0

        while(coins > 0):
            coins = coins - (rows + 1)
            if(coins >= 0):
                rows += 1
            else:
                break
        return rows

数学：等差数列

n个硬币最多排 k 行，k 行有 k 个数，也就是说求不大于 n 的最大前 k 项和，即：n ≥ ((1 + k) * k) / 2

1
2
3
class Solution:
    def arrangeCoins(self, n: int) -> int:
        return int((pow(8 * n + 1, 0.5) - 1) / 2)

2025-11-15 找到所有数组中消失的数字

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n]范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
	"""
	获取 nums 长度，确定 n
	先对数组去重 nums_set
	
	如果[1, n]区间没有出现在 nums_set 中，则加入 res 中
	"""
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        nums_set = set(nums)
        res = []
        for n in range(1, len(nums) + 1):
            if(n not in nums_set):
                res.append(n)
        return res

下面记录一种不使用额外空间且时间复杂度为 O(N)的算法

通过将数字对应的索引位置的值标记为负数来表示该数字出现过。最后，遍历数组，哪些索引位置的值还是正数，就说明该索引+1的数字没有出现。

比如 nums = [4,3,2,7,8,2,3,1]，对于第一个数字 4，其如果按照从小到大的顺序排列应该是位于索引 3 的位置，这时只需要将该位置所对应的值取负数就说明该数出现过

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        for i in range(len(nums)):
            if(nums[abs(nums[i]) - 1] > 0):
                nums[abs(nums[i]) - 1] *= -1
        
        res = []
        for i in range(len(nums)):
            if(nums[i] > 0):
                res.append(i + 1)
        return res

btw太抽象了，这是人类能想出的解法？

2025-11-16 分发饼干

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是满足尽可能多的孩子，并输出这个最大数值。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
	"""
	先将胃口和饼干大小分别按照从小到大排序
	
	每次拿出一个最小的饼干，匹配胃口最小的小孩，找到了便计数加一
	如果饼干数量多于小孩数量，需要判断下标是否越界：res < len(g)
	"""
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        res = 0
        for cookie in s:
            if(res < len(g) and cookie >= g[res]):
                res += 1
        return res

2025-11-17 重复的子字符串

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

代码思路如下：

1
2
3
4
5
6
class Solution:
	"""
	如果一个字符串 s存在子串，那么 s 一定会存在于用两个 s 拼接的新字符串 ss （去掉首尾两个字符）
	"""
    def repeatedSubstringPattern(self, s: str) -> bool:
        return s in (s + s)[1:-1]

2025-11-18 汉明距离

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。

给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

代码思路如下：

1
2
3
4
5
6
class Solution:
	"""
	异或之后统计1的个数
	"""
    def hammingDistance(self, x: int, y: int) -> int:
        return (x ^ y).bit_count()

2025-11-19 岛屿的周长

给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。

网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。

岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。

代码思路如下：

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:
	"""
	遍历每个格子，如果存在格子是陆地：
		假设该块陆地周长为 4
		判断其上下左右是否有陆地接壤，每有一块陆地接壤，该块陆地的周长就-1
		每次判断一块陆地就更新总周长
	"""
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        row = len(grid)
        col = len(grid[0])

        res = 0
        for r in range(row):
            for c in range(col):
                if(grid[r][c] == 1):
                    temp_res = 4
                    up = r - 1
                    down = r + 1
                    left = c - 1
                    right = c + 1
                    if(up != -1 and grid[up][c] == 1):
                            temp_res -= 1
                    if(down != row and grid[down][c] == 1):
                            temp_res -= 1
                    if(left != -1 and grid[r][left] == 1):
                            temp_res -= 1
                    if(right != col and grid[r][right] == 1):
                            temp_res -= 1                    
	        res += temp_res
        return res

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
	"""
	递归每一块陆地，如果递归到边界外或者水域，这周长加 1
	再将访问过的陆地标记为 2，直接返回 0，避免重复计算
	"""
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        row = len(grid)
        col = len(grid[0])

        def dfs(r, c):
            if not (-1 < r < row and -1 < c < col) or grid[r][c] == 0:
                return 1
            if(grid[r][c] == 2):
                return 0
            grid[r][c] = 2

            return dfs(r - 1, c) + dfs(r + 1, c) + dfs(r, c - 1) + dfs(r, c + 1)
        
        for r in range(row):
            for c in range(col):
                if(grid[r][c] == 1):
                    return dfs(r, c)

2025-11-20 数字的补数

对整数的二进制表示取反（0 变 1 ，1 变 0）后，再转换为十进制表示，可以得到这个整数的补数。

  • 例如，整数 5 的二进制表示是 "101" ，取反后得到 "010" ，再转回十进制表示得到补数 2 。

给你一个整数 num ，输出它的补数。

代码思路如下：

1
2
3
4
5
6
7
8
9
class Solution:
	"""
	只需要二进制 num 的每一位和 1 异或运算即可
	用 bit_length 计算出 num 的二进制位数，接着求出当前长度全为 1 的二进制数
	最后异或
	"""
    def findComplement(self, num: int) -> int:
        res = num ^ (2 ** num.bit_length() - 1)
        return res

2025-11-21 密钥格式化

给定一个许可密钥字符串 s，仅由字母、数字字符和破折号组成。字符串由 n 个破折号分成 n + 1 组。你也会得到一个整数 k 。

我们想要重新格式化字符串 s，使每一组包含 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
30
31
32
class Solution:
	"""
	字符串字母全部转为大写
	
	replace 所有 "-"，并得到新字符串 new_s 的长度new_s_len
	
	反转 new_s 得到 reversed_s
	
	构造后续保存 按大小为 k 的滑动区间截取的字符串组构成的列表reversed_s_list
	
	用"-"连接列表，然后倒序输入即为答案
	"""
    def licenseKeyFormatting(self, s: str, k: int) -> str:
        upper_s = s.upper()
        
        new_s = upper_s.replace('-', '')
        new_s_len = len(new_s)
        
        reversed_s = new_s[::-1]
        
        reversed_s_list = []
        index = 0
        
        while(index + k < new_s_len):
            reversed_s_list.append(reversed_s[index:(index + k)])
            index += k
            
        reversed_s_list.append(reversed_s[index:])
        
        res = '-'.join(reversed_s_list)
        
        return res[::-1]

2025-11-22 最大连续 1 的个数

给定一个二进制数组 nums ， 计算其中最大连续 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
class Solution:
	"""
	res记录最终结果
	temp_res 记录临时 最大连续 1 的个数
	
	遍历数组，如果遇到 1 ，则 temp_res++
	否则为 0且此前记录的 temp_res 大于 res，大于就更新 res，然后将 temp_res 置为 0
	否则，temp_res 置为 0，开始记录下一串为 1 的个数
	"""
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        res = 0
        temp_res = 0
        index = 0
        len_nums = len(nums)
        
        while(index < len_nums):
            if(nums[index] == 1):
                temp_res += 1
            elif(temp_res > res):
                res = temp_res
                temp_res = 0
            else:
                temp_res = 0
            index += 1

        return res if res > temp_res else temp_res

2025-11-23 构造矩形

作为一位web开发者， 懂得怎样去规划一个页面的尺寸是很重要的。 所以，现给定一个具体的矩形页面面积，你的任务是设计一个长度为 L 和宽度为 W 且满足以下要求的矩形的页面。要求：

  1. 你设计的矩形页面必须等于给定的目标面积。
  2. 宽度 W 不应大于长度 L ，换言之，要求 L >= W 。
  3. 长度 L 和宽度 W 之间的差距应当尽可能小。

返回一个 数组 [L, W]，其中 L 和 W 是你按照顺序设计的网页的长度和宽度。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
	"""
	从 area 的平方根开始遍历 w，遇到第一个能整除的 w 就返回
	"""
    def constructRectangle(self, area: int) -> List[int]:
        sqrt_area = int(sqrt(area))
        res = []
        while(sqrt_area >= 1):
            w = area % sqrt_area
            if(w == 0):
                l = int(area / sqrt_area)
                res.append(l)
                res.append(sqrt_area)
                return res
            sqrt_area -= 1

2025-11-24 提莫攻击

在《英雄联盟》的世界中，有一个叫 “提莫” 的英雄。他的攻击可以让敌方英雄艾希（编者注：寒冰射手）进入中毒状态。

当提莫攻击艾希，艾希的中毒状态正好持续 duration 秒。

正式地讲，提莫在 t 发起攻击意味着艾希在时间区间 [t, t + duration - 1]（含 t 和 t + duration - 1）处于中毒状态。如果提莫在中毒影响结束 前 再次攻击，中毒状态计时器将会 重置，在新的攻击之后，中毒影响将会在 duration 秒后结束。

给你一个 非递减 的整数数组 timeSeries ，其中 timeSeries[i] 表示提莫在 timeSeries[i] 秒时对艾希发起攻击，以及一个表示中毒持续时间的整数 duration 。

返回艾希处于中毒状态的 总 秒数。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
	"""
	记录每一次攻击间隔time_gap
	如果间隔大于等于中毒效果duration，则总中毒total_duration = duration
	否则加上time_gap
	"""
    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:
        len_timeSeries = len(timeSeries)
        total_duration = 0
        for i in range(len_timeSeries - 1):
            time_gap = timeSeries[i + 1] - timeSeries[i]
            if(time_gap >= duration):
                total_duration += duration
            else:
                total_duration += time_gap
        total_duration += duration

        return total_duration

2025-11-25 下一个更大元素 I

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。

给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。

返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
	"""
	暴力法找到 x 在 num2 中的位置，再往后查找
	"""
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        len1 = len(nums1)
        len2 = len(nums2)
        ans = []
        for index1 in range(len1):
            for index2 in range(len2):
                if(nums1[index1] == nums2[index2]):
                    for index3 in range(index2, len2):
                        if(nums2[index2] < nums2[index3]):
                            ans.append(nums2[index3])
                            break
                        if(index3 == len2 - 1):
                            ans.append(-1)
        return ans

单调栈（借鉴灵茶山艾府大佬）

单调栈是一种特殊的栈，它要求栈中的元素始终保持单调递增或单调递减的顺序。

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:
	"""
	使用栈 stack 保存着这些数： 尚未找到其“下一个更大元素”
	mapping 记录了 nums2 中每个数的“下一个更大元素”，初始化均为-1
	
	遍历 nums2：
		while 循环判断：当栈不为空并且当前元素大于栈顶元素pop_out：
			说明找到了pop_out的“下一个元素” n2，
			将pop_out弹出，并记录在 mapping 中
		否则将当前元素压入栈
		
	遍历 nums1，在 mapping 查找需要的结果
		
	"""
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        stack = []
        mapping = {i: -1 for i in nums2}
        ans = []

        for n2 in nums2:
            while(stack and n2 > stack[-1]):
                pop_out = stack.pop()
                mapping[pop_out] = n2
            stack.append(n2)

        for n1 in nums1:
            ans.append(mapping[n1])

        return ans

2025-11-26 键盘行

给你一个字符串数组 words ，只返回可以使用在 美式键盘 同一行的字母打印出来的单词。键盘如下图所示。（看看你的键盘）

请注意，字符串 不区分大小写，相同字母的大小写形式都被视为在同一行**。**

美式键盘 中：

  • 第一行由字符 "qwertyuiop" 组成。
  • 第二行由字符 "asdfghjkl" 组成。
  • 第三行由字符 "zxcvbnm" 组成。

代码思路如下：

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:
	"""
	1. 首先定义了三个集合，分别对应键盘的三行字母。    
	2. 初始化一个空列表ans用于存放结果。
	3. 遍历单词列表words中的每个单词，将其转换为小写，因为键盘行中的字母都是小写的。
	4. 对于每个单词，初始化which_row为0，表示尚未确定当前单词属于哪一行；cur_row表示当前字母属于哪一行。
	5. 遍历单词中的每个字母：
	    - 如果字母在第一行，则设置cur_row为1。
	        
	    - 如果字母在第二行，则设置cur_row为2。
	        
	    - 如果字母在第三行，则设置cur_row为3。
	        
	    - 如果which_row为0（即第一次遇到字母），则设置which_row为当前行号。
	        
	    - 如果which_row不为0，且当前行号cur_row与which_row不同，则说明这个单词不是在同一行打的，跳出循环。  
	6. 循环结束后，如果cur_row等于which_row（说明没有提前跳出，即所有字母都在同一行），则将原单词（未小写化的）加入结果列表。
	"""
    def findWords(self, words: List[str]) -> List[str]:
        first_row = {char: char for char in list("qwertyuiop")}
        second_row = {char: char for char in list("asdfghjkl")}
        third_row = {char: char for char in list("zxcvbnm")}

        ans = []

        for word in words:
            lower_word = word.lower()
            which_row = 0
            cur_row = 0
            for letter in lower_word:
                if(letter in first_row):
                    cur_row = 1
                    if(which_row == 0):
                        which_row = 1
                    elif(cur_row != which_row):
                        break
                elif(letter in second_row):
                    cur_row = 2
                    if(which_row == 0):
                        which_row = 2
                    elif(cur_row != which_row):
                        break
                elif(letter in third_row):
                    cur_row = 3
                    if(which_row == 0):
                        which_row = 3
                    elif(cur_row != which_row):
                        break

            if(cur_row == which_row):
                ans.append(word)
        return ans

2025-11-27 二叉搜索树中的众数

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

  • 结点左子树中所含节点的值 小于等于 当前节点的值
  • 结点右子树中所含节点的值 大于等于 当前节点的值
  • 左子树和右子树都是二叉搜索树

代码思路如下：

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
	"""
	引用编程文青李狗蛋老师的注释：
	因为可能存在多个众数，我们用 cnt 记录当前元素重复的次数，用 maxCnt 记录已经遍历过的元素当中出现最多的元素的出现次数，用 ans 记录众数。

具体做法就是：
	比较当前的元素值 ordered_list[i] 与前一个元素值 pre：

	如果 ordered_list[i] == pre，cur_cnt = cur_cnt + 1。
	如果 ordered_list[i] > pre，cur_cnt = 1。
	比较当前元素重复的次数 cur_cnt 与 maxCnt：
	
	如果 cur_cnt == maxCnt，说明当前的元素值 ordered_list[i] 出现的次数等于当前众数出现的次数，将 ordered_list[i] 加入 ans。
	如果 cur_cnt > maxCnt，说明当前的元素值 ordered_list[i] 出现的次数大于当前众数出现的次数，所以将 maxCnt 更新为 cur_cnt，清空 ans，之后将 ordered_list[i] 加入 ans。
	"""
    def findMode(self, root: Optional[TreeNode]) -> List[int]:
        ordered_list = []
        self.dfs(root, ordered_list)
        
        max_cnt = 1
        cur_cnt = 1
        ans = [ordered_list[0]]
        pre = ordered_list[0]


        for i in range(1, len(ordered_list)):
            if(pre == ordered_list[i]):
                cur_cnt += 1
            else:
                cur_cnt = 1
            
            if(cur_cnt > max_cnt):
                max_cnt = cur_cnt
                ans = [ordered_list[i]]
            elif(cur_cnt == max_cnt):
                ans.append(ordered_list[i])

            pre = ordered_list[i]
        return ans
	
	"""
	中序遍历拿到有序列表 num_list
	"""
    def dfs(self, root: Optional[TreeNode], num_list: List[int]):
        if(root == None):
            return None
        self.dfs(root.left, num_list)
        num_list.append(root.val)
        self.dfs(root.right, num_list)

2025-11-28 相对名次

给你一个长度为 n 的整数数组 score ，其中 score[i] 是第 i` 位运动员在比赛中的得分。所有得分都 互不相同 。

运动员将根据得分 决定名次 ，其中名次第 1 的运动员得分最高，名次第 2 的运动员得分第 2 高，依此类推。运动员的名次决定了他们的获奖情况：

  • 名次第 1 的运动员获金牌 "Gold Medal" 。
  • 名次第 2 的运动员获银牌 "Silver Medal" 。
  • 名次第 3 的运动员获铜牌 "Bronze Medal" 。
  • 从名次第 4 到第 n 的运动员，只能获得他们的名次编号（即，名次第 x 的运动员获得编号 "x"）。

使用长度为 n 的数组 answer 返回获奖，其中 answer[i] 是第 i 位运动员的获奖情况。

代码思路如下：

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
class Solution:
	"""
	original_order记录每个运动员的初始位置
	然后将 score 降序排序
	遍历排序后的 score，然后再定位到初始位置，从高到低赋予排名
	"""
    def findRelativeRanks(self, score: List[int]) -> List[str]:
        original_order = {}
        len_score = len(score)
        index = 0
        answer = [0] * len_score

        while(index < len_score):
            original_order[score[index]] = index
            index += 1

        score.sort(reverse =True)
        
        for i in range(len_score):
            if (i == 0):
                answer[original_order[score[i]]] = 'Gold Medal'
            elif(i == 1):
                answer[original_order[score[i]]] = 'Silver Medal'
            elif(i == 2):
                answer[original_order[score[i]]] = 'Bronze Medal'
            else:
                answer[original_order[score[i]]] = str(i + 1)
        return answer

2025-11-29 完美数

对于一个 正整数，如果它和除了它自身以外的所有 正因子 之和相等，我们称它为 「完美数」。

给定一个 整数 n， 如果是完美数，返回 true；否则返回 false。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
class Solution:
	"""
	暴力法，找出所有因子，然后因子求和等于 2 * num 即为完美数
	"""
    def checkPerfectNumber(self, num: int) -> bool:
        factors = set()
        for i in range(1, int(math.sqrt(num)) + 1):
            if num % i == 0:
                factors.add(i)
                factors.add(num // i)
        return sum(factors) == 2 * num

2025-11-30 斐波拉契数

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def fib(self, n: int) -> int:
        if(n == 0):
            return 0
        if(n == 1):
            return 1
        res = (n + 1) * [0]
        res[0] = 0
        res[1] = 1

        for i in range(2, n + 1):
            res[i] = res[i  - 1] + res[i - 2]
        return res[n]

2025-12-01 最长特殊序列I

给你两个字符串 a 和 b，请返回 _这两个字符串中 最长的特殊序列 的长度。如果不存在，则返回 -1 。

「最长特殊序列」** 定义如下：该序列为 某字符串独有的最长子序列（即不能是其他字符串的子序列 。

字符串 s 的子序列是在从 s 中删除任意数量的字符后可以获得的字符串。

  • 例如，"abc" 是 "aebdc" 的子序列，因为删除 "a_**e**_b**_d_**c" 中斜体加粗的字符可以得到 "abc"。 "aebdc" 的子序列还包括 "aebdc" 、 "aeb" 和 "" (空字符串)。

代码思路如下：

1
2
3
4
5
6
7
8
class Solution:
	"""
	字符相等返回-1，不相等返回较长字符的长度
	"""
    def findLUSlength(self, a: str, b: str) -> int:
        if(a == b):
            return -1
        return len(a) if len(a) >= len(b) else len(b)

2025-12-02 二叉搜索树的最小绝对差

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。

代码思路如下：

递归版：

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
	"""
	中序遍历得到一个顺序增大序列
	然后扫描序列求解最小绝对值差，用delta记录最小绝对值差
	"""
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        values = []
        self.dfs(root, values)

        delta = float('inf')
        for i in range(len(values) - 1):
            delta = min(abs(values[i] - values[i + 1]), delta)
        return delta
        
    def dfs(self, root: Optional[TreeNode], values):
        if(root is None):
            return 

        self.dfs(root.left, values)
        values.append(root.val)
        self.dfs(root.right, values)

迭代版：

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
	"""
	初始化栈 stack
	记录前一个节点 pre
	记录全局最小值 global_min
	
	当栈不为空或者根节点不为空时：
		如果根节点不为空则：
			将根节点入栈，同时一直遍历左子树
		否则（遍历完了左子树，该遍历“根”节点）：
			弹出栈顶节点记为 cur
			如果 cur 的 pre 值存在：
				计算全局最小值
			pre = cur
			
			然后开始遍历右子树root = cur.right
	"""
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        stack = []
        pre = None
        global_min = float('inf')

        while stack or root:
            if root:
                stack.append(root)
                root = root.left
            else:
                cur = stack.pop()
                if(pre):
                    global_min = min(cur.val - pre.val, global_min)
                pre = cur
                root = cur.right
        return global_min

2025-12-03 反转字符串 II

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

  • 如果剩余字符少于 k 个，则将剩余字符全部反转。
  • 如果剩余字符小于 2k 但大于或等于 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
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution:
	"""
	如果字符串长度小于等于k，直接反转整个字符串并返回
	计算有多少个完整的2k字符周期
	
	如果没有完整的2k周期：
	    如果长度大于等于k：反转前k个，加上剩余部分
        否则：反转整个字符串（这个分支其实不会执行，因为前面已处理）
        
    对于每个完整的2k周期：
    反转前k个字符（s[left:right]）
    保持接下来的k个字符不变 
    移动指针到下一个周期
    
    如果剩余字符多于k个：反转前k个，保持剩余不变
	如果剩余字符少于等于k个：反转所有剩余字符
	"""
    def reverseStr(self, s: str, k: int) -> str:
        if len(s) <= k:
            return s[::-1]
        rounds = len(s) // (2 * k)

        left = 0
        right = k
        res = ''
        if(rounds == 0):
            if(len(s) >= k):
                return s[:right][::-1] + s[right:]
            else:
                return s[::-1]

        while(rounds > 0):
            res = res + s[left: right][::-1] + s[right:right + k]
            left += 2 * k
            right = left + k
            rounds -= 1
        
        if(len(s) - left > k):
            res = res + s[left:left + k][::-1] + s[left + k:]
        else:
            res = res + s[left:len(s)][::-1]
        return res

简洁版：

1
2
3
4
5
6
7
8
class Solution:
    def reverseStr(self, s: str, k: int) -> str:
	    result = ""
	    for i in range(0, len(s), 2*k):
	        # 反转前k个，加上接下来的k个（或剩余部分）
	        chunk = s[i:i+2*k]
	        result += chunk[:k][::-1] + chunk[k:]
	    return result

2025-12-04 二叉树的直径

给你一棵二叉树的根节点，返回该树的 直径 。

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的 长度 由它们之间边数表示。

代码思路如下：

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
	"""
	递归计算树的高度的同时，计算并保存每个节点的最大直径（左右子树的高度和）到 res
	"""
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        res = [0]
        self.recursive(root, res)
        return res[0]
    def recursive(self, root: Optional[TreeNode], res: List[int]) -> int:
        if(root is None):
            return 0
        left_edges = 0
        right_edges = 0
        if(root.left):
            left_edges = self.recursive(root.left, res)
        if(root.right):
            right_edges = self.recursive(root.right, res)
        res[0] = max(left_edges + right_edges, res[0])
        return max(left_edges, right_edges) + 1

2025-12-05 学生出勤记录 I

给你一个字符串 s 表示一个学生的出勤记录，其中的每个字符用来标记当天的出勤情况（缺勤、迟到、到场）。记录中只含下面三种字符：

  • 'A'：Absent，缺勤
  • 'L'：Late，迟到
  • 'P'：Present，到场

如果学生能够 同时 满足下面两个条件，则可以获得出勤奖励：

  • 按 总出勤 计，学生缺勤（'A'）严格 少于两天。
  • 学生 不会 存在 连续 3 天或 连续 3 天以上的迟到（'L'）记录。

如果学生可以获得出勤奖励，返回 true ；否则，返回 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
class Solution:
	"""
	对A，L，P 分别进行如下判断：
		若出现 A：
			count_A计数加一，同时清空累计迟到 L 清空
			同时判断缺勤次数是否严格少于两天
		若出现 L：
			累计迟到加1
			同时判断是否连续缺勤三天以上
		否则（到场）：
			重置累计迟到concecutive_L
	"""
    def checkRecord(self, s: str) -> bool:
        count_A = 0
        concecutive_L = 0
        for record in s :
            if(record == 'A'):
                count_A += 1
                concecutive_L = 0
                if(count_A >= 2):
                    return False
            elif(record == 'L'):
                concecutive_L += 1
                if(concecutive_L >= 3):
                    return False
            else:
                concecutive_L = 0
        return True

灵神大佬的写法：

1
2
3
class Solution:
    def checkRecord(self, s: str) -> bool:
        return s.count('A') < 2 and "LLL" not in s

os：突然觉得自己耳朵中间夹着的不是脑袋（有内置 API 还是要用啊）

2025-12-06 反转字符串中的单词 III

给定一个字符串 s ，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
class Solution:
	"""
	切割字符串，倒序索引反转字符
	and需要注意的是结果字符串的最后一个空格字符
	"""
    def reverseWords(self, s: str) -> str:
        splited_s = s.split(' ')
        res = ''
        for word in splited_s:
            res += word[::-1] + ' '
        return res[:-1]

2025-12-07 N叉树的最大深度

给定一个 N 叉树，找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
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
"""
# Definition for a Node.
class Node:
    def __init__(self, val: Optional[int] = None, children: Optional[List['Node']] = None):
        self.val = val
        self.children = children
"""

class Solution:
	"""
	与求解二叉树的深度逻辑类似，有一点需要注意的是：depth 的初始化要为[0]而不是 []，因为如果
	初始化为[]，遍历到叶子节点，叶子节点的 num_children 不存在，那么循环就不执行，max(depth)就会报错（空列表）
	"""
    def maxDepth(self, root: 'Node') -> int:
        return self.dfs(root)
    def dfs(self, root: 'Node') -> int:
        if(root is None):
            return 0

        depth = [0]
        children = root.children
        num_children = len(children)
        print(num_children)
        for i in range(num_children):
            depth.append(self.dfs(children[i]))
        return max(depth) + 1

2025-12-08 数组拆分

给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
class Solution:
	"""
	假设小数 a 和大数 b
	如果两个数相差较大，这样会浪费一个较大的数，因为可能存在一个比较大的数更大的数 c，从而会遗漏min(b, c)
	所以要求两个数之间尽可能的相等
	
	也就是说，将数组排序，然后取偶数下标的数然后求和即可
	"""
    def arrayPairSum(self, nums: List[int]) -> int:
		return sum(sorted(nums)[::2])

2025-12-09 二叉树的坡度

给你一个二叉树的根节点 root ，计算并返回 整个树 的坡度 。

一个树的 节点的坡度 定义即为，该节点左子树的节点之和和右子树节点之和的 差的绝对值 。如果没有左子树的话，左子树的节点之和为 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
26
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
	"""
	后序遍历递归计算每个子树的总和left_tree_sum + right_tree_sum + root.val，
	同时根据定义计算每个节点的坡度并保存到全局变量 res 
	"""
    def findTilt(self, root: Optional[TreeNode]) -> int:
        res = []
        self.dfs(root, res)
        return sum(res)

    def dfs(self, root: Optional[TreeNode], res) -> int:
        if(root is None):
            return 0

        left_tree_sum = self.dfs(root.left, res)
        right_tree_sum = self.dfs(root.right, res)
        
        cur_root = abs(left_tree_sum - right_tree_sum)
        res.append(cur_root)
        return left_tree_sum + right_tree_sum + root.val

2025-12-10 重塑矩阵

在 MATLAB 中，有一个非常有用的函数 reshape ，它可以将一个 m x n 矩阵重塑为另一个大小不同（r x c）的新矩阵，但保留其原始数据。

给你一个由二维数组 mat 表示的 m x n 矩阵，以及两个正整数 r 和 c ，分别表示想要的重构的矩阵的行数和列数。

重构后的矩阵需要将原始矩阵的所有元素以相同的 行遍历顺序 填充。

如果具有给定参数的 reshape 操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。

代码思路如下：

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:
	"""
	能够 reshape 的前提是，变化前后的行列乘积相等
	
	先将数组扁平化
	
	根据新的 shape 创建多维数组，并逐个添加数
	"""
    def matrixReshape(self, mat: List[List[int]], r: int, c: int) -> List[List[int]]:
        m = len(mat)
        n = len(mat[0])

        res = []
        if(m * n == r * c):
            flatten = [num for sub_set in mat for num in sub_set]
            index = 0
            for row in range(r):
                res.append([])
                for col in range(c):
                    res[row].append(flatten[index])
                    index += 1
            return res
        return mat

==2025-12-11 另一颗树的子树==

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

代码思路如下：

极致的暴力美学，isSubtree方法寻找当前节点开始的树是否和 subRoot 的相同，相同返回 True，否则递归检查 root 的左右子树；而isSameTree具体实现树的比较。

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        if not subRoot:  # 空树是任何树的子树
            return True
        if not root:  # 主树为空，子树不为空
            return False
        # 检查当前节点开始的树是否相同
        if self.isSameTree(root, subRoot):
            return True
        # 否则检查左右子树
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
    
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        # 都为空，相同
        if not p and not q:
            return True
        # 一个空一个不空，不相同
        if not p or not q:
            return False
        # 值不相等，不相同
        if p.val != q.val:
            return False

        # 递归检查左右子树
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.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
30
31
class Solution:
    # 代码逻辑同 104. 二叉树的最大深度
    def getHeight(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        left_h = self.getHeight(root.left)
        right_h = self.getHeight(root.right)
        return max(left_h, right_h) + 1

    # 100. 相同的树
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if p is None or q is None:
            return p is q  # 必须都是 None
        return p.val == q.val and \
            self.isSameTree(p.left, q.left) and \
            self.isSameTree(p.right, q.right)

    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        hs = self.getHeight(subRoot)

        # 返回 node 的高度，以及是否找到了 subRoot
        def dfs(node: Optional[TreeNode]) -> (int, bool):
            if node is None:
                return 0, False
            left_h, left_found = dfs(node.left)
            right_h, right_found = dfs(node.right)
            if left_found or right_found:
                return 0, True
            node_h = max(left_h, right_h) + 1
            return node_h, node_h == hs and self.isSameTree(node, subRoot)
        return dfs(root)[1]

参考链接：https://leetcode.cn/problems/subtree-of-another-tree/solutions/2868217/cong-onm-dao-onpythonjavacgo-by-endlessc-uukp/

2025-12-12 分糖果

Alice 有 n 枚糖，其中第 i 枚糖的类型为 candyType[i] 。Alice 注意到她的体重正在增长，所以前去拜访了一位医生。

医生建议 Alice 要少摄入糖分，只吃掉她所有糖的 n / 2 即可（n 是一个偶数）。Alice 非常喜欢这些糖，她想要在遵循医生建议的情况下，尽可能吃到最多不同种类的糖。

给你一个长度为 n 的整数数组 candyType ，返回： Alice 在仅吃掉 n / 2 枚糖的情况下，可以吃到糖的 最多 种类数。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
	"""
	遍历并记录能吃的新的糖果种类 allowed_type
	过程中只要 allowed_type 种类大于建议值suggestion，则返回建议值
	否则遍历结束返回 allowed_type
	"""
    def distributeCandies(self, candyType: List[int]) -> int:
        suggestion = len(candyType) // 2
        allowed_type = {}
        
        for candy in candyType:
            if(candy in allowed_type):
                continue
            else:
                allowed_type[candy] = 1
            if(suggestion <= len(allowed_type)):
                return suggestion
        return len(allowed_type)

更简洁的写法

1
2
3
class Solution:
    def distributeCandies(self, candyType: List[int]) -> int:
        return min(len(set(candyType)), len(candyType) //2)

2025-12-13 N 叉树前序遍历

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
"""
# Definition for a Node.
class Node:
    def __init__(self, val: Optional[int] = None, children: Optional[List['Node']] = None):
        self.val = val
        self.children = children
"""

class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        res = []
        return self.dfs(root, res )
    def dfs(self, root: 'Node', res: List[int]) -> List[int]:
        if(root is None):
            return None 
        res.append(root.val)
        for child in root.children:
            self.dfs(child, res)
        return res

2025-12-14 最长和谐子序列

和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。

给你一个整数数组 nums ，请你在所有可能的 子序列 中找到最长的和谐子序列的长度。

数组的 子序列 是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
# 1. 统计每个数字出现的频率
# 2. 遍历统计结果，对每个数字检查num+1是否存在
# 3. 若存在，则计算这两个数字的总出现次数
# 4. 记录并返回所有配对中的最大总次数
    def findLHS(self, nums: List[int]) -> int:
        count = Counter(nums)
        res = 0
        for num, c in count.items():
            if((num + 1) in count):
                res = max(res, c + count[num + 1])
        return res

2025-12-15 种花问题

假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true，不能则返回 false 。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
	"""
	前后补 0 占位：避免了在遍历时单独处理首尾元素的复杂判断
	
	从头遍历，只要前后包括自身位置（0）没有花就种下
	每种一朵花，n -= 1
	最后 n≤0 说明花已经种完
	"""
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        flowerbed = [0] + flowerbed + [0]
        for i in range(1, len(flowerbed) - 1):
            if(flowerbed[i] == 0):
                if(flowerbed[i - 1] == 0 and flowerbed[i + 1] == 0):
                    flowerbed[i] = 1
                    n -= 1
        return n <= 0

2025-12-16 三个数的最大乘积

给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
"""
首先将数组从小到大排序。
两种可能的最大乘积：
	max1: 最大的三个数相乘（即排序后末尾的三个数）。
	max2: 最小的两个数（可能是负数）乘以最大的数（如果两个负数相乘会得到正数，再乘以最大数可能产生更大乘积）。
"""

    def maximumProduct(self, nums: List[int]) -> int:
        nums.sort()
        max1 = nums[-1] * nums[-2] * nums[-3]
        max2 = nums[0] * nums[1] * nums[-1]
        return max1 if max1 > max2 else max2

2025-12-17 二叉树的层平均值

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

代码思路如下：

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
	"""
	将得到的 res 中的每一层的值求平均
	"""
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        res = []
        ans = []
        self.dfs(root, res, 0)
        for r in res:
            ans.append(sum(r) / len(r))
        return ans
    """
    res数组记录每一层的值
    求解每一层，用 level 标记每一层，比如第零层：res[0]
    递归求解左右子树
    """
    def dfs(self, root: Optional[TreeNode], res: List[List[int]], level: int):
        if(root is None):
            return
        if(len(res) <= level):
            res.append([])
        res[level].append(root.val)

        self.dfs(root.left, res, level + 1)
        self.dfs(root.right, res, level + 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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
	"""
	all_avg 记录结果
	current_level表示当前层
	循环：
		结算每一层的平均值
		遍历当前层，记录下一层 next_level 的节点
		current_level = next_level
	"""
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        all_avg = []
        current_level = [root]

        while len(current_level):
            all_avg.append(sum(node.val for node in current_level) / len(current_level))

            next_level = []
            for node in current_level:
                if(node.left):
                    next_level.append(node.left)
                if(node.right):
                    next_level.append(node.right)
            current_level = next_level

        return all_avg

2025-12-18 子数组最大平均数 I

给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。

请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。

任何误差小于 10-5 的答案都将被视为正确答案。

代码思路如下（超时案例）：

1
2
3
4
5
6
7
8
9
10
class Solution:
	"""
	暴力求解，窗口滑动
	"""
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        max_sum = float('-inf')
        for i in range(0, len(nums) - k + 1):
            if(max_sum < sum(nums[i:i + k])):
                max_sum = sum(nums[i:i + k])
        return max_sum / k

优化版：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
	"""
	初始化窗口
	每次往后滑动一个单位，nums[i]表示窗口末尾新加入的元素，nums[i - k]表示窗口开头离开的元素
	"""
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        max_sum = sum(nums[:k])
        temp_sum = sum(nums[:k])
        for i in range(k, len(nums)):
            temp_sum = temp_sum - nums[i - k] + nums[i]
            max_sum = max(max_sum, temp_sum)
        return max_sum / k

小结：

对于所有定长窗口滑动问题：
1. 初始化窗口
2. 移动窗口（去除窗口头部元素，加入窗口尾部元素）
3. 计算当前窗口的元素是否满足条件

2025-12-19 错误的集合

集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。

给定一个数组 nums 代表了该集合发生错误后的结果。

请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。

代码思路如下：

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
class Solution:
	"""
	先将数组从小到大排序
	求出实际数组 actual_nums_sum 总和
	求出理论数组 standard_nums_sum 的总和（等差数列求和）
	
	delta表示实际和和理论和的差值，该差值可能为正，可能为负，为正则表示某一个较小的数（missing）被替换成较大的数（duplicate），因此实际和 会大于理论和，反之亦然。
	
	同时有满足delta = duplicate - missing
	
	最后只需要顺序遍历 nums，找到 duplicate，利用上面式子即可找到 missing
	"""
    def findErrorNums(self, nums: List[int]) -> List[int]:
        nums = sorted(nums)
        actual_nums_sum = sum(nums)
        standard_nums_sum = ((1 + len(nums)) * len(nums) ) // 2
        delta =  actual_nums_sum - standard_nums_sum
        duplicate = 0
        missing = 0

        for i in range(1, len(nums)):
            if(nums[i] == nums[i - 1]):
                duplicate = nums[i]
                break
        missing = duplicate - delta

        return [duplicate, missing]

更快的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
	"""
	不需要排序，利用关系：missing = duplicate - (actual_nums_sum - standard_nums_sum)
	
	"""
    def findErrorNums(self, nums: List[int]) -> List[int]:
        n = len(nums)
        seen = set()
        duplicate = -1
        actual_nums_sum = 0
        
        for num in nums:
            actual_nums_sum += num
            if num in seen:
                duplicate = num
            seen.add(num)
        
        standard_nums_sum = n * (n + 1) // 2
        missing = duplicate - (actual_nums_sum - standard_nums_sum)
        
        return [duplicate, missing]

2025-12-20 两数之和 IV - 输入二叉搜索树

给定一个二叉搜索树 root 和一个目标结果 k，如果二叉搜索树中存在两个元素且它们的和等于给定的目标结果，则返回 true。

代码思路如下（中序遍历 + 双指针扫描）：

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
	"""
	双指针暴力查找是否存在两元素之和等于 k
	"""
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        num_list = []
        self.dfs(root, num_list)
        if(len(num_list) < 2):
            return False
        for i in range(0, len(num_list) - 1):
            for j in range(i + 1, len(num_list)):
                if(num_list[i] + num_list[j] == k):
                    return True
        return False
    """
    中序遍历二叉搜索树，结果保存到 num_list
    """
    def dfs(self, root: Optional[TreeNode], num_list: List[int]):
        if(root is None):
            return
        self.dfs(root.left, num_list)
        num_list.append(root.val)
        self.dfs(root.right, num_list)

优化版（线性时间复杂度）

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        num_list = []
        self.dfs(root, num_list)
        if(len(num_list) < 2):
            return False
        left = 0
        right = len(num_list) - 1
        """
        关键改动：
	        左右指针向中间逼近，如果大于目标结果，说明右指针的数略大，右指针左移，反之亦然
	        如果遇到等于目标结果，直接返回 True
	    未在循环中返回，说明不存在两个元素且它们的和等于给定的目标结果，返回 False
        """
        while(left < right):
            if(num_list[left] + num_list[right] > k):
                right -= 1
            elif(num_list[left] + num_list[right] < k):
                left += 1
            else:
                return True
        return False

    def dfs(self, root: Optional[TreeNode], num_list: List[int]):
        if(root is None):
            return
        self.dfs(root.left, num_list)
        num_list.append(root.val)
        self.dfs(root.right, num_list)

2025-12-21 机器人能否返回原点

在二维平面上，有一个机器人从原点 (0, 0) 开始。给出它的移动顺序，判断这个机器人在完成移动后是否在 (0, 0) 处结束。

移动顺序由字符串 moves 表示。字符 move[i] 表示其第 i 次移动。机器人的有效动作有 R（右），L（左），U（上）和 D（下）。

如果机器人在完成所有动作后返回原点，则返回 true。否则，返回 false。

**注意：**机器人“面朝”的方向无关紧要。 “R” 将始终使机器人向右移动一次，“L” 将始终向左移动等。此外，假设每次移动机器人的移动幅度相同。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
	"""
	奇数次总移动不可能回到原点
	偶数次总移动需要分别统计每次移动方向的次数，上和下，左和右的次数必须分别相等
	"""
    def judgeCircle(self, moves: str) -> bool:
        if(len(moves) % 2 != 0):
            return False        

        count_U, count_D, count_L, count_R = 0, 0, 0, 0
        for action in moves:
            if(action == 'U'):
                count_U += 1
            elif(action == 'D'):
                count_D += 1
            elif(action == 'L'):
                count_L += 1
            else:
                count_R += 1
        return True if count_U == count_D and count_L == count_R else False

2025-12-22 图片平滑器

图像平滑器 是大小为 3 x 3 的过滤器，用于对图像的每个单元格平滑处理，平滑处理后单元格的值为该单元格的平均灰度。

每个单元格的  平均灰度 定义为：该单元格自身及其周围的 8 个单元格的平均值，结果需向下取整。（即，需要计算蓝色平滑器中 9 个单元格的平均值）。

如果一个单元格周围存在单元格缺失的情况，则计算平均灰度时不考虑缺失的单元格（即，需要计算红色平滑器中 4 个单元格的平均值）。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
	"""
	暴力法
	"""
    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:
        m, n  = len(img), len(img[0])
        res  = [[0] * n for _ in range(m)]

        for i in range(m):
            for j in range(n):
                total, num = 0, 0
                for x in range(max(i - 1, 0), min(i + 2, m)):
                    for y in range(max(j - 1, 0), min(j + 2, n)):
                        total += img[x][y]
                        num += 1
                res[i][j] = total // num
        return res

2025-12-23 二叉树中第二小的节点

给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一个。

更正式地说，即 root.val = min(root.left.val, root.right.val) 总成立。

给出这样的一个二叉树，你需要输出所有节点中的 第二小的值 。

如果第二小的值不存在的话，输出 -1 。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
	
    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:
        num_list = []
        self.dfs(root, num_list)
        num_list = sorted(num_list)
        for i in range(0, len(num_list) - 1):
            if(num_list[i] < num_list[i + 1]):
                return num_list[i + 1]
        return -1

    def dfs(self, root: Optional[TreeNode], num_list: List[int]):
        if(root is None):
            return
        self.dfs(root.left, num_list)
        num_list.append(root.val)
        self.dfs(root.right, num_list)

简易版：

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
	"""
	只需要在遍历中找到比根节点 min_val 大的值就立刻返回
	"""
    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:
        res = inf
        min_val = root.val

        def dfs(root: Optional[TreeNode], min_val:int):
            if(root is None):
                return
            
            if(root.val > min_val):
                nonlocal res
                res = min(res, root.val)
                return
            dfs(root.left, min_val)
            dfs(root.right, min_val)

        dfs(root, min_val)
        return -1 if res == inf else res

2025-12-24 最长连续递增序列

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
	"""
	遍历数组，判断前后元素是否严格递增，递增则 temp_length ++，然后和最大长度max_length比较；否则 temp_length = 1（连胜终结（bushi）
	"""
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        max_length = 1
        temp_length = 1
        for i in range(0, len(nums) - 1):
            if(nums[i] < nums[i + 1]):
                temp_length += 1
                max_length = max(max_length, temp_length)
            else:
                temp_length = 1
        return max_length

2025-12-25 验证回文串 II

给你一个字符串 s，最多 可以从中删除一个字符。

请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false 。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
	"""
	从两头向中间判断回文，假设如果遇到不相等两个字符AB，删除 A 或 B 字符，若剩余字符构成回文则返回 True
	"""
    def validPalindrome(self, s: str) -> bool:
        left = 0
        right = len(s) - 1

        while(left < right):
            if(s[left] != s[right]):
	            """
	            关键代码
	            """
                return s[left + 1: right + 1] == s[left + 1: right + 1][::-1] or s[left: right] == s[left: right][::-1]
            left += 1
            right -= 1
        return True

2025-12-26 棒球比赛

你现在是一场采用特殊赛制棒球比赛的记录员。这场比赛由若干回合组成，过去几回合的得分可能会影响以后几回合的得分。

比赛开始时，记录是空白的。你会得到一个记录操作的字符串列表 ops，其中 ops[i] 是你需要记录的第 i 项操作，ops 遵循下述规则：

  1. 整数 x - 表示本回合新获得分数 x
  2. "+" - 表示本回合新获得的得分是前两次得分的总和。题目数据保证记录此操作时前面总是存在两个有效的分数。
  3. "D" - 表示本回合新获得的得分是前一次得分的两倍。题目数据保证记录此操作时前面总是存在一个有效的分数。
  4. "C" - 表示前一次得分无效，将其从记录中移除。题目数据保证记录此操作时前面总是存在一个有效的分数。

请你返回记录中所有得分的总和。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
	"""
	使用数组记录分数，if-else 判断
	"""
    def calPoints(self, operations: List[str]) -> int:
        scores = []
        for op in operations:
            if(op == '+'):
                scores.append(scores[-1] + scores[-2])
            elif(op == 'C'):
                scores.pop()
            elif(op == 'D'):
                scores.append(2 * scores[-1])
            else:
                scores.append(int(op))
        return sum(scores)

2025-12-27 交替位二进制数

给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。

代码思路如下：

1
2
3
4
5
6
7
8
9
class Solution:
	"""
	满足条件数 n 和其右移一位后的数 按位异或的结果是全为 1 的二进制数
	将该数记位 num
	若 num 和 num + 1 的 与运算 结果为 0 便是目标数
	"""
    def hasAlternatingBits(self, n: int) -> bool:
        num = n ^ (n >> 1)
        return num & (num + 1) == 0

2025-12-28 计数二进制子串

给定一个字符串 s，统计并返回具有相同数量 0 和 1 的非空（连续）子字符串的数量，并且这些子字符串中的所有 0 和所有 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

class Solution:
	"""
	通过遍历字符串，每当遇到相邻的两个字符不同（即一个0和一个1）时，就以这两个字符为中心，向两边扩展，直到不能扩展为止。每次扩展都会得到一个新的满足条件的子串。
	"""
    def countBinarySubstrings(self, s: str) -> int:
        length = len(s)
        if(length == 1):
            return 0
        
        res = 0
        for i in range(0, length - 1):
            if(s[i] != s[i + 1]):
                res += 1
                j = i - 1
                k = i + 2
                while(j >= 0 and k <= length - 1):
                    if(s[j] == s[i] and s[k] == s[i + 1]):
                        res += 1
                        j -= 1
                        k += 1
                    else:
                        break 
        return res

分组计数

对于相邻的两个块，假设它们分别有 u 个 0 和 v 个 1，或者 u 个 1 和 v 个 0。我们可以组成多少个合法的子串呢？
每个合法的子串都需要一个相等数量的 0 和 1，并且它们必须是连续的。
如果你有 u 个连续的 0 和 v 个连续的 1，你最多只能组成 min(u, v) 个合法的子串。原因是：
如果 u < v，你最多只能从 u 个 0 和 u 个 1 组成合法的子串，即最多组成 u 个子串。
如果 v < u，你最多只能从 v 个 1 和 v 个 0 组成合法的子串，即最多组成 v 个子串。

思路参考链接：https://leetcode.cn/problems/count-binary-substrings/solutions/3022725/ccan-kao-guan-fang-ti-jie-by-fervent-wes-xf28/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        groups = []
        count = 1
        
        # 第一步：计算连续字符的分组长度
        for i in range(1, len(s)):
            if s[i] == s[i-1]:
                count += 1
            else:
                groups.append(count)
                count = 1
        groups.append(count)  # 添加最后一组
        
        # 第二步：相邻分组取最小值相加
        res = 0
        for i in range(1, len(groups)):
            res += min(groups[i-1], groups[i])
        
        return res

2025-12-29 数组的度

给定一个非空且只包含非负数的整数数组 nums，数组的 度 的定义是指数组里任一元素出现频数的最大值。

你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。

代码思路如下：

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:
	"""
	1. 使用Counter统计每个数字出现的次数。
    
	2. 找到出现次数最多的次数（度）most_common[0][1]。
    
	3. 遍历所有出现次数等于度的数字，对于每个这样的数字，找到其在原数组中最左和最右的位置，计算包含该数字的连续子数组的长度（right - left + 1）。
    
	4. 将所有这样的长度放入res列表中，最后返回最小值。
	"""
    def findShortestSubArray(self, nums: List[int]) -> int:
        res = []
        count = Counter(nums)
        length = len(nums)
        most_common = count.most_common(1)
        for num in count:
            if(count[num] == most_common[0][1]):
                left = 0
                right = length - 1
                while(left <= length - 1):
                    if(nums[left] == num):
                        break
                    left += 1
                while(0 <= right):
                    if(nums[right] == num):
                        break
                    right -= 1
                res.append(right - left + 1)
        return min(res)

2025-12-30 二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
	"""
	二分查找
	"""
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        cur_node = root
        while(cur_node):
            if(cur_node.val == val):
                return cur_node
            elif(cur_node.val < val):
                cur_node = cur_node.right
            else:
                cur_node = cur_node.left
        return None

2025-12-31 数据流中的第 K 大元素

设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。

请实现 KthLargest 类：

  • KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
  • int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。

代码思路如下：

暴力解法使用数组容易超时，那么可以使用数据结构：堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class KthLargest:
    # 初始化方法，设置K值并构建初始的最小堆
    def __init__(self, k: int, nums: List[int]):
        self.k = k  # 存储K值，表示我们要找第K大的元素
        self.min_heap = []  # 初始化一个空的最小堆
        
        # 遍历输入数组，构建初始的最小堆
        for num in nums:
            heapq.heappush(self.min_heap, num)  # 将当前数字加入最小堆
            # 如果堆的大小超过K，弹出堆顶元素（最小的元素）
            if len(self.min_heap) > k:
                heapq.heappop(self.min_heap)  # 移除堆顶，保持堆中只有K个元素
    
    # 添加新元素并返回当前第K大的元素
    def add(self, val: int) -> int:
        # 将新值加入最小堆
        heapq.heappush(self.min_heap, val)
        # 如果堆的大小超过K，弹出堆顶元素（最小的元素）
        if len(self.min_heap) > self.k:
            heapq.heappop(self.min_heap)
        # 返回堆顶元素，即当前第K大的元素
        return self.min_heap[0]

2026-01-01 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果 target 存在返回下标，否则返回 -1。

你必须编写一个具有 O(log 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
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # 初始化左右指针
        left = 0
        right = len(nums) - 1
        
        # 特殊情况处理：数组只有一个元素
        if left == right:
            if target == nums[left]:
                return left  # 找到目标
            else:
                return -1   # 未找到目标
        
        # 主循环：当左右指针不相邻时继续搜索
        while left + 1 != right:
            # 计算中间位置（向下取整）
            middle = floor((right + left) / 2)
            
            if nums[middle] < target:
                left = middle      # 目标在右侧，移动左指针
            elif nums[middle] > target:
                right = middle     # 目标在左侧，移动右指针
            else:
                return middle      # 找到目标，返回索引
        
        # 循环结束后，检查左右指针位置
        if target == nums[left]:
            return left
        elif target == nums[right]:
            return right
        return -1  # 未找到目标

2026-01-02 设计哈希集合

不使用任何内建的哈希表库设计一个哈希集合（HashSet）。

实现 MyHashSet 类：

  • void add(key) 向哈希集合中插入值 key 。
  • bool contains(key) 返回哈希集合中是否存在这个值 key 。
  • void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。

代码思路如下（邪修法，空间换时间）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class MyHashSet:
    # 初始化方法：创建一个固定大小的布尔数组
    def __init__(self):
        # 创建长度为1,000,001的布尔数组，所有元素初始化为False
        # 因为题目要求键的范围是0到1,000,000
        self.hash_set = [False] * 1000001
    
    # 添加元素：将对应索引位置设为True
    def add(self, key: int) -> None:
        self.hash_set[key] = True  # 标记该键存在
    
    # 删除元素：将对应索引位置设为False
    def remove(self, key: int) -> None:
        self.hash_set[key] = False  # 标记该键不存在
    
    # 检查元素是否存在：返回对应索引位置的值
    def contains(self, key: int) -> bool:
        return self.hash_set[key]  # 直接返回布尔值

改良版

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 MyHashSet:

    def __init__(self):
        self.buckets = 1009
        self.hash_table = [[] for _ in range(self.buckets)]

    def hash(self, key: int):
        return key % self.buckets

    def add(self, key: int) -> None:
        hash_val = self.hash(key)
        if key in self.hash_table[hash_val]:
            return
        self.hash_table[hash_val].append(key)

    def remove(self, key: int) -> None:
        hash_val = self.hash(key)
        if key not in self.hash_table[hash_val]:
            return
        self.hash_table[hash_val].remove(key)

    def contains(self, key: int) -> bool:
        hash_val = self.hash(key)
        return key in self.hash_table[hash_val]

2026-01-03 设计哈希映射

不使用任何内建的哈希表库设计一个哈希映射（HashMap）。

实现 MyHashMap 类：

  • MyHashMap() 用空映射初始化对象
  • void put(int key, int value) 向 HashMap 插入一个键值对 (key, value) 。如果 key 已经存在于映射中，则更新其对应的值 value 。
  • int get(int key) 返回特定的 key 所映射的 value ；如果映射中不包含 key 的映射，返回 -1。
  • void remove(key) 如果映射中存在 key 的映射，则移除 key 和它所对应的 value 。

代码思路如下：

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 MyHashMap:

    def __init__(self):
        self.buckets = 1009
        self.hash_talbe = [[] for _ in range(self.buckets)]

    def hash(self, key):
        return key % self.buckets

    def put(self, key: int, value: int) -> None:
        hash_val = self.hash(key)
        for ele in self.hash_talbe[hash_val]:
            if ele[0] == key:
                ele[1] = value
                return
        self.hash_talbe[hash_val].append([key, value])

    def get(self, key: int) -> int:
        hash_val = self.hash(key)
        for ele in self.hash_talbe[hash_val]:
            if ele[0] == key:
                return ele[1]
        return -1

    def remove(self, key: int) -> None:
        hash_val = self.hash(key)
        for index, ele in enumerate(self.hash_talbe[hash_val]):
            if ele[0] == key:
                self.hash_talbe[hash_val].pop(index)
                return

2026-01-04 转换成小写字母

给你一个字符串 s ，将该字符串中的大写字母转换成相同的小写字母，返回新的字符串。

代码思路如下（字典法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def toLowerCase(self, str: str) -> str:
        dic = {'A':'a', 'B':'b', 'C':'c', 'D':'d', 'E':'e', 'F':'f',
               'G':'g', 'H':'h', 'I':'i', 'J':'j', 'K':'k', 'L':'l',
               'M':'m', 'N':'n', 'O':'o','P':'p', 'Q':'q', 'R':'r',
               'S':'s', 'T':'t', 'U':'u', 'V':'v', 'W':'w', 'X':'x',
               'Y':'y', 'Z':'z'}
        s = ''
        for char in str:
            if dic.get(char):
                s += dic[char]
            else:
                s += char
        return s

ASCII编码法

1
2
3
4
5
6
7
8
9
10
11
class Solution:
	# 'A' - 'Z' 对应的 ascii码 65 - 90；
	# 'a' - 'z' 对应的 ascii码 97 - 122；
    def toLowerCase(self, str: str) -> str:
        s = ''
        for char in str:
            if  65 <= ord(char) <= 90:
                s += chr(ord(char) + 32)
            else:
                s += char
        return s

2026-01-05 1 比特与 2 比特字符

有两种特殊字符：

  • 第一种字符可以用一比特 0 表示
  • 第二种字符可以用两比特（10 或 11）表示

给你一个以 0 结尾的二进制数组 bits ，如果最后一个字符必须是一个一比特字符，则返回 true 。

代码思路如下：

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:
    def isOneBitCharacter(self, bits: List[int]) -> bool:
        # 特殊情况：只有一个比特，且为0（根据题意，数组以0结尾）
        if len(bits) == 1:
            return True  # 肯定是"0"字符
        
        index = 0  # 当前遍历位置索引
        
        # 遍历整个数组
        while index < len(bits):
            # 如果当前比特是1，它必须与下一个比特组成两比特字符
            if bits[index] == 1:
                index += 2  # 跳过当前比特和下一个比特
            # 如果当前比特是0，它是一个单独的一比特字符
            elif bits[index] == 0:
                index += 1  # 只移动一个位置
            
            # 检查是否到达最后一个比特（索引为len(bits)-1）
            if index == len(bits) - 1:
                return True  # 最后一个比特是独立的
        
        # 如果循环结束仍未返回，说明最后一个比特被前一个1"占用"了
        return False

2026-01-06 寻找数组的中心下标

给你一个整数数组 nums ，请计算数组的 中心下标 。

数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。

如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        # 计算数组所有元素的总和
        total = sum(nums)
        
        # 初始化左侧和为0
        left_sum = 0
        
        # 遍历数组中的每个元素及其索引
        for i, num in enumerate(nums):
            # 检查当前索引是否为中心下标
            # 使用公式：2*左侧和 + 当前元素 = 总和
            if 2 * left_sum + num == total:
                # 找到中心下标，直接返回
                return i
            
            # 更新左侧和，将当前元素加入左侧和
            left_sum += num
        
        # 遍历完所有元素未找到中心下标
        return -1

2026-01-07 自除数

自除数 是指可以被它包含的每一位数整除的数。

  • 例如，128 是一个 自除数 ，因为 128 % 1 == 0，128 % 2 == 0，128 % 8 == 0。

自除数 不允许包含 0 。

给定两个整数 left 和 right ，返回一个列表，列表的元素是范围 [left, 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
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
class Solution:
	"""    
	自除数定义：
	1. 数字能被其每一位数字整除
	2. 数字中不包含数字0
	"""
    def selfDividingNumbers(self, left: int, right: int) -> List[int]:        
        # 初始化结果列表，用于存储找到的自除数
        res = []
        
        # 遍历给定区间内的每一个数字
        for num in range(left, right + 1):
            # 复制当前数字用于处理，避免修改原数字
            temp_num = num
            
            # 存储数字的每一位（不包括0）
            digits = []
            
            # 标志位，表示当前数字是否能被其所有位整除
            is_divided = True
            
            # 标志位，表示当前数字是否包含数字0
            # 初始假设不包含0，如果发现0则设为False
            no_zero = True
            
            # 分解数字的每一位
            # 使用while循环从个位开始逐位提取
            while(temp_num > 0):
                # 获取最后一位数字（个位）
                digit = temp_num % 10
                
                # 检查当前位是否为0
                if(digit):
                    # 如果数字非0，将其添加到digits列表中
                    digits.append(digit)
                else:
                    # 如果数字为0，将no_zero标志设为False
                    # 因为自除数不能包含0
                    no_zero = False
                
                # 去掉已经处理的最后一位，继续处理下一位
                # 例如：123 // 10 = 12，这样就可以处理十位了
                temp_num //= 10
            
            # 检查当前数字是否能被其每一位整除
            for d in digits:
                # 如果数字不能被某一位整除
                if(num % d != 0):
                    # 设置标志为False并跳出循环
                    is_divided = False
                    break  # 只要有一位不能整除，就不是自除数
            
            # 如果同时满足两个条件：
            # 1. 能被所有位整除 (is_divided = True)
            # 2. 不包含数字0 (no_zero = True)
            if(is_divided and no_zero):
                # 将当前数字添加到结果列表中
                res.append(num)
        
        # 返回所有找到的自除数
        return res

2026-01-08 图像渲染

有一幅以 m x n 的二维整数数组表示的图画 image ，其中 image[i][j] 表示该图画的像素值大小。你也被给予三个整数 sr ,  sc 和 color 。你应该从像素 image[sr][sc] 开始对图像进行上色 填充 。

为了完成 上色工作：

  1. 从初始像素开始，将其颜色改为 color。
  2. 对初始坐标的 上下左右四个方向上 相邻且与初始像素的原始颜色同色的像素点执行相同操作。
  3. 通过检查与初始像素的原始颜色相同的相邻像素并修改其颜色来继续 重复 此过程。
  4. 当 没有 其它原始颜色的相邻像素时 停止 操作。

最后返回经过上色渲染 修改 后的图像 。

代码思路如下（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
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
from typing import List  # 导入类型注解模块

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        """       
        参数:
        image: 二维整数数组，表示图像像素矩阵
        sr: 起始行索引（起始像素的行位置）
        sc: 起始列索引（起始像素的列位置）
        color: 要填充的新颜色值
        
        返回:
        填充后的图像矩阵
        """
        
        # 获取图像的行数（高度）
        sr_length = len(image)
        # 获取图像的列数（宽度） - 通过第一行的长度确定
        sc_length = len(image[0])
        
        # 记录起始位置像素的原始颜色
        origin_color = image[sr][sc]
        
        # 调用深度优先搜索(DFS)函数进行填充
        # 注意：如果新颜色与原始颜色相同，直接返回原图像，不需要处理
        # 因为dfs函数中会通过条件判断避免无限递归
        self.dfs(image, sr, sc, sr_length, sc_length, color, origin_color)
        
        # 返回填充后的图像
        return image
    
    def dfs(self, image: List[List[int]], sr: int, sc: int, 
            sr_length: int, sc_length: int, color: int, origin_color: int):
        """
        深度优先搜索辅助函数，递归地填充相邻的相同颜色像素
        
        参数:
        image: 二维整数数组，表示图像像素矩阵
        sr: 当前处理的行索引
        sc: 当前处理的列索引
        sr_length: 图像的行数
        sc_length: 图像的列数
        color: 要填充的新颜色值
        origin_color: 起始像素的原始颜色值
        """
        
        # 1. 边界检查：检查当前像素是否超出图像范围
        # 如果越界（行或列为负数，或超过最大索引），直接返回
        if sr < 0 or sc < 0 or sr > sr_length - 1 or sc > sc_length - 1:
            return
        
        # 2. 有效性检查：判断当前像素是否需要被填充
        # 条件1: 如果当前像素已经是新颜色，说明已经填充过，避免重复处理（也避免死循环）
        # 条件2: 如果当前像素颜色不是原始颜色，说明不在同一连通区域中，不需要填充
        if image[sr][sc] == color or image[sr][sc] != origin_color:
            return
        
        # 3. 填充当前像素：将当前像素设置为新颜色
        image[sr][sc] = color
        
        # 4. 递归填充四个相邻方向（上、下、左、右）
        # 向上移动一行（sr-1），列不变
        self.dfs(image, sr - 1, sc, sr_length, sc_length, color, origin_color)
        # 向下移动一行（sr+1），列不变
        self.dfs(image, sr + 1, sc, sr_length, sc_length, color, origin_color)
        # 向左移动一列（sc-1），行不变
        self.dfs(image, sr, sc - 1, sr_length, sc_length, color, origin_color)
        # 向右移动一列（sc+1），行不变
        self.dfs(image, sr, sc + 1, sr_length, sc_length, color, origin_color)

BFS

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
from typing import List

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:        
        # 记录起始像素的原始颜色
        old_color = image[sr][sc]
        
        # 初始化队列，存储需要处理的像素坐标
        # 队列使用列表实现，但需要注意插入和弹出方式
        queue = [(sr, sc)]
        
        # 如果新颜色与原始颜色相同，直接返回原图像
        # 这是重要的优化，避免无限循环和不必要的工作
        if old_color == color:
            return image
        
        # 广度优先搜索主循环
        while queue:
            # 从队列尾部取出一个像素点进行处理
            # 注意：这里使用pop()从列表尾部弹出，但插入时使用insert(0, ...)
            # 这实际上实现了队列的先进先出特性
            point = queue.pop()
            
            # 将当前像素的颜色改为新颜色
            image[point[0]][point[1]] = color
            
            # 生成当前像素的四个相邻方向：上、下、左、右
            # 使用zip函数将两个元组合并成四个坐标对
            # 第一个元组：(point[0]-1, point[0]+1, point[0], point[0]) - 行坐标
            # 第二个元组：(point[1], point[1], point[1]-1, point[1]+1) - 列坐标
            # 对应关系：
            # 1. (point[0]-1, point[1]) - 上方像素
            # 2. (point[0]+1, point[1]) - 下方像素
            # 3. (point[0], point[1]-1) - 左方像素
            # 4. (point[0], point[1]+1) - 右方像素
            for new_sr, new_sc in zip(
                (point[0] - 1, point[0] + 1, point[0], point[0]),
                (point[1], point[1], point[1] - 1, point[1] + 1)
            ):
                # 检查相邻像素是否满足填充条件
                # 条件1: 新坐标在图像范围内
                # 条件2: 相邻像素的颜色等于原始颜色（即需要被填充）
                if (0 <= new_sr < len(image) and 
                    0 <= new_sc < len(image[0]) and 
                    image[new_sr][new_sc] == old_color):
                    
                    # 将满足条件的相邻像素插入到队列头部
                    # 使用insert(0, ...)确保广度优先的遍历顺序
                    queue.insert(0, (new_sr, new_sc))
        
        # 返回填充后的图像
        return image

2026-01-09 寻找比目标字母大的最小字母

给你一个字符数组 letters，该数组按非递减顺序排序，以及一个字符 target。letters 里至少有两个不同的字符。

返回 letters 中大于 target 的最小的字符。如果不存在这样的字符，则返回 letters 的第一个字符。

代码思路如下：

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
class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:        
        # 初始化二分查找的左右边界
        # 左边界指向列表第一个元素
        # 右边界指向列表末尾的下一个位置（开区间）
        left, right = 0, len(letters)
        
        # 二分查找主循环
        # 当左边界小于右边界时继续查找
        while left < right:
            # 计算中间位置（向下取整）
            mid = (left + right) // 2
            
            # 判断中间位置的字符与目标字符的关系
            # 注意：这里使用 > 而不是 >=
            # 这样可以找到第一个大于目标字符的位置
            if letters[mid] > target:
                # 如果中间字符大于目标字符
                # 说明要找的字符可能在当前位置或左侧
                # 将右边界移动到中间位置（继续在左半部分查找）
                right = mid
            else:
                # 如果中间字符小于等于目标字符
                # 说明要找的字符一定在中间位置的右侧
                # 将左边界移动到中间位置的下一个位置
                left = mid + 1
        
        # 循环结束后，left指向第一个大于目标字符的位置
        # 或者当所有字符都不大于目标字符时，left会等于len(letters)
        
        # 如果left在有效索引范围内，返回该位置的字符
        # 否则返回列表的第一个字符（实现循环查找）
        return letters[left] if left < len(letters) else letters[0]

2026-01-10 使用最小花费爬楼梯

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from typing import List

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        # 在cost数组末尾添加一个0，表示到达顶部（终点）的费用为0
        # 这样我们可以将问题转化为：到达第n个位置（n=len(original_cost)）的最小费用
        cost = cost + [0]
        
        # 创建动态规划数组dp，dp[i]表示到达第i个位置的最小总花费
        dp = [0] * len(cost)
            
        # 动态规划主循环：开始计算每个位置的最小花费
        for i in range(len(cost)):
            # 状态转移方程：
            # 到达第i个位置的最小花费 = 
            #   min(从i-1位置走1步到i, 从i-2位置走2步到i) + 当前位置的费用cost[i]
            dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]
        
        # 返回最后一个位置（终点）的最小花费
        # dp[-1]表示dp数组的最后一个元素
        return dp[-1]

2026-01-11 至少是其他数字两倍的最大数

给你一个整数数组 nums ，其中总是存在 唯一的 一个最大整数 。

请你找出数组中的最大元素并检查它是否 至少是数组中每个其他数字的两倍 。如果是，则返回 最大元素的下标 ，否则返回 -1 。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
class Solution:
	"""
	只需要判断最大元素是否至少是第二大元素的两倍即可。因为如果最大元素至少是第二大元素的两倍，那么对于其他比第二大元素还小的元素，自然满足条件。
	"""
    def dominantIndex(self, nums: List[int]) -> int:
        index_nums = list(enumerate(nums))
        index_nums = sorted(index_nums, key = lambda item: item[1], reverse = True)
        if(index_nums[0][1] >= index_nums[1][1] * 2):
            return index_nums[0][0]
        return -1

2026-01-12 最短补全词

给你一个字符串 licensePlate 和一个字符串数组 words ，请你找出 words 中的 最短补全词 。

补全词 是一个包含 licensePlate 中所有字母的单词。忽略 licensePlate 中的 数字和空格 。不区分大小写。如果某个字母在 licensePlate 中出现不止一次，那么该字母在补全词中的出现次数应当一致或者更多。

例如：licensePlate = "aBc 12c"，那么它的补全词应当包含字母 'a'、'b' （忽略大写）和两个 'c' 。可能的 补全词 有 "abccdef"、"caaacab" 以及 "cbca" 。

请返回 words 中的 最短补全词 。题目数据保证一定存在一个最短补全词。当有多个单词都符合最短补全词的匹配条件时取 words 中 第一个 出现的那个。

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
from typing import List

class Solution:
    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:    
        # 第一步：提取licensePlate中的所有字母，并转换为小写
        cleaned_licensePlate = []
        for char in licensePlate:
            # 检查字符是否为字母（包括大小写）
            if ('a' <= char <= 'z') or ('A' <= char <= 'Z'):
                # 将字母转换为小写并添加到列表中
                # 注意：这里存储的是所有字母，包括重复的字母
                # 例如：licensePlate = "1s3 PSt" -> cleaned_licensePlate = ['s', 'p', 's', 't']
                cleaned_licensePlate.append(char.lower())
        
        # 第二步：将单词列表按照长度升序排序
        # 使用稳定排序，这样相同长度的单词会保持原来的相对顺序
        # 这对于后续返回第一个满足条件的单词很重要
        words = sorted(words, key=lambda word: len(word))
        
        # 第三步：遍历排序后的单词列表，查找第一个满足条件的单词
        for word in words:
            # 创建licensePlate字母列表的副本，用于检查单词是否满足条件
            pattern = cleaned_licensePlate.copy()
            
            # 检查当前单词是否包含pattern中的所有字母
            for letter in word:
                # 如果当前字母在pattern中，则从pattern中移除一个该字母
                if letter in pattern:
                    pattern.remove(letter)
            
            # 如果pattern列表为空，说明单词包含了licensePlate中的所有字母
            # 且每个字母的出现次数都满足要求
            if not pattern:
                # 返回当前单词（由于单词已按长度排序，这将是长度最短的满足条件的单词）
                return word

2026-01-13 二进制表示中质数个计算置位

给你两个整数 left 和 right ，在闭区间 [left, right] 范围内，统计并返回 计算置位位数为质数 的整数个数。

计算置位位数 就是二进制表示中 1 的个数。

  • 例如， 21 的二进制表示 10101 有 3 个计算置位。

代码思路如下：

1
2
3
4
5
6
7
8
class Solution:
	# 使用列表推导式和sum函数进行计数：
	# 1. for num in range(left, right + 1): 遍历区间内的每个整数
	# 2. num.bit_count(): 计算整数num的二进制表示中1的个数
	# 3. ... in [2, 3, 5, 7, 11, 13, 17, 19]: 检查1的个数是否在质数列表中
	# 4. sum(...): 对所有结果为True（1）的项求和，得到满足条件的整数个数
    def countPrimeSetBits(self, left: int, right: int) -> int:
        return sum(num.bit_count() in {2, 3, 5, 7, 11, 13, 17, 19} for num in range(left, right + 1))

2026-01-14 托普利茨矩阵

给你一个 m x n 的矩阵 matrix 。如果这个矩阵是托普利茨矩阵，返回 true ；否则，返回 false 。

如果矩阵上每一条由左上到右下的对角线上的元素都相同，那么这个矩阵是 托普利茨矩阵 。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class SolutionCorrect:
    def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
        """
        检查每个元素是否与其左上角的元素相等
        """
        row = len(matrix)
        col = len(matrix[0])
        
        # 从第二行第二列开始检查，每个元素应该与其左上角的元素相等
        for r in range(1, row):
            for c in range(1, col):
                if matrix[r][c] != matrix[r-1][c-1]:
                    return False
        return True

进阶：

  • 如果矩阵存储在磁盘上，并且内存有限，以至于一次最多只能将矩阵的一行加载到内存中，该怎么办？
  • 如果矩阵太大，以至于一次只能将不完整的一行加载到内存中，该怎么办？

2026-01-15 旋转字符串

给定两个字符串, s 和 goal。如果在若干次旋转操作之后，s 能变成 goal ，那么返回 true 。

s 的 旋转操作 就是将 s 最左边的字符移动到最右边。 

  • 例如, 若 s = 'abcde'，在旋转一次之后结果就是'bcdea' 。

代码思路如下：

1
2
3
4
5
6
7
8
class Solution:
	"""
	将 s 重复一次得到 double_s，这样所有可能的旋转都会出现在 double_s 中
	同时 s 和 goal 的长度必须相等（否则不可能通过旋转得到）
	"""
    def rotateString(self, s: str, goal: str) -> bool:
        double_s = s + s
        return goal in double_s and len(s) == len(goal)

2026-01-16 唯一摩尔斯密码词

国际摩尔斯密码定义一种标准编码方式，将每个字母对应于一个由一系列点和短线组成的字符串， 比如:

  • 'a' 对应 ".-" ，
  • 'b' 对应 "-..." ，
  • 'c' 对应 "-.-." ，以此类推。

为了方便，所有 26 个英文字母的摩尔斯密码表如下：

[“.-“,”-…”,”-.-.”,”-..”,”.”,”..-.”,”–.”,”….”,”..”,”.—“,”-.-“,”.-..”,”–”,”-.”,”—“,”.–.”,”–.-“,”.-.”,”…”,”-“,”..-“,”…-“,”.–”,”-..-“,”-.–”,”–..”]

给你一个字符串数组 words ，每个单词可以写成每个字母对应摩尔斯密码的组合。

  • 例如，"cab" 可以写成 "-.-..--..." ，(即 "-.-." + ".-" + "-..." 字符串的结合)。我们将这样一个连接过程称作 单词翻译 。

对 words 中所有单词进行单词翻译，返回不同 单词翻译 的数量。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
	"""
	根据题意模拟即可
	密码表按照字母顺序排列，然后用当前字母的 ASCII 码和 a 的相减得到的值就是对应字母在密码表的位置
	"""
    def uniqueMorseRepresentations(self, words: List[str]) -> int:
        res = set()
        code = [".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]

        for word in words:
            encode = ''
            for char in word:
                encode += code[ord(char) - ord('a')]
            res.add(encode)
        return len(res)

2026-01-17 写字符串需要的行数

我们要把给定的字符串 S 从左到右写到每一行上，每一行的最大宽度为100个单位，如果我们在写某个字母的时候会使这行超过了100 个单位，那么我们应该把这个字母写到下一行。我们给定了一个数组 widths ，这个数组 widths[0] 代表 ‘a’ 需要的单位， widths[1] 代表 ‘b’ 需要的单位，…， widths[25] 代表 ‘z’ 需要的单位。

现在回答两个问题：至少多少行能放下S，以及最后一行使用的宽度是多少个单位？将你的答案作为长度为2的整数列表返回。

示例 1:
输入:
widths = [10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
S = “abcdefghijklmnopqrstuvwxyz”
输出: [3, 60]
解释:
所有的字符拥有相同的占用单位10。所以书写所有的26个字母，
我们需要2个整行和占用60个单位的一行。

代码思路如下：

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
from typing import List

class Solution:
    def numberOfLines(self, widths: List[int], s: str) -> List[int]:
        """
        计算需要多少行来写字符串s，以及最后一行的宽度
        
        参数:
        widths: 26个整数的列表，表示a-z每个字母的宽度（单位：像素）
        s: 要写的字符串
        
        返回:
        一个包含两个整数的列表：[总行数, 最后一行的宽度]
        """
        
        # 初始化：至少有一行，当前行剩余宽度为100像素
        row_count = 1
        cur_row_width = 100  # 当前行剩余可用的宽度
        
        # 遍历字符串中的每个字符
        for char in s:
            # 获取当前字符的宽度
            # ord(char) - ord('a') 将字符映射到0-25的索引
            char_width = widths[ord(char) - ord('a')]
            
            # 如果当前行有足够空间放下这个字符
            if char_width <= cur_row_width:
                # 在当前行写入字符，减少剩余宽度
                cur_row_width -= char_width
            else:
                # 当前行空间不足，需要换到新的一行
                row_count += 1  # 行数加1
                cur_row_width = 100 - char_width  # 新行剩余宽度 = 100 - 当前字符宽度
        
        # 计算最后一行的实际使用宽度
        # 如果cur_row_width是当前行剩余宽度，那么100 - cur_row_width就是已使用宽度
        last_row_width = 100 - cur_row_width
        
        # 返回结果：[总行数, 最后一行的宽度]
        return [row_count, last_row_width]

2026-01-18 最大三角形面积

给你一个由 X-Y 平面上的点组成的数组 points ，其中 points[i] = [xi, yi] 。从其中取任意三个不同的点组成三角形，返回能组成的最大三角形的面积。与真实值误差在 10-5 内的答案将会视为正确答案。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
class Solution:
	"""
	面积法
	"""
    def largestTriangleArea(self, points: List[List[int]]) -> float:
        res = 0
        for p1, p2, p3 in combinations(points, 3):
            x1, y1 = p1[0] - p2[0], p1[1] - p2[1]
            x2, y2 = p1[0] - p3[0], p1[1] - p3[1]
            res = max(res, abs(x1 * y2 - y1 * x2) / 2)
        return res

2026-01-19 最常见的单词

给你一个字符串 paragraph 和一个表示禁用词的字符串数组 banned ，返回出现频率最高的非禁用词。题目数据 保证 至少存在一个非禁用词，且答案 唯一 。

paragraph 中的单词 不区分大小写 ，答案应以 小写 形式返回。

注意 单词不包含标点符号。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
	"""
	步骤：
	1. 将段落中的标点符号（!?',;.）替换为空格。
	2. 转换为小写。
	3. 分割成单词列表。
	4. 使用 Counter 统计单词频率。
	5. 遍历频率最高的单词（降序），找到第一个不在 banned 中的单词。
	"""
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
        edited_paragraph = re.sub(r'[^\w\s]', ' ', paragraph).lower().split()
        ele = Counter(edited_paragraph).most_common()
        for e in ele:
            if(e[0] not in set(banned)):
                return e[0]

2026-01-20 字符的最短距离

给你一个字符串 s 和一个字符 c ，且 c 是 s 中出现过的字符。

返回一个整数数组 answer ，其中 answer.length == s.length 且 answer[i] 是 s 中从下标 i 到离它 最近 的字符 c 的 距离 。

两个下标 i 和 j 之间的 距离 为 abs(i - j) ，其中 abs 是绝对值函数。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        # 结果数组
        res = []
        # 存储字符c在字符串s中所有出现位置的索引
        c_position = []
        
        # 第一次遍历：记录字符c在字符串s中的所有出现位置
        for j in range(len(s)):
            if c == s[j]:
                c_position.append(j)
        
        # 第二次遍历：计算每个位置到最近的字符c的距离
        for i in range(len(s)):
            distance = float('inf')  # 初始化距离为无穷大
            # 计算当前位置i到每个字符c位置的距离，取最小值
            for j in c_position:
                distance = min(distance, abs(i - j))
            res.append(distance)  # 将最短距离添加到结果数组
        
        return res  # 返回结果数组

2026-01-21 山羊拉丁文

给你一个由若干单词组成的句子 sentence ，单词间由空格分隔。每个单词仅由大写和小写英文字母组成。

请你将句子转换为 “山羊拉丁文（Goat Latin）”（一种类似于 猪拉丁文 - Pig Latin 的虚构语言）。山羊拉丁文的规则如下：

  • 如果单词以元音开头（'a', 'e', 'i', 'o', 'u'），在单词后添加"ma"。
    • 例如，单词 "apple" 变为 "applema" 。
  • 如果单词以辅音字母开头（即，非元音字母），移除第一个字符并将它放到末尾，之后再添加"ma"。
    • 例如，单词 "goat" 变为 "oatgma" 。
  • 根据单词在句子中的索引，在单词最后添加与索引相同数量的字母'a'，索引从 1 开始。
    • 例如，在第一个单词后添加 "a" ，在第二个单词后添加 "aa" ，以此类推。

返回将 sentence 转换为山羊拉丁文后的句子。

代码思路如下：

根据题意模拟即可

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def toGoatLatin(self, sentence: str) -> str:
        res = []
        vowels = set(['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'])

        words = sentence.split()
        for i in range(len(words)):
            if words[i][0] in vowels:
                res.append(words[i] + 'ma' + 'a' * (i + 1))
            else:
                res.append(words[i][1:] + words[i][0] + 'ma' + 'a' * (i + 1))
        return ' '.join(res)

2026-01-22 较大分组的位置

在一个由小写字母构成的字符串 s 中，包含由一些连续的相同字符所构成的分组。

例如，在字符串 s = "abbxxxxzyy" 中，就含有 "a", "bb", "xxxx", "z" 和 "yy" 这样的一些分组。

分组可以用区间 [start, end] 表示，其中 start 和 end 分别表示该分组的起始和终止位置的下标。上例中的 "xxxx" 分组用区间表示为 [3,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
32
33
34
35
36
37
from typing import List  # 导入类型注解所需的List

class Solution:
    def largeGroupPositions(self, s: str) -> List[List[int]]:
        """
        找出字符串中所有长度 >= 3 的连续相同字符子串的起始和结束位置。
        
        思路：遍历字符串，跟踪当前字符、当前字符的起始索引和连续长度。
        当字符改变时，检查前一个字符的连续长度，如果 >= 3，则记录其区间。
        """
        
        cur_char = s[0]           # 当前正在统计的字符
        cur_char_index = 0        # 当前字符的起始索引
        concecutation = 0         # 当前字符的连续长度
        res = []                  # 存储结果的列表
        
        # 遍历字符串的每个字符
        for i in range(len(s)):
            if cur_char == s[i]:  # 如果字符与当前统计的字符相同
                concecutation += 1  # 连续长度+1
            else:                # 字符发生变化
                # 检查前一个字符的连续长度是否 >= 3
                if concecutation >= 3:
                    # 记录区间：[起始索引, 结束索引]
                    res.append([cur_char_index, cur_char_index + concecutation - 1])
                
                # 重置为新的字符
                cur_char = s[i]
                cur_char_index = i  # 新字符的起始位置
                concecutation = 1   # 新字符的长度初始化为1
        
        # 处理字符串末尾的字符组（循环结束后还未处理）
        if concecutation >= 3:
            # 最后一个字符组的结束索引为字符串长度-1
            res.append([cur_char_index, len(s) - 1])
        
        return res

2026-01-23 翻转图像

给定一个 n x n 的二进制矩阵 image ，先 水平 翻转图像，然后 反转 图像并返回 结果 。

水平翻转图片就是将图片的每一行都进行翻转，即逆序。

  • 例如，水平翻转 [1,1,0] 的结果是 [0,1,1]。

反转图片的意思是图片中的 0 全部被 1 替换， 1 全部被 0 替换。

  • 例如，反转 [0,1,1] 的结果是 [1,0,0]。

代码思路如下：

1
2
3
4
5
6
7
8
class Solution:
	# 使用嵌套列表推导式，一行代码完成两个操作
	# 外层推导式：遍历原始矩阵的每一行
	# 内层推导式：对每一行先水平翻转，然后对每个元素取反
	# row[::-1]：水平翻转当前行
	# 1 ^ x：使用异或运算反转像素值（0->1, 1->0）
    def flipAndInvertImage(self, image: List[List[int]]) -> List[List[int]]:
        return [[1 ^ x for x in row[::-1]] for row in image]

2026-01-24 矩形重叠

矩形以列表 [x1, y1, x2, y2] 的形式表示，其中 (x1, y1) 为左下角的坐标，(x2, y2) 是右上角的坐标。矩形的上下边平行于 x 轴，左右边平行于 y 轴。

如果相交的面积为 正 ，则称两矩形重叠。需要明确的是，只在角或边接触的两个矩形不构成重叠。

给出两个矩形 rec1 和 rec2 。如果它们重叠，返回 true；否则，返回 false 。

代码思路如下：

1
2
3
4
5
6
class Solution:
	"""
	两个矩形重叠当且仅当它们在x轴和y轴上的投影都有重叠
	"""
    def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:
        return rec1[0] < rec2[2] and rec1[2] > rec2[0] and rec1[1] < rec2[3] and rec1[3] > rec2[1]

2026-01-25 比较含退格的字符串

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。

**注意：**如果对空文本输入退格字符，文本继续为空。

代码思路如下：

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
class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        """
        比较两个字符串在应用退格符(#)后是否相等。
        
        退格符'#'表示删除前一个字符，如果字符串中有多个连续的退格符，
        则会删除对应数量的前一个字符。
      
        """
        
        # 使用列表模拟栈结构来构建处理后的字符串
        s_list = []  # 用于存储s处理后的字符
        t_list = []  # 用于存储t处理后的字符
        
        # 处理第一个字符串s
        for char in s:
            if char == '#':  # 遇到退格符
                if s_list:   # 如果栈非空，则弹出最后一个字符（模拟退格）
                    s_list.pop()
            else:            # 普通字符，压入栈中
                s_list.append(char)
        
        # 处理第二个字符串t（逻辑相同）
        for char in t:
            if char == '#':  # 遇到退格符
                if t_list:   # 如果栈非空，则弹出最后一个字符
                    t_list.pop()
            else:            # 普通字符，压入栈中
                t_list.append(char)
        
        # 比较两个处理后的字符列表是否相等
        return s_list == t_list

2026-01-26 亲密字符串

给你两个字符串 s 和 goal ，只要我们可以通过交换 s 中的两个字母得到与 goal 相等的结果，就返回 true ；否则返回 false 。

交换字母的定义是：取两个下标 i 和 j （下标从 0 开始）且满足 i != j ，接着交换 s[i] 和 s[j] 处的字符。

  • 例如，在 "abcd" 中交换下标 0 和下标 2 的元素可以生成 "cbad" 。

代码思路如下：

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:
    def buddyStrings(self, s: str, goal: str) -> bool:
        """
        两种情况可以通过一次交换使两个字符串相等:
        1. s和goal只有两个位置不同，并且交换这两个位置的字符后s等于goal
        2. s和goal完全相同，并且s中有至少一个字符出现两次或以上（交换相同字符不影响字符串）
        """
        
        # 情况1: 长度不同，不可能通过一次交换变得相同
        if len(s) != len(goal):
            return False
        
        unique = 0  # 记录s和goal中不同字符的位置数量
        unique_index = []  # 记录不同字符的位置索引
        more_than_twice = False  # 标记s中是否有字符出现两次或以上
        
        # 遍历字符串，比较每个位置上的字符
        for i in range(len(s)):
            if s[i] != goal[i]:  # 字符不同
                unique += 1  # 不同位置计数增加
                unique_index.append(i)  # 记录位置索引
            # 如果不同位置超过2个，无法通过一次交换变得相同
            if unique > 2:
                return False
        
        # 统计s中字符出现频率
        count_s = Counter(s)
        # 检查是否有字符出现两次或以上
        for ele in count_s:
            if count_s[ele] >= 2:
                more_than_twice = True
                break
        
        # 判断是否满足交换条件:
        # 1. 有且仅有两个位置不同，且交换这两个位置的字符后s等于goal
        # 2. 两个字符串完全相同，且s中有重复字符（交换两个相同字符不影响字符串）
        return (unique == 2 and s[unique_index[0]] == goal[unique_index[1]] 
                and s[unique_index[1]] == goal[unique_index[0]]) \
                or (unique == 0 and more_than_twice)

2026-01-27

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        five = 0
        ten = 0
        twenty = 0
        for b in bills:
            if(b == 5):
                five += 1
            elif(b == 10):
                five -= 1
                ten += 1
            else:
                if(ten > 0):
                    ten -= 1
                    five -= 1
                else:
                    five -= 3
            if(five < 0):
                return False
        return True

2026-01-28 转置矩阵

给你一个二维整数数组 matrix， 返回 matrix 的 转置矩阵 。

矩阵的 转置 是指将矩阵的主对角线翻转，交换矩阵的行索引与列索引。

代码思路如下：

1
2
3
4
5
6
7
8
class Solution:
    def transpose(self, matrix: List[List[int]]) -> List[List[int]]:
        m, n = len(matrix), len(matrix[0])
        res = [[0] * m for _ in range(n)]
        for i, row in enumerate(matrix):
            for j, num in enumerate(row):
                res[j][i] = num
        return res

2026-01-29 二进制间距

给定一个正整数 n，找到并返回 n 的二进制表示中两个 相邻 1 之间的 最长距离 。如果不存在两个相邻的 1，返回 0。

如果只有 0 将两个 1 分隔开（可能不存在 0 ），则认为这两个 1 彼此 相邻 。两个 1 之间的距离是它们的二进制表示中位置的绝对差。例如，"1001" 中的两个 1 的距离为 3 。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def binaryGap(self, n: int) -> int:     
        # 将整数n转换为二进制字符串，并去掉前面的'0b'前缀
        b_str = bin(n)[2:]
        
        # 记录上一个1的位置索引
        last = 0
        # 记录最大距离
        res = 0

        # 遍历二进制字符串的每个字符
        for i in range(len(b_str)):
            if b_str[i] == '1':  # 当前位置是1
                # 更新最大距离：当前距离 = i - last
                res = max(res, i - last)
                # 更新上一个1的位置为当前位置
                last = i
        
        return res

2026-01-30 叶子相似的树

请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。

代码思路如下：

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
	"""
	遍历树，保存叶子节点比较即可
	"""
    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:    
        res1 = []
        res2 = []
        self.dfs(root1, res1)
        self.dfs(root2, res2)

        return res1 == res2 

    def dfs(self, root, res):
        if root is None:
            return
        if(root.left is None and root.right is None):
            res.append(root.val)
            return
        self.dfs(root.left, res)
        self.dfs(root.right, res)

2026-01-31 链表的中间结点

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
	"""
	快慢指针，快指针遍历完时，慢指针所在位置就是中间节点
	"""
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow, fast = head, head
        while(fast and fast.next):
            slow = slow.next
            fast = fast.next.next
        return slow

2026-02-01 三维形体投影面积

在 n x n 的网格 grid 中，我们放置了一些与 x，y，z 三轴对齐的 1 x 1 x 1 立方体。

每个值 v = grid[i][j] 表示有一列 v 个正方体叠放在格子 (i, j) 上。

现在，我们查看这些立方体在 xy 、yz 和 zx 平面上的_投影_。

投影 就像影子，将 三维 形体映射到一个 二维 平面上。从顶部、前面和侧面看立方体时，我们会看到“影子”。

返回 所有三个投影的总面积 。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
	"""
	总面积 = 不为0的点数量 + 每一行的最大值之和 + 每一列的最大值之和
	"""
    def projectionArea(self, grid: List[List[int]]) -> int:
        xy = sum([1 if item != 0 else 0 for sub_grid in grid for item in sub_grid])
        
        yz = sum([max([grid[j][i] for j in range(len(grid))]) for i in range(len(grid))])

        zx = sum([max(g) for g in grid])

        return xy + yz + zx

2026-02-02 两句话中的不常见单词

句子 是一串由空格分隔的单词。每个 单词 仅由小写字母组成。

如果某个单词在其中一个句子中恰好出现一次，在另一个句子中却 没有出现 ，那么这个单词就是 不常见的 。

给你两个 句子 s1 和 s2 ，返回所有 不常用单词 的列表。返回列表中单词可以按 任意顺序 组织。

代码思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
	"""
	1. 将两个句子拼接起来，中间用空格隔开，然后按空格分割成单词列表。
	2. 使用Counter统计每个单词出现的次数。
	3. 遍历Counter中的每个键值对，如果出现次数为1，则将其添加到结果列表中。
	"""
    def uncommonFromSentences(self, s1: str, s2: str) -> List[str]:
        combined_str = Counter((s1 + ' ' + s2).split(' '))
        res = []
        for key, value in combined_str.items():
            if(value == 1):
                res.append(key)
        return res

2026-02-03 公平的糖果交换

爱丽丝和鲍勃拥有不同总数量的糖果。给你两个数组 aliceSizes 和 bobSizes ，aliceSizes[i] 是爱丽丝拥有的第 i 盒糖果中的糖果数量，bobSizes[j] 是鲍勃拥有的第 j 盒糖果中的糖果数量。

两人想要互相交换一盒糖果，这样在交换之后，他们就可以拥有相同总数量的糖果。一个人拥有的糖果总数量是他们每盒糖果数量的总和。

返回一个整数数组 answer，其中 answer[0] 是爱丽丝必须交换的糖果盒中的糖果的数目，answer[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
class Solution:
	"""
	设Alice的总糖果大小为alice_total，Bob的总糖果大小为bob_total。  
	假设Alice给出的糖果大小为x，Bob给出的糖果大小为y。  
	那么交换后，Alice的总大小为：alice_total - x + y  
	Bob的总大小为：bob_total - y + x  
	我们要使得这两个相等，即：  
	alice_total - x + y = bob_total - y + x  
	化简得：2*(y - x) = bob_total - alice_total  
	令 diff = bob_total - alice_total  
	则 y - x = diff / 2，即 y = x + diff / 2
	
	将Alice的糖果大小放入一个集合中，然后遍历Bob的糖果大小y，检查是否存在x = y - half_diff（其中half_diff = diff // 2）在Alice的集合中。  
如果存在，则返回[x, y]。	
	"""
    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:
        alice_total = sum(aliceSizes)
        bob_total = sum(bobSizes)
        half_diff = (bob_total - alice_total) // 2

        aliceSizes_set = set(aliceSizes)

        for bob_candy in bobSizes:
            if((bob_candy - half_diff) in aliceSizes_set):
                return [bob_candy - half_diff, bob_candy]

2026-02-04 三维形体的表面积

给你一个 n * n 的网格 grid ，上面放置着一些 1 x 1 x 1 的正方体。每个值 v = grid[i][j] 表示 v 个正方体叠放在对应单元格 (i, 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
from typing import List

class Solution:
    def surfaceArea(self, grid: List[List[int]]) -> int:
        # 处理空网格的情况
        if not len(grid) or not len(grid[0]):
            return 0

        # 初始化变量
        blocks = 0    # 存储所有立方体的总数
        covers = 0    # 存储所有被覆盖的面数（内部堆叠接触面 + 相邻接触面）

        # 遍历网格中的每个位置
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                # 计算当前位置的立方体数量
                v = grid[i][j]
                
                # 累加立方体总数
                blocks += v

                # 1. 计算当前格子内部的堆叠接触面（垂直方向）
                # 如果有v个立方体垂直堆叠，会有(v-1)个接触面
                # 每个接触面覆盖2个面（上立方体的底面和下立方体的顶面）
                # 注意：这里我们先加接触面数量，最后统一乘以2
                if v > 1:
                    covers += v - 1

                # 2. 计算与上方邻居格子的接触面
                # 只有当前格子有立方体且不在第一行时才需要考虑
                if i > 0 and v > 0:
                    # 接触面数量 = 两个格子中立方体数量的较小值
                    covers += min(v, grid[i-1][j])

                # 3. 计算与左方邻居格子的接触面
                # 只有当前格子有立方体且不在第一列时才需要考虑
                if j > 0 and v > 0:
                    covers += min(v, grid[i][j-1])
                    
        return 6 * blocks - 2 * covers