問題ページはこちら。
2553. Separate the Digits in an Array
与えられた数値を１桁ずつ返す問題。
整数で与えられるので、文字列として解釈して１文字ずつ解を得ればOK。
class Solution:
def separateDigits(self, nums: List[int]) -> List[int]:
ans = []
for num in nums:
for char in str(num):
ans.append(int(char))
return ans2554. Maximum Number of Integers to Choose From a Range I
小さい値から貪欲に取っていく。
bannedはリストで与えられるが、重複があるかもしれないのと、x in bannedは計算量がO(N)で遅いのでsetに直す。
class Solution:
def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:
banned = set(banned)
ans = 0
for i in range(1, n+1):
if i in banned:
continue
if maxSum >= i:
maxSum -= i
ans += 1
else:
break
return ans2555. Maximize Win From Two Segments
ある範囲が与えられ、長さk以下の区間を2個選んだ時に得られる個数の最大値を答える問題。
左右から尺取法をしていって答えを求める。
[0, i]と[i+1, n]のそれぞれの最大値の和が最大になれば良い。
答えを求めるための最後のループは配列外参照に注意。
class Solution:
def maximizeWin(self, prizePositions: List[int], k: int) -> int:
n = len(prizePositions)
left = [0] * n
left[0] = 1
j = 0
for i in range(1, n):
while prizePositions[i] - prizePositions[j] > k:
j += 1
left[i] = max(left[i-1], i-j+1)
right = [0] * n
right[n-1] = 1
j = n-1
for i in range(n-2, -1, -1):
while prizePositions[j] - prizePositions[i] > k:
j -= 1
right[i] = max(right[i+1], j-i+1)
ans = 0
for i in range(n):
ans = max(ans, left[i] + (right[i+1] if i != n-1 else 0))
return ans左からの尺取でO(N）、右からの尺取でO(N)、答えを求める計算がO(N)かかるので、計算量はO(3N)=O(N)となる。
ここで、尺取を1回行うだけで解けないか考えてみる。
[left, right]が1つの候補に挙がる時、もう1つの候補は[0, left – 1]で得られる最大値を足せば良いことに気づく。
i番目までに得られる最大値をdp[i]とすると
尺取中の範囲[left, right] ＋ dp[left – 1]が答えになる。
0-indexで+1するかどうか注意しながら実装。
class Solution:
def maximizeWin(self, prizePositions: List[int], k: int) -> int:
n = len(prizePositions)
dp = [0] * (n + 1)
ans = 0
l = 0
for r in range(n):
while prizePositions[r] - prizePositions[l] > k:
l += 1
dp[r + 1] = max(dp[r], r - l + 1)
ans = max(ans, r - l + 1 + dp[l])
return ansO(N)1回分の計算量で解くことができた。
2556. Disconnect Path in a Binary Matrix by at Most One Flip
グラフの1箇所だけを通れなくして、ゴールまでたどり着けるかどうか判定する問題。
ゴールまでたどり着くには複数の経路があるはずだが、全ての経路で共通して通る1マスが存在しているかどうか見つければいい。
その1マスを通れなくすれば、全ての経路でゴールまでたどり着けなくなる。
前処理として、そもそもゴールまで到達可能かどうか調べる。
class Solution:
def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:
m = len(grid)
n = len(grid[0])
reachable = [[False] * n for _ in range(m)]
reachable[0][0] = True
for i in range(1, m):
reachable[i][0] = reachable[i-1][0]
for i in range(1, n):
reachable[0][i] = reachable[0][i-1]
for i in range(1, m):
for j in range(1, n):
if grid[i][j] == 1:
reachable[i][j] = reachable[i-1][j] or reachable[i][j-1]
if not reachable[m-1][n-1]:
return Trueその後はBFSをしていく。
全てのマスで共通して通る1マスがあれば、キューにある座標が1個だけになるはずである。
ただし、スタートとゴールがキューにあると同じく個数が1個になるので注意する。
visited = set()
visited.add((0, 0))
q = deque()
q.append((0,0))
while q:
if len(q) == 1 and q[0] != (0,0) and q[0] != (m-1, n-1):
return True
for _ in range(len(q)):
row, col = q.popleft()
for i, j in [(1,0),(0,1)]:
if row + i == m or col + j == n:
continue
if grid[row+i][col+j] == 1 and (row+i, col+j) not in visited:
q.append((row+i, col+j))
visited.add((row+i, col+j))
return False別解として、ゴールから逆算する方法を考える。
スタートからゴールに行けるということは、ゴールからスタートにも行けるはずである。
ここで、スタートから座標(i,j)に到達する経路の数をforward[i][j]、ゴールからの経路の数をbackward[i][j]、全ての経路の数をtotalとする。
BFSを使った解法と同じく、もし全ての経路が共通で通る1マスが存在する場合、total = forward[i][j] * backward[i][j]が成り立つことを利用する。
噛み砕いて考えると、A→Bに行く方法が2通り、B→Cに行く方法が3通りであれば、A→Cに行く方法は6通りになる、という計算と同じになる。
二次元配列で添字が増えるとややこしいが、アイデア自体は単純なはず。
class Solution:
def isPossibleToCutPath(self, grid: List[List[int]]) -> bool:
m = len(grid)
n = len(grid[0])
forward = [[0] * n for _ in range(m)]
forward[0][0] = 1
for i in range(m):
for j in range(n):
if i > 0 and grid[i][j] == 1:
forward[i][j] += forward[i-1][j]
if j > 0 and grid[i][j] == 1:
forward[i][j] += forward[i][j-1]
backward = [[0] * n for _ in range(m)]
backward[m-1][n-1] = 1
for i in range(m-1, -1, -1):
for j in range(n-1, -1, -1):
if i < m-1 and grid[i][j] == 1:
backward[i][j] += backward[i+1][j]
if j < n-1 and grid[i][j] == 1:
backward[i][j] += backward[i][j+1]
total = forward[m-1][n-1]
if total == 0:
return True
for i in range(m):
for j in range(n):
if forward[i][j] * backward[i][j] == total:
if (i,j) != (0,0) and (i,j) != (m-1,n-1):
return True
return False
コメント