盡可能使字串相等
給你兩個長度相同的字串，s 和 t，
將 s 中的第 i 個字符變到 t 中的第 i 個字符需要 |s[i] - t[i]| 的開銷（開銷可能為 0），也就是兩個字符的 ASCII 碼值的差的絕對值，
用于變更字串的最大預算是 maxCost，在轉化字串時，總開銷應當小于等于該預算，這也意味著字串的轉化可能是不完全的，
如果你可以將 s 的子字串轉化為它在 t 中對應的子字串，則回傳可以轉化的最大長度，
如果 s 中沒有子字串可以轉化成 t 中對應的子字串，則回傳 0，
示例 1：
輸入：s = “abcd”, t = “bcdf”, cost = 3
輸出：3
解釋：s 中的 “abc” 可以變為 “bcd”，開銷為 3，所以最大長度為 3，
示例 2：
輸入：s = “abcd”, t = “cdef”, cost = 3
輸出：1
解釋：s 中的任一字符要想變成 t 中對應的字符，其開銷都是 2，因此，最大長度為 1，
示例 3：
輸入：s = “abcd”, t = “acde”, cost = 0
輸出：1
解釋：你無法作出任何改動，所以最大長度為 1，
解題思路
設字串 s 和 t 的長度均為n，把 s 中第 i 個元素轉換成 t 中的第 i 個元素，所需要花費的開銷為兩者 ASCII 碼之差的絕對值，即 |s[i] - t[i]| ，
以示例1為例，其中s = “abcd”, t = “bcdf”, cost = 3，當 i = 0時，a -> b 所需要的開銷為1；當 i = 1時，b -> c 所需要的開銷為1，以此類推，最后會得到一個與兩個字串等長的花銷陣列，記為costs = [1, 1, 1, 2] ，題中給出 maxCost = 3，則最多允許其前面三個字符進行轉換，
則題目等價為：已知一個 costs陣列 ，求：和不超過 maxCost 時最長的連續子陣列的長度，
在求子區間問題時，最常用的方法就是滑動視窗
對于滑動視窗指標移動的解釋有好多，我覺得這個更加容易理解：滑動視窗中用到了左右兩個指標，它們移動的思路是：以右指標作為驅動，拖著左指標向前走，右指標每次只移動一步，而左指標在內部 while 回圈中每次可能移動多步，右指標是主動前移，探索未知的新區域；左指標是被迫移動，負責尋找滿足題意的區間，
鏈接：[https://leetcode-cn.com/problems/get-equal-substrings-within-budget/solution/fen-xiang-zhen-cang-de-hua-dong-chuang-k-e3rd/]
代碼
class Solution {
public int equalSubstring(String s, String t, int maxCost) {
int n = s.length();
int[] costs = new int[n];
for (int i=0;i<n;i++) {
costs[i] = Math.abs(s.charAt(i) - t.charAt(i));
}
//滑動視窗(求子區間問題)
int left, right;//雙指標，表示當前遍歷的區間[left, right]
//sums用來統計該區間內所有字符對應轉換所需要的開銷.res保存最大的滿足題目要求的子串的長度
int res, sums;
left = right = res = sums = 0;
//當右側還有元素時---沒到陣列的結尾
while (right < n) {
sums += costs[right];
while (sums > maxCost) {
sums -= costs[left];
left++;//指標右移
}
//right - left + 1為當前區間長度
res = Math.max(res, right - left + 1);
right++;//指標右移
}
return res;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/257478.html
標籤：其他
下一篇：寒假學習——ES6（4）