KK's blog

LeetCode

<div>

You are given the root of a binary tree with n nodes where each node in the tree has node.val coins. There are n coins in total throughout the whole tree.

In one move, we may choose two adjacent nodes and move one coin from one node to another. A move may be from parent to child, or from child to parent.

Return the minimum number of moves required to make every node have exactly one coin.

Example 1:

<pre>Input: root = [3,0,0] Output: 2 Explanation: From the root of the tree, we move one coin to its left child, and one coin to its right child. </pre>

Example 2:

<pre>Input: root = [0,3,0] Output: 3 Explanation: From the left child of the root, we move two coins to the root [taking two moves]. Then, we move one coin from the root of the tree to the right child. </pre>

Constraints:

• The number of nodes in the tree is n.
• 1 <= n <= 100
• 0 <= Node.val <= n
• The sum of all Node.val is n.

</div>

题目大意：

二叉树某些节点含有硬币，求将这些硬币推向其他节点，使得所有节点都有一个硬币，求总移动次数

解题思路：

先思考，若硬币都在root，也就是求所有节点的路径和。可以用每个节点的路径和求和，也可以定义dfs返回节点数，用全局变量加左右数，每轮递归都加一次，所以每个节点被加了其路径长度的次数。本算法采用后者
下面思考若硬币不在root，由于硬币可以从儿子给父亲，这是双向的，所以dfs定义为儿子给父亲的硬币数，若节点没有硬币，返回值会是负数，也就是父亲给儿子硬币，此时这个负数正是以此节点为root的数的总的节点数，所以与上述定义一致。
所以返回root.val + left + right - 1，left和right都是负数，left + right - 1是树的大小的负数，此结果为剩余硬币推给父亲的硬币数
res += abs(left) + abs(right)左子树和右子树所有节点一起走一条边的路径和

解题步骤：

N/A

注意事项：

1. dfs定义为儿子给父亲的硬币数(若有硬币)，同时是子树的节点数的负数(若无硬币)

Python代码：

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

def distributeCoins(self, root: TreeNode) -> int:
	res = 0

	def dfs(root):
		if not root:
			return 0
		nonlocal res
		left = dfs(root.left)
		right = dfs(root.right)
		res += abs(left) + abs(right)
		return root.val + left + right - 1

	dfs(root)
	return res

算法分析：

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

A nonogram is a logic puzzle, similar to a crossword, in which the player is given a blank grid and has to color it according to some instructions. Specifically, each cell can be either black or white, which we will represent as 0 for black and 1 for white. +------------+ | 1 1 1 1 | | 0 1 1 1 | | 0 1 0 0 | | 1 1 0 1 | | 0 0 1 1 | +------------+ For each row and column, the instructions give the lengths of contiguous runs of black (0) cells. For example, the instructions for one row of [ 2, 1 ] indicate that there must be a run of two black cells, followed later by another run of one black cell, and the rest of the row filled with white cells. These are valid solutions: [ 1, 0, 0, 1, 0 ] and [ 0, 0, 1, 1, 0 ] and also [ 0, 0, 1, 0, 1 ] This is not valid: [ 1, 0, 1, 0, 0 ] since the runs are not in the correct order. This is not valid: [ 1, 0, 0, 0, 1 ] since the two runs of 0s are not separated by 1s. Your job is to write a function to validate a possible solution against a set of instructions. Given a 2D matrix representing a player's solution; and instructions for each row along with additional instructions for each column; return True or False according to whether both sets of instructions match.

题目大意：

Nonogram日本游戏，0表示黑子，[2, 1]表示黑子的连续数目，如棋盘状态[ 1, 0, 0, 1, 0 ]，表示连续黑子数为[2, 1]
[ 1, 0, 0, 0, 1 ]连续黑子数为[3]. 验证棋盘的每一行和每一列是否满足rows和cols所指定的连续黑子数

解题思路：

按题意求解

解题步骤：

N/A

注意事项：

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

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

def valid_nonogram(self, matrix, rows, cols):
	for i in range(len(matrix)):
		if self.get_consecutive_zeros(matrix[i]) != rows[i]:
			return False
	for j in range(len(matrix[0])):
		col_vals = []
		for i in range(len(matrix)):
			col_vals.append(matrix[i][j])
		if self.get_consecutive_zeros(col_vals) != cols[j]:
			return False
	return True

# [ 1, 0, 0, 1, 0 ] -> [2, 1], # of 0s
def get_consecutive_zeros(self, matrix_row):
	count, res = 0, []
	for n in matrix_row:
		if n == 0:
			count += 1
		else:
			if count > 0:
				res.append(count)
			count = 0
	if count > 0:
		res.append(count)
	return res

算法分析：

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

