LeetCode Experience

二叉树 binary tree

我们来拿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

而这里还有一个就是反转tree，又叫做invertTree，核心思路就是出现一个root节点的时候，交换他们的左右子树，不是交换值，而是直接交换左右节点：

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

其实从这里也基本可以看到了有时候需要嵌套一个函数

广度优先，要用的数据结构是队列，就是queue，这个非常重要，因为广度优先最要紧的就是FIFO，因此我们需要考虑用层数一层一层来，下面是最著名的问题：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

哈希表

哈希表是用于存放频率的一个数据结构，主要初始化的方式是：

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

链表

ListNode()

这个最核心的就是两个，一个是val，一个是stack

核心操作主要是：

第一个操作是反转

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

第二个常见操作是：

dummy = ListNode()
head = dummy

通过dummy来处理很多head的问题，或者说只有一个节点的

要取数值的话，只有一个个遍历，就是O(N)

关于循环链表，还可以需要用循环指针

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

双指针模版，用于删除倒数第n个元素

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

动态规划的意思不是指每次从头开始计算，而是利用已经计算过的或者说不断累积已经知道的结果，比如下面这道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]

当然也可以用动态规划去接最大subarray的值

# 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)

对于动态规划来说，更加核心的是，做或者不做，因此其实不需要设定太多规则，就是记录当前就行了，比如是198. House Robber这个问题，就是第几个房子，我抢还是不抢，要求就是不能连续抢两家，因此代码

# 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]

上面这道题目还可以更加精简一点，降低到n(1)的复杂度，因为我们已经可以发现我们只需要记录前两个和当前这个数值就好了。

# 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

而322. Coin Change这道题目就是更加典型了，因为要考虑的是首先我们要关注怎么定义dp的状态，这个是首先需要考虑的要凑齐一定amount金额的，需要有现在硬币的哪几种。因此最核心的，就是看状态的定义和状态转移方程。

# 我们首先要确定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

首先是关于树的结构，有一个节点和两条边

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

通过这种方式就建立起了树结构，但是如果想要建树就需要：

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

对于DFS（Depth First search）首先最重要的思想就是递归。

递归，就是先找到最终节点，然后开始一层一层返回，或者说是通过找到最终状态，然后return后，一层层回去。

递归是一种函数自己调用自己的编程技巧，就是函数内部有自己函数调用。

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

那这里有下一步需要考虑的就是不同的遍历方式，存在三种遍历方式

1. preorder（前序）： root —> left —> right 2. inorder（中序）: left —> root —> right 3. postorder（后序）: left—> right —> root

核心的区别就在于root在什么位置。

特别注意如果针对有序binary search tree （BST），inorder其实是有序的出来以后，升序。

从代码来理解这三种区别

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)

后序非常重要，因为很多问题都是：

我必须先知道左右子树的信息，然后才能计算当前节点。

例如：

Maximum Depth

Balanced Binary Tree

Diameter of Binary Tree

Maximum Path Sum

我们来拿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

而这里还有一个就是反转tree，又叫做invertTree，核心思路就是出现一个root节点的时候，交换他们的左右子树，不是交换值，而是直接交换左右节点：

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

堆，就是维护一个列表，因此初始化的时候，也还是[]这种形式开始，heap最多就是能保证父节点≤子节点，但不保证是一个有序数列。

这个也是一个合法的heap，因此不一定是有序的，这个非常重要！

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

因此可以看到有点类似于树结构。

比如针对力扣的215这道题目，我们就可以看到一个很有意思的思路，就是控制k个最大值：

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)

对于347. Top K Frequent Elements这道题目，其实很有意思，返回一个数组

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

这里有一个非常有趣的情况，就是我们在复制节点的时候，需要考虑的是深度复制，即应该新创建一个node，然后利用这个新创建的node，去连接别的新创建的node。

在133.Clone Graph这道题目中，就是这个思路。

其实总体来看，思路就是做一个dfs，然后去遍历所有的node。在这道题目中，最重要的是让node遍历完以后，还要创建邻居，用旧的node作为hashmap，去检索。

因此主要解题过程：

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

下面有非常有意思的事情和需要明确记住的方式：

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


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

因此我们就可以去做相应的拓扑排序的分析了

我们更加重要的是，需要去判断是否存在一个环，因此我们就需要用一个非常有意思的方法去做，那就是采用队列

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

回溯算法最核心的其实就是利用DFS进行，然后一个回溯的过程，核心代码就是：

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

由此我们可以看到这个整个过程，就是先添加，再回溯。

通过先添加，后面再弹出的方式，使得路径可以回退，但这里用dfs与在树结构用dfs有个很大的差别，树结构通过到达叶子节点以后返回，但是回溯是通过把条件都过一遍以后，再选择返回。

那现在让我们来手写完成39. Combination Sum，这道题目的要点就是，有一个candidates列表，然后有一个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

Anagram这道题目仍旧考虑用hashmap

这道题目是49. Group Anagrams，很明显根据这道题目，我们可以采用hashmap来存对应的排序后的strs，因为hashmap的key要求的是唯一性，因此可以用排序后的字符串来作为一个key，但是这里会有一个非常难的事情在于，怎么把这个字符串变成一个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"

通过上面这种方式就可以进一步处理了，在hashmap中存入对应的字符串就好了，因此针对这道题目，完整的就是：

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())

HashSet的一些用法

在力扣中128. Longest Consecutive Sequence这道题目，要求我们去找到最长的连续的序列，比如：

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.

因此，如果在不考虑时间复杂度的情况下，那就直接用set就好了，为什么不用list呢？因为这里面可能会存在重复的数字，因此我们可以用排完序的list，然后来比较就好了。

# 下面是错误事例！
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

但是这道题目特别强调了时间复杂度不能超过O(n)，但我们用了sorted，因此就会导致时间复杂度达到了O(nlogn)，我们要做的是所有数值仅仅遍历一遍。

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

Prefix这种题目

这种题目的核心要领就是有一部分其实可以用数组存下来，已经是固定的，或者说类似于用数组存下来，而不用每次都去计算。

特别针对的是238. Product of Array Except Self这道题目，就是正如这道题目所描述的，就是要求我们去算除了自己以外的product值，然后这道题目非常要求的是，不能让时间复杂度超过O(n)。

如果可以超过O(n)，那么相当于每个数都遍历过来，然后再遍历前后就好了，时间复杂度是O(n^2)，因此可以有现在：

最核心的思路就是空间换时间，多用几个数组，来存储对应的数据

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