LeetCode 995 K連続ビットの最小反転回数HERODINGのLeetCodeの道

5893 ワード

LeetCode アルゴリズム lettecode c++ データ構造プログラム人生

0と1のみを含む配列Aでは、Kビット反転は、長さKの(連続)サブ配列を選択するとともに、サブ配列の各0を1に変更し、各1を0に変更することを含む.
配列に0の値を持つ要素がないように、必要なKビット反転の最小回数を返します.不可能な場合は、-1を返します.
例1:
入力:A=[0,1,0],K=1出力:2解釈:A[0]を反転してからA[2]を反転します.
例2:
入力:A=[1,1,0],K=2出力:-1解釈:サイズが2のサブ配列をどのように反転しても,配列を[1,1,1]に変えることはできない.
例3:
入力:A=[0,0,1,0,0,1,1,0],K=3出力:3解釈:反転A[0],A[1],A[2]:Aが[1,1,1,1,0,1,0]反転A[4],A[5],A[6]:Aが[1,1,1,1,1,1,0,0]反転A[5],A[7]:Aが[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
ヒント:

1 <= A.length <= 30000
1 <= K <= A.length

ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/minimum-number-of-k-consecutive-bit-flips著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
问题の考え方:この问题は公式の考え方を参考にして书いたもので、もちろん公式の考え方はあまり理解しにくいですが、ここで私は自分で理解する方法でみんなに解釈して、全体の考え方は贪欲で、今は1が反転しないで、0が反転して、最后まで、もし最后のK个数の范囲内に0があるならば、それは仕方がなくて、直接-1に戻って、毎回反転する前に反転した回数を統計しなければならないが、この回数は累積したものではない.例を挙げると、kが2で、最初の数が0で、2番目の数が1であれば、まず最初のK長配列を反転して[1,0]になり、このとき反転回数を統計するreverse数群が更新され、0+2位置の値-1が、ここから反転しないことを意味する.前のk範囲配列に対して1回の反転が少なく、このとき1を減算すると計算され、1回の反転ごとに現在の反転回数、すなわちcur++が更新されるので、要するに、i+k位置はタグに相当し、これからreverse[i+k]回の反転が少なくなることを示す.もちろんメモリの実行効率を高めるためにreverse配列を使わなくてもいいですが、どのようにマークしますか?これは問題に与えられたA配列を利用しなければならない.配列中の値の範囲は0または1であるため、A配列中の対応する位置の値を1より大きい値に更新すればマークとすることができる.詳細は問題解を参照し、コードは以下の通りである.

class Solution {
     
public:
    int minKBitFlips(vector<int> &A, int K) {
     
        int len = A.size();
        int count = 0;
        int cur = 0;
        //     
        vector<int> reverse(len + 1);
        for(int i = 0; i < len; i ++) {
     
            //         
            cur += reverse[i];
            //       
            if((cur + A[i]) % 2 == 0) {
     
                //     
                if(i + K > len) {
     
                    return -1;
                }
                count ++;
                cur ++;
                reverse[i + K] --;
            }
        }
        return count;
    }
};




/*  ：heroding
  ：https://leetcode-cn.com/problems/minimum-number-of-k-consecutive-bit-flips/solution/zui-xiang-xi-cti-jie-by-heroding-1c4p/
  ：  （LeetCode）
        。             ，          。*/

LeetCode 1370上昇下降文字列HERODINGのLeetCodeの道

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