C++でゼロに反転

numsという整数配列が1つあり、これに0と1が含まれているとします。数値でインデックスiを選択し、インデックスiで要素を反転し、iの右側にあるすべての数値を反転する操作があるとします。 numにすべて0を含めるために必要な操作の最小数を見つける必要があります。

したがって、入力が[1,0,1]の場合、出力は3になり、インデックス0で操作され、[0,1,0]に変換され、次にインデックス1で[ 0,0,1]、次にインデックス2、[0,0,0]。

これを解決するには、次の手順に従います-

• n：=numsのサイズ

• サイズnの配列opを定義します

• ret：=0

• 初期化i：=0の場合、i

  • i --1> =0の場合、-

    • op [i]：=op [i] + op [i-1]

  • （nums [i] + op [i]）＆1がゼロ以外の場合、-

    • （op [i]を1増やします）

    • （retを1増やします）

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int solve(vector<int>& nums) {
      int n = nums.size();
      vector<int> op(n);
      int ret = 0;
      for (int i = 0; i < nums.size(); i++) {
         if (i - 1 >= 0) {
            op[i] += op[i - 1];
         }
         if ((nums[i] + op[i]) & 1) {
            op[i]++;
            ret++;
         }
      }
      return ret;
   }
};
main() {
   Solution ob;
   vector<int> v = {1,0,1};
   cout << (ob.solve(v));
}

入力

{1,0,1}

出力

3