C++에서 0으로 뒤집기

nums라는 정수 배열이 하나 있고 여기에는 0과 1이 포함되어 있다고 가정합니다. 숫자에서 인덱스 i를 선택하고 인덱스 i에서 요소를 뒤집고 i의 오른쪽에 있는 모든 숫자를 뒤집는 작업이 있다고 가정합니다. 숫자에 모두 0이 포함되도록 하는 데 필요한 최소 연산 수를 찾아야 합니다.

따라서 입력이 [1,0,1]과 같으면 출력은 3이 되고 인덱스 0에 대한 작업은 [0,1,0]으로 변환된 다음 인덱스 1에서 [ 0,0,1], 인덱스 2, [0,0,0].

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=숫자 크기
크기가 n인 배열 연산 정의
렛 :=0
initialize i :=0의 경우, i <숫자의 크기일 때 업데이트(i를 1만큼 증가), 수행 -
- i - 1>=0이면 -
  - 연산[i] :=연산[i] + 연산[i - 1]
- (nums[i] + op[i]) &1이 0이 아닌 경우 -
  - (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}