KK's blog

LeetCode

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

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

题目大意：

将数组的0全部移到数组末

解题思路：

简单题。Quicksort的partition的应用

解题步骤：

N/A

注意事项：

1. Python代码：

   1 2 3 4 5 6 7 8 9

   def moveZeroes(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ non_zero_idx = 0 for i in range(len(nums)): if nums[i] != 0: nums[i], nums[non_zero_idx] = nums[non_zero_idx], nums[i] non_zero_idx += 1

算法分析：

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

LeetCode

Input: num = “123”, target = 6
Output: [“123”,”1+2+3”]
Explanation: Both “123” and “1+2+3” evaluate to 6.

Input: num = “232”, target = 8
Output: [“23+2”,”2+32”]
Explanation: Both “23+2” and “2+32” evaluate to 8.

Input: num = “3456237490”, target = 9191
Output: []
Explanation: There are no expressions that can be created from “3456237490” to evaluate to 9191.

题目大意：

求一串数字加入加减乘能得到target的所有可能性

解题思路：

求所有可能用DFS。属于分割型DFS，在数位之间加符号，数位可以是1个到多个。
一轮递归分割出符号 + 数字
另一种选择是数字 + 符号，但需要额外变量sign，因为不能立刻计算到结果。也不符合正常逻辑。所以选择前者。

由于运算都是二元，也就是用上述分割法，第一个数要特别处理。所以DFS中要特别处理第一个数。这样可以开始写加减。引入prev_res作为DFS参数，这样只要prev_res 加减 该轮数字即可得到该轮结果。用DFS模板5个标准参数外加prev_res：

1

def dfs(self, num, st, target, prev_res, path, res):

这样只处理加减的DFS比较容易实现

最大难点在于乘法，参考LeetCode 227 Basic Calculator II，加减和乘除属于两层计算需要分别处理，所以引入新参数prev_multi_res，用于保存乘法结果，而刚才的命名为prev_add_res保存加减乘的全部结果

1

def dfs(self, num, st, target, prev_add_res, prev_multi_res, path, res):

举例2+3*4，按照原来的逻辑会计算到2+3=5，但此时如果遇到乘号，就要重新计算加法结果，先减去乘法结果，退回到2，再计算3*4=12这是乘法结果，再加回2得到新加法结果。进一步理解prev_multi_res，如果该轮是加减法，仍要将该轮的数作为prev_multi_res传到下轮DFS，因为如果下一轮是乘法，它就是第一个乘法的数。

解题步骤：

1. 先实现加减法
2. 再实现乘法

注意事项：

1. 分割型DFS，选择每轮递归分割符号 + 数字。由于运算都是二元，特别处理第一个数
2. 引入参数prev_add_res, prev_multi_res. prev_multi_res若是加减，用(+/-)cur_num, 否则用乘法结果prev_multi_res * cur_num。注意若是减法cur_num用负号
3. 分割时数字不能有前缀0
4. prev_res不用恢复状态因为是标量

Python代码：

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

def addOperators(self, num: str, target: int) -> List[str]:
	res = []
	self.dfs(num, 0, target, 0, 0, '', res)
	return res

def dfs(self, num, st, target, prev_add_res, prev_multi_res, path, res):
	if st == len(num):
		if target == prev_add_res:
			res.append(path)
		return
	for i in range(st, len(num)):
		if i > st and num[st] == '0': # remember
			continue
		cur_num = int(num[st:i + 1])
		if not path: # remember
		    # first number, same as + case
			self.dfs(num, i + 1, target, prev_add_res + cur_num, cur_num, str(cur_num), res)
		else:
			self.dfs(num, i + 1, target, prev_add_res + cur_num, cur_num, path + '+' + str(cur_num), res) # use cur_num rather than cur
			self.dfs(num, i + 1, target, prev_add_res - cur_num, -cur_num, path + '-' + str(cur_num), res) # -cur_num rather than cur_num
			self.dfs(num, i + 1, target, (prev_add_res - prev_multi_res) + prev_multi_res * cur_num, prev_multi_res * cur_num, path + '*' + str(cur_num), res) # prev_multi_res * cur_num not cur_num

算法分析：

时间复杂度为O(4n)，空间复杂度O(n), 因为每个字符之间都有不加操作符，加3个操作符，所以是4，有n-1个间隔

LeetCode

Suppose you are at a party with n people labeled from 0 to n - 1 and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1 people know the celebrity, but the celebrity does not know any of them.

Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is ask questions like: “Hi, A. Do you know B?” to get information about whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense).

