KK's blog

Amazon Prime Free Trial

This Prime Day, save up to 70% on speakers, smart TVs, smart watches and more!

Blink Outdoor Camera - Early Prime Day Deals

Ads by Amazon

Linked List

Posted on 2026-06-02 Edited on 2026-06-21 Disqus:

注意事项：

a.next = b。 b赋值给a的next，指向是从左到右，也就是a.next指向b
it = it.next记得移动指针
fake_node如果链首会改变，引入fake_node
决定是while it还是it.next
删除节点.next = None

Python代码：

LeetCode 138 Copy List with Random Pointer

def copyRandomList(self, head: 'Node') -> 'Node':
	if not head:
		return None
	old_to_new = {}
	fake_head = Node(0)
	it, it_new = head, fake_head
	while it:
		new_node = Node(it.val)
		it_new.next = new_node
		old_to_new[it] = new_node
		it, it_new = it.next, it_new.next
	it, it_new = head, fake_head.next
	while it:
		if it.random:
			old_to_new[it].random = old_to_new[it.random]
		it = it.next
	return fake_head.next

算法分析：

时间复杂度为O(n)，空间复杂度O(1)。

KV Store Serialize & Deserialize

Posted on 2026-05-29 Edited on 2026-06-03 Disqus:

Implement a key-value store that can serialize multiple string key-value pairs into a single string and deserialize it back. Both keys and values can contain any characters including delimiters, newlines, and special characters.

Example 1:

Input: {“a,”: “4,,5”, “b”: “”}

题目大意：

实现一个serialize和deserialize键值存储的方法。

解题思路：

用key和value的长度及自定义分隔符[][]来作为serialized的一部分，从而避开delimiter的限制.
上面的例子serialize后变成[2]a,[4]4,,5[1]b[0]

解题步骤：

N/A

注意事项：

不用+=连接res，用list和join提交效率
用index方法找自定义分隔符而不是逐字符处理
重复代码来处理token可以放入子函数，用nonlocal不用作为输入参数且可以修改此变量

Python代码：

def serialize(kv):
    tokens = []
    for k, v in kv.items():
        tokens.append(f"[{len(k)}]{k}[{len(v)}]{v}")
    return "".join(tokens)

def deserialize(serialized):
    i = 0
    dict = {}
    while i < len(serialized):

        def get_token(s):
            nonlocal i
            token_len_st = serialized.find("[", i) + 1
            token_len_end = serialized.find("]", i)
            token_len = int(serialized[token_len_st:token_len_end])
            token_st = token_len_end + 1
            i = token_st + token_len
            return serialized[token_st:token_st + token_len]

        k = get_token(serialized)
        v = get_token(serialized)
        dict[k] = v
    return dict

算法分析：

时间复杂度为O(n)，空间复杂度O(n)

Python代码：

def serialize2(kv):
    res = ""
    for k, v in kv.items():
        res += f"[{len(k)}]{k}[{len(v)}]{v}"
    return res

def deserialize2(serialized):
    is_key = True
    i, kv_length = 0, -1
    k, v = "", ""
    dict = {}
    serialized += " "
    while i < len(serialized):
        if kv_length >= 0:
            if is_key:
                k = serialized[i:i + kv_length] # a,
            else:
                v = serialized[i:i + kv_length] # 4,,5
                dict[k] = v
            is_key = False if is_key else True
            i += kv_length
            kv_length = -1
        if serialized[i] == "[":
            st = i + 1 # 6
        elif serialized[i] == "]":
            end = i # 2
            kv_length = int(serialized[st:end]) # 4
        i += 1
    return dict

Binary Search

Posted on 2026-05-27 Edited on 2026-06-29 Disqus:

算法思路：

循环条件start + 1 < end。当跳出循环时，start和end的关系只能是相等或相邻。
相等是若数组只有一个元素，没有进入循环时出现。当进入过循环，一定是相邻。
跳出循环后比较start和end的关系从而判断答案。

这可以满足二分法找first position或者last position, peak element的题目。
first position中若等于target，end = mid，因为要在左半部分找，相反last
position在右半部分找，所以start = mid。

应用：

有序数组找目标
没给定目标情况下，找峰值，缺失数(元素间关系)
没给定目标情况下，求第k小的数，如求根号（数值关系）

找目标

注意事项：

判断数组是否为空。
如果只有唯一的target的话，target==nums[mid]可以并入任何一种。end和target的顺序也没关系。其他注意循环后要根据题目条件(如小于或者大于或者等于tgt)，
再比较一次start和end上的元素，详见下表
start + (end - start) // 2 是// 2

