算法題:給定正整數(shù)數(shù)組和正整數(shù)k民镜。數(shù)組中只含有0或1啡专,可以最多k次將0翻轉(zhuǎn)成1。求數(shù)組中最長連續(xù)1的長度制圈。
以下是該段JavaScript代碼的解題思路:
解題思路:
1植旧、初始化參數(shù):
· 初始化左邊界left和右邊界right,均指向數(shù)組的第一個(gè)元素离唐。
· 初始化zeros病附,用于記錄當(dāng)前窗口內(nèi)0的個(gè)數(shù)。
· 初始化maxLength亥鬓,用于記錄最長連續(xù)1的長度完沪。
2、遍歷數(shù)組:
· 使用while循環(huán)遍歷數(shù)組嵌戈,直到右邊界right到達(dá)數(shù)組的末尾覆积。
3、處理右邊界:
· 每次循環(huán)熟呛,檢查右邊界對(duì)應(yīng)的元素是否為0宽档。如果是,則zeros增加1庵朝。
4吗冤、調(diào)整窗口大小:
· 如果zeros的數(shù)量超過了k(即允許翻轉(zhuǎn)的0的最大數(shù)量)九府,則需要縮小窗口椎瘟,以去除多余的0。
· 使用內(nèi)部的while循環(huán)侄旬,逐步移動(dòng)左邊界left肺蔚,直到zeros的數(shù)量減少到k或以下。
· 在移動(dòng)左邊界的過程中儡羔,如果左邊界對(duì)應(yīng)的元素是0宣羊,則zeros減少1。
5汰蜘、更新最長連續(xù)1的長度:
· 在每次循環(huán)中仇冯,計(jì)算當(dāng)前窗口的大小(right - left + 1)鉴扫,并與之前記錄的最長連續(xù)1的長度maxLength比較赞枕。
· 如果當(dāng)前窗口大小更大,則更新maxLength坪创。
6炕婶、移動(dòng)右邊界:
· 在每次循環(huán)的末尾,右邊界right向右移動(dòng)一位莱预,以處理下一個(gè)數(shù)組元素柠掂。
7、返回結(jié)果:
· 當(dāng)右邊界right遍歷完整個(gè)數(shù)組后依沮,返回最長連續(xù)1的長度maxLength涯贞。
這個(gè)解題思路的核心是利用滑動(dòng)窗口技巧來動(dòng)態(tài)地調(diào)整窗口的大小,使得窗口內(nèi)0的個(gè)數(shù)不超過k危喉,從而找到最長連續(xù)1的長度宋渔。通過不斷移動(dòng)窗口的左右邊界,算法能夠在一次遍歷中有效地解決問題辜限。
javascript解題參考代碼:
//javascript
function longestOnes(nums, k) {
let left = 0; // 滑動(dòng)窗口左邊界
let right = 0; // 滑動(dòng)窗口右邊界
let zeros = 0; // 窗口內(nèi)0的個(gè)數(shù)
let maxLength = 0; // 最長連續(xù)1的長度
while (right < nums.length) {
// 如果當(dāng)前數(shù)字是0皇拣,則增加0的計(jì)數(shù)
if (nums[right] === 0) {
zeros++;
}
// 如果0的個(gè)數(shù)超過了k,則需要收縮窗口左邊界
while (zeros > k) {
// 如果左邊界的數(shù)字是0薄嫡,則減少0的計(jì)數(shù)
if (nums[left] === 0) {
zeros--;
}
// 左邊界向右移動(dòng)
left++;
}
// 更新最長連續(xù)1的長度
maxLength = Math.max(maxLength, right - left + 1);
// 右邊界向右移動(dòng)
right++;
}
return maxLength;
}
// 測試
const nums = [1, 0, 0, 1, 1, 0, 1, 1, 0, 1];
const k = 2;
const result = longestOnes(nums, k);
console.log("最長連續(xù)1的長度為:", result);
這段代碼定義了一個(gè)longestOnes函數(shù)氧急,它接收一個(gè)只包含0和1的數(shù)組nums以及一個(gè)正整數(shù)k作為參數(shù)。函數(shù)內(nèi)部使用滑動(dòng)窗口技巧來遍歷數(shù)組毫深,并維護(hù)一個(gè)窗口吩坝,其中最多包含k個(gè)0。當(dāng)0的個(gè)數(shù)超過k時(shí)哑蔫,窗口的左邊界會(huì)向右移動(dòng)钉寝,直到0的個(gè)數(shù)減少到k或以下。在此過程中闸迷,函數(shù)記錄并更新最長連續(xù)1的長度瘩蚪。最后,函數(shù)返回這個(gè)長度稿黍。
在測試部分疹瘦,我們創(chuàng)建了一個(gè)示例數(shù)組nums并設(shè)置了k的值為2,然后調(diào)用longestOnes函數(shù)并打印結(jié)果巡球。