Re: [閒聊] 每日leetcode已回收
看板Marginalman作者sustainer123 (caster )時間1年前 (2024/05/28 13:21)推噓3(3推 0噓 1→)留言4則, 4人參與討論串287/1548 (看更多)
※ 引述《oin1104 (是oin的說)》之銘言：
: 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;
: }
: };
思路:
sliding window 差值<=maxcost right往前並更新結果 反之 left往前
把left的差值加回去
Python Code:
class Solution:
def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
left = 0
right = 0
res = 0
while right < len(s):
d = abs(ord(s[right]) - ord(t[right]))
if d > maxCost:
maxCost += abs(ord(s[left]) - ord(t[left]))
left += 1
else:
right += 1
maxCost -= d
res = max(right - left,res)
return res
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.43.162.199 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1716873671.A.1FC.html
推
05/28 13:21,
1年前
, 1F
05/28 13:21, 1F
推
05/28 13:21,
1年前
, 2F
05/28 13:21, 2F
推
05/28 13:29,
1年前
, 3F
05/28 13:29, 3F
→
05/28 13:32,
1年前
, 4F
05/28 13:32, 4F
討論串 (同標題文章)