KK's blog

每天积累多一些

0%

Posted on Disqus:

LeetCode



You are given an m x n grid grid of values 0, 1, or 2, where:

each 0 marks an empty land that you can pass by freely, each 1 marks a building that you cannot pass through, and
each 2 marks an obstacle that you cannot pass through.

You want to build a house on an empty land that reaches all buildings in the shortest total travel distance. You can only move up, down, left, and right.

Return the shortest travel distance for such a house. If it is not possible to build such a house according to the above rules, return -1.

The total travel distance is the sum of the distances between the houses of the friends and the meeting point.

The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

Example 1:



Input: grid = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]
Output: 7
Explanation: Given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2).
The point (1,2) is an ideal empty land to build a house, as the total travel distance of 3+3+1=7 is minimal.
So return 7.


Example 2:

Input: grid = [[1,0]]
Output: 1


Example 3:

Input: grid = [[1]]
Output: -1


Constraints: m == grid.length
n == grid[i].length 1 <= m, n <= 50
grid[i][j] is either 0, 1, or 2. There will be at least one building in the grid.

题目大意：

找到所有大厦最短距离的点，这个点不能是大厦也不能是障碍

解题思路：

一开始觉得类似于LeetCode 296 Best Meeting Point，但由于有障碍，所以不能用贪婪法。最值考虑用BFS。属于对所有节点BFS。类似于LeetCode 200 Number of Islands，
从每一栋大厦开始做BFS，计算每个点到此大厦距离。然后对累计到这个点的总距离矩阵dis中。最后求距离矩阵的最小值。

此题难点在于-1的情况，也就是一个点不能到达其中一个building或者是这个building不能到达的点。所以要再用一个矩阵house_count来记录每一个点能到达的大厦数。

解题步骤：

N/A

注意事项：

  1. -1的情况，用一个矩阵house_count来记录每一个点能到达的大厦数。
  2. 用常数记录矩阵长和宽，不用x >= len(grid) or y >= len(grid[0]), 否则会TLE

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
33
OFFSETS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def shortestDistance(self, grid: List[List[int]]) -> int:
	dis = [[0 for _ in range(len(grid[0]))] for _ in range(len(grid))]
	house_count = [[0 for _ in range(len(grid[0]))] for _ in range(len(grid))]
	total_houses = 0
	for i in range(len(grid)):
		for j in range(len(grid[0])):
			if grid[i][j] == 1:
				self.bfs(grid, i, j, dis, house_count)
				total_houses += 1
	min_dis = float('inf') # remember
	for i in range(len(dis)):
		for j in range(len(dis[0])):
			if dis[i][j] > 0 and house_count[i][j] == total_houses:
				min_dis = min(min_dis, dis[i][j])
	return -1 if min_dis == float('inf') else min_dis # remember

def bfs(self, grid, start_x, start_y, dis, house_count):
	h = len(grid)
	w = len(grid[0]) # remember otherwise TLE
	queue = collections.deque([(start_x, start_y, 0)])
	visited = [[False for _ in range(len(grid[0]))] for _ in range(len(grid))]
	visited[start_x][start_y] = True
	while queue:
		node = queue.popleft()
		for _dx, _dy in OFFSETS:
			x, y = node[0] + _dx, node[1] + _dy
			if x < 0 or x >= h or y < 0 or y >= w or grid[x][y] != 0 or visited[x][y]:
				continue
			queue.append((x, y, node[2] + 1))
			visited[x][y] = True
			dis[x][y] += node[2] + 1
			house_count[x][y] += 1

算法分析：

时间复杂度为O(nm * nm)，空间复杂度O(nm)

Posted on Disqus:

LeetCode



Given a 2D matrix matrix, handle multiple queries of the following type:

Calculate the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Implement the NumMatrix class: NumMatrix(int[][] matrix) Initializes the object with the integer matrix matrix.
int sumRegion(int row1, int col1, int row2, int col2) Returns the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Example 1:



