KK's blog

LeetCode 785 Is Graph Bipartite?

Posted on 2022-02-06 Edited on 2026-06-03 Disqus:

<div>

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:

<pre>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.</pre>

Example 2:

<pre>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}.</pre>

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.

</div>

题目大意：

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

解题思路：

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

解题步骤：

N/A

注意事项：

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

Python代码：

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 309 Best Time to Buy and Sell Stock with Cooldown

Posted on 2022-02-03 Edited on 2026-06-03 Disqus:

LeetCode 309 Best Time to Buy and Sell Stock with Cooldown

Say you have an array for which the i<sup>th</sup> element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

Example:

<pre> prices = [1, 2, 3, 0, 2] maxProfit = 3 transactions = [buy, sell, cooldown, buy, sell] </pre>

题目大意：

给定一个数组，第i个元素代表某只股票在第i天的价格。设计一个算法计算最大收益。你可以完成多次交易（多次买入、卖出同一只股票），需要满足下列限制：你不可以在同一时间参与多个交易（在买入股票之前必须卖出）。在卖出股票之后，你不可以在第二天马上买入。（需要一天的冷却（CD）时间）。也就是卖出后过两天才能买入。

解题思路：

因为有限制条件，所以没有特别方法，只能计算所有结果，也就是用动态规划。动态规划首先是写出递归式（数学归纳法）。

定义f(n)为第n日卖出股票（一定要卖出，不能持有）的利润，加强了命题。
递归式如下图，f(n)只能由f(n-1)卖出后立刻买入（相当于n-1时候不卖出）或者f(n-3)卖出n-1时候买入两种情况。
现在可以写出递归式：

F(x)=max{f(1),...,f(n)}求加强命题最大值即为本题解。这里考虑到负数，方便程序实现，否则，f(n)的前3个值计算就不能放入循环而要特别处理了。

注意事项：

数组为空或者1个
负数组的实现方法

Java代码：

public int maxProfit(int[] prices){
	int sell[] = new int[prices.length];
	int max = 0;
	for(int i=1;i<prices.length;i++){
		sell[i] = Math.max(f(i-3, sell), f(i-1, sell))+ prices[i]-prices[i-1];
		if(sell[i]>max)
			max = sell[i];
	}
	return max;		
}

