KK's blog

LeetCode

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:

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

Example 2:

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

Constraints:

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

题目大意：

矩阵中每一行有序，下一行的首元素大于上一行的尾元素。求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

注意事项：

1. 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

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:

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.

Example 2:

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.

Example 3:

Input: root = [1,2], p = 1, q = 2
Output: 1

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.

题目大意：

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

解题思路：

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中的节点。

LeetCode 248 Strobogrammatic Number III

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).
Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high.

Example:

**Input: low = "50", high = "100"

**Output:** 3 

Explanation: 69, 88, and 96 are three strobogrammatic numbers.

Note: Because the range might be a large number, the lowand high numbers are represented as string.

题目大意：

求某范围的旋转数的个数。旋转数是这个数旋转180度还是一样，如0, 1, 8， 还含两位的如69， 96.

解题思路：

低频题。这是M公司的题目。这题不能用乘法原理，因为情况多变，要实实在在地找出每一个可能性。
类似于L351安卓解码种数，数字间有关系，求[m, n]范围间种数。用DFS将每一位填上合法位，此题区别是
需要它有对称性，所以DFS从中间向两边。API为f(res, low, high, map), res为当前结果字符串，map为旋转数的映射关系，
终止条件为res超过high，若在范围内，结果+1，也就是先将自己加入到结果中，然后两边加入旋转字符，进入下一轮递归，
累加到结果中。

注意: 与上题一样，和最左位不能为0除了0自己本身。

注意事项：

1. 带限制条件的填位法DFS。
2. 奇偶位。对称中心既可以是奇数位也可以是偶数位。所以DFS有空字符，单个字符0, 1, 8等4种。
3. 此题难点在验证： 三种情况，需要比较字符串，所以要比较长度
   1) 当前结果长度大于high, 长度等于high但大于high，返回0. 只有这种情况是终止条件
   2) 当前结果长度大于low, 长度等于low但大于等于low，res = 1
   3) 最左位为0，不合法如0880，但0本身除外， res = 0

Python代码：

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

def strobogrammaticInRange(self, low: str, high: str) -> int:
	stro_dict = {'0': '0', '1': '1', '8': '8', '6': '9', '9': '6'}
	res = 0
	res += self.dfs('', low, high, stro_dict)
	res += self.dfs('0', low, high, stro_dict)
	res += self.dfs('1', low, high, stro_dict)
	res += self.dfs('8', low, high, stro_dict)
	return res

def dfs(self, s, low, high, stro_dict):
	if len(s) > len(high) or (len(s) == len(high) and s > high):
		return 0
	res = 0
	if len(s) > len(low) or (len(s) == len(low) and s >= low):
		res = 1
	if len(s) > 1 and s[0] == '0': # i.e. 08
		res = 0
	for key, val in stro_dict.items():
		res += self.dfs(key + s + val, low, high, stro_dict)
	return res

注意事项：

1. 奇偶位。对称中心既可以是奇数位也可以是偶数位。
2. 最左位为0，不合法如0880，但0本身除外。

Java代码：

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

public int strobogrammaticInRange(String low, String high) {
	Map<String, String> map = new HashMap<>();
	map.put("6", "9");
	map.put("9", "6");
	map.put("1", "1");
	map.put("8", "8");
	map.put("0", "0");
	
	int result = 0;
	result += dfs("", low, high, map);
	result += dfs("1", low, high, map);
	result += dfs("0", low, high, map);
	result += dfs("8", low, high, map);
	return result;
}
	
public int dfs(String res, String low, String high, Map<String, String> map) {
	if(res.length() > high.length() || (res.length() == high.length() && res.compareTo(high) > 0)) 
		return 0;
	int result = 0;
	if((res.length() == low.length() && res.compareTo(low) >= 0)  || res.length() > low.length()) 
		result = 1;
	if(res.length() > 1 && res.charAt(0) == '0')
		result = 0;
	
	for (Map.Entry<String, String> entry : map.entrySet()) {
		result += dfs(entry.getKey() + res + entry.getValue(), low, high, map);
	}
	return result;
}

算法分析：

