刷题记录帖子

自己开一个帖子， 激励自己，刷题记录。

今天准备明天的报告，只刷了一题， LC 299 Bulls and Cows。

比较简单，说白了就是通过一次遍历，这个时候你一定是位置 match 的，因为你之检测一个位置。所以现在，内容 Match 的就是 Bulls，如果内容不 Match 那么你就记录下来，用一个【0～9】的数组，因为后面只需要比较这里的【0，9】各自在两个数组出现了多少次，然后取每个数字少的那个，当然初始话要都是 0.
时间复杂度 O(n) + 9 其实就是 O(n) 遍历数组的时间，空间复杂度，不算原来的数组，其实只要 O（1）两个长度为 10 的数组记录各相同位置不同内容数字的总体出现次数。

LC 442 Find All Duplicates in an Array

The idea is we do a linear pass using the input array itself as a hash to store which numbers have been seen before. We do this by making elements at certain indexes negative.

1. class Solution:
   
2.     def findDuplicates(self, nums: List[int]) -> List[int]:
   
3.         # HashMap is an obvious solution, we will not check it
   
4.         # Try to solve it in O(n) time without extra space
   
5.         # so we must use space in the array itself
   
6.         # Then we will cancel each other if possible
   
7.         res = []
   
8.         for item in nums:
   
9.             if nums[abs(item) - 1] < 0:
   
10.                 res.append( abs(item) )
    
11.             else:
    
12.                 nums[abs(item) - 1] *= -1
    
13.         return res

复制代码

53. Maximum Subarray

这道题目真是很经典，推荐几个视频还是做的很不错的。https://blog.ihuxu.com/xiaoxu-ex ... 3-maximum-subarray/

https://www.youtube.com/watch?v=7J5rs56JBs8

https://www.youtube.com/watch?v=2MmGzdiKR9Y

（1）暴力 n 平方的方法搜索
（2）一维 dp，记住 dp 的含义，这里是 到第 i 位元素的时候最大的 sum， 如果 sum 不足够大那么还不如，不 包括之前的元素，直接自己成为答案
（3）divide and conquer， 分成三部分，左半部分，右半部分，和 如果包含中间元素的解法。

39. Combination Sum

DFS 解决，但是如何去重 和 加速求解非常值得学习，这里记录下解法，https://maxming0.github.io/2020/10/02/Combination-Sum/

答案真是巧妙，通过两个调节比较

核心是，每次比较的时候判断是不是需要加入， 首先是排序

显然，
（1） num 大于 target 就没必要加入了， 甚至后面的都不用加入了
（2） 其次是，num 必须比已经加入答案的最后那个元素 大，否则，如果这个 num 加入就会算入了 更小的那个答案，这里必须加入以去重！

1009. Complement of Base 10 Integer

这道题目做过，结果还是没做出来，最好的方法其实是 用 11111 mask 和 原数 取 XOR，这样就可以保留下 complment 的要求。

记忆！

701 Insert into a Binary Search Tree

啊啊啊啊啊啊啊啊啊啊啊，居然忘记了 BST 的 insert。

其实错误就发生在写法上，最简洁的方法是 如果 遇到null node 就是插入的 node，这个时候确实是需要新建 node 但是也相应的丢掉了，新建 node 的 parent。所以解决方法就是层层 递归的时候层层赋值。

449 Serialize and Deserialize BST

其实题目还是很经典，很实用的。但是如何简单高效地实现就是考验功力的地方。

先序遍历tree，然后存下来，注意 int 变成 str 之后必须指定 seperator 不然你不知道怎么切割。
然后，直接在建立树的时候带入，左右子树的范围，开始是 -inf 到 +inf。

具体讲解在这儿， https://maxming0.github.io/2020/ ... nd-Deserialize-BST/

452 Minimum Number of Arrows to Burst Balloons

经典的 greedy 题。

https://maxming0.github.io/2020/ ... -to-Burst-Balloons/

316 Remove Duplicate Letters AND 1081. Smallest Subsequence of Distinct Characters

真是经典题目，删除当前已经有的 char 的条件是，新加入的 char 更小，同时 后面还有想删除的字符，同时 stack 不为 空。
stack 为空，则直接加入即可。

Leetcode 会出现重复题目，比如这道题就是 316， 1081 完全是相同的题目，充分说明 核心题目在大约 500 道 左右。

148 Sort List

真是经典题，虽然是用 merge sort 做，但是还是有很多细节要记忆，比如如何找到 linked list 的中间点。

89         Gray Code        Medium

镜像法

