這次的比賽和昨晚也差不多，不過第三題傻逼了，一個低階錯誤導致連錯了4次，然後就啥都就不回來了，看了一下國內排名大約被拉了100名吧，唉，要不肯定能進前5%的……
給出題目一的試題連結如下：
這次的第一題實在是不想多說什麼，難點完全在於理解題意，說白了就是所有的1事實上都要連在一起，然後只要有1個就算連續……
所以程式碼其實就很好寫，問題就是你題目是否能一次性理解了……
給出python程式碼實現如下：
class Solution:
def checkOnesSegment(self, s: str) -> bool:
res = 0
n = len(s)
cnt = 0
for c in s:
if c == '0':
if cnt > 0:
res += 1
cnt = 0
else:
cnt += 1
if cnt > 0:
res += 1
return res <= 1
提交程式碼評測得到：耗時28ms，佔用記憶體14MB。
給出題目二的試題連結如下：
這一題其實是我感覺的這次比賽當中最為簡單的一道題，只要先算出與目標的差值，然後儘可能快速地填充就行了。
由於能夠用於填充的數的絕對值有上限，因此事實上就是不斷地用最大值進行填充直至可以覆蓋就行了。
給出python程式碼實現如下：
class Solution:
def minElements(self, nums: List[int], limit: int, goal: int) -> int:
delta = abs(sum(nums) - goal)
return (delta-1) // limit + 1
提交程式碼評測得到：耗時724ms，佔用記憶體26.9MB。
給出題目三的試題連結如下：
這一題坦率地說思路上雖然感覺有點複雜，但是挺順利成章的，只可惜比賽的時候我犯了一個傻逼錯誤，然後就導致連錯了4次，真的是累感不愛，但是有一說一，確實還是挺直接的。
思路上而言，感覺就是：
其中，對於第一步，我們可以採用逐步遍歷的方式進行搜尋，而對於第二步，就是一個動態規劃的問題……
我們給出python程式碼實現如下：
class Solution:
def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:
MOD = 10**9 + 7
edgelist = {}
graph = defaultdict(set)
for u, v, d in edges:
graph[u].add(v)
graph[v].add(u)
u, v = (u, v) if u < v else (v, u)
if (u, v) not in edgelist:
edgelist[(u, v)] = d
else:
edgelist[(u, v)] = min(d, edgelist[(u, v)])
distance = [-1 for _ in range(n+1)]
q = [(0, n)]
while q:
dis, u = heapq.heappop(q)
if distance[u] != -1:
continue
distance[u] = dis
for v in graph[u]:
if distance[v] == -1:
uu, vv = (u, v) if u < v else (v, u)
heapq.heappush(q, (dis + edgelist[(uu, vv)], v))
@lru_cache(None)
def dp(u):
if u == n:
return 1
res = 0
for v in graph[u]:
if distance[v] < distance[u]:
res += dp(v) % MOD
return res % MOD
return dp(1)
提交程式碼評測得到：耗時1744ms，佔用記憶體63MB。
給出題目四的試題連結如下:
這一題現在想來其實感覺挺坑的，比賽的時候沒能做出來，然後賽後看了一下答案之後發現還是一樣的思路，然後重寫了一下之後這次就過了……
果然是比賽的時候腦子太亂了的關係吧，或許，大概……
話不多說，這道題核心就是在於想明白最終的答案一定滿足條件：
因此，事實上我們就是先將所有對k餘數相同的的陣列成一個集合進行考察，統計其中資料的分佈。
對於最終的答案，可以想見的是，他一定滿足：
因此，我們只要分別考察每一個餘數下的堆作為補充值的情況就可以了。
不過需要注意的是，由於對於某一個確定的餘數位置，它的可用候選值可能有多個（比如1和2的頻數均為3，那麼這個位置下的數即可以選1也可以選2），因此，我們可以使用一個迭代演演算法來處理這個問題。
借用快取機制，這就可以轉換為一個動態規劃的演演算法。
不過，即便如此，該演演算法還是會出現超時問題，因此，我們還需要對其來做一下剪枝。
給出最終的演演算法實現如下：
class Solution:
def minChanges(self, nums: List[int], k: int) -> int:
cnt = [defaultdict(int) for _ in range(k)]
for i, x in enumerate(nums):
cnt[i % k][x] += 1
def get_max(counter):
_max = max(counter.values())
return [x for x in counter if counter[x] == _max]
cand = [get_max(c) for c in cnt]
tot = sum([c[x[0]] for c, x in zip(cnt, cand)])
n = len(nums)
res = n-k+1
@lru_cache(None)
def dp(i, idx, s):
nonlocal res
if i == k:
if idx != -1:
res = min(res, n - (tot - cnt[idx][cand[idx][0]] + cnt[idx][s]))
# print(f"update res to {res}")
return
if idx == -1:
dp(i+1, i, s)
else:
if n - (tot - cnt[idx][cand[idx][0]]) >= res:
return
for c in cand[i]:
dp(i+1, idx, s^c)
return
dp(0, -1, 0)
return res
提交程式碼評測得到：耗時5792ms，佔用記憶體343.1MB。