พลิกเป็นศูนย์ใน C++

สมมติว่าเรามีอาร์เรย์จำนวนเต็มหนึ่งชุดที่เรียกว่า nums และประกอบด้วย 0s และ 1s สมมติว่าเรามีการดำเนินการที่เราเลือกดัชนี i เป็น nums และพลิกองค์ประกอบที่ดัชนี i รวมทั้งตัวเลขทั้งหมดทางด้านขวาของ i เราต้องหาจำนวนขั้นต่ำของการดำเนินการที่จำเป็นเพื่อให้ nums มีทั้งหมด 0s

ดังนั้น หากอินพุตเป็น [1,0,1] เอาต์พุตจะเป็น 3 การดำเนินการกับดัชนี 0 มันจะแปลง [0,1,0] จากนั้นในดัชนี 1 [ 0,0,1] จากนั้นดัชนี 2, [0,0,0].

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของ nums

• กำหนดอาร์เรย์ขนาด n

• ยกเลิก :=0

• สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดของ nums ให้อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ -

  • ถ้า i - 1>=0 แล้ว −

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

  • ถ้า (nums[i] + op[i]) &1 ไม่ใช่ศูนย์ ดังนั้น −

    • (เพิ่ม op[i] ขึ้น 1)

    • (เพิ่มการถอยกลับโดย 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