LeetCode Experience — Kaituo Zhang

Binary Tree

Let's practice with MaxDepth:

def maxDepth(self, root:Optional[TreeNode]) --> int:
	# 最重要的第一步，先给定返回的条件，这个也是递归算法非常重要的一个部分：
	if not root:
		return 0
	
	# 这一步是递归算法，相当于从左边节点先开始算深度
	left_depth = self.maxDepth(root.left)
	right_depth = self.maxDepth(root.right)
	
	return max(left_depth, right_depth) + 1

Another problem is tree inversion, also known as invertTree. The core idea is that when a root node appears, we swap its left and right subtrees, not just swapping values, but directly swapping the left and right nodes.

def invertTree(self, root:Optional[TreeNode]) --> Optional[TreeNode]:
	if not root:
		return
	
	# 写递归的时候，一定得想清楚函数的返回值是什么，以及该怎么用
	# 在这道题目里面返回值是树的节点，因此可以直接用进行交换
	
	# 交换节点
	root.left, root.right = root.right, root.left
	
	
	# 进行递归
	invertTree(self.left)
	invertTree(self.right)
	
	return root

From this point, you can see that sometimes it's necessary to nest a function.

For breadth-first search, the data structure used is a queue, which is very important because the key aspect of breadth-first search is FIFO. Therefore, we need to consider traversing layer by layer. Below is the most famous problem:102. Binary Tree Level Order Traversal

from collections import deque