类型	if target = nums[mid]	循环之后	备注
binary_search	任意	任意	N/A
last_position	向右start = mid	先end且是否等于tgt	贪婪法，找最后一个target，所以尽量靠后，先end
first_position	向左end = mid	先start是否等于tgt	贪婪法，找第一个target，所以尽量靠前，先start
smaller(_or_equal)_position	向左end = mid	先end是否小于tgt	贪婪法，找最后一个小于target的数，所以尽量靠近target，先end
greater(_or_equal)_position	向右start = mid	先start是否大于tgt	贪婪法，找第一个大于target的数，所以尽量靠近target，先start

Python代码：

def binary_search(self, nums: List[int], target: int) -> int:
	if not nums:
		return -1
	start, end = 0, len(nums) - 1
	while start + 1 < end:
		mid = start + (end - start) // 2
		if target < nums[mid]:
			end = mid
		else:
			start = mid

	if nums[end] == target:
		return end
	elif nums[start] == target:
		return start
	else:
		return -1

Python代码：

def last_position(self, nums: List[int], target: int) -> int:
	if not nums:
		return -1
	start, end = 0, len(nums) - 1
	while start + 1 < end:
		mid = start + (end - start) // 2
		if target < nums[mid]:
			end = mid
		elif target > nums[mid]:
			start = mid
		else:  # Depends on the target on the right side or left side. For fist pos, use end = mid
			start = mid

	if nums[end] == target:
		return end
	elif nums[start] == target:
		return start
	else:
		return -1

Python代码：

def first_position(self, nums: List[int], target: int) -> int:
	if not nums:
		return -1
	start, end = 0, len(nums) - 1
	while start + 1 < end:
		mid = start + (end - start) // 2
		if target < nums[mid]:
			end = mid
		elif target > nums[mid]:
			start = mid
		else:
			end = mid

	if nums[start] == target:
		return start
	elif nums[end] == target:
		return end
	else:
		return -1

Python代码：

如果是smaller_or_equal_position，Line 13和15取等号

def smaller_position(self, nums: List[int], target: int) -> int:
	if not nums:
		return -1
	start, end = 0, len(nums) - 1
	while start + 1 < end:
		mid = start + (end - start) // 2
		if target > nums[mid]:
			start = mid
		elif target < nums[mid]:
			end = mid
		else:
			end = mid
	if nums[end] < target:  # nums[end] <= target for smaller_or_equal_position
		return end
	if nums[start] < target:  # nums[start] < target for smaller_or_equal_position
		return start
	return -1

Python代码：

如果是greater_or_equal_position，Line 13和15取等号

def greater_position(self, nums: List[int], target: int) -> int:
	if not nums:
		return -1
	start, end = 0, len(nums) - 1
	while start + 1 < end:
		mid = start + (end - start) // 2
		if target > nums[mid]:
			start = mid
		elif target < nums[mid]:
			end = mid
		else:
			start = mid
	if nums[start] > target:  # nums[start] >= target for greater_or_equal_position
		return start
	if nums[end] > target:  # nums[end] >= target for greater_or_equal_position
		return end
	return -1

找峰值

注意事项：

判断mid+1的元素不越界
最后返回start和end之中较大者

Python代码：

def find_peak(self, nums: List[int]) -> int:
	if not nums:
		return -1
	start, end = 0, len(nums) - 1
	while start + 1 < end:
		mid = start + (end - start) // 2
		if mid + 1 <= end and nums[mid] < nums[mid + 1]:
			start = mid
		else:
			end = mid
	return start if nums[start] > nums[end] else end

数值二分法 - 找第k小的数

模板类似于标准二分法模板，区别是start和end取值以及epsilon取值是0.5而不是1

Python代码：

def minEatingSpeed(self, piles: List[int], target: int) -> int:
	def f(piles, k):
		return <按照题目要求>

	start, end = <数值最小值>, <数值最小值> 
	while start + 0.5 < end: 
		mid = start + (end - start) / 2   
		res = f(piles, mid)
		if <target与res的关系，需要在某一个条件取等号，以为是数值二分法>:
			end = mid
		else:
			start = mid
	return int(end)

注意事项：

思考数组范围(代码连续3行都是注意事项)
epsilon取0.5. 一般整数题都取0.5
mid是除2获得不是//2
模板中target和res取等号时，不能return，要继续在某半区找，因为要达到误差epsilon内才会停止。类似于first_position或者last_position

Python代码：

import math
def binary_select(self, nums: List[int], k: int) -> int:
	if not nums:
		return -1
	start, end, epsilon = min(nums), max(nums), 0.5
	while end - start > epsilon:
		mid = start + (end - start) / 2
		count = len([n for n in nums if n <= mid])
		if k < count:
			end = mid
		elif k > count:
			start = mid
		else:
			start =  mid
	return int(end)

