文章
问答
冒泡
LeetCode 每日一题

尽可能使字符串相等

image.png

思路

初次看到此题的描述,最直观的感受就是嵌套两层循环,进行字符比较ASCII码值的比较,同时与最大子字符串长度进行比较。
那么其实剥开此层皮,实际上我们可以发现本质就是通过一个int 数组来存放每个索引的字符串ASCII码的差值的绝对值,然后简化为对一个int数组,求连续元素和为target值的最大区间长度。很欣慰的是官方解法的双指针也是这么做的,嗨皮😨,最终简化为比如 数组
[1,2,2,3,3],target 为7,那么匹配的最长子区间为[2,2,3]长度为3
那么最终还是通过双指针来实现

代码实现

class Solution {
    public int equalSubstring(String s, String t, int maxCost) {
        int ans = 0, sum=0;
        int len = s.length();
        int left=0,right=0;
        if(len==0) return ans;
        int[] diff = new int[len];  // 此处就是通过int 数组存放对应索引位置的字符ascii差值的绝对值
        for(int i=0;i<len;i++){
            diff[i]=Math.abs(s.charAt(i)-t.charAt(i));
        }
        while(right<len){
            sum += diff[right];
            while (sum > maxCost) { //此处是通过 while 包一层循环,而不是if语句
                sum -= diff[left];
                left++;
            }
            ans = Math.max(ans, right - left + 1);
            right++;
            }

        return ans; 
    }
}
数据结构与算法

关于作者

Kirago
个人站点 https://kiragoo.github.io/
获得点赞
文章被阅读