LeetCode

<div>

Given a string s, return the longest palindromic substring in s.

Example 1:

<pre>Input: s = "babad" Output: "bab" Explanation: "aba" is also a valid answer. </pre>

Example 2:

<pre>Input: s = "cbbd" Output: "bb" </pre>

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

</div>

题目大意：

最长回文

解题思路：

遍历每个字符，以该字符为中心，往前后比较是否回文，求最长回文

解题步骤：

N/A

注意事项：

1. 回文字符串的中心位可以为1个或2个
2. 此题求最长回文字符串，而不是其长度
3. 避免死循环，记得i -= 1, j += 1
4. Line 63 若不相等，要break，或者return[i + 1:j]和下面return一样

Python代码：

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

def longestPalindrome(self, s: str) -> str:
	res = ''
	for i in range(len(s)):
		tmp = self.longestPalindromeFromCenter(s, i, i)
		if len(tmp) > len(res):
			res = tmp
		if i + 1 < len(s):
			tmp = self.longestPalindromeFromCenter(s, i, i + 1)
			if len(tmp) > len(res):
				res = tmp
	return res

def longestPalindromeFromCenter(self, s, left, right):
	while left >= 0 and right <= len(s) - 1:
		if s[left] != s[right]:
			break
		left -= 1
		right += 1
	return s[left + 1:right]

算法分析：

时间复杂度为<code>O(n²)</code>，空间复杂度O(1)

LeetCode

<div>

Given an integer n, return any array containing n unique integers such that they add up to 0.

Example 1:

<pre>Input: n = 5 Output: [-7,-1,1,3,4] Explanation: These arrays also are accepted [-5,-1,1,2,3] , [-3,-1,2,-2,4]. </pre>

Example 2:

<pre>Input: n = 3 Output: [-1,0,1] </pre>

Example 3:

<pre>Input: n = 1 Output: [0] </pre>

Constraints:

• 1 <= n <= 1000

</div>

题目大意：

给定n，求n个数的数组使得数组和为0

解题思路：

Easy题，只要将相反数放入数组即可

解题步骤：

N/A

注意事项：

Python代码：

1
2
3
4
5
6
7
8

def sumZero(self, n: int) -> List[int]:
	res = []
	if n % 2 == 1:
		res.append(0)
	for i in range(n // 2):
		res.append(i + 1)
		res.append(-i - 1)
	return res

算法分析：

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

LeetCode

<div>

A string s is called happy if it satisfies the following conditions:

• s only contains the letters 'a', 'b', and 'c'.
• s does not contain any of "aaa", "bbb", or "ccc" as a substring.
• s contains at most a occurrences of the letter 'a'.
• s contains at most b occurrences of the letter 'b'.
• s contains at most c occurrences of the letter 'c'.

Given three integers a, b, and c, return the longest possible happy string. If there are multiple longest happy strings, return any of them. If there is no such string, return the empty string "".

A substring is a contiguous sequence of characters within a string.

Example 1:

<pre>Input: a = 1, b = 1, c = 7 Output: "ccaccbcc" Explanation: "ccbccacc" would also be a correct answer. </pre>

Example 2:

<pre>Input: a = 7, b = 1, c = 0 Output: "aabaa" Explanation: It is the only correct answer in this case. </pre>

Constraints:

• 0 <= a, b, c <= 100
• a + b + c > 0

</div>

题目大意：

给定三个整数代表abc的个数，生成一个字符串，字符串abc频数不能超过这3个数，不能有连续的aaa, bbb, ccc, 求此种字符串的最大长度

解题思路：

由第一个例子看出，先尽量用频数最多的字符，直到连续3个为止，然后再用次多的，如此反复做。这里用到最多和次多，所以考虑用Heap

解题步骤：

N/A

注意事项：

1. 每次选频数最高的字符，但若此字符已连续3次，选次高的，用heap。
2. 大于0的频数才加入到heap Line 4和Line 17
3. heapreplace等于heappop次高的和heappush最高的。既然要有次高，heap就不能为空

Python代码：

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

def longestDiverseString(self, a: int, b: int, c: int) -> str:
	res = ''
	heap = []
	if a > 0: # remember
		heapq.heappush(heap, (-a, 'a'))
	if b > 0:
		heapq.heappush(heap, (-b, 'b'))
	if c > 0:
		heapq.heappush(heap, (-c, 'c'))
	while heap:
		count, char = heapq.heappop(heap)
		if len(res) > 1 and res[-2] == res[-1] == char:
			if not heap:
				break
			count, char = heapq.heapreplace(heap, (count, char))
		res += char
		if count + 1:
			heapq.heappush(heap, (count + 1, char))
	return res

算法分析：

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