笔记仓库

正常人的正常笔记集

LeetCode Weekly Contest 134

https://leetcode.com/contest/weekly-contest-134

Moving Stones Until Consecutive

原题地址 https://leetcode.com/contest/weekly-contest-134/problems/moving-stones-until-consecutive/

Three stones are on a number line at positions a, b, and c.

Each turn, let’s say the stones are currently at positions x, y, z with x < y < z. You pick up the stone at either position x or position z, and move that stone to an integer position k, with x < k < z and k != y.

The game ends when you cannot make any more moves, ie. the stones are in consecutive positions.

When the game ends, what is the minimum and maximum number of moves that you could have made? Return the answer as an length 2 array: answer = [minimum_moves, maximum_moves]

Example 1:

Input: a = 1, b = 2, c = 5
Output: [1, 2]
Explanation: Move stone from 5 to 4 then to 3, or we can move it directly to 3.
Example 2:

Input: a = 4, b = 3, c = 2
Output: [0, 0]
Explanation: We cannot make any moves.

Note:

  1. 1 <= a <= 100
  2. 1 <= b <= 100
  3. 1 <= c <= 100
  4. a != b, b != c, c != a

移动次数最多的做法:两边的石头都分别向中间一次移动一位直至相邻。还有很多等价的做法,不赘述了。

移动次数最少的做法:把两边的石头一次放到与中间相邻的位置。需要注意,当两石头距离为2时,可以直接把另一个石头放到中间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def numMovesStones(self, a, b, c):
"""
:type a: int
:type b: int
:type c: int
:rtype: List[int]
"""
a, b, c = tuple(sorted([a, b, c]))
max_moves = c - a - 2
d1, d2 = tuple(sorted([b - a, c - b]))
if d2 == 1:
return [0, 0]
if d1 <= 2:
return [1, max_moves]
return [2, max_moves]

Coloring A Border

原题地址 https://leetcode.com/contest/weekly-contest-134/problems/coloring-a-border/

Given a 2-dimensional grid of integers, each value in the grid represents the color of the grid square at that location.

Two squares belong to the same connected component if and only if they have the same color and are next to each other in any of the 4 directions.

The border of a connected component is all the squares in the connected component that are either 4-directionally adjacent to a square not in the component, or on the boundary of the grid (the first or last row or column).

Given a square at location (r0, c0) in the grid and a color, color the border of the connected component of that square with the given color, and return the final grid.

Example 1:

1
2
Input: grid = [[1,1],[1,2]], r0 = 0, c0 = 0, color = 3
Output: [[3, 3], [3, 2]]

Example 2:

1
2
Input: grid = [[1,2,2],[2,3,2]], r0 = 0, c0 = 1, color = 3
Output: [[1, 3, 3], [2, 3, 3]]

Example 3:

1
2
Input: grid = [[1,1,1],[1,1,1],[1,1,1]], r0 = 1, c0 = 1, color = 2
Output: [[2, 2, 2], [2, 1, 2], [2, 2, 2]]

Note:

  1. 1 <= grid.length <= 50
  2. 1 <= grid[0].length <= 50
  3. 1 <= grid[i][j] <= 1000
  4. 0 <= r0 < grid.length
  5. 0 <= c0 < grid[0].length
  6. 1 <= color <= 1000

没有什么特别的DFS,从(r0, c0)找不足4个同色邻结点的同色点

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
class Solution(object):
def colorBorder(self, grid, r0, c0, color):
"""
:type grid: List[List[int]]
:type r0: int
:type c0: int
:type color: int
:rtype: List[List[int]]
"""
border = []
seen = {(r0, c0)}
n, m = len(grid), len(grid[0])

def dfs(x, y):
nei = 0
for i, j in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
if 0 <= i < n and 0 <= j < m and grid[i][j] == grid[x][y]:
nei += 1
if (i, j) not in seen:
seen.add((i, j))
dfs(i, j)
if nei < 4:
border.append((x, y))

dfs(r0, c0)

for (x, y) in border:
grid[x][y] = color

return grid

