笔记仓库

正常人的正常笔记集

LeetCode Weekly Contest 136

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

Robot Bounded In Circle

原题地址 https://leetcode.com/contest/weekly-contest-136/problems/robot-bounded-in-circle/

On an infinite plane, a robot initially stands at (0, 0) and faces north. The robot can receive one of three instructions:

  • "G": go straight 1 unit;
  • "L": turn 90 degrees to the left;
  • "R": turn 90 degress to the right.
    The robot performs the instructions given in order, and repeats them forever.

Return true if and only if there exists a circle in the plane such that the robot never leaves the circle.

Example 1:

1
2
3
4
5
Input: "GGLLGG"
Output: true
Explanation:
The robot moves from (0,0) to (0,2), turns 180 degrees, and then returns to (0,0).
When repeating these instructions, the robot remains in the circle of radius 2 centered at the origin.

Example 2:

1
2
3
4
Input: "GG"
Output: false
Explanation:
The robot moves north indefinetely.

Example 3:

1
2
3
4
Input: "GL"
Output: true
Explanation:
The robot moves from (0, 0) -> (0, 1) -> (-1, 1) -> (-1, 0) -> (0, 0) -> ...

Note:

  1. 1 <= instructions.length <= 100
  2. instructions[i] is in {'G', 'L', 'R'}

如果执行完一遍instructions后位置没有变,则无论执行多少次也不会变。如果执行完一遍instructions确实产生了位移,并有了方向的改变,那么执行多次instructions一定会形成一个凸多边形,也就是回路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
def isRobotBounded(self, instructions):
"""
:type instructions: str
:rtype: bool
"""
directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]
d = 0
x = y = 0

for i in instructions:
if i == 'G':
dx, dy = directions[d]
x, y = x + dx, y + dy
elif i == 'L':
d = (d + 1) % 4
else:
d = (d - 1) % 4

return (x, y) == (0, 0) or d != 0

Flower Planting With No Adjacent

原题地址 https://leetcode.com/contest/weekly-contest-136/problems/flower-planting-with-no-adjacent/

You have N gardens, labelled 1 to N. In each garden, you want to plant one of 4 types of flowers.

paths[i] = [x, y] describes the existence of a bidirectional path from garden x to garden y.

Also, there is no garden that has more than 3 paths coming into or leaving it.

Your task is to choose a flower type for each garden such that, for any two gardens connected by a path, they have different types of flowers.

Return any such a choice as an array answer, where answer[i] is the type of flower planted in the (i+1)-th garden. The flower types are denoted 1, 2, 3, or 4. It is guaranteed an answer exists.

Example 1:

1
2
Input: N = 3, paths = [[1,2],[2,3],[3,1]]
Output: [1,2,3]

Example 2:

1
2
Input: N = 4, paths = [[1,2],[3,4]]
Output: [1,2,1,2]

Example 3:

1
2
Input: N = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]
Output: [1,2,3,4]

Note:

  1. 1 <= N <= 10000
  2. 0 <= paths.size <= 20000
  3. No garden has 4 or more paths coming into or leaving it.
  4. It is guaranteed an answer exists.

看着以为是“四色问题”很吓人,其实按部就班给每个点上与邻接点不同的颜色就可以了,反正邻接点不会超过3个的……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
def gardenNoAdj(self, N, paths):
"""
:type N: int
:type paths: List[List[int]]
:rtype: List[int]
"""
graph = collections.defaultdict(list)
res = [0] * N
for i, j in paths:
graph[i - 1].append(j - 1)
graph[j - 1].append(i - 1)

for i in range(N):
if res[i] == 0:
res[i] = min({1, 2, 3, 4} - set(res[j] for j in graph[i]))

return res

Partition Array for Maximum Sum

原题地址 https://leetcode.com/contest/weekly-contest-136/problems/partition-array-for-maximum-sum/

Given an integer array A, you partition the array into (contiguous) subarrays of length at most K. After partitioning, each subarray has their values changed to become the maximum value of that subarray.

Return the largest sum of the given array after partitioning.

Example 1:

1
2
3
Input: A = [1,15,7,9,2,5,10], K = 3
Output: 84
Explanation: A becomes [15,15,15,9,10,10,10]

Note:

  1. 1 <= K <= A.length <= 500
  2. 0 <= A[i] <= 10^6

dp[i]表示到A[i]为止最大替换的和。对于前K个数,找到最大值覆盖整个子数组即可。当i>=K时,最多能向前覆盖K个数,因此可以找满足i-K<=j<i的最大dp[j]+max(A[j+1:i])*(i-j)

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

for i in range(K, n):
temp_max = 0
for j in range(i, i - K, -1):
temp_max = max(temp_max, A[j])
dp[i] = max(dp[i], dp[j - 1] + temp_max * (i - j + 1))

return dp[-1]