LeetCode 1004最大連続1の個数III HERODINGのLeetCodeの道

4826 ワード

LeetCode アルゴリズム lettecode c++ スライドウィンドウデータ構造

いくつかの0と1からなる配列Aを与え,K個の値を最大0から1に変えることができる.
1のみを含む最長(連続)サブ配列の長さを返します.
例1:
入力:A=[1,1,1,0,0,0,0,1,1,1,1,0,K=2出力:6解釈:[1,1,1,1,0,1,1,1,1,1]太字数は0から1に反転し,最長のサブ配列長は6であった.
例2:
入力:A=[0,0,1,1,0,0,1,0,1,1,0,0,1,1,1,1,K=3出力:10解釈:[0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]太字数が0から1に反転し、最長のサブ配列長さが10となる.
ヒント:

1 <= A.length <= 20000
0 <= K <= A.length
A[i]   0   1

ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/max-consecutive-ones-iii著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
これは古典的なスライドウィンドウの問題で、ウィンドウの範囲内で、ウィンドウの中の0の個数がKを超えない限り、このウィンドウの長さは連続するサブ配列の条件に合致して、私達が探しているのは最も長いこの条件を満たすサブ配列で、だからまず私達は最大の長さを定義して、ウィンドウの左側、ウィンドウの右側、配列を遍歴する時、もし0に出会ったら、このとき、ウィンドウの0の個数がKより多い場合、ウィンドウの左側を移動し続け、ウィンドウの0の個数がK個以下になるまで移動し、最後に最大長を更新する.コードは次のとおりです.

class Solution {
     
public:
    int longestOnes(vector<int>& A, int K) {
     
        //       ，     ，     
        int max_len = K;
        int left = 0;
        int right = 0;
        while(right < A.size()) {
     
            //       0
            if(A[right] == 0) {
     
                K --;
            }
            //         
            while(K < 0) {
     
                K = K + 1 - A[left];
                left ++;
            }
            //       
            max_len = max(max_len, right - left + 1);
            //     
            right ++;
        }
        return max_len;
    }
};


/*  ：heroding
  ：https://leetcode-cn.com/problems/max-consecutive-ones-iii/solution/ji-bai-shuang-95zui-xiang-xi-csi-lu-by-h-sufl/
  ：  （LeetCode）
        。             ，          。*/

ORA-04091:テーブルXXが変化し、トリガー/関数が読めなくなった

小さい字の世代(c/c++)の本題は1つの巨大な家族の家譜を与えて、あなたに最小の世代のリストを与えてください.