KK's blog

LeetCode

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

<pre>Input: root = [4,2,5,1,3], target = 3.714286 Output: 4 </pre>

Example 2:

<pre>Input: root = [1], target = 4.428571 Output: 1 </pre>

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

题目大意：

求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

<div>

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

• n == nums.length
• 1 <= n <= 10<sup>4</sup>
• 0 <= nums[i] <= n
• All the numbers of nums are unique.

Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

</div>

题目大意：

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

排序法解题思路：

N/A

解题步骤：

N/A

注意事项：

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)

LeetCode

<div>

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:

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

Example 2:

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

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?

</div>

题目大意：

通过调用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

<div>

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

Example 1:

<pre>Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 Output: true </pre>

Example 2:

<pre>Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 Output: false </pre>

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -10<sup>4</sup> <= matrix[i][j], target <= 10<sup>4</sup>

</div>

题目大意：

矩阵中每一行有序，下一行的首元素大于上一行的尾元素。求target是否在矩阵中

列+行搜索解题思路：

先对列做二分搜索，再对行

LeetCode 074 Search a 2D Matrix 每一行有序，下一行的首元素大于上一行的尾元素 + 找target
LeetCode 240 Search a 2D Matrix II 按行按列有序 + 找target
LeetCode 378 Kth Smallest Element in a Sorted Matrix 按行按列有序 + 找第k大
矩阵结构方面，第一道每一行都是独立，所以可以独立地按行按列做二分法
后两道，矩阵二维连续，所以解法都是类BFS，从某个点开始，然后比较它相邻的两个点。出发点不同，第二道在近似矩阵中点(右上角或左下角)，第三道在左上角出发。

解题步骤：

N/A

注意事项：

Python代码：

1
2
3
4
5
6
7
8
9
10
11

def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
	col = [matrix[i][0] for i in range(len(matrix))]
	row_idx = bisect.bisect(col, target) - 1
	if row_idx < 0 or row_idx >= len(matrix):
		return False
	if matrix[row_idx][0] == target:
		return True
	col_idx = bisect.bisect(matrix[row_idx], target) - 1
	if col_idx < 0 or col_idx >= len(matrix[0]):
		return False
	return True if matrix[row_idx][col_idx] == target else False

算法分析：

时间复杂度为O(logn + logm)，空间复杂度O(n), 可以写一个二分法来做列搜索，这样空间为常量。

全矩阵搜索算法II解题思路：

对矩阵的左上，右下元素作为start, end得到mid转化成(i, j)找到矩阵位置。

Java代码：

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

public boolean searchMatrix(int[][] matrix, int target) {
	if (matrix.length==0)
		return false;
	int lo = 0;
	int hi = matrix.length*matrix[0].length - 1;
	while (lo <= hi) {
		// Key is in a[lo..hi] or not present.
		int mid = lo + (hi - lo) / 2;
		int x = mid/matrix[0].length;
		int y = mid%matrix[0].length;
		if (target < matrix[x][y])
			hi = mid - 1;
		else if (target > matrix[x][y])
			lo = mid + 1;
		else
			return true;
	}
	return false;
}

算法分析：

时间复杂度为O(logn + logm)，空间复杂度O(1)。

LeetCode

<div>

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:

<pre>Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Output: 3 Explanation: The LCA of nodes 5 and 1 is 3. </pre>

Example 2:

<pre>Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 Output: 5 Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition. </pre>

Example 3:

<pre>Input: root = [1,2], p = 1, q = 2 Output: 1 </pre>

Constraints:

• The number of nodes in the tree is in the range [2, 10<sup>5</sup>].
• -10<sup>9</sup> <= Node.val <= 10<sup>9</sup>
• All Node.val are unique.
• p != q
• p and q will exist in the tree.

</div>

题目大意：

二叉树中求给定的两节点的最低共同父亲节点

解题思路：

DFS

解题步骤：

N/A

注意事项：

1. pq一定存在，所以有**三种情况： 1) p或q是root，另一是其子孙。 2) p，q分列root两边。 3) p，q在root的一边

Python代码：

1
2
3
4
5
6
7
8
9
10

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
	if not root:
		return None
	if root == p or root == q:
		return root
	left = self.lowestCommonAncestor(root.left, p, q)
	right = self.lowestCommonAncestor(root.right, p, q)
	if left and right:
		return root
	return left if left else right

算法分析：

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

算法II解题思路：

BFS遍历树（可以找到就停止），然后记录子节点到父节点的映射，将所有父节点放到set中，同样查找另一个节点的父节点们，找到第一个在set中的节点。