先給題
盡可能使字串相等
給你兩個長度相同的字串，s 和 t，
將 s 中的第 i 個字符變到 t 中的第 i 個字符需要 |s[i] - t[i]| 的開銷（開銷可能為 0），也就是兩個字符的 ASCII 碼值的差的絕對值，
用于變更字串的最大預算是 maxCost，在轉化字串時，總開銷應當小于等于該預算，這也意味著字串的轉化可能是不完全的，
如果你可以將 s 的子字串轉化為它在 t 中對應的子字串，則回傳可以轉化的最大長度，
如果 s 中沒有子字串可以轉化成 t 中對應的子字串，則回傳 0，
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/get-equal-substrings-within-budget
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
有興趣的可以先做一下
本人用的C++的代碼
1.首先先說暴力破解
（這是我的第一想法，很蠢，但還是要寫出來） 我首先想到的是從第一位開始，依次進行比較,超出最大則從記錄的地址(a)值下一位開始
class Solution {
public:
int equalSubstring(string s, string t, int maxCost) {
int sum = 0;
int min = 0, n = 0;//min 記錄最大的長度 n 記錄當前長度
int a = 0;//用來記錄地址
for (int i = 0; i < s.length(); i++) {
n++;
sum += abs((int)(s[i] - t[i]));
if (sum > maxCost) {
i = ++a;
n--;
min = n > min ? n : min;
n = 0;
sum = 0;
}
}
//如果字串最后一位正好達到max 還需要在進行一次比較
return (n > min ? n : min);
}
};
毫無疑問，暴力破解是超時的，那么接下來就得優化程序，我想的是讓地址值a的移動進行一些適當的改變，
在優化程序中，我看了一下題解，這時恍然大悟，可以轉換一下，轉換成自己做過的題目，
我們可以把s和t第i個字符ASCII 碼值的差的絕對值先算出來，存盤在一個陣列中，這樣問題就轉換成了最大子陣列問題（只不過加了一些限制，沒有負數和有最大上限），
演算法導論p38-p42 有對最大子陣列的描述，分治法和一個線性時間的演算法，（以此為參考來討論這個題）
可以觀看我的博客，我對最大子陣列問題也進行過分析，
2.說一下我對暴力的優化
這是我根據轉化后的陣列進行的一個修改，雖然通過了，但是時間還是很長，只能說勉強過了，我先解釋一下我的這個代碼，交代一下我的思路，然后再說我從其他博客以及題解中獲得的思想
class Solution {
public:
int equalSubstring(string s, string t, int maxCost) {
int length = s.length();
int* num = new int[length + 1];
for (int i = 1; i < length + 1; i++) {
num[i] = abs((int)(s[i - 1] - t[i - 1]));
cout << num[i] << " ";
}
int sum = 0, maxsum = 0;
int low = 0;
int maxlow = 0, maxhigh = 0;
for (int i = 1; i <= length; i++) {
sum += num[i];
while (sum > maxCost)
{
low++;
sum -= num[low];
}
if (((i - low) > (maxhigh - maxlow)))
{
maxhigh = i;
maxlow = low;
maxsum = sum;
}
}
return maxhigh - maxlow;
}
};
這是暴力破解的一個改良版，讓判定的sum值更少了一些（我忽略了本題想要解的東西，本題只想解出最大長度，而我卻一直在糾結最大子陣列是哪個）
我們直接舉例子來說明我的代碼吧
假設1 2 3 的總值是小于maxCost的 而 1 2 3 4的總值是大于maxCost的，那么接下來我們就要讓它減小到maxCost即讓low++ 縮減到2 3 4，判斷是否達到最小（等會看后面的講解這一步其實是沒必要回圈的）
如果長度大于我們記錄的最大長度，那么替換相應的值即可，
相比較暴力破解，我們省去了2 和 3 和 2 3 這樣的比較程序，
3.看題解了解了滑動視窗這樣的解法，
https://leetcode-cn.com/problems/get-equal-substrings-within-budget/solution/shuang-zhi-zhen-hua-dong-chuang-kou-by-c-3ktr/
https://leetcode-cn.com/problems/longest-repeating-character-replacement/solution/ti-huan-hou-de-zui-chang-zhong-fu-zi-fu-eaacp/
以上是參考
其實我的想法和答案很接近了，但唯一差出的就是判斷sum>maxCost時，我一直想要讓sum的值降下來，好求最大子陣列坐標，但本題并沒有讓你去求這個坐標，只需要知道長度即可，
那么改為if的話，如果大于maxCost low++ 我們所記錄的最大的長度是沒有改變的，只有當sum<=maxCost時，長度才會增加，所以我們沒必要讓sum始終<=maxCost，只要保證最后的是最大長度即可，
那么接下來修改代碼
int equalSubstring(string s, string t, int maxCost) {
int length = s.length();
int* num = new int[length + 1];
for (int i = 1; i < length + 1; i++) {
num[i] = abs((int)(s[i - 1] - t[i - 1]));
}
int sum = 0;
int low = 1;
int i = 1;
for (; i <= length; i++) {
sum += num[i];
if (sum > maxCost)
{
sum -= num[low];
low++;
}
}
return i - low;
}
這是修改后的代碼，耗時還是長，應該是開辟陣列的緣故，我們就不開辟陣列了，
int equalSubstring(string s, string t, int maxCost) {
int length = s.length();
int sum = 0;
int low = 0;
int i = 0;
for (; i < length; i++) {
sum += abs((int)(s[i] - t[i]));
if (sum > maxCost)
{
sum -= abs((int)(s[low] - t[low]));
low++;
}
}
return i - low;
}
速度與記憶體都得到了改善，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/257671.html
標籤：其他