KK's blog

LeetCode

There is an undirected graph with n nodes, where each node is numbered between 0 and n - 1. You are given a 2D array graph, where graph[u] is an array of nodes that node u is adjacent to. More formally, for each v in graph[u], there is an undirected edge between node u and node v. The graph has the following properties:

There are no self-edges (graph[u] does not contain u). There are no parallel edges (graph[u] does not contain duplicate values).
If v is in graph[u], then u is in graph[v] (the graph is undirected). The graph may not be connected, meaning there may be two nodes u and v such that there is no path between them.

A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B.

Return true if and only if it is bipartite.

Example 1:

Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: false
Explanation: There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.

Example 2:

Input: graph = [[1,3],[0,2],[1,3],[0,2]]
Output: true
Explanation: We can partition the nodes into two sets: {0, 2} and {1, 3}.

Constraints:

graph.length == n 1 <= n <= 100
0 <= graph[u].length < n 0 <= graph[u][i] <= n - 1
graph[u] does not contain u. All the values of graph[u] are unique.
* If graph[u] contains v, then graph[v] contains u.

题目大意：

无向图中是否存在一个划分，将节点分为两集合，任何一条边都连接着两个集合，也就是不存在一条边在单一集合内。

解题思路：

图上色法。两种颜色，将节点上色0，儿子上色1，若某个节点已经上的色和将要上的色矛盾（来自的路径不同），即不合法

解题步骤：

N/A

注意事项：

1. 图上色法。两种颜色，将节点上色0，儿子上色1，若某个节点已经上的色和将要上的色矛盾（来自的路径不同），即不合法
2. 题意表示，图可能是有几个连通图，所以要从每个节点做BFS，除非节点已访问过， Line 4. node_to_color作为visited的功能
3. return True在两个函数中要写，否则返回None

Python代码：

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

def isBipartite(self, graph: List[List[int]]) -> bool:
	node_to_color = collections.defaultdict(int)
	for i in range(len(graph)):
		if i in node_to_color: # disconnected nodes
			continue
		node_to_color[i] = 0
		if not self.bfs(graph, i, node_to_color):
			return False
	return True

def bfs(self, graph, n, node_to_color):
	queue = collections.deque([n])
	while queue:
		node = queue.popleft()
		for neighbor in graph[node]:
			if neighbor in node_to_color and node_to_color[neighbor] != 1 - node_to_color[node]:
				return False
			if neighbor in node_to_color:
				continue
			queue.append(neighbor)
			node_to_color[neighbor] = 1 - node_to_color[node]
	return True

算法分析：

时间复杂度为O(V + E)，空间复杂度O(V + E)

LeetCode

Input: expression = “e + 8 - a + 5”, evalvars = [“e”], evalints = [1]
Output: [“-1a”,”14”]

Input: expression = “e - 8 + temperature - pressure”, evalvars = [“e”, “temperature”], evalints = [1, 12]
Output: [“-1pressure”,”5”]

Input: expression = “(e + 8)  (e - 8)”, evalvars = [], evalints = []
Output: [“1ee”,”-64”]

题目大意：

表达式含有若干变量evalvars及其对应值evalints，且含加减乘和括号，求结果。若变量不在evalvars就简化表达式

解题思路：

此题不需要掌握，若考到就认命好了。之前的LeetCode 224 Basic Calculator含有括号和加法已经是Hard，此题不但有括号和加减乘，还有变量，难度不止提高一个数量级。不过不可以用eval函数的条件去掉了。所以就是考察eval。
如果不含变量，直接调用eval即可求解

Python代码：

1
2

def basicCalculatorIV(self, expression: str, evalvars: List[str], evalints: List[int]) -> List[str]:
	return eval(expression)

含变量且变量有值，就调用字典将变量替代掉，这里考到了regex替代函数re.sub

Python代码：

1
2
3
4
5
6
7
8
9
10
11

def basicCalculatorIV(self, expression: str, evalvars: List[str], evalints: List[int]) -> List[str]:
	var_to_val = dict(zip(evalvars, evalints))

	def f(s):
		token = s.group()
		s = str(var_to_val[token] if token in var_to_val else token)
		return s

	converted_expr = re.sub(r'\w+', f, expression)
	res = eval(converted_expr)
	return res

由于变量可能没有值，所以核心思路是用dict进行计算，如x + 2，用集合求和{(x,): 1} + {(): 2}得到{(‘x’,): 1, (): -2}，用dict来计算及保存结果

解题步骤：

1. regex替代变量
2. 将表达式用f包装，如(f(“x”) + f(“8”)) * (f(“x”) - f(“8”))
3. 实现dict的加减乘
4. dict的计算结果转成题目所求

注意事项：

1. Python代码：

   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

   def basicCalculatorIV(self, expression: str, evalvars: List[str], evalints: List[int]) -> List[str]: class MyCounter(Counter): def __add__(self, other): self.update(other) return self def __sub__(self, other): self.subtract(other) return self def __mul__(self, other): product = MyCounter() for x in self: for y in other: xy = tuple(sorted(x + y)) product[xy] += self[x] * other[y] return product var_to_val = dict(zip(evalvars, evalints)) def f(s): token = s s = str(var_to_val[token] if token in var_to_val else token) return MyCounter({(s, ): 1}) if s.isalpha() else MyCounter({(): int(s)}) converted_expr = re.sub(r'(\w+)', r'f("\1")', expression) # (f("x") + f("8")) * (f("x") - f("8")) res = eval(converted_expr) # # C({('x', 'x'): 1, ('x',): 0, (): -64}) return ['*'.join((str(res[x]), ) + x) for x in sorted(res, key=lambda x: (-len(x), x)) if res[x]]

