HHR的小站
享受代码带来的快乐吧
首页
最新评论
使用滑动窗口算法解决一些问题
2021-02-05 |HHR | 代码使人快乐, LeetCode

使用滑动窗口算法解决一些问题

在Leetcode上做到了一道题

题目

给你两个长度相同的字符串,st

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;
    }
}
respond-post-504

添加新评论

请填写称呼
请填写合法的电子邮箱地址
请填写合法的网站地址
请填写内容