485. Max Consecutive Ones (最大連續 1 的個數)
更新於 發佈於 閱讀時間約 2 分鐘
↑看個小廣告，支持好內容↑
❶ Counter
想像我們拿著計數器，當看到 1 就按一下、看到 0 就歸零，計數器最高累積到多少，即代表陣列最長有連續出現過幾個 1，這蠻 make sense 的。
❷ Two Pointers
我們需要每按一下都去跟最大值比較嗎？其實不用。讓雙指針來幫我們判斷就行！
- 慢針：固定在起點
- 快針：一路往下檢查，碰到
0就停下來 - 結算兩針之間的距離，然後在下個起點會合
當快針 F 停下來時，它與慢針 S 的距離，即代表連續出現了幾項 1
如上圖，兩個指針會共同跑完一次迴圈，結算次數則減為 3 次。雙指針法在執行思路上蠻固定的，非常推薦用這題熟悉它！
參考程式碼：
var findMaxConsecutiveOnes = function(nums) {
let slow=fast=0;
let max=0;
while(fast<nums.length){
// 快針碰到 0 就停止
while(nums[fast]==1){
fast++
};
max=Math.max(fast-slow, max);
// 兩針於下個起點會合
fast++; slow=fast;
}
return max;
};
❸ 彩蛋加碼
這有點亂搞，如果我們用 0 把陣列分割開呢？(什麼？你還不知道 join 跟 split？)
// join: 把陣列各項，用符號連接起來
[1,0,1,1,0,1].join("") // "101101"
// split: 把文字內容，依符號切割開來
"101101".split("0") // ["1","11","1"]
陣列最大項的長度，不就是要輸出的答案了嗎？Magic ^^
- 本題分類標籤：
Array - 本題正解率＝
57.9％
❤️ 若內容對你實用，歡迎追蹤本專題，或小額贊助支持～
⭐ 這是我的第 14 篇刷題筆記，完整解題索引看這裡 → Here
留言0
查看全部
你可能也想看
Google News 追蹤
隨著理財資訊的普及，越來越多台灣人不再將資產侷限於台股，而是將視野拓展到國際市場。特別是美國市場，其豐富的理財選擇，讓不少人開始思考將資金配置於海外市場的可能性。
然而，要參與美國市場並不只是盲目跟隨標的這麼簡單，而是需要策略和方式，尤其對新手而言，除了選股以外還會遇到語言、開戶流程、Ap
嘿，大家新年快樂~ 新年大家都在做什麼呢？
跨年夜的我趕工製作某個外包設計案，在工作告一段落時趕上倒數。
然後和兩個小孩過了一個忙亂的元旦。在深夜時刻，看到朋友傳來的解籤網站，興致勃勃熬夜體驗了一下，覺得非常好玩，或許有人玩過了，但還是想寫上來分享紀錄一下~
題目敘述 149. Max Points on a Line
給定一串2維平面的點座標，請問最多有幾個點落在同一條直線上?
落在同一條直線也就是數學上所謂的"共線" colinear
題目敘述:
給定一個二維陣列的高與寬，並且給定起點位置座標。
請從起點位置開始順時針拜訪陣列元素，並且把沿路走過的座標記錄下來。
以陣列的形式返回答案。
題目敘述 Minimum Increment to Make Array Unique
給定一個整數陣列，每回合可以任意挑一個數字進行+1的加法操作。
請問最少需要多少次的+1加法操作，才能讓每個數字都相異?
給定兩個輸入整數陣列, 若在兩個陣列遇到相同的數字可以連成一線, 但是有規定連線不可和別的連線有交叉, 請問最多可以形成幾條連線? 解答中探討了演算法化簡的技巧和DP模型, 可以透過演算法化簡的技巧, 把這題映射到原本已經學會的Longest Common Subsequence的DP模型來解開。
題目敘述 Single Number II
給定一個輸入陣列，已知有一個烙單的數字，其他剩餘的數字都恰巧出現三次。
請找出這個烙單的數字。
題目額外提出限制，請使用O(n)線性時間、O(1)常數空間複雜度的演算法。
測試範例
Example 1:
Input: nums = [2,2,
題目敘述 Single Number III
給定一個輸入陣列，已知有兩個烙單的數字，其他剩餘的數字都恰巧出現兩次。
請找出這兩個烙單的數字。
題目額外提出限制，請使用O(n)線性時間、O(1)常數空間複雜度的演算法。
測試範例
Example 1:
Input: nums = [1,
題目敘述
題目會給我們一個鏈結串列的頭部結點Head node，要求我們計算鏈結串列中的Twin sum最大值是多少？
註: Twin Sum的定義就是頭尾結點相對位置相同的，互相配對加總在一起的值。
例如 給定串列= 1 -> 3 -> 2 -> 5 -> 100 -> 8
1, 8 一組
題目敘述
題目會給定一個二元陣列nums(也就是說，陣列元素只有0,1這兩種情況)。
我們必須從裡面選擇一個元素刪除之後，請問連續為1的最長子陣列的長度是多少?
測試範例
Example 1:
Input: nums = [1,1,0,1]
Output: 3
Explanation:
題目敘述
題目會給定一個二元陣列nums(也就是說，陣列元素只有0,1這兩種情況)和指定的k值。
我們最多可以把k個0反轉成1，請問連續唯一的最長子陣列的長度是多少?
題目的原文敘述
測試範例
Example 1:
Input: nums = [1,1,1,0,0,0,1,1,1,1,
隨著理財資訊的普及，越來越多台灣人不再將資產侷限於台股，而是將視野拓展到國際市場。特別是美國市場，其豐富的理財選擇，讓不少人開始思考將資金配置於海外市場的可能性。
然而，要參與美國市場並不只是盲目跟隨標的這麼簡單，而是需要策略和方式，尤其對新手而言，除了選股以外還會遇到語言、開戶流程、Ap
嘿，大家新年快樂~ 新年大家都在做什麼呢？
跨年夜的我趕工製作某個外包設計案，在工作告一段落時趕上倒數。
然後和兩個小孩過了一個忙亂的元旦。在深夜時刻，看到朋友傳來的解籤網站，興致勃勃熬夜體驗了一下，覺得非常好玩，或許有人玩過了，但還是想寫上來分享紀錄一下~
題目敘述 149. Max Points on a Line
給定一串2維平面的點座標，請問最多有幾個點落在同一條直線上?
落在同一條直線也就是數學上所謂的"共線" colinear
題目敘述:
給定一個二維陣列的高與寬，並且給定起點位置座標。
請從起點位置開始順時針拜訪陣列元素，並且把沿路走過的座標記錄下來。
以陣列的形式返回答案。
題目敘述 Minimum Increment to Make Array Unique
給定一個整數陣列，每回合可以任意挑一個數字進行+1的加法操作。
請問最少需要多少次的+1加法操作，才能讓每個數字都相異?
給定兩個輸入整數陣列, 若在兩個陣列遇到相同的數字可以連成一線, 但是有規定連線不可和別的連線有交叉, 請問最多可以形成幾條連線? 解答中探討了演算法化簡的技巧和DP模型, 可以透過演算法化簡的技巧, 把這題映射到原本已經學會的Longest Common Subsequence的DP模型來解開。
題目敘述 Single Number II
給定一個輸入陣列，已知有一個烙單的數字，其他剩餘的數字都恰巧出現三次。
請找出這個烙單的數字。
題目額外提出限制，請使用O(n)線性時間、O(1)常數空間複雜度的演算法。
測試範例
Example 1:
Input: nums = [2,2,
題目敘述 Single Number III
給定一個輸入陣列，已知有兩個烙單的數字，其他剩餘的數字都恰巧出現兩次。
請找出這兩個烙單的數字。
題目額外提出限制，請使用O(n)線性時間、O(1)常數空間複雜度的演算法。
測試範例
Example 1:
Input: nums = [1,
題目敘述
題目會給我們一個鏈結串列的頭部結點Head node，要求我們計算鏈結串列中的Twin sum最大值是多少？
註: Twin Sum的定義就是頭尾結點相對位置相同的，互相配對加總在一起的值。
例如 給定串列= 1 -> 3 -> 2 -> 5 -> 100 -> 8
1, 8 一組
題目敘述
題目會給定一個二元陣列nums(也就是說，陣列元素只有0,1這兩種情況)。
我們必須從裡面選擇一個元素刪除之後，請問連續為1的最長子陣列的長度是多少?
測試範例
Example 1:
Input: nums = [1,1,0,1]
Output: 3
Explanation:
題目敘述
題目會給定一個二元陣列nums(也就是說，陣列元素只有0,1這兩種情況)和指定的k值。
我們最多可以把k個0反轉成1，請問連續唯一的最長子陣列的長度是多少?
題目的原文敘述
測試範例
Example 1:
Input: nums = [1,1,1,0,0,0,1,1,1,1,