1004 solved.

liuyubobobo · liuyubobobo · commit 127a0711ec57 · 2019-03-03T13:29:42.000-08:00
diff --git a/1004-Max-Consecutive-Ones-III/cpp-1004/CMakeLists.txt b/1004-Max-Consecutive-Ones-III/cpp-1004/CMakeLists.txt
@@ -0,0 +1,6 @@
+cmake_minimum_required(VERSION 3.13)
+project(C)
+
+set(CMAKE_CXX_STANDARD 14)
+
+add_executable(C main.cpp)
diff --git a/1004-Max-Consecutive-Ones-III/cpp-1004/main.cpp b/1004-Max-Consecutive-Ones-III/cpp-1004/main.cpp
@@ -0,0 +1,56 @@
+/// Source : https://leetcode.com/problems/max-consecutive-ones-iii/
+/// Author : liuyubobobo
+/// Time   : 2019-03-02
+
+#include <iostream>
+#include <vector>
+
+using namespace std;
+
+
+/// Sliding Window
+/// Time Complexity: O(n)
+/// Space Complexity: O(1)
+class Solution {
+public:
+    int longestOnes(vector<int>& A, int K) {
+
+        int i = 0, j = -1, curK = 0, curLen = 0, best = 0;
+        while(j + 1 < A.size()){
+            if(A[j + 1] == 1)
+                curLen += 1,
+                j ++;
+            else{
+                // data[j + 1].first == 0
+                if(curK < K)
+                    curLen += 1,
+                    curK += 1,
+                    j ++;
+                else
+                    curLen -= 1,
+                    curK -= (A[i] == 0 ? 1 : 0),
+                    i ++;
+            }
+            best = max(best, curLen);
+        }
+        return best;
+    }
+};
+
+
+int main() {
+
+    vector<int> A1 = {1,1,1,0,0,0,1,1,1,1,0};
+    cout << Solution().longestOnes(A1, 2) << endl;
+    // 6
+
+    vector<int> A2 = {0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1};
+    cout << Solution().longestOnes(A2, 3) << endl;
+    // 10
+
+    vector<int> A3 = {1,0,0,0,1,1,0,0,1,1,0,0,0,0,0,0,1,1,1,1,0,1,0,1,1,1,1,1,1,0,1,0,1,0,0,1,1,0,1,1};
+    cout << Solution().longestOnes(A3, 8) << endl;
+    // 25
+
+    return 0;
+}
diff --git a/readme.md b/readme.md
@@ -668,4 +668,5 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
 | | | | | | |
 | 1002 | [Find Common Characters](https://leetcode.com/problems/find-common-characters/) | [无] | [C++](1002-Find-Common-Characters/cpp-1002/) | | |
 | 1003 | [Check If Word Is Valid After Substitutions](https://leetcode.com/problems/check-if-word-is-valid-after-substitutions/) | [无] | [C++](1003-Check-If-Word-Is-Valid-After-Substitutions/cpp-1003/) | | |
+| 1004 | [Max Consecutive Ones III](https://leetcode.com/problems/max-consecutive-ones-iii/) | [无] | [C++](1004-Max-Consecutive-Ones-III/cpp-1004/) | | |
 | | | | | | |