class Solution:
	def levelOrder(self, root:Optional[TreeNode] --> List[List[int]]:
		# standard flow:
		if not root:
			return []
			
		# define the inital
		queue = deque([root])
		result = []
		
		while queue:
			# 保存每一层的情况
			
			# 这里的len(queue)是指这个队列里面有多少个树节点元素。
			level_size = len(queue)
			level = []
			
			for _ in range(level_size):
			
				node = queue.popleft()
				level.append(node.val)
				
				if node.left:
					queue.append(node.left)
				
				if node.right:
					queue.append(node.right)
					
			result.append(level)
		
		return result

Hash Table

A hash table is a data structure used to store frequencies, primarily initialized as follows:

hashmap = {}

# 加入最新的key和对应的val主要采用的方式是

for num in nums:
	# 在这里用get进行初始化
	hashmap[num] = hashmap.get(num, 0) + 1

for num, freq in hashmap.items():
	# 通过.items()这种方式遍历，而不能用enumerate，enumerate就看成了index

Linked List

ListNode()

The core components are two: one is val, and the other is stack.

The main operations are as follows:

The first operation is reversal.

prev = None
current_next = current.next
current.next = prev
prev = current
current = current_next

The second common operation is:

dummy = ListNode()
head = dummy

Using a dummy node to handle many head-related issues, or cases with only one node.

To retrieve values, you can only traverse one by one, resulting in O(N).

For circular linked lists, circular pointers may also be necessary.

slow = head
fast = head.next

while slow != fast:
	if not fast or not fast.next:
		return False
	slow = slow.next
	fast = fast.next.next
return True

The two-pointer template is used to delete the nth last element.

dummy = ListNode()
dummy.next = head

point1 = dummy
point2 = dummy

for _ in range(n):
	point2 = point2.next
	
while point2.next:

	point1 = point1.next
	point2 = point2.next
	
point1.next = point1.next.next

return dummy.next

Dynamic Programming

Dynamic programming does not mean recalculating from scratch each time, but rather utilizing previously computed results or continuously accumulating known results, as seen in the problem below.70. Climbing Stairs

# define the state
dp = [0] * (n + 1)

# define the initial states
dp[1] = 1
dp[2] = 2

# define state-transition equation
# dp[n] = dp[n - 1] + dp[n - 2]
# 要么就是从上面一步到或者两步之前到
for i in range(3, n+1)
	dp[i] = dp[i - 1] + dp[i - 2]
	
# obtain the result: dp[n]

return dp[n]

Dynamic programming can also be used to obtain the maximum subarray value.

# define the state
# the max value include this num
# nums is the list of all numbers
dp = [0] * len(nums)

# define the initial state
dp[0] = nums[0]

# define the state-transition equation
for i in (1, range(nums)):
	dp[i] = max(nums[i], dp[i - 1] + nums[i])
	
return max(dp)

For dynamic programming, the core aspect is whether to take an action or not, so it is not necessary to set many rules; just recording the current state is sufficient, for example,198. House RobberIn this problem, the decision for each house is whether to rob it or not, with the condition that no two adjacent houses can be robbed.

# define the state and judge the special condition
if len(nums) == 1:
	return nums[0]

dp = [0] * len(nums)

# define the initial state
dp[0] = nums[0]
# this step is very important, here is not the dp[1] = nums[1]
# Because our state is until this house, the biggest money
# for this house means whether to rob
dp[1] = max(nums[0], nums[1])


# define state-transition equation
for i in range(2, len(nums))
	dp[i] = max(dp[i-1], dp[i-2] + nums[i])

# get the result, for this problem, we can find the last one is the biggest
return dp[-1]

The above problem can be further simplified to reduce the complexity to O(1), as we can observe that we only need to keep track of the previous two values and the current value.

# define the state and judge the special condition
if len(nums) == 1:
	return nums[0]
	
prev2 = nums[0]
prev1 = max(nums[0], nums[1])

current = prev2

for i in range(2, len(nums)):
	current = max(prev1, prev2 + nums[i])
	
	# this is very important, the state-transition
	prev2 = prev1
	prev1 = current

return current

In contrast,322. Coin ChangeThis problem is more typical since we must first consider how to define the dp states. This involves figuring out which denominations of coins are available to make up a specific amount. Thus, the most critical aspect is the definition of states and the state transition equation.

# 我们首先要确定dp，这里的dp应当是设置为当前金额，需要用到coins里面的哪几种，以及能否凑出来
# 如果能凑出来就不是无限，凑不出来就是无限，这里面特别注意无限可以用float('inf')这个函数
# 然后需要进行遍历coins里面，看看能不能凑出来
# 特别需要注意的是，怎么找dp，那就是找这个问题能否被拆解为更小的子问题，比如找amount 7，
# 那我们可以看看amount(7-coins)有没有更小的方案，因此这就是为什么我们把dp设置为金额

# define state
dp = [float("inf")] * (amount + 1)

# define inital state
dp[0] = 0

# define state-transition equation
for i in (1, amount + 1):
	for coin in coins:
		if i >= coin:
		# whether can use the coin to reach the amount
			dp[i] = min(dp[i], dp[i - coin] + 1)

# Can't reach the amount
if dp[amount] == float("inf"):
	return -1
	
return dp[amount]

Binary Tree

First, regarding the structure of a tree, there is one node and two edges.

class TreeNode:
	def __init__(self, val, right=None, left=None):
		self.val = 0
		self.right = right
		self.left = left

Using this method establishes a tree structure, but to construct a tree, it is necessary to:

root = TreeNode(0)

root.left = TreeNode(1)
root.right = TreeNode(2)


root.left.left = TreeNode(3)
root.left.right = TreeNode(4)

root.left.right.val
# we will get: 4

DFS

For DFS (Depth First Search), the most important idea is recursion.

Recursion means first finding the final node, then returning layer by layer, or identifying the final state and then returning backwards layer by layer.

Recursionis a function that calls itself.Programming techniques,which involve self-calling functions within their own scope.

def dfs(root):
	# 这一步非常重要，因为我们需要考虑究竟还存不存在这个TreeNode
	if not root:
		return
		
	# 自己调用自己
	dfs(root.left)
	dfs(root.right

Next, we need to consider the different traversal methods, of which there are three.

1. preorder: root → left → right 2. inorder: left → root → right 3. postorder: left → right → root

The core difference lies in the position of the root.

It is especially important to note that for a sorted binary search tree (BST), an inorder traversal actually produces the elements in sorted order, ascending.

Let's understand the differences between these three through code.

def preorder(root):
	if not root:
		return
		
	print(root.val)
	preorder(root.left)
	preorder(root.right)
	

def inorder(root):
	if not root:
		return
	
	preorder(root.left)
	print(root.val)
	preorder(root.right)
	
	
def postorder(root):
	if not root:
		return
	
	postorder(root.left)
	postorder(root.right)
	print(root.val)

Postorder is very important because many problems involve:

I must first know the information of the left and right subtrees before I can compute the current node.

For example:

Maximum Depth

Balanced Binary Tree

Diameter of Binary Tree

Maximum Path Sum

Let's practice with MaxDepth:

def maxDepth(self, root:Optional[TreeNode]) --> int:
	# 最重要的第一步，先给定返回的条件，这个也是递归算法非常重要的一个部分：
	if not root:
		return 0
	
	# 这一步是递归算法，相当于从左边节点先开始算深度
	left_depth = self.maxDepth(root.left)
	right_depth = self.maxDepth(root.right)
	
	return max(left_depth, right_depth) + 1

def invertTree(self, root:Optional[TreeNode]) --> Optional[TreeNode]:
	if not root:
		return
	
	# 写递归的时候，一定得想清楚函数的返回值是什么，以及该怎么用
	# 在这道题目里面返回值是树的节点，因此可以直接用进行交换
	
	# 交换节点
	root.left, root.right = root.right, root.left
	
	
	# 进行递归
	invertTree(self.left)
	invertTree(self.right)
	
	return root

From this point, you can see that sometimes it's necessary to nest a function.

from collections import deque

class Solution:
	def levelOrder(self, root:Optional[TreeNode] --> List[List[int]]:
		# standard flow:
		if not root:
			return []
			
		# define the inital
		queue = deque([root])
		result = []
		
		while queue:
			# 保存每一层的情况
			
			# 这里的len(queue)是指这个队列里面有多少个树节点元素。
			level_size = len(queue)
			level = []
			
			for _ in range(level_size):
			
				node = queue.popleft()
				level.append(node.val)
				
				if node.left:
					queue.append(node.left)
				
				if node.right:
					queue.append(node.right)
					
			result.append(level)
		
		return result

Heap

A heap maintains a list, so during initialization, it starts in this form: []. A heap ensures that a parent node ≤ child nodes, but it does not guarantee a sorted sequence.

This is also a valid heap and thus not necessarily sorted, which is very important!

heap = [1, 3, 2, 7, 6, 5]

Therefore, it can be seen that it is somewhat similar to a tree structure.

For example, regarding LeetCode problem 215, we can see an interesting idea, which is to control the k largest values:

import heapq #这个是最重要的package，对于heap来说
Class Solution:
	def KthLargestElement(self, nums:List[int], k:int) -> int:
		 heap = []
		 
		 for num in nums:
			 heapq.heappush(heap, num)
			 
			 # 最关键的一步，就是当heap中的元素数量超过k的时候，我们就可以直接维护这个k个
			 # 然后提取出顶端的这个，就是第k个最大的数了
			 # 由于heap已经是一个类似排好序的情况，因此我们可以直接从中提取出最小的
			 # 
		 
		 if len(heap) > k:
			 heapq.heappop(heap)

For347. Top K Frequent ElementsThis problem is quite interesting; it returns an array.

import heapq
Class Solution:
	def TopKFrequentElements(self, nums: List[int], k: int) -> List[int]:
		# 这道题目的思路是，先用hashmap来统计frequency，然后再考虑用heap来统计k个频率
		heap = []
		hashmap = {}
		
		for num in nums:
			hashmap[num] = hashmap.get(num, 0) + 1
		
		for num, freq in hashmap.items():
		# 注意这里有一个trick，就是我们用tuple，当我们用tuple的时候，heap排序是跟着第一个元素
			heapq.heappush(heap, (freq, num))
			if len(heap) > k:
				heapq.heappop(heap)
		
		return [num for freq, num in heap]

# 这道题目还有一种就是用桶排序来解决，这个比较有意思

Class Solution:
	def TopKFrequentElements(self, nums: List[int], k: int) -> List[int]:
		hashmap = {}
		
		# 对桶进行初始化
		backet = [ [] for _ in range(len(nums) + 1)]
		# 注意上面这句，与下面这句非常不一样
		# backet = [[]] * (len(nums) + 1)
		# 因为如果用下面这句，就是指引全都指向同一个
		
		for num in nums:
			hashmap[num] = hashmap.get(num, 0) + 1
			
		# 根据频率放入对应的桶里面
		
		for num, freq in hashmap.items():
			backet[freq].append(num)
			
		result = []
		# 下面这个循环非常有意思，相当于是从尾到头倒序
		for i in range( len(nums) + 1, 0 , -1):
			for num in backet[i]:
				result.append(backet[i])
			
			if len(result) == k:
				return result

graph deep

There is a very interesting situation here: when copying nodes, we need to consider deep copying, which means creating a new node and then using this newly created node to connect to other newly created nodes.

In LeetCode problem 133, Clone Graph, this is the thought process.

Overall, the approach is to perform a DFS and traverse all the nodes. In this problem, the key point is that after a node has been traversed, we also need to create neighbors, using the old node as a hashmap for retrieval.

Thus, the main problem-solving process is as follows:

def CloneGraph(self, node: Optional['Node']) -> Optional['Node']:
	# 首先需要先初始化一下我们的hashmap
	# 因为这个hashmap是用于我们去存储和检查原始的node和新node的关系
	# 以及里面会存储着new node的相关邻居
	
	hashmap = {}
	
	# 接下来开始定义dfs函数，首先我们需要搞清楚，究竟要返回什么
	# 很明显，我们要返回的是hashmap中当我们给定old node，应该是返回new node
	
	def dfs(node):
		# 第一步先判断是否为空！
		if not node:
			return None
		
		# 第二步要判断究竟这个node是否之前已经遍历过了
		# 如果遍历过了，就返回这个遍历过的node的新head
		if node in hashmap:
			# 返回新的node
			return hashmap[node]
			
		# 创建node
		new_node = Node(node.val)
		# 注意要立即加入这个node进hashmap
		hashmap[node] = new_node
		
		# 开始给new node添加邻居了
		for neighbor in node.neighbor:
			# 在这里有一步非常关键，就是dfs(neighbor)这个很关键
			# 因为我们要添加的是new node
			new_node.neighbors.append(dfs(neighbor))
		
		# 等都结束了，那就返回old node的new node
		return hashmap[node]
		
return dfs(node)

Topological Sort

There are very interesting things and ways to remember here:

# 当我们开始想要去做那种设定二维数组的时候，比如记录图中某个节点的下一个节点是什么的时候
# 我们就得开始利用二维数组，但是初始化要按照下面这个方式
graph = [[] for _ in range(n)]
# 注意千万不是下面这种！
graph = [[]] * n !!! Wrong!
# 这是因为python中用这种方法来加载二维数组会导致一起改变
graph[0] 是指第一个节点，其中的数据就是连接的是哪几个节点


# 初始化一维数组
indegree = [0] * n
indegree[0] 则表示第一个节点的indegree数据

Thus, we can proceed with the corresponding analysis of topological sorting.

What is more important is that we need to judge whether there is a cycle, so we need to use a very interesting method to do this, which is to adopt a queue.

from collections import deque

def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:

	graph = [[] for _ in range(numCourses)]
	
	indegree = [0] * numCourses
	
	
	# 创建队列
	queue = deque()
	
	# 先将节点放到graph中
	
	for course, prerequisite in prerequisites:
		# 我们要记录的是当前这个pre连接着哪几节以它为基础的课
		graph[prerequisite].append(course)
		# 然后要这节course的indegree需要增加
		indegree[course] += 1
		
	for i in len(numCourses):
		if indegree[i] == 0:
		# 代表这节课是否没有前置课程的
			queue.append(i)
	
	# 记录一下有多少课	
	result= []
	
	while queue:
		node = queue.popleft()
		
		# 将没有前置课先给弹出来
		result.append(node)
		
		# 开始遍历以它为前置的courses
		for neighbor in graph[node]:
			indegree[neighbor] -= 1
			if indegree[neighbor] == 0:
				queue.append(neighbor)
	
	return len(result) == numCourses

Backtracking

The core of the backtracking algorithm is actually to utilize DFS, followed by a backtracking process, where the core code is:

def backtracking(start, path):
	if XXXX:
		return
	
	for i in range(start, path):
		path.append(nums[i])
		
		# 核心的递归算法来了
		backtracking(i + 1, path)
		
		path.pop()

From this, we can see that the entire process consists of adding first and then backtracking.

By adding first and then popping later, the path can backtrack; however, there is a significant difference between using DFS here and using DFS in a tree structure. In the tree structure, you return after reaching the leaf node, but backtracking involves iterating through all conditions before choosing to return.

Now let's manually complete 39. Combination Sum. The key point of this problem is that there is a candidates list and a target:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

"""
	我们需要先理清一下思路，那就是这道题目需要用到回溯算法，因为我们需要用里面的一层一层去
	读取，因此通过这个方式我们可以得到更加具体的数字。

"""

def combinationSum(self, candidates:List[int], target:int) -> List[List[int]]:
	# results 用于存储最终返回的list
	results = []
	amount = 0
	path = []
	
	def backtracking(start, amount, path):
		# 一切DFS一开始都要先判断返回条件如何
		if amount > target:
			return
		
		if amount == target:
			# 如果达到了target，那么就说明
			# 这里有一个大坑！！！就是关于path[:]这里一定要用这样子，不然path会随着改变的
			# 类似于指针指向，因此到最后就变成了空数组！
			return results.append(path[:])
		
		#遍历一遍
		for i in range(start, len(candidates)):
			# 第一步先将candidates中，目前选到的数加到path里面
			path.append(candidates[i])
			amount += candidates[i]
			
			backtracking(i, amount, path)
			
			path.pop()
			amount -= candidates[i]
			
	backtracking(0, amount, path)
	
	return results

For the Anagram problem, we still consider using a hashmap.

This problem is 49. Group Anagrams. It is clear that based on this problem, we can use a hashmap to store the corresponding sorted strs. Since the key of a hashmap requires uniqueness, we can use the sorted string as a key. However, there is a very challenging issue here: how to convert this string into a key.

strs = ["abs", "bas", "her"]

# if we directly use:
str = sorted(strs[0])
# str is not a str, but it is a list:["a", "b", "s"]
# 因此应当用的是
str = "".join(str)
# str此时就变成了 str = "abs"

With the above method, we can further process by simply storing the corresponding strings in the hashmap. Therefore, for this problem, the complete solution is:

class Solution:
	def Multi_Anagram(self, strs:List[str]) -> List[List[str]]:
		hashmap = {}
		
		for s in strs:
			s_sorted = ''.join(sorted(s))
			
			if s_sorted not in hashmap:
				hashmap[s_sorted] = []
			
			hashmap[s_sorted].append(s)
			
		return List(hashmap.values())

Some uses of HashSet.

In LeetCode,128. Longest Consecutive Sequence. This problem requires us to find the longest consecutive sequence, for example:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Therefore, if we do not consider time complexity, we can directly use a set. Why not use a list? Because there may be duplicate numbers, thus we can use a sorted list to compare.

# 下面是错误事例！
class Solution:
	def Longest_Consecutive_Sequence_Set(self, nums:List[int]) -> int:
		# 为什么需要sorted，这是因为set只能去重，但不会排序
		# 所以用下面这句是大错特错！因为就算是一个sorted list，丢入给set，还是会被打乱顺序
		hashset = set(list(sorted(nums)))
		# 真的要用有序序列的话，就得用
		# new_list = sorted(set(nums))
		
		max_length = 1
		current_length = 1
		
		for num in hashset:
			
			if num + 1 in hashset:
				current_length += 1
			else:
				current_length = 1
			
			max_length = max(max_length, current_length)
		
		return max_length

However, this problem specifically emphasizes that the time complexity cannot exceed O(n). Since we used sorting, it leads to a time complexity of O(nlogn), whereas we need to ensure all values are traversed only once.

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
				# 这一步不能改变，因为还是要去重
        num_set = set(nums)

        max_length = 0

        for num in num_set:
            current_length = 1
            current_num = num
						# 这一步是至关重要的，因为通过这个方式可以来确定之前是否已经遍历过了
						# 即如果已经存在连续队列里面了，那就不用去走一遍了
            if current_num - 1 not in num_set:

                while current_num + 1 in num_set:
                    current_length += 1
                    current_num += 1
                max_length = max(current_length, max_length)
		
        return max_length

Problems involving Prefix.

The core point of such problems is that a part can actually be stored in an array, which is fixed, or similar to storing in an array, rather than calculating every time.

Specifically targeting 238. Product of Array Except Self. This problem, as described, requires us to calculate the product value excluding oneself, and this problem demands that the time complexity not exceed O(n).

If it could exceed O(n), then it would mean traversing every number and then traversing before and after again, leading to a time complexity of O(n^2). Therefore, we can have the current approach:

The core idea is to trade space for time, using multiple arrays to store corresponding data.

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        # First initialization
        left = [1] * len(nums)
        right = [1] * len(nums)
        result = [1] * len(nums)

        # Store the left side production
        for i in range(1, len(nums)):
            left[i] = left[i - 1] * nums[i - 1]
        
        # Store the right side production
        # For the right side, we should use the descending order
        for i in range(len(nums) - 2, -1, -1):
            right[i] = right[i + 1] * nums[i + 1]

        for i in range(len(nums)):
            result[i] = left[i] * right[i]
        
        return result