位移法, i ^ (i//2)

295        Find Median from Data Stream        Hard        5        Classic Using Two Heap for Partion

1. class MedianFinder(object):
   
2. 
   
3.     def __init__(self):
   
4.         """
   
5.         initialize your data structure here.
   
6.         """
   
7.         # small to large
   
8.         # pop large by multiplying -1
   
9.         self.Heap1 = []
   
10.         # large to small
    
11.         # pop small
    
12.         self.Heap2 = []
    
13. 
    
14.     def addNum(self, num):
    
15.         """
    
16.         :type num: int
    
17.         :rtype: None
    
18.         """
    
19.         heappush(self.Heap1, -num)
    
20.         heappush(self.Heap2, -heappop(self.Heap1))
    
21.         
    
22.         if len(self.Heap2) > len(self.Heap1):
    
23.             heappush(self.Heap1, -heappop(self.Heap2))
    
24. 
    
25.     def findMedian(self):
    
26.         """
    
27.         :rtype: float
    
28.         """
    
29.         if len(self.Heap1) != len(self.Heap2):
    
30.             return -self.Heap1[0]
    
31.         else:
    
32.             return (self.Heap2[0]-self.Heap1[0]) / 2
    
33. 
    
34. 
    
35. # Your MedianFinder object will be instantiated and called as such:
    
36. # obj = MedianFinder()
    
37. # obj.addNum(num)
    
38. # param_2 = obj.findMedian()

复制代码

夏日柠檬红茶 发表于 2026-2-12 21:35
支持一下楼主。看到你2020年就开始刷了。
现在AI大行其道，其实这挺影响我刷题的热情的[捂脸]

我也不喜欢刷题，但是没办法，面试还没改革，那就得继续刷。加油！

880 Decoded String at Index

正向做是常规思路，但是会 TLE，所以 backward 做是最好的。官方解析很好，https://leetcode.com/problems/decoded-string-at-index/solution/

一个优化是，直接 break 累加，参考这个帖子，https://maxming0.github.io/2020/12/20/Decoded-String-at-Index/

LeetCode 987 Vertical Order Traversal of a Binary Tree

Sorting a List of Elements by the First element but if Equal sort by the second == > Forming a tuple and range them by order

1. tmp = sorted(res[i], key=lambda tup: (-1 * tup[1],tup[2]))
   

复制代码

MaxMing 的讲解很好， https://maxming0.github.io/2020/ ... l-of-a-Binary-Tree/

当然我的做法就是慢慢来解决，当然代码不太清晰但是还是可以看出功能。

补下昨天的，104 Maximum Depth of Binary Tree

出现了低级失误，居然没做出来。

其实很简单就是递归，先看root，再 left， 再 right，最后对于该节点做一个归纳，决定怎么输出。

List all scenarios of what a binary tree could be like:

1. when a binary tree is null, simply return maximum depth as 0
2. when a binary tree just have a root node, return maximum depth as 1
3. when a binary tree has a root node and child nodes, maximum depth would be the depth of the bigger side between left and right subtrees plus 1.

LC 806. Number of Lines To Write String

还是很简单的题目，其实可以很容易看懂思路，设置两个变量然后不断检查当前的字符。

赞一个，楼主讲解的很详细！加油！

1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree

这个题目其实我不知道为什么要给 old tree 完全是冗余条件，但是其实就是纯粹的traverse tree 然后你比较 value 并且记录当前的 treeNode。

今天复习 双指针 topic， 参照这个 Github 帖子， 双指针

167. Two Sum II - Input array is sorted 非常直接双指针使用，直接两头夹逼出答案

633. Sum of Square Numbers 需要注意的是，这个是从 0 开始的，换句话说 0**2 + 2**2 == 4 是符合平方和要求的。

345. Reverse Vowels of a String 首先是如何从 Python String 转 List，其次是从 List 转回 String，因为 String 在 Python 中不可变。 其次是需要考虑字符串的大小写问题。最后是其实写判断条件的时候，时刻注意两个 Pointer 的范围，越界是比较讨厌的问题。同时双指针满足条件，交换了内容之后别忘记更新指针。

1108       
Defanging an IP Address     太简单，就是简单的字符串操作练习，没啥提高。

LC 1395. Count Number of Teams 周六比赛的时候暴力求解，现在看到花花的视频，还可以用压缩解法，对于 O(n^3) 的算法，肯定确实是如果超过300就不太暴力做了。
学习了，其实就是变第二趟遍历的时候，可以统计出可能的状态数，这样简单乘法计算即可，而不用一个个检测。代码快了接近 30 倍。

1. class Solution:
   
2.     def numTeams(self, rating: List[int]) -> int:
   
3.         totalN = len(rating)
   
4.         """
   
5.         This time we use the j th ratings to cut the array into two parts
   
6.         then i is choosen from the left part,
   
7.              j is choosen from the right part,
   
8.              so i < j < k
   
9.         Since unique rating values in ratings
   
10.         Then (1) for rating[i] < rating[j] < rating[k]
    
11.              we can count how many elements in j left part is smaller than j which is the possible value of i saying it is numL
    
12.              (2) for rating[i] > rating[j] > rating[k]
    
13.              total number of all elements in j th left part is j, so the number of elements that is larger than j th is ( j - numL )
    
14.         """
    
15. 
    
16.         res = 0
    
17.         for j in range(1,totalN-1):
    
18.             # Both numL and numR are for smaller cases
    
19.             numL = 0
    
20.             numR = 0
    
21.             for i in range(0, j):
    
22.                 if rating[i] < rating[j]:
    
23.                     numL += 1
    
24.             for k in range(j+1,totalN):
    
25.                 if rating[j] < rating[k]:
    
26.                     numR += 1
    
27.             # print("%d , %d"%(numL, numR))
    
28.             res = res + numL * numR + (j - numL) * (totalN - j - numR - 1)
    
29.             # print(res)
    
30.         return res
    
31.             
    
32.             

复制代码

1295. Find Numbers with Even Number of Digits 把数字转换成字符串再用字符串长度 %2 计算。 其实可以用位运算。