学习内容

滑动窗口LeeCodeJava

1208.尽可能使字符串相等

我的代码

class Solution {
    public int equalSubstring(String s, String t, int maxCost) {
        int res=0;
        int left=0;
        int right;
        int count=0;
        for (right = 0; right < t.length(); right++) {
            int def=calculateTheDifference(s.charAt(right),t.charAt(right));
            maxCost-=def;
            if(def<=maxCost){
                count++;
            }else{
                if(count>res){
                    res=count;
                }
                count++;
                while(maxCost<0){
                    maxCost+=calculateTheDifference(s.charAt(left),t.charAt(left));
                    left++;
                    count--;
                }
            }
        }
        if(count>res){
            res=count;
        }
        return res;
    }
    int calculateTheDifference(int a,int b){
        return Math.abs(a-b);
    }
}

思路:

使用滑动窗口的思想,使用双指针的方法,右指针一查到底,左指针会当maxCount处于负数的时候,则将左指针向右移动,缩小窗口,直到MaxCount重新达到0以上(即合法).随后,当窗口再次合法后稳定了.计算窗口的大小,如果窗口的大小,超过了目前已知的最大的窗口大小,就刷新窗口的最大值.不要忘记,在最后尝试刷新一下最大窗口的大小.

优解大小

class Solution {
    public int equalSubstring(String s, String t, int maxCost) {
        int n = s.length();
        int[] diff = new int[n];
        for (int i = 0; i < n; i++) {
            diff[i] = Math.abs(s.charAt(i) - t.charAt(i));
        }
        int maxLength = 0;
        int start = 0, end = 0;
        int sum = 0;
        while (end < n) {
            sum += diff[end];
            while (sum > maxCost) {
                sum -= diff[start];
                start++;
            }
            maxLength = Math.max(maxLength, end - start + 1);
            end++;
        }
        return maxLength;
    }
}

心得

1.如果要计算的话,可以把循环里面的给拆开来,就比如这里的循环中每个位置都需要计算一下,可以用一个循环来单独计算一下.
2.在这个循环中省略了count的技术,减少了循环的计算.进而减少运算时间.
3.思路差不多,以这个为主.