Lật sang Zeros trong C ++

Giả sử chúng ta có một mảng số nguyên được gọi là nums và mảng này chứa các số 0 và 1. Giả sử chúng ta có một phép toán trong đó chúng ta chọn một chỉ số i trong nums và lật phần tử ở chỉ mục i cũng như tất cả các số ở bên phải của i. Chúng tôi phải tìm số lượng thao tác tối thiểu cần thiết để tạo ra các số chứa tất cả các số 0.

Vì vậy, nếu đầu vào là [1,0,1], thì đầu ra sẽ là 3, hoạt động trên chỉ số 0, nó sẽ chuyển đổi [0,1,0], sau đó trên chỉ mục 1 [ 0,0,1], sau đó đến chỉ mục 2, [0,0,0].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

n:=kích thước của nums
Xác định op mảng có kích thước n
ret:=0
để khởi tạo i:=0, khi tôi
- nếu tôi - 1> =0, thì -
  - op [i]:=op [i] + op [i - 1]
- if (nums [i] + op [i]) &1 là khác 0, thì -
  - (tăng op [i] lên 1)
  - (tăng ret lên 1)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

{1,0,1}

Lật sang Zeros trong C ++

Ví dụ

Đầu vào

Đầu ra