LeetCode上尽可能使字符串相等,记录下解题思路
也同样是个滑动块的题目,假设为传入的是s = "abcd", t = "bcdf", cost = 3,可以通过charCodeAt
获得ASCII码,然后对比,可以得到如下表格
其实只要把题目理解成,在costnum是对应位置s转换为t的开销,那么有一个窗口,从0开始不断增加,就会有下面的过程([]内为当前窗口内的值)
完成窗口的移动
程序开始的时候, left=0/right=0,maxCost=3 currentCost=1
当前窗口: [1] 1 1 2
此时right还没到字符串的末尾,那么要currentCost += costnum[i]
,加完之后此时的currentCost<=maxCost
可以right++
窗口扩展,left=0/right=1,maxCost=3 currentCost=2
当前窗口: [1 1] 1 2
也是把当前costnum加入到currentCost中,并且currentCost<=maxCost
,窗口继续扩展
此时left=0/right=2,maxCost=3 currentCost=3
当前窗口: [1 1 1] 2
currentCost<=maxCost
还是成立,那么窗口还能扩展
此时left=0/right=3,maxCost=3 currentCost=5
当前窗口: [1 1 1 2]
此时currentCost > maxCost
,这次扩展之后窗口left需要右移,保证窗口内值的和小于maxCost
,将costnum[left]的值从currentCost内减去,并且left右移。这里会用一个while
循环,left不断右移,直到窗口内的值小于maxCost
每次移动的时候还需判断每次的窗口大小,都存储最大的那个,最后返回即为结果
var equalSubstring = function(s, t, maxCost) {
// 创建并生成对应的cost数组
let costnum = Array(s.length).fill(0)
costnum.map((x,i) => {
costnum[i] = Math.abs(s[i].charCodeAt() - t[i].charCodeAt())
})
// 定义初始窗口
let right = 0
let left = 0
// 用于记录窗口的最大值,即返回的结果
let max = 0
// 记录当前的cost
let currentCost = 0
console.log(costnum);
// 定义左右
// 从0开始扩展窗口
while(right < s.length) {
// 当右侧指针在字符串范围内进行循环
// 每次都把当前的cost加入到max中
currentCost += costnum[right]
while(currentCost > maxCost) {
// 如果当前的和比传入的最大cost大
// 那么窗口就要移动了
currentCost = currentCost - costnum[left]
left++
}
// 记录下当前的最大长度
max = Math.max(max,right - left + 1)
right++
}
return max
};