若nums有序，count的统计可以用bisect(nums, mid)完成，记得不需要用+1，而且空数组也无问题
上面line 8可以改成

1	count = bisect.bisect(matrix[i], mid)

注意事项：

数值比较，所以mid是除2获得不是//2。start，end，mid都是数值而不是索引
k是从0开始，count==k的时候，k在mid的右边，如数组1-10, k=3, mid=3.5, count=3，k是前4个数，所以在mid右边。nums[i] <= mid这个等号有没有也没关系，因为mid是小数，不会相等的。
最后start，end区间内是一个整数正是所求，所以返回end向下取整

算法分析：

时间复杂度为O(nlog(|hi-lo|/epsilon))，如果数据比较平均也就是差值相当的情况下(比如1,2,3)，复杂度为O(nlogn). 空间复杂度O(1)。若不需要搜索全数组，前面的n会变成logn

例子：

LeetCode 875 Koko Eating Bananas

Python代码：

def minEatingSpeed(self, piles: List[int], h: int) -> int:
	#if len(piles) == 1: # attn
	 #   return math.ceil(piles[0] / h)
	# piles.sort()
	
	def get_hours(piles, k):
		return sum([math.ceil(n / k) for n in piles])


	# start, end = piles[0], piles[-1] # 3, 4
	start, end = 1, max(piles) # attn: 1 rather than min(piles)
	while start + 0.5 < end: # attn: use 0.5
		mid = start + (end - start) / 2 # attn /2 not // 2 | 7, 5, 4            
		hours = get_hours(piles, int(mid))  # attn: int(mid) | 5, 8, 8
		if h >= hours: # eat slower, attn 8 > 5
			end = mid # end=7, 5, 4
		else:
                start = mid

注意事项：

start是从1开始，不是min(piles)。最大值取max(piles)因为跟取整型最大值是一样的。这样也可以避免单独处理单元素数组。
epsilon取0.5. 一般整数题都取0.5
mid是除2获得不是//2
mid作为参数输入到get_hours()要去int(mid)与题目一致，因为题目的k是整数
模板中h==hours时，不能return，要继续在左半区找，因为要达到误差epsilon内才会停止。类似于first_position

BST的非递归和递归中序，前序，后序遍历

Posted on 2026-05-27 Edited on 2026-06-03 Disqus:

中序遍历算法思路：

如图所示，总体思路是左节点按层次遍历，而区别在于何时加入到结果集。

首先初始化将root的所有左儿子加入到stack。
开始循环，取出节点，判断其右儿子不为空，因为左儿子已经访问过。
若右子树不为空，跟初始化一样，将右子树的所有左儿子加入到栈中。
用到两个指针node和n，分别指向出栈节点和遍历所有左儿子节点。

若前序遍历，只要把打印语句从出栈时打印移到入栈时打印即可。见L144

应用：

BST的关于Iterator的题目Leetcode 173
不需要遍历所有节点而需要遍历某些节点的题目如求某target最接近N个节点。Leetcode 272

中序遍历

Leetcode 094 Binary Tree Inorder Traversal

Python代码：

def iterative_inorder(self, root: TreeNode) -> List[int]:
	if not root:
		return []
	res, stack = [], []
	it = root
	while it:
		stack.append(it)
		it = it.left
	while stack:
		node = stack.pop()
		res.append(node.val)
		if node.right:
			n = node.right
			while n:
				stack.append(n)
				n = n.left
	return res

前序遍历

Leetcode 144 Binary Tree Preorder Traversal
只要将出栈节点加入结果换到入栈前加即可，也就是将Line 11换到取Line 7和Line 15

Python代码：

def iterative_preorder(self, root: TreeNode) -> List[int]:
	if not root:
		return []
	res, stack = [], []
	it = root
	while it:
		stack.append(it)
		res.append(it.val)
		it = it.left
	while stack:
		node = stack.pop()
		if node.right:
			n = node.right
			while n:
				stack.append(n)
				res.append(n.val)
				n = n.left
	return res

后序遍历

Leetcode 145 Binary Tree Postorder Traversal
跟中序比，需要用一个记数器来记录出现在栈顶的次数，若为2次就加入到结果集，并且不能继续迭代到右节点，因为第一次时候已做了。
由于tuple不可改，所以即使次数为1，也要出栈，更新次数后重新入栈。代码区别在Line 10 - 17.

注意事项：

记得要continue。
每个node出栈后再次入栈(else里面)

Python代码：

def iterative_postorder(self, root: TreeNode) -> List[int]:
	if not root:
		return []
	it = root
	stack, res, freq = [], [], defaultdict(int)
	while it:
		stack.append(it)
		it = it.left
	while stack:
		node = stack.pop()
		freq[node] += 1
		if freq[node] == 2:
			res.append(node.val)
			continue
		else:
			stack.append(node)
		if node.right:
			n = node.right
			while n:
				stack.append(n)
				n = n.left
	return res