时间复杂度为O(# of results)，空间复杂度O(lengh(high))。

LeetCode 378 Kth Smallest Element in a Sorted Matrix

Given an n x n matrix where each of the rows and columns is sorted in ascending order, return the k<sup>th</sup> smallest element in the matrix.

Note that it is the k<sup>th</sup> smallest element in the sorted order, not the k<sup>th</sup> distinct element.

You must find a solution with complexity better than O(n<sup>2</sup>).

Example 1:

**Input:** matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
**Output:** 13
**Explanation:** The elements in the matrix are [1,5,9,10,11,12,13,**13**,15], and the 8th smallest number is 13

Example 2:

**Input:** matrix = [[-5]], k = 1
**Output:** -5

Constraints:

• n == matrix.length == matrix[i].length
• 1 <= n <= 300
• -10<sup>9</sup> <= matrix[i][j] <= 10<sup>9</sup>
• All the rows and columns of matrix are guaranteed to be sorted in non-decreasing order.
• 1 <= k <= n<sup>2</sup>

Follow up: Could you solve the problem in O(n) time complexity?

题目大意：

按行按列有序矩阵中，找第k小的数。

Heap解题思路(推荐)：

见Heap知识点。 分别将(value, i, j)放入heap中，取出堆顶元素后，去(i, j)相邻右和下节点放入堆中。这个方法容易实现，所以推荐。

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，从某个点开始，然后比较它相邻的两个点。出发点不同，第二道在近似矩阵中点(右上角或左下角)，第三道在左上角出发。

注意事项：

1. 将(value, i, j)放入heap中

Python代码：

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

def kthSmallest4(self, matrix: List[List[int]], k: int) -> int:
	OFFSETS = [(0, 1), (1, 0)]
	heap = [(matrix[0][0], 0, 0)]
	visited = set([(0, 0)])
	while heap:
		node = heapq.heappop(heap)
		k -= 1
		if k == 0:
			return node[0]
		for _dx, _dy in OFFSETS:
			x, y = node[1] + _dx, node[2] + _dy
			if x < 0 or x >= len(matrix) or y < 0 or y >= len(matrix[0]) or (x, y) in visited:
				continue
			heapq.heappush(heap, (matrix[x][y], x, y))
			visited.add((x, y))
	return -1

算法分析：

for循环是k个，每次循环理论上产生2个节点，所以总共是2^k个，复杂度为O(klog(2k), 也就是O(k2)
由于矩阵最多n^2个元素，所以复杂度为O(klog(n2)
所以时间复杂度为O(klogn)，空间复杂度O(n2)。

数值二分法算法II解题思路：

第k的数运用数值二分法

解题步骤：

1. 数值二分法
2. 难点在于统计小于mid的个数。若遍历全矩阵比较慢，采用按行遍历，每行再用二分法找到小于mid的数的个数，再求和。

注意事项：

1. 注意k–, k从1开始
2. 每行统计小于mid个数用find smaller的模板。返回值要加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 kthSmallest(self, matrix: List[List[int]], k: int) -> int:
	k -= 1
	if not matrix or not matrix[0]:
		return -1
	N, M = len(matrix), len(matrix[0])
	start, end, epsilon = matrix[0][0], matrix[N - 1][M - 1], 0.5
	while end - start > epsilon:
		mid = start + (end - start) / 2
		count = sum([self.get_count(matrix[i], mid) for i in range(N)])
		if k < count:
			end = mid
		elif k > count:
			start = mid
		else:
			start = mid
	return math.floor(end)

def get_count(self, nums: List[int], target: float) -> int:
	start, end = 0, len(nums) - 1
	while start + 1 < end:
		mid = start + (end - start) // 2
		if target > nums[mid]:
			start = mid
		elif target < nums[mid]:
			end = mid
		else:
			end = mid
	if nums[end] < target:
		return end + 1
	if nums[start] < target:
		return start + 1
	return 0

用bisect优化

Python代码：

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

def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
	k -= 1
	if not matrix or not matrix[0]:
		return -1
	N, M = len(matrix), len(matrix[0])
	start, end, epsilon = matrix[0][0], matrix[N - 1][M - 1], 0.5
	while end - start > epsilon:
		mid = start + (end - start) / 2
		count = sum([bisect.bisect(matrix[i], mid) + 1 for i in range(N)])
		if k < count:
			end = mid
		elif k > count:
			start = mid
		else:
			start = mid
	return math.floor(end)

算法分析：

while循环有log[(max - min)/epsilon]个，假设数字平均分布，复杂度是log(n), 每个循环按每行(n行)统计小于mid的个数，
每次统计调用get_count用了log(n)，
所以总时间复杂度为O(log(n) * nlogn)，空间复杂度O(1)。

LeetCode

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Constraints:

The number of the nodes in the list is in the range [0, 10<sup>4</sup>]. -10<sup>5</sup> <= Node.val <= 10<sup>5</sup>
pos is -1 or a valid index in the linked-list.

*Follow up: Can you solve it using O(1) (i.e. constant) memory?

题目大意：

求LL是否存在循环

解题思路：

快慢指针。若存在循环就一定会相遇，这是显然的。

解题步骤：

N/A

注意事项：

1. 不涉及删除，所以不需要哟用到fake_node，但循环中先走再判断。

Python代码：

1
2
3
4
5
6
7

def hasCycle(self, head: ListNode) -> bool:
	fast, slow= head, head
	while fast and fast.next:
		fast, slow = fast.next.next, slow.next
		if fast == slow: # meets again
			return True
	return False

算法分析：

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