Uncrossed Lines

原题地址 https://leetcode.com/contest/weekly-contest-134/problems/uncrossed-lines/

We write the integers of A and B (in the order they are given) on two separate horizontal lines.

Now, we may draw a straight line connecting two numbers A[i] and B[j] as long as A[i] == B[j], and the line we draw does not intersect any other connecting (non-horizontal) line.

Return the maximum number of connecting lines we can draw in this way.

Example 1:

1
2
3
4
Input: A = [1,4,2], B = [1,2,4]
Output: 2
Explanation: We can draw 2 uncrossed lines as in the diagram.
We cannot draw 3 uncrossed lines, because the line from A[1]=4 to B[2]=4 will intersect the line from A[2]=2 to B[1]=2.

Example 2:

1
2
Input: A = [2,5,1,2,5], B = [10,5,2,1,5,2]
Output: 3

Example 3:

1
2
Input: A = [1,3,7,1,7,5], B = [1,9,2,5,1]
Output: 2

Note:

  1. 1 <= A.length <= 500
  2. 1 <= B.length <= 500
  3. 1 <= A[i], B[i] <= 2000

动态规划找最大值。dp[i+1][j+1]表示A的前i位和B的前j位直接最多可以连几条线,如果A[i]B[j]可以连线,那么前面A[:i-1]B[:j-1]之间的连线也可以保留。如果不可以,则只能按照AB退一位后两个数组之间形成的最多连线的最大值决定A[:i]B[:j]之间至多有多少连线。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def maxUncrossedLines(self, A, B):
"""
:type A: List[int]
:type B: List[int]
:rtype: int
"""
n, m = len(A), len(B)
dp = [[0] * (m + 1) for _ in range(n + 1)]

for i in range(n):
for j in range(m):
temp = max(dp[i][j + 1], dp[i + 1][j])
if A[i] == B[j]:
dp[i + 1][j + 1] = max(dp[i][j] + 1, temp)
else:
dp[i + 1][j + 1] = temp

return dp[-1][-1]

Escape a Large Maze

原题地址 https://leetcode.com/contest/weekly-contest-134/problems/escape-a-large-maze/

In a 1 million by 1 million grid, the coordinates of each grid square are (x, y) with 0 <= x, y < 10^6.

We start at the source square and want to reach the target square. Each move, we can walk to a 4-directionally adjacent square in the grid that isn’t in the given list of blocked squares.

Return true if and only if it is possible to reach the target square through a sequence of moves.

Example 1:

1
2
3
4
Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
Output: false
Explanation:
The target square is inaccessible starting from the source square, because we can't walk outside the grid.

Example 2:

1
2
3
4
Input: blocked = [], source = [0,0], target = [999999,999999]
Output: true
Explanation:
Because there are no blocked cells, it's possible to reach the target square.

Note:

  1. 0 <= blocked.length <= 200
  2. blocked[i].length == 2
  3. 0 <= blocked[i][j] < 10^6
  4. source.length == target.length == 2
  5. 0 <= source[i][j], target[i][j] < 10^6
  6. source != target

参考这个解法B个点组成的blocked最多能把source锁死在大小为B*(B-1)/2的区域内,也就是45度夹角的斜线与边界构成的一个等腰直角三角形内。进行dfs搜索,只要路径长度大于B*(B-1)/2就说明并没有被锁死,当然可以到达target

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
class Solution(object):
def isEscapePossible(self, blocked, source, target):
"""
:type blocked: List[List[int]]
:type source: List[int]
:type target: List[int]
:rtype: bool
"""
blocked = set(map(tuple, blocked))
B = len(blocked)
target = tuple(target)
seen = set()

def dfs(x, y, step):
if (x, y) == target or step > (B * (B - 1) / 2):
return True
seen.add((x, y))
for i, j in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
if 0 <= i < 10**6 and 0 <= j < 10**6 and (i, j) not in seen and (i, j) not in blocked:
seen.add((i, j))
if dfs(i, j, step + 1):
return True
return False

return dfs(source[0], source[1], 0)