使用滑动窗口算法解决一些问题
在Leetcode上做到了一道题。
题目
给你两个长度相同的字符串,s
和 t
。
将 s
中的第 i
个字符变到 t
中的第 i
个字符需要 |s[i] - t[i]|
的开销(开销可能为 0),也就是两个字符的 ASCII 码值的差的绝对值。
用于变更字符串的最大预算是 maxCost
。在转化字符串时,总开销应当小于等于该预算,这也意味着字符串的转化可能是不完全的。
如果你可以将 s
的子字符串转化为它在 t
中对应的子字符串,则返回可以转化的最大长度。
如果 s
中没有子字符串可以转化成 t
中对应的子字符串,则返回 0。
解答
删去其中繁杂的题干,题意大概是从一个自然数串中,找出最长的和小于 maxCost
的串。此题可以用滑动窗口的思路解决。
滑动窗口
定义一个左指针 leftPtr
,一个右指针 rightPtr
,开始时将两个指针都置于最左边。右侧指针每次向右移动一格,判断左指针所处的位置是否符合题意。如果不符合,将其向右移动,直到符合题意为止。存储最大的符合题意的距离,即为答案。
简单说来,可以理解成右指针拉着左指针向右动,它们之间用一根线(maxCost
)相连。如果线足够长(rightPtr - leftPtr <= maxCost
),左指针就不会动,否则它也会跟着向右移。
代码
class Solution {
public int equalSubstring(String s, String t, int maxCost) {
int length = s.length();
int[] cost = new int[length];
for (int i = 0; i < length; i++) {
cost[i] = Math.abs(s.charAt(i) - t.charAt(i));
}
int rightPtr = 0, leftPtr = 0, max = 0, nowCost = 0;
while (rightPtr < length) {
nowCost += cost[rightPtr];
while (nowCost > maxCost) {
nowCost -= cost[leftPtr];
leftPtr++;
}
if (rightPtr - leftPtr + 1 > max) {
max = rightPtr - leftPtr + 1;
}
rightPtr++;
}
return max;
}
}