You are given a helper function bool knows(a, b) that tells you whether A knows B. Implement a function int findCelebrity(n). There will be exactly one celebrity if they are at the party.

Return the celebrity’s label if there is a celebrity at the party. If there is no celebrity, return -1.

Example 1:

Input: graph = [[1,1,0],[0,1,0],[1,1,1]]
Output: 1
Explanation: There are three persons labeled with 0, 1 and 2. graph[i][j] = 1 means person i knows person j, otherwise graph[i][j] = 0 means person i does not know person j. The celebrity is the person labeled as 1 because both 0 and 2 know him but 1 does not know anybody.

Example 2:

Input: graph = [[1,0,1],[1,1,0],[0,1,1]]
Output: -1
Explanation: There is no celebrity.

Constraints:

n == graph.length n == graph[i].length
2 <= n <= 100 graph[i][j] is 0 or 1.
graph[i][i] == 1

Follow up: If the maximum number of allowed calls to the API knows is `3 n`, could you find a solution without exceeding the maximum number of calls?

题目大意：

通过调用a是否认识b函数，找出名人。名人是除自己的所有人都认识他，他不认识其他所有人

解题思路：

类似于LeetCode 169 Majority Element，用水王法

解题步骤：

1. 找出可能名人，通过查看是否i后面的每一个人都认识i，若不是将candidate换成当前下标
2. 按定义验证第一步的结果是否名人，两步验证

注意事项：

1. 按照定义，若i不认识candiate才换candidate，用not。因为edge case是没有边或者图存在循环
2. 验证时候，第二步验证candidate若认识任意人就不是名人，排除candidate认识自己。题目条件candidate认识自己。

Python代码：

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

def findCelebrity(self, n: int) -> int:
	# find potential candidate
	candidate = 0
	for i in range(1, n):
		if not knows(i, candidate):
			candidate = i
	# validate
	for i in range(n):
		if not knows(i, candidate):
			return -1
	for i in range(n):
		if candidate != i and knows(candidate, i):
			return -1
	return candidate

算法分析：

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

LeetCode

Given the root of a binary search tree and a target value, return the value in the BST that is closest to the target. Example 1:

Input: root = [4,2,5,1,3], target = 3.714286
Output: 4

Example 2:

Input: root = [1], target = 4.428571
Output: 1

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

题目大意：

求BST中最接近target的值

解题思路：

接近target的值在BST搜索路径上，越后搜索到的(越后入栈的)越接近，但最接近的可能大于或小于target(predecessors or successors)，只能逐一比较.
类似于LeetCode 272 Closest Binary Search Tree Value II

解题步骤：

N/A

注意事项：

1. 循环中用it，不能用root，注意检查
2. 接近target的值在BST搜索路径上，逐一比较

Python代码：

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

def closestValue(self, root: TreeNode, target: float) -> int:
	closest_vals = []
	it = root
	while it:
		closest_vals.append(it.val)
		if target < it.val:
			it = it.left
		else:
			it = it.right
	min_val, res = float('inf'), 0
	for n in closest_vals:
		if abs(target - n) < min_val:
			min_val = abs(target - n)
			res = n
	return res

算法分析：

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

LeetCode

Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

题目大意：

数组缺失一个数，所有数应该在[0, n]内，求缺失数

排序法解题思路：

N/A

解题步骤：

N/A

注意事项：

1. Python代码：

   1 2 3

   def canPermutePalindrome(self, s: str) -> bool: char_to_count = collections.Counter(s) return False if len([count for count in char_to_count.values() if count % 2 == 1]) > 1 else True

算法分析：

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

异或法解题思路II：

高斯原理

Python代码：

1
2
3
4
5

def missingNumber2(self, nums: List[int]) -> int:
	res = len(nums) # remember
	for i, n in enumerate(nums):
		res ^= i ^ n
	return res

算法分析：

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

数学法解题思路III：

高斯原理

Python代码：

1
2
3

def missingNumber3(self, nums: List[int]) -> int:
	n = len(nums)
	return (0 + n) * (n + 1) // 2 - sum(nums)

算法分析：

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