KK's blog

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: <pre>**Input: low = "50", high = "100"

Output: 3

Explanation: 69, 88, and 96 are three strobogrammatic numbers. </pre>

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:

<pre>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,<u>13</u>,15], and the 8^th smallest number is 13 </pre>

Example 2:

<pre>Input: matrix = [[-5]], k = 1 Output: -5 </pre>

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个，复杂度为<code>O(klog(2^k)</code>, 也就是<code>O(k²)</code>
由于矩阵最多n^2个元素，所以复杂度为<code>O(klog(n²)</code>
所以时间复杂度为O(klogn)，空间复杂度<code>O(n²)</code>。

数值二分法算法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

<div>

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

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 (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

Do not modify the linked list.

Example 1:

<pre>Input: head = [3,2,0,-4], pos = 1 Output: tail connects to node index 1 Explanation: There is a cycle in the linked list, where tail connects to the second node. </pre>

Example 2:

<pre>Input: head = [1,2], pos = 0 Output: tail connects to node index 0 Explanation: There is a cycle in the linked list, where tail connects to the first node. </pre>

Example 3:

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

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?

</div>

题目大意：

求LL是否存在循环，若存在返回循环起点

解题思路：

先用快慢指针找到相遇点，然后将slow指针移回fake_head起点，同速度移动直到相遇即为所求

证明：

A为起点，B为快慢指针相遇点，假设长度分别为z, y, x

1
2
3
4
5

fast在相遇时走过的距离为: z + x + y + y, 比slow多走一圈  
slow在相遇时走过的距离为: z + y  
由于fast速度是slow的两倍，所以相遇时，同一时间内，走过的距离也是两倍。
z + x + y + y = 2 * (z + y)
x = z得证

解题步骤：

N/A

注意事项：

1. 不涉及删除，所以不需要哟用到fake_node，但循环中先走再判断。
2. 循环可能不存在，此时返回None

Python代码：

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

def detectCycle(self, head: ListNode) -> ListNode:
	fast, slow= head, head
	while fast and fast.next:
		fast, slow = fast.next.next, slow.next
		if fast == slow: # meets again
			break
	if not fast or not fast.next:
		return None # remember
	slow = head
	while fast != slow:
		fast, slow = fast.next, slow.next
	return fast

算法分析：

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

LeetCode

<div>

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:

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

Example 2:

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

Example 3:

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

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?

</div>

题目大意：

求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)

LeetCode

<div>

Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Example 1:

<pre>Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] Output: 4 </pre>

Example 2:

<pre>Input: matrix = [["0","1"],["1","0"]] Output: 1 </pre>

Example 3:

<pre>Input: matrix = [["0"]] Output: 0 </pre>

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 300
• matrix[i][j] is '0' or '1'.

</div>

题目大意：

求子正方形矩阵全是1的最大面积

解题思路：

求最值且是矩阵考虑用DP，但公式比较难写。
dp[i][j]为以(i-1, j-1)为右下端点的正方形的边长 递归式：

1
2

dp[i][j] = min{dp[i-1][j-1], dp[i-1][j], dp[i][j-1]} + 1 if matrix[i][j] == 1
         = 0                                             otherwise

解题步骤：

严格遵守DP的5点注意事项

注意事项：

1. 严格遵守DP的5点注意事项。初始值是0，表示第一行或第一列的点的边长最多只能为1.
2. 输入是字符，所以比较是否1时候用字符比较

Python代码：

1
2
3
4
5
6
7
8
9
10
11

# dp[i][j] = min{dp[i-1][j-1], dp[i-1][j], dp[i][j-1]} + 1 if matrix[i][j] == 1
#          = 0                                             otherwise
def maximalSquare(self, matrix: List[List[str]]) -> int:
	dp = [[0 for _ in range(len(matrix[0]) + 1)] for _ in range(len(matrix) + 1)] # remember 0 not 1 or float(inf)
	# dp[0][0] = 0
	res = 0
	for i in range(1, len(dp)):
		for j in range(1, len(dp[0])):
			dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1 if matrix[i - 1][j - 1] == '1' else 0 # remember '1' not 1
			res = max(res, dp[i][j])
	return res * res

算法分析：

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