Input
[“NumMatrix”, “sumRegion”, “sumRegion”, “sumRegion”]
[[[[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]], [2, 1, 4, 3], [1, 1, 2, 2], [1, 2, 2, 4]]
Output
[null, 8, 11, 12]

Explanation
NumMatrix numMatrix = new NumMatrix([[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (i.e sum of the red rectangle)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (i.e sum of the green rectangle)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (i.e sum of the blue rectangle)


Constraints: m == matrix.length
n == matrix[i].length 1 <= m, n <= 200
-10<sup>5</sup> <= matrix[i][j] <= 10<sup>5</sup> 0 <= row1 <= row2 < m
0 <= col1 <= col2 < n At most 10<sup>4</sup> calls will be made to sumRegion.

题目大意：

求子矩阵和

解题思路：

计算presum公式:

1
dp[i][j] = matrix[i-1][j-1] + dp[i-1][j] + dp[i][j] - dp[i-1][j-1]

计算子矩阵公式：

1
res = presum[x][y] - left - top + diag

解题步骤：

N/A

注意事项：

  1. dp有左上边界，计算子矩阵注意dp和输入差1

Python代码：

1
2
3
4
5
6
7
8
9
10
class NumMatrix(TestCases):

    def __init__(self, matrix: List[List[int]]):
        self.dp = [[0 for _ in range(len(matrix[0]) + 1)] for _ in range(len(matrix) + 1)]
        for i in range(1, len(self.dp)):
            for j in range(1, len(self.dp[0])):
                self.dp[i][j] = matrix[i - 1][j - 1] + self.dp[i - 1][j] + self.dp[i][j - 1] - self.dp[i - 1][j - 1]

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        return self.dp[row2 + 1][col2 + 1] - self.dp[row2 + 1][col1] - self.dp[row1][col2 + 1] + self.dp[row1][col1]

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given a list of accounts where each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account.

Now, we would like to merge these accounts. Two accounts definitely belong to the same person if there is some common email to both accounts. Note that even if two accounts have the same name, they may belong to different people as people could have the same name. A person can have any number of accounts initially, but all of their accounts definitely have the same name.

After merging the accounts, return the accounts in the following format: the first element of each account is the name, and the rest of the elements are emails in sorted order. The accounts themselves can be returned in any order.

Example 1:

Input: accounts = [[“John”,”johnsmith@mail.com”,”john_newyork@mail.com”],[“John”,”johnsmith@mail.com”,”john00@mail.com”],[“Mary”,”mary@mail.com”],[“John”,”johnnybravo@mail.com”]]
Output: [[“John”,”john00@mail.com”,”john_newyork@mail.com”,”johnsmith@mail.com”],[“Mary”,”mary@mail.com”],[“John”,”johnnybravo@mail.com”]]
Explanation:
The first and second John’s are the same person as they have the common email “johnsmith@mail.com”.
The third John and Mary are different people as none of their email addresses are used by other accounts.
We could return these lists in any order, for example the answer [[‘Mary’, ‘mary@mail.com’], [‘John’, ‘johnnybravo@mail.com’],
[‘John’, ‘john00@mail.com’, ‘john_newyork@mail.com’, ‘johnsmith@mail.com’]] would still be accepted.


Example 2:

Input: accounts = [[“Gabe”,”Gabe0@m.co”,”Gabe3@m.co”,”Gabe1@m.co”],[“Kevin”,”Kevin3@m.co”,”Kevin5@m.co”,”Kevin0@m.co”],[“Ethan”,”Ethan5@m.co”,”Ethan4@m.co”,”Ethan0@m.co”],[“Hanzo”,”Hanzo3@m.co”,”Hanzo1@m.co”,”Hanzo0@m.co”],[“Fern”,”Fern5@m.co”,”Fern1@m.co”,”Fern0@m.co”]]
Output: [[“Ethan”,”Ethan0@m.co”,”Ethan4@m.co”,”Ethan5@m.co”],[“Gabe”,”Gabe0@m.co”,”Gabe1@m.co”,”Gabe3@m.co”],[“Hanzo”,”Hanzo0@m.co”,”Hanzo1@m.co”,”Hanzo3@m.co”],[“Kevin”,”Kevin0@m.co”,”Kevin3@m.co”,”Kevin5@m.co”],[“Fern”,”Fern0@m.co”,”Fern1@m.co”,”Fern5@m.co”]]


Constraints:

1 <= accounts.length <= 1000 2 <= accounts[i].length <= 10
1 <= accounts[i][j] <= 30 accounts[i][0] consists of English letters.
* accounts[i][j] (for j > 0) is a valid email.

题目大意：

每个人都有一堆邮件，根据邮件是否相同判断是否同一个人，合并同一个人的所有邮件。

BFS解题思路(推荐)：

根据输入建图，然后类似于Num of island从某一个邮件出发用BFS找连通的所有邮件，迭代所有邮件，全局visited来记录访问过的，这点跟Num of island一样。

解题步骤：

N/A

注意事项：

  1. 图的初始化，要记得没有边的图要加入到邻接表中，注意不存在的时候才加入，否则会覆盖现有的邻接表Line 8 - 9
  2. 处理名字(第一个元素)，名字对确定是否连通没有任何作用，只需要加入到最后结果即可
  3. 有重复邮件，所以一开始去重。结果按同一账号内按字母排序

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
33
34
35
36
37
38
def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
	for li in accounts:
		li[:] = [li[0]] + list(set(li[1:]))
	graph = collections.defaultdict(list)
	name_dict = collections.defaultdict(str)
	for li in accounts:
		name_dict[li[1]] = li[0]
		if li[1] not in graph:
			graph[li[1]] = [] # remember single email
		for i in range(2, len(li)):
			graph[li[1]].append(li[i])
			graph[li[i]].append(li[1])
	res, visited = [], set()
	for email in graph.keys():
		sub_res = self.bfs(graph, email, visited, name_dict)
		if sub_res:
			res.append(sub_res)
	return res

def bfs(self, graph, start, visited, name_dict):
	if start in visited:
		return
	res, name = [], ''
	queue = collections.deque([start])
	visited.add(start)
	while queue:
		node = queue.popleft()
		res.append(node)
		if node in name_dict:
			name = name_dict[node]
		for neighbor in graph[node]:
			if neighbor in visited:
				continue
			queue.append(neighbor)
			visited.add(neighbor)
	res.sort()
	res.insert(0, name)
	return res

算法分析：

时间复杂度为O(nklognk)，空间复杂度O(nk), n, k分别账号数，每个账号的邮件数, 因为结果需要按字母排序

UnionFind算法II解题思路(不推荐)：

这题很容易想到用连通集做，但其实连通集应用条件为动态求连通集个数。这题是静态求连通数，所以类似于L200 Num of island可以用DFS或者BFS。

注意事项：

  1. union只做每个list里面的，而list之间相同的邮件不用做union，因为既然相同自动做了
  2. 模板的问题，见UnionFind里的注意事项： if self.parent[email] != email, self.parent[parent] = parent2
  3. 处理名字
  4. 有重复邮件

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
33
34
35
36
37
38
39
40
41
42
43
44
class Solution(TestCases):

    def accountsMerge2(self, accounts: List[List[str]]) -> List[List[str]]:
        for li in accounts:
            li[::] = [li[0]] + list(set(li[1:]))
        uf = UnionFind(accounts)

        for li in accounts:
            for i in range(2, len(li)):
                uf.union(li[i - 1], li[i])

        visited = set()
        res = collections.defaultdict(list)
        name_dict = collections.defaultdict(str)
        for li in accounts:
            name_dict[uf.find(li[1])] = li[0]
            for email in li[1:]:
                if email in visited:  # remember
                    continue
                res[uf.find(email)].append(email)
                visited.add(email)
        for _id, li in res.items():
            li.sort()
            li.insert(0, name_dict[_id])
        return list(res.values())

class UnionFind:

    def __init__(self, email_list):
        self.parent = collections.defaultdict(str)
        for i, li in enumerate(email_list):
            for email in li[1:]:
                self.parent[email] = email

    def find(self, email):
        if self.parent[email] != email:  # if statement
            self.parent[email] = self.find(self.parent[email])
        return self.parent[email]

    def union(self, email, email2):
        parent = self.find(email)
        parent2 = self.find(email2)
        if parent != parent2:
            self.parent[parent] = parent2 # remember not self.parent[email] = email2

算法分析：

时间复杂度为O(nklognk)，空间复杂度O(nk), n, k分别账号数，每个账号的邮件数

Posted on Disqus:

LeetCode



Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and uses only constant extra space.

Example 1:

Input: nums = [1,3,4,2,2]
Output: 2


Example 2:

Input: nums = [3,1,3,4,2]
Output: 3


Constraints:

1 <= n <= 10<sup>5</sup> nums.length == n + 1
1 <= nums[i] <= n All the integers in nums appear only once except for precisely one integer which appears two or more times.

Follow up:

How can we prove that at least one duplicate number must exist in nums? Can you solve the problem in linear runtime complexity?

题目大意：

给定数值范围[1, n]找重复的数，只有一个重复数，但可能重复多次。题目要求不能用额外空间，不能修改数组

解题思路：

数值二分法

解题步骤：

N/A

注意事项：

  1. 比较mid和count的关系，用例子来写程序，如[1, 2, 2, 3, 4]
  2. 重复的数可能重复多次，所以不能用异或法

Python代码：

1
2
3
4
5
6
7
8
9
10
def findDuplicate(self, nums: List[int]) -> int:
	start, end, epsilon = min(nums), max(nums), 0.5
	while end - start > epsilon:
		mid = start + (end - start) / 2
		count = len([n for n in nums if n <= mid])
		if count <= mid:
			start = mid
		else:
			end = mid
	return int(end)

算法分析：

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

Posted on Disqus:

LeetCode



You are given an m x n grid rooms initialized with these three possible values.

-1 A wall or an obstacle. 0 A gate.
INF Infinity means an empty room. We use the value 2<sup>31</sup> - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

Example 1:



Input: rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
Output: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]


Example 2:

Input: rooms = [[-1]]
Output: [[-1]]


Constraints: m == rooms.length
n == rooms[i].length 1 <= m, n <= 250
* rooms[i][j] is -1, 0, or 2<sup>31</sup> - 1.

题目大意：

求所有房间到门的最短距离

解题思路：

属于多始点BFS类型

解题步骤：

N/A

注意事项：

  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
OFFSET = [(-1, 0), (1, 0), (0, 1), (0, -1)]
class Solution(TestCases):

    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        """
        Do not return anything, modify rooms in-place instead.
        """
        gates = []
        for i in range(len(rooms)):
            for j in range(len(rooms[0])):
                if rooms[i][j] == 0:
                    gates.append((i, j, 0))
        queue = collections.deque(gates)
        visited = set(gates)
        while queue:
            x, y, distance = queue.popleft()
            if rooms[x][y] != 0: # not distance != 0
                rooms[x][y] = distance
            for _dx, _dy in OFFSET:
                _x, _y = x + _dx, y + _dy
                if _x < 0 or _x >= len(rooms) or _y < 0 or _y >= len(rooms[0]) or \
                        rooms[_x][_y] == -1 or (_x, _y) in visited:
                    continue
                queue.append((_x, _y, distance + 1))
                visited.add((_x, _y))

算法分析：

时间复杂度为O(nm)，空间复杂度O(mn)

Free mock interview