0995 solved.

liuyubobobo · liuyubobobo · commit 78ce43cceb69 · 2019-02-18T18:21:02.000-08:00
diff --git a/0995-Minimum-Number-of-K-Consecutive-Bit-Flips/cpp-0995/CMakeLists.txt b/0995-Minimum-Number-of-K-Consecutive-Bit-Flips/cpp-0995/CMakeLists.txt
@@ -0,0 +1,6 @@
+cmake_minimum_required(VERSION 3.13)
+project(C)
+
+set(CMAKE_CXX_STANDARD 11)
+
+add_executable(C main2.cpp)
diff --git a/0995-Minimum-Number-of-K-Consecutive-Bit-Flips/cpp-0995/main.cpp b/0995-Minimum-Number-of-K-Consecutive-Bit-Flips/cpp-0995/main.cpp
@@ -0,0 +1,47 @@
+/// Source : https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/
+/// Author : liuyubobobo
+/// Time   : 2019-02-16
+
+#include <iostream>
+#include <vector>
+
+using namespace std;
+
+
+/// Greedy + Simulation
+/// Time Complexity: O((N - K) * K)
+/// Space Complexity: O(1)
+class Solution {
+public:
+    int minKBitFlips(vector<int>& A, int K) {
+
+        int res = 0;
+        for(int i = 0; i < A.size(); i ++)
+            if(A[i] == 0){
+                if(i + K > A.size()) return -1;
+
+                res ++;
+                for(int j = 0; j < K; j ++)
+                    A[i + j] = 1 - A[i + j];
+            }
+        return res;
+    }
+};
+
+
+int main() {
+
+    vector<int> A1 = {0,1,0};
+    cout << Solution().minKBitFlips(A1, 1) << endl;
+    // 2
+
+    vector<int> A2 = {1,1,0};
+    cout << Solution().minKBitFlips(A2, 2) << endl;
+    // -1
+
+    vector<int> A3 = {0,0,0,1,0,1,1,0};
+    cout << Solution().minKBitFlips(A3, 3) << endl;
+    // 3
+
+    return 0;
+}
diff --git a/0995-Minimum-Number-of-K-Consecutive-Bit-Flips/cpp-0995/main2.cpp b/0995-Minimum-Number-of-K-Consecutive-Bit-Flips/cpp-0995/main2.cpp
@@ -0,0 +1,56 @@
+/// Source : https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/
+/// Author : liuyubobobo
+/// Time   : 2019-02-18
+
+#include <iostream>
+#include <vector>
+
+using namespace std;
+
+
+/// Greedy + Events
+/// Record every closed event
+/// Time Complexity: O(N)
+/// Space Complexity: O(N)
+class Solution {
+public:
+    int minKBitFlips(vector<int>& A, int K) {
+
+        int res = 0;
+        vector<bool> event(A.size(), false);
+        int flip = 0;
+
+        for(int i = 0; i < A.size(); i ++){
+            if((A[i] && flip % 2) || (!A[i] && flip % 2 == 0)){
+
+                if(i + K - 1 >= A.size()) return -1;
+
+                res ++;
+
+                flip ++;
+                event[i + K - 1] = true;
+            }
+
+            if(event[i]) flip --;
+        }
+        return res;
+    }
+};
+
+
+int main() {
+
+    vector<int> A1 = {0,1,0};
+    cout << Solution().minKBitFlips(A1, 1) << endl;
+    // 2
+
+    vector<int> A2 = {1,1,0};
+    cout << Solution().minKBitFlips(A2, 2) << endl;
+    // -1
+
+    vector<int> A3 = {0,0,0,1,0,1,1,0};
+    cout << Solution().minKBitFlips(A3, 3) << endl;
+    // 3
+
+    return 0;
+}
diff --git a/readme.md b/readme.md
@@ -659,4 +659,5 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
 | 992 | [Subarrays with K Different Integers](https://leetcode.com/problems/subarrays-with-k-different-integers/) | [solution](https://leetcode.com/problems/subarrays-with-k-different-integers/solution/) | [C++](0992-Subarrays-with-K-Different-Integers/cpp-0992/) | | |
 | 993 | [Cousins in Binary Tree](https://leetcode.com/problems/cousins-in-binary-tree/) | [solution](https://leetcode.com/problems/cousins-in-binary-tree/solution/) | [C++](0993-Cousins-in-Binary-Tree/cpp-0993/) | | |
 | 994 | [Rotting Oranges](https://leetcode.com/problems/rotting-oranges/) | [solution](https://leetcode.com/problems/rotting-oranges/solution/) | [C++](0994-Rotting-Oranges/cpp-0994/) | | |
+| 995 | [Minimum Number of K Consecutive Bit Flips](https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/) | [solution](https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/solution/) | [C++](0995-Minimum-Number-of-K-Consecutive-Bit-Flips/cpp-0995/) | | |
 | | | | | | |
