KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

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)

Posted on Edited on Disqus:

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

Posted on Edited on Disqus:

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

Posted on Edited on Disqus:

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

Posted on Edited on Disqus:

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

Free mock interview