def iterative_postorder(self, root: TreeNode) -> List[int]:
	if not root:
		return []
	res, stack = [], []
	it = root
	while it:
		stack.append((it, 0))  # count for it in the stack top
		it = it.left
	while stack:
		pair = stack.pop()
		node = pair[0]
		occurrence = pair[1] + 1
		if occurrence == 2:
			res.append(node.val)
			continue  # don't iterate on right node again
		else:
			stack.append((node, occurrence))
		if node.right:
			n = node.right
			while n:
				stack.append((n, 0))
				n = n.left
	return res

递归写法

DFS
BST的递归前序遍历Leetcode 0144
BST的递归中序遍历Leetcode 0094

Python代码：

def recursive_inorder(self, root: TreeNode) -> List[int]:
	return self.dfs_inorder(root)

def dfs_inorder(self, root):
	if not root:
		return []
	return self.dfs_inorder(root.left) + [root.val] + self.dfs_inorder(root.right)

def recursive_preorder(self, root: TreeNode) -> List[int]:
	return self.recursive_preorder(root)

def recursive_preorder(self, root):
	if not root:
		return []
	return [root.val] + self.recursive_preorder(root.left) + self.recursive_preorder(root.right)

def recursive_postorder(self, root: TreeNode) -> List[int]:
	return self.recursive_postorder(root)

def recursive_postorder(self, root):
	if not root:
		return []
	return self.recursive_postorder(root.left) + self.recursive_postorder(root.right) + [root.val]

Java代码：

protected void iterativeInorder(BinaryNode p) {  
	Stack<BinaryNode> stack = new Stack<BinaryNode>();  
	BinaryNode head = p;
	while(head != null) {
		stack.push(head);
		head = head.left;
	}
	
	BinaryNode node = null;
	while (stack.size() > 0) {  
		node = stack.pop();
		System.out.print(node.data);
		if(node.right != null) {
			BinaryNode n = node.right; 
			while(n != null) {
				stack.push(n);
				n = n.left;
			}
		}
	}  
}

算法分析：

时间复杂度为O(n)，n为字符串长度，空间复杂度O(logn)，最差为O(n)。

组合

Posted on 2026-05-27 Edited on 2026-06-03 Disqus:

算法思路：

Leetcode 078的题目。这里作为知识点归纳。

递归中i=st开始。
回溯： path递归后去恢复状态。
dfs中传入i+1。
结果要复制new ArrayList<>(path)
一般来说，终止条件才加入结果，但由于子集任何path修改都是子集，所有立即加入。

和全排列的区别：

由于排列可以乱序如[1,2,3]结果是[1,3,2]也就是一个结果需要多次从左向右完全扫描，所以i=0开始且维护visited数组
组合的结果是按照数组顺序的，所以只要从左到右扫描一次即可，所以用i=st。
结果方面，排列结果是满长度，而组合不是。所以在加入到res位置上，组合用st来判断是否结束且加入到path就立刻进入最后
结果，而排列是在终结条件上加入。

注意事项：

输入不合法，返回[[]]
记得API是dfs(nums, st, path, result), 4个参数
递归是i+1，不是start+1

学习要点：

详见DFS要点，大部分DFS题目涉及

用到全组合的API: dfs(nums, start, path, result), 4个参数
用到全组合的递归: dfs(nums, i + 1, path, result)
用到全排列的其他部分包括恢复状态和终止条件(加入res)

应用：

找所有可能性

def combine(self, nums: List[int]) -> List[List[int]]:
	if not nums:
		return [[]]
	path, result = [], []
	self.dfs(nums, 0, path, result)
	return result

def dfs(self, nums, st, path, result):
	if len(path) == len(nums):
		return

	for i in range(st, len(nums)):
		path.append(nums[i])
		result.append(list(path))
		self.dfs(nums, i + 1, path, result)
		path.pop()

Java代码：

public List<List<Integer>> subsets(int[] nums) {
	List<Integer> path = new ArrayList<>();
	List<List<Integer>> res = new ArrayList<>();
	res.add(new ArrayList<>(path)); //empty set
	if(nums == null || nums.length == 0)
		return res;
	dfs(nums, 0, path, res);
	return res;
}

void dfs(int[] nums, int st, List<Integer> path, List<List<Integer>> res) {
	if(st == nums.length)
		return;
	
	for(int i = st; i < nums.length; i++) {
		path.add(nums[i]);
		res.add(new ArrayList<>(path));
		dfs(nums, i + 1, path, res);
		path.remove(path.size() - 1);
	}
}

算法分析：

时间复杂度为O(2ⁿ) ，空间复杂度O(1)。