Re: [閒聊] 每日leetcode
1208. Get Equal Substrings Within Budget
給兩個長度相同字串s、t以及一個整數maxCost
可以將把maxCost減去|s[i]-t[i]|把s[i]變成t[i]
請回傳經過上述操作後s、t每個元素都相同的最長子字串
思路:
用two pointer
start記錄子字串開始的位置
每次把maxCost扣掉|s[i]-t[i]|
當maxCost>=0時更新最大值
當maxCost<0時把maxCost加上|s[start]-t[start]|，並將start向前移
最後回傳答案
C code:
int equalSubstring(char* s, char* t, int maxCost) {
int n=strlen(s),start=0,ans=0;
for (int i=0;i<n;i++){
int diff=(int)(s[i])-(int)(t[i]);
maxCost-=abs(diff);
if (maxCost>=0){
ans=i-start+1;
}else{
int tmp=(int)(s[start])-(int)(t[start]);
maxCost+=abs(tmp);
start++;
}
}
return ans;
}
int abs(int i){
if (i>0){
return i;
}
return -i;
}
--
https://i.imgur.com/r9FBAGO.gif
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.164.176 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1716901010.A.CFD.html
推
05/28 20:57,
1年前
, 1F
05/28 20:57, 1F
推
05/28 20:57,
1年前
, 2F
05/28 20:57, 2F
推
05/28 21:01,
1年前
, 3F
05/28 21:01, 3F
推
05/28 21:26,
1年前
, 4F
05/28 21:26, 4F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 288 之 1548 篇)：