public int f(int i, int[] r){
	if(i<1)
		return 0;
	else
		return r[i];

这个实现有个错误就是忽略了一种重要的情况：f(n-4),...,f(1)的情况。看以下例子：[6,1,6,4,3,0,2]

Index	0	1	2	3	4	5	6
price	6	1	6	4	3	0	2
f(n)	0	-5	5	3	2	2	5

按照上面算法结果为5，但是很容易看出来1->6, 0->2结果是7。问题出在最后一个f(6)=max{f(3),f(5)}+2=max{3,2}+2。很明显，第3天卖出获利为3并不是最佳，第二天卖出获利为5才是最佳，我们忽略了f(n-3)之前的所有情况。解决方案是再创建一个数组维护前n天最大获利值。定义g(n)为第n日（包括第n日）前卖出股票（不一定要第n天卖出）的利润。修改递归式为，把f(n-3)改为g(n-3)：

Java代码：

public int maxProfit2(int[] prices){
	int sell[] = new int[prices.length];
	int preSell[] = new int[prices.length];
	int max = 0;
	for(int i=1;i<prices.length;i++){
		sell[i] = Math.max(g(i-3, preSell), f(i-1, sell))+ prices[i]-prices[i-1];
		if(sell[i]>max)
			max = sell[i];
		
		preSell[i] = Math.max(preSell[i-1], sell[i]);
	}
	return max;		
}

public int f(int i, int[] r){
	if(i<1)
		return 0;
	else
		return r[i];
}

public int g(int i, int[] g){
	if(i<1)
		return 0;
	else
		return g[i];
}

算法分析：

时间复杂度为O(n)，n为数组长度，空间复杂度O(n)。

current, first分别通过f和g的计算公式计算，second是通过current获得

Python代码：

# g(n) = max{f(n), g(n-1)}
# f(n) = A[n] - A[n - 1] + max{f(n - 1), g(n-3)}
def maxProfit(self, prices: List[int]) -> int:
	# g(n-3), f(n-2), f(n-1)
	first, second, current = 0, 0, 0
	for i in range(1, len(prices)):
		current, second, first = prices[i] - prices[i - 1] + max(current, first), current, max(second, first)
	return max(current, second, first)

空间优化：

由于此题目，f(n)只与前三个状态有关f(n-1), f(n-2)(虽然没直接关系，但程序实现需要记录),g(n-3)。四个状态可以用三个变量
推进，如sell=Math.max(preSell, sell)，同一个变量旧状态更新到新状态，所以可以避免维护数组开销。代入preSell=g(n-3), sell_1=f(n-2), sell=f(n-1)到公式即得 f(n) = sell = max{preSell, sell}+prices[n]-prices[i-1] g(n-2) = preSell = max{g(n-3), f(n-2)} = max{preSell, sell_1} f(n-1) = sell_1 = PreValue(sell) 本题解就是preSell, sell_1, sell的最大值。

Java代码：

public int maxProfit(int[] prices){
	//g(n-3), f(n-2), f(n-1)
	int preSell=0, sell_1=0, sell = 0;
	for(int i=1;i<prices.length;i++){
		int tmp = sell;
		sell = Math.max(preSell, sell)+ prices[i]-prices[i-1];
		preSell = Math.max(preSell, sell_1);
		sell_1 = tmp;
	}
	return Math.max(Math.max(preSell, sell_1), sell);		
}

算法分析：

时间复杂度为O(n)，n为数组长度，空间复杂度O(1)。本题有更简单解法但比较难想出。

最后注意事项：

数组为空或者1个
三种情况f(n-1),f(n-3),g(n-3)可以得到f(n)。解就是preSell, sell_1, sell的最大值。
DP流程，定义函数（是否加强）、递归式、空间优化。

LeetCode 339 Nested List Weight Sum

Posted on 2022-02-03 Edited on 2026-06-03 Disqus:

LeetCode

<div>

You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists.

The depth of an integer is the number of lists that it is inside of. For example, the nested list [1,[2,2],[[3],2],1] has each integer's value set to its depth.

Return the sum of each integer in nestedList multiplied by its depth.

Example 1:

<pre>Input: nestedList = [[1,1],2,[1,1]] Output: 10 Explanation: Four 1's at depth 2, one 2 at depth 1. 12 + 12 + 21 + 12 + 1*2 = 10. </pre>

Example 2:

<pre>Input: nestedList = [1,[4,[6]]] Output: 27 Explanation: One 1 at depth 1, one 4 at depth 2, and one 6 at depth 3. 11 + 42 + 6*3 = 27.</pre>

Example 3:

<pre>Input: nestedList = [0] Output: 0 </pre>

Constraints:

1 <= nestedList.length <= 50
The values of the integers in the nested list is in the range [-100, 100].
The maximum depth of any integer is less than or equal to 50.

</div>

题目大意：

求NestedInteger的和。越深，权重越高

最后计算权重解题思路(推荐)：

BFS按层遍历

Nested List题目：
LeetCode 341 Flatten Nested List Iterator Iterator - Stack LeetCode 339 Nested List Weight Sum - BFS LeetCode 364 Nested List Weight Sum II - BFS

解题步骤：

N/A

注意事项：

Line 9中，需要将NestedInteger展开，里面的所有的NestedInteger入列。Python中，用extend来加入list中所有元素到另一个list，而不是append
按层遍历模板中，不需要level变量，for可以达到。

Python代码：

def depthSum(self, nestedList) -> int:
	queue = collections.deque(nestedList)
	sums, max_depth, res = [], 0, 0
	while queue:
		layer_sum = 0
		for _ in range(len(queue)):
			node = queue.popleft()
			if node.isInteger():
				layer_sum += node.getInteger()
			else:
				queue.extend(node.getList()) # remember
		sums.append(layer_sum)
		max_depth += 1
	for i, n in enumerate(sums):
		res += n * (i + 1)
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(k), k为每层最多节点数 + 最大层数

每层计算权重算法II解题思路：

Python代码：

def depthSum(self, nestedList) -> int:
	queue = collections.deque(nestedList)
	res, layer = 0, 1
	while queue:
		level_sum = 0
		for _ in range(len(queue)):
			node = queue.popleft()
			if not node.isInteger():
				queue.extend(node.getList()) # remember
			else:
				level_sum += node.getInteger()
		res += level_sum * layer
		layer += 1
	return res

算法分析：

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

LeetCode 337 House Robber III

Posted on 2022-02-03 Edited on 2026-06-03 Disqus:

LeetCode

<div>

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root.

Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police.

Example 1:

<pre>Input: root = [3,2,3,null,3,null,1] Output: 7 Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7. </pre>

Example 2:

<pre>Input: root = [3,4,5,1,3,null,1] Output: 9 Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9. </pre>

Constraints:

The number of nodes in the tree is in the range [1, 10<sup>4</sup>].
0 <= Node.val <= 10<sup>4</sup>

</div>

题目大意：

二叉树，相隔一层投，求最大值

解题思路：

多状态DP。返回值为，第一个是以root为结尾的最大值，第二个为儿子层总和的最大值。

与LeetCode 309 Best Time to Buy and Sell Stock with Cooldown相似

DFS解题步骤：

N/A

注意事项：

以儿子层的前n最大值 = max(left) + max(right)

Python代码：

def rob2(self, root: TreeNode) -> int:
	res = self.dfs2(root)
	return max(res)

def dfs2(self, root):
	if not root:
		return (0, 0)

	left = self.dfs2(root.left)
	right = self.dfs2(root.right)

	return root.val + left[1] + right[1], max(left) + max(right)

算法分析：

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

记忆法搜索算法II解题思路：

递归式：

1 2	f(n) = root.val + g(root.left) + g(root.right) g(n) = max(f(root.left), g(root.left)) + max(f(root.right), g(root.right))

Python代码：

def rob(self, root: TreeNode) -> int:
	f, g = {}, {}
	res = self.dfs(root, f, g)
	return max(res)

def dfs(self, root, f, g):
	if not root:
		return (0, 0)
	if root.left not in f or root.left not in g:
		f[root.left], g[root.left] = self.dfs(root.left, f, g)
	if root.right not in f or root.right not in g:
		f[root.right], g[root.right] = self.dfs(root.right, f, g)
	f[root] = root.val + g[root.left] + g[root.right]
	g[root] = max(f[root.left], g[root.left]) + max(f[root.right], g[root.right])
	return f[root], g[root]

算法分析：

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

LeetCode 364 Nested List Weight Sum II

Posted on 2022-02-03 Edited on 2026-06-03 Disqus:

LeetCode

<div>

You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists.

The depth of an integer is the number of lists that it is inside of. For example, the nested list [1,[2,2],[[3],2],1] has each integer's value set to its depth. Let maxDepth be the maximum depth of any integer.

The weight of an integer is maxDepth - (the depth of the integer) + 1.

Return the sum of each integer in nestedList multiplied by its weight.

Example 1:

<pre>Input: nestedList = [[1,1],2,[1,1]] Output: 8 Explanation: Four 1's with a weight of 1, one 2 with a weight of 2. 11 + 11 + 22 + 11 + 1*1 = 8 </pre>

Example 2:

<pre>Input: nestedList = [1,[4,[6]]] Output: 17 Explanation: One 1 at depth 3, one 4 at depth 2, and one 6 at depth 1. 13 + 42 + 6*1 = 17 </pre>

Constraints:

1 <= nestedList.length <= 50
The values of the integers in the nested list is in the range [-100, 100].
The maximum depth of any integer is less than or equal to 50.

</div>

题目大意：

求NestedInteger的和。越浅，权重越高

解题思路：

BFS按层遍历。此题类似于LeetCode 339 Nested List Weight Sum。归纳成更一般的方法：因为权重只与第几层有关。所以先求每一层的和，存到sums里面，再按照题目要求每个和乘以相应的权重求和。

Nested List题目：
LeetCode 341 Flatten Nested List Iterator Iterator - Stack LeetCode 339 Nested List Weight Sum - BFS LeetCode 364 Nested List Weight Sum II - BFS

解题步骤：

N/A

注意事项：

queue.extend(node.getList())将节点的儿子节点即node.getList()放入queue

Python代码：

def depthSumInverse(self, nestedList) -> int:
	queue = collections.deque(nestedList)
	sums, max_depth, res = [], 0, 0
	while queue:
		layer_sum = 0
		for _ in range(len(queue)):
			node = queue.popleft()
			if node.isInteger():
				layer_sum += node.getInteger()
			else:
				queue.extend(node.getList()) # remember
		sums.append(layer_sum)
		max_depth += 1
	for i, n in enumerate(sums):
		res += n * (max_depth - i)
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(k), k为每层最多节点数 + 最大层数

题目大意：

解题思路：

解题步骤：

注意事项：

Python代码：

算法分析：

题目大意：

解题思路：

注意事项：

Java代码：

Java代码：

算法分析：

Python代码：

空间优化：

Java代码：

算法分析：

最后注意事项：

相关题目：

题目大意：

最后计算权重解题思路(推荐)：

解题步骤：

注意事项：

Python代码：

算法分析：

每层计算权重算法II解题思路：

Python代码：

算法分析：

题目大意：

解题思路：

DFS解题步骤：

注意事项：

Python代码：

算法分析：

记忆法搜索算法II解题思路：

Python代码：

算法分析：

题目大意：

解题思路：

解题步骤：

注意事项：

Python代码：

算法分析：