推 wwndbk: 大師 05/28 20:57
推 Smallsh: 大師 05/28 20:57
推 DJYOSHITAKA: 別捲了 05/28 21:01
推 orangeNoob: 別捲了 05/28 21:26
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