推 SydLrio: 芋圓寶早安05/28 08:57
→ oin1104: 早安05/28 08:57
→ SydLrio: 我愛你05/28 08:58
※ 編輯: oin1104 (49.216.49.126 臺灣), 05/28/2024 09:01:19
推 orangeNoob: 大師 05/28 13:07
You are given two strings s and t of the same length and an integer maxCost.
You want to change s to t. Changing the ith character of s to ith character of t
costs |s[i] - t[i]| (i.e., the absolute difference between the ASCII values of
the characters).
Return the maximum length of a substring of s that can be changed to be the same
as the corresponding substring of t with a cost less than or equal to maxCost.
If there is no substring from s that can be changed to its corresponding substri
ng from t, return 0.
題目:
給你兩個字串 s跟t 還有maxCost
你可以更改每個字母的ascii值
但是更改總值不可以超過maxCost
問你最長的更改後相同子字串有多長
思路:
這種區間內求東西的
而且需要一直紀錄更改區間內的值
所以用sliding window 就很方便
```cpp
class Solution {
public:
int equalSubstring(string s, string t, int maxCost)
{
int res = 0;
int len = s.size();
vector<int> paper(len , 0);
for(int i = 0 ; i < len ; i ++)
{
paper[i] = abs(s[i]-t[i]);
}
int l = 0;
int r = 0;
int cn = 0;
for(r = 0 ; r < len ; r ++)
{
cn += paper[r];
while(cn > maxCost)
{
cn -= paper[l];
l ++;
}
res = max(r-l+1, res);
}
return res;
}
};
```
然後我res = max(r-l+1, res);
感覺可以放在while迴圈裡面
然後出迴圈了在檢查值
早起刷題身體好
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.49.126 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1716857817.A.DB8.html