Re: [閒聊] 每日leetcode

看板Marginalman作者dont (dont)時間1年前 (2024/09/05 13:57)推噓1(1推 0噓 1→)

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

2028. Find Missing Observations ## 思路先計算n個rolls的總和如果不在全丟1或丟6的範圍內就回傳[] 除上n, 讓所有骰子全丟a 剩下的餘數分配到b個骰子 ## Code ```python class Solution: def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]: m = len(rolls) total = (m+n) * mean - sum(rolls) if total < n * 1 or total > n * 6: return [] a, b = divmod(total, n) return [a+1] * b + [a] * (n-b) ``` --- 2472. Maximum Number of Non-overlapping Palindrome Substrings ## 思路跟 5. Longest Palindromic Substring 差不多回文有分基偶數的case: aba, abba 掃整個字串, 把(i,i), (i,i+1) 當中心點往左右掃找回文用變數last_r記錄目前的字串邊界, 如果left <= last_r就表示overlap 只要回文的長度為k或k+1就結束並更新邊界last_r ## Code ```python class Solution: def maxPalindromes(self, s: str, k: int) -> int: n = len(s) res, last_r = 0, -1 def check(left, right): nonlocal res, last_r while left >= 0 and right < n and s[left] == s[right]: # overlap if left <= last_r: break # substring if right - left + 1 >= k: res += 1 last_r = right break left -= 1 right += 1 for i in range(n): check(i, i) check(i, i+1) return res ``` -- https://i.imgur.com/kyBhy6o.jpeg