0795 solved.

liuyubobobo · liuyubobobo · commit 2e3ac03c542c · 2018-03-05T10:55:06.000-08:00
diff --git a/0795-Number-of-Subarrays-with-Bounded-Maximum/cpp-0795/CMakeLists.txt b/0795-Number-of-Subarrays-with-Bounded-Maximum/cpp-0795/CMakeLists.txt
@@ -0,0 +1,7 @@
+cmake_minimum_required(VERSION 3.5)
+project(cpp_0795)
+
+set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11")
+
+set(SOURCE_FILES main2.cpp)
+add_executable(cpp_0795 ${SOURCE_FILES})
diff --git a/0795-Number-of-Subarrays-with-Bounded-Maximum/cpp-0795/main.cpp b/0795-Number-of-Subarrays-with-Bounded-Maximum/cpp-0795/main.cpp
@@ -0,0 +1,90 @@
+/// Source : https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/description/
+/// Author : liuyubobobo
+/// Time   : 2018-03-05
+
+#include <iostream>
+#include <vector>
+
+using namespace std;
+
+
+/// Counting
+///
+/// Transform vector A into nums, which only includes elements 0, 1, 2
+/// which means elements in A: less than L; between L and R (includes); larger than R
+/// Then counting how many subarrays in only 01 subarray that include element 1
+/// Using all the subarray number for any 01 subarray MINUS
+/// all the subarray number for only 0 subarrays
+///
+/// Time Complexity: O(n)
+/// Space Complexity: O(n)
+class Solution {
+public:
+    int numSubarrayBoundedMax(vector<int>& A, int L, int R) {
+
+        vector<int> nums;
+        for(int a: A)
+            if(a < L)
+                nums.push_back(0);
+            else if(a > R)
+                nums.push_back(2);
+            else
+                nums.push_back(1);
+
+        // print_vec(nums, 0, nums.size());
+
+        int start = start_of_non(2, nums, 0);
+        int res = 0;
+        for(int i = start + 1 ; i <= nums.size() ; )
+            if(i == nums.size() || nums[i] == 2){
+                // print_vec(nums, start, i);
+                res += count(nums, start, i);
+                // cout << "res = " << res << endl;
+                start = start_of_non(2, nums, i);
+                i = start + 1;
+            }
+            else
+                i ++;
+        return res;
+    }
+
+private:
+    int count(const vector<int>& nums, int l, int r){
+
+        int res = (1 + r - l) * (r - l) / 2;
+        int start = start_of_non(1, nums, l);
+        for(int i = start + 1 ; i <= r ; )
+            if(i == r || nums[i] == 1){
+                res -= (1 + i - start) * (i - start) / 2;
+                start = start_of_non(1, nums, i);
+                i = start + 1;
+            }
+            else
+                i ++;
+        return res;
+    }
+
+    int start_of_non(int target, const vector<int>& nums, int start){
+        for(int i = start ; i < nums.size() ; i ++)
+            if(nums[i] != target)
+                return i;
+        return nums.size();
+    }
+
+    void print_vec(const vector<int>& vec, int l, int r){
+        for(int i = l ; i < r ; i ++)
+            cout << vec[i] << " ";
+        cout << endl;
+    }
+};
+
+int main() {
+
+//    vector<int> A1 = {2, 1, 4, 3};
+//    cout << Solution().numSubarrayBoundedMax(A1, 2, 3) << endl;
+
+    vector<int> A2 = {2, 9, 2, 5, 6};
+    cout << Solution().numSubarrayBoundedMax(A2, 2, 8) << endl;
+
+    return 0;
+}
diff --git a/0795-Number-of-Subarrays-with-Bounded-Maximum/cpp-0795/main2.cpp b/0795-Number-of-Subarrays-with-Bounded-Maximum/cpp-0795/main2.cpp
@@ -0,0 +1,48 @@
+/// Source : https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/description/
+/// Author : liuyubobobo
+/// Time   : 2018-03-05
+
+#include <iostream>
+#include <vector>
+
+using namespace std;
+
+
+/// Counting
+/// Using function count to calculate the subarray numbers of maximum <= bound
+///
+/// Time Complexity: O(n)
+/// Space Complexity: O(1)
+class Solution {
+public:
+    int numSubarrayBoundedMax(vector<int>& A, int L, int R) {
+
+        return count(A, R) - count(A, L - 1);
+    }
+
+private:
+    int count(const vector<int>& nums, int bound){
+
+        int res = 0;
+        int cur = 0;
+        for(int num: nums)
+            if(num <= bound){
+                cur ++;
+                res += cur;
+            }
+            else
+                cur = 0;
+        return res;
+    }
+};
+
+int main() {
+
+//    vector<int> A1 = {2, 1, 4, 3};
+//    cout << Solution().numSubarrayBoundedMax(A1, 2, 3) << endl;
+
+    vector<int> A2 = {2, 9, 2, 5, 6};
+    cout << Solution().numSubarrayBoundedMax(A2, 2, 8) << endl;
+
+    return 0;
+}
diff --git a/readme.md b/readme.md
@@ -256,6 +256,7 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
 | 792 | [Number of Matching Subsequences](https://leetcode.com/problems/number-of-matching-subsequences/description/) | [solution](https://leetcode.com/problems/number-of-matching-subsequences/solution/) | [C++](0792-Number-of-Matching-Subsequences/cpp-0792/) | | |
 | 793 | [Preimage Size of Factorial Zeroes Function](https://leetcode.com/problems/preimage-size-of-factorial-zeroes-function/description/) | [solution](https://leetcode.com/problems/preimage-size-of-factorial-zeroes-function/solution/) | [C++](0793-Preimage-Size-of-Factorial-Zeroes-Function/cpp-0793/) | | |
 | 794 | [Valid Tic-Tac-Toe State](https://leetcode.com/problems/valid-tic-tac-toe-state/description/) | [solution](https://leetcode.com/problems/valid-tic-tac-toe-state/solution/) | [C++](0794-Valid-Tic-Tac-Toe-State/cpp-0794/) | | |
+| 795 | [Number of Subarrays with Bounded Maximum](https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/description/) | [solution](https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/solution/)| [C++](0795-Number-of-Subarrays-with-Bounded-Maximum/cpp-0795/) | | |
 
 ---
 
