Re: [閒聊] 每日LeetCode
904. Fruit Into Baskets
題目就不附了，標準的 sliding window
class Solution {
public:
int totalFruit(vector<int>& fruits) {
unordered_map<int, int> M;
int n = fruits.size(), left = 0;
for (int i = 0; i < n; i++) {
M[fruits[i]] += 1;
if (M.size() > 2) {
M[fruits[left]] -= 1;
if (M[fruits[left]] == 0)
M.erase(fruits[left]);
left += 1;
}
}
return n - left;
}
想討論的是 sliding window 的形式，通常會看到兩種寫法
第一種是每次都一定縮到當下的最大合法 window 的，這種比較單純
第二種是每次最多只縮一格的，像上面寫的那樣
今天來練習證明看看上面的程式是對的
Claim: 每當程式跑到迴圈的 i < n 這裡時，下面的條件都會成立：
「僅考慮 fruits[0], ..., fruits[i-1] 時的答案會是 i - left」
在最開始 i = 0 時上式顯然成立
現在我們用歸納法證明，假設在 i = k 時都成立
我們希望證明經過一次迴圈後 i 變成 k + 1 時還是成立
在這一次迴圈 (i = k)，fruits[k] 進來了
根據前提，fruits[0], ..., fruits[k-1] 的答案是 k - left
此時有兩種可能
1. fruits[left], ..., fruits[k] 裡只有不到兩種水果
則目前的答案會是 k-left+1，也就是 fruits[left], ..., fruits[k]
不可能更大，因為 fruits[left-1], ..., fruits[k-1] 一定已經不合法了
否則上一輪的答案會 >= k-left+1，和我們歸納的前提不符
2. fuits[i], ..., fruits[k] 裡有超過兩種水果
則 fruits[k] 對答案沒有幫助，答案還是和上一輪一樣，也就是 k-left
在這個 case 時我們的程式會把 left 加一
因此，當程式執行完 i++ 後，i 變成 k + 1
在第一種情形，答案是 k-left+1，所以會等於 i-left
在第二種情形，答案是 k-(上一輪的left)，但因為我們在這種情形會把 left 加一
所以依舊會是 k-(這一輪的left-1) = k+1-left = i-left
因此，程式執行到 i < n 時我們的 Claim 永遠正確
最後 i 變成 n 時跳出迴圈，此時 i-left = n-left 就會是最終答案
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.175 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1675749455.A.E2C.html
→
02/07 13:58,
2年前
, 1F
02/07 13:58, 1F
推
02/07 14:58,
2年前
, 2F
02/07 14:58, 2F
討論串 (同標題文章)
完整討論串 (本文為第 222 之 719 篇)：