算法分析：

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

[
[“3234.html”, “xys.html”, “7hsaa.html”], // user1
[“3234.html”, “sdhsfjdsh.html”, “xys.html”, “7hsaa.html”] // user2
]

输出两个user的最长连续且相同的访问记录。

题目大意：

求连续最长子数组

解题思路：

类似于LeetCode 1143先求最长公共子字符串。

LeetCode 1143 Longest Common Subsequence, 求最长公共子字符串
Karat 002 Longest Common Continuous Subarray 一样的题目，结果类型不同：最长长度和结果

不同之处在于：

1. 由于是连续，所以递归只有相同的情况，其他情况为0。
2. 答案不是最后一位，而是全局最值

递归式为

1
2

dp[i][j] = dp[i - 1][j - 1] + 1 if text1[i - 1] == text2[j - 1]
         = 0

解题步骤：

N/A

注意事项：

1. 递归只有一种情况
2. 答案需求全局

Python代码：

1
2
3
4
5
6
7
8
9
10
11

# dp[i][j] = dp[i - 1][j - 1] + 1 if text1[i - 1] == text2[j - 1]
#          = 0
def longestCommonContinuous(self, text1: str, text2: str) -> int:
	dp = [[0 for _ in range(len(text2) + 1)] for _ in range(len(text1) + 1)]
	res = 0
	for i in range(1, len(dp)):
		for j in range(1, len(dp[0])):
			if text1[i - 1] == text2[j - 1]:
				dp[i][j] = dp[i - 1][j - 1] + 1
				res = max(res, dp[i][j])
	return res

优化空间：

1
2
3
4
5
6
7
8
9

def longestCommonContinuous(self, text1: str, text2: str) -> int:
	dp = [[0 for _ in range(len(text2) + 1)] for _ in range(2)]
	res = 0
	for i in range(1, len(text1) + 1):
		for j in range(1, len(dp[0])):
			if text1[i - 1] == text2[j - 1]:
				dp[i % 2][j] = dp[(i - 1) % 2][j - 1] + 1
				res = max(res, dp[i % 2][j])
	return res

回到原题，输入是列表而不是字符串，但原理一样。还有需要输出公共结果，而不是数字

Python代码：

1
2
3
4
5
6
7
8
9
10
11

def longestCommonContinuousSubarray(self, history1, history2):
	dp = [[0 for _ in range(len(history2) + 1)] for _ in range(len(history1) + 1)]
	max_len, res = 0, []
	for i in range(1, len(dp)):
		for j in range(1, len(dp[0])):
			if history1[i - 1] == history2[j - 1]:
				dp[i][j] = dp[i - 1][j - 1] + 1
				if dp[i][j] > max_len:
					max_len = dp[i][j]
					res = history1[i - dp[i][j]:i]
	return res

算法分析：

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

LeetCode

Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.

Input: amount = 10, coins = [10]
Output: 1

题目大意：

求兑换硬币的种数

解题思路：

类似于LeetCode 322 Coin Change，那题求最小个数，此题求总数，也是用DP。
递归式：

1

dp[i] = sum(dp[j]), i = j + coins[i]

LeetCode 377 Combination Sum IV 题目基本一样，唯一区别是结果元素有序，属于排列
LeetCode 518 Coin Change 2 题目基本一样，唯一区别是结果元素无序，属于组合

解题步骤：

递归5部曲

注意事项：

1. for循环顺序不能错，先coin再dp，否则会有重复计算，如dp[3] = 2 + 1和1 + 2. 字面上理解也是可以知道重复。但如果coin先的话，就只能用1的硬币，第二轮是只能用2的硬币，如此类推，显然不会重复，dp[3] = dp[2] + 1(只用硬币1), dp[1] + 2(只用硬币2)

Python代码：

1
2
3
4
5
6
7
8
9

# dp[i] = dp[j], i = j + coins[i]
def change(self, amount: int, coins: List[int]) -> int:
	dp = [0] * (amount + 1)
	dp[0] = 1
	for coin in coins:
		for i in range(len(dp)): # [0, 0]
			if i + coin <= amount:
				dp[i + coin] += dp[i]
	return dp[-1]

算法分析：

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

LeetCode

Input: nums = [-2,0,1,3], target = 2
Output: 2
Explanation: Because there are two triplets which sums are less than 2:
[-2,0,1]
[-2,0,3]

Input: nums = [], target = 0
Output: 0

Input: nums = [0], target = 0
Output: 0

题目大意：

找三数和小于target的组合个数

解题思路：

类似于三数和等于target，但当小于target时，直接求个数，类似于LeetCode 315 Count of Smaller Numbers After Self。

解题步骤：

N/A

注意事项：

1. res不是+1而是right - left

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def threeSumSmaller(self, nums: List[int], target: int) -> int:
	if len(nums) < 3:
		return 0
	nums.sort()
	res = 0
	for i in range(len(nums) - 2):
		left, right = i + 1, len(nums) - 1
		while left < right:
			if nums[i] + nums[left] + nums[right] < target:
				res += right - left # remember
				left += 1
			else:
				right -= 1
	return res

算法分析：

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