Re: Leetcode Weekly Contest 414

看板Marginalman作者dont (dont)時間4月前 (2024/09/08 13:40)推噓2(2推 0噓 0→)

留言2則, 2人參與討論串2/2 (看更多)

3280. Convert Date to Binary 轉int再轉binary 懶人寫法 ```python class Solution: def convertDateToBinary(self, date: str) -> str: def convert(s): return bin(int(s))[2:] return '-'.join(map(convert, date.split('-'))) ``` 3281. Maximize Score of Numbers in Ranges 排序後對answer做Binary Search check function 檢查curr + diff 是否在start[i] + d範圍內 ```python class Solution: def maxPossibleScore(self, start: List[int], d: int) -> int: start.sort() n = len(start) def check(diff): curr = start[0] for i in range(1, n): if curr + diff > start[i] + d: return False curr = max(start[i], curr + diff) return True res = 0 left, right = 0, 2_000_000_001 while left <= right: mid = (left + right) // 2 if check(mid): res = mid left = mid + 1 else: right = mid - 1 return res ``` 3282. Reach End of Array With Max Score 每次都往下一個 >= 的值跳之前在討論區看過差不多的題目= = 差別只是他是(j-i) * nums[j] https://leetcode.com/discuss/interview-question/5633414/ ```python class Solution: def findMaximumScore(self, nums: List[int]) -> int: # jump to next greater/equal num n = len(nums) res = 0 i = 0 for j in range(n-1): if nums[j] >= nums[i]: res += (j-i) * nums[i] i = j res += (n-1-i) * nums[i] return res ``` 第四題 DP + bitmask 1. 用BFS找(x,y)到(nx,ny)的步數 2. DP找(x,y)開始走的min/max步數用bitmask 紀錄走過的position 過了但很慢 10000ms都快要TLE了 ```python class Solution: def maxMoves(self, kx: int, ky: int, positions: List[List[int]]) -> int: n = len(positions) dirs = [(1, 2), (1, -2), (2, 1), (2, -1), (-1, 2), (-1, -2), (-2, 1), (-2, -1)] @cache def dist(x, y, nx, ny): seen = set() step = 0 queue = deque([(x, y)]) while queue: for _ in range(len(queue)): x, y = queue.popleft() if x == nx and y == ny: return step for dx, dy in dirs: if not (0 <= x + dx < 50 and 0 <= y + dy < 50): continue if (x+dx, y+dy) in seen: continue seen.add((x+dx, y+dy)) queue.append((x+dx, y+dy)) step += 1 return float('inf') @cache def dp(x, y, mask, is_alice): if mask == (1 << n) - 1: return 0 if is_alice: res = float('-inf') for i in range(n): if mask & (1 << i): continue nx, ny = positions[i] res = max(res, dist(x, y, nx, ny) + dp(nx, ny, mask | (1 << i), False)) else: res = float('inf') for i in range(n): if mask & (1 << i): continue nx, ny = positions[i] res = min(res, dist(x, y, nx, ny) + dp(nx, ny, mask | (1 << i), True)) return res return dp(kx, ky, 0, True) ``` -- https://i.imgur.com/kyBhy6o.jpeg