feat(ml): cpp code

lucifer · lucifer · commit 8566ece32dc9 · 2021-01-18T17:12:02.000+08:00
diff --git a/problems/80.remove-duplicates-from-sorted-array-ii.md b/problems/80.remove-duplicates-from-sorted-array-ii.md
@@ -84,7 +84,7 @@ for (int i = 0; i < len; i++) {
 
 ## 代码
 
-代码支持： Python
+代码支持： Python, CPP
 
 Python Code：
 
@@ -101,6 +101,21 @@ class Solution:
         return i
 ```
 
+CPP Code:
+
+```cpp
+class Solution {
+public:
+    int removeDuplicates(vector<int>& A) {
+        int j = 0;
+        for (int i = 0; i < A.size(); ++i) {
+            if (j - 2 < 0 || A[j - 2] != A[i]) A[j++] = A[i];
+        }
+        return j;
+    }
+};
+```
+
 **复杂度分析**
 
 - 时间复杂度：$$O(N)$$
@@ -120,8 +135,6 @@ class Solution:
 
 ![](https://tva1.sinaimg.cn/large/007S8ZIlly1ghlu0vrcvlj318c0se0wm.jpg)
 
-
-
 大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
 ![](https://tva1.sinaimg.cn/large/007S8ZIlly1gfcuzagjalj30p00dwabs.jpg)
diff --git a/problems/84.largest-rectangle-in-histogram.md b/problems/84.largest-rectangle-in-histogram.md
@@ -14,7 +14,6 @@ https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
 
 ![](https://tva1.sinaimg.cn/large/007S8ZIlly1ghltx9kgd2j305805oa9z.jpg)
 
-
 图中阴影部分为所能勾勒出的最大矩形面积，其面积为  10  个单位。
 
 ```
@@ -152,6 +151,10 @@ class Solution:
 
 ### 代码
 
+代码支持： Python,CPP
+
+Python Code:
+
 ```python
 class Solution:
     def largestRectangleArea(self, heights: List[int]) -> int:
@@ -163,6 +166,29 @@ class Solution:
         return ans
 ```
 
+CPP Code:
+
+```cpp
+class Solution {
+public:
+    int largestRectangleArea(vector<int>& A) {
+        A.push_back(0);
+        int N = A.size(), ans = 0;
+        stack<int> s;
+        for (int i = 0; i < N; ++i) {
+            while (s.size() && A[s.top()] >= A[i]) {
+                int h = A[s.top()];
+                s.pop();
+                int j = s.size() ? s.top() : -1;
+                ans = max(ans, h * (i - j - 1));
+            }
+            s.push(i);
+        }
+        return ans;
+    }
+};
+```
+
 **复杂度分析**
 
 - 时间复杂度：$$O(N)$$
diff --git a/problems/85.maximal-rectangle.md b/problems/85.maximal-rectangle.md
@@ -57,6 +57,10 @@ https://leetcode-cn.com/problems/maximal-rectangle/
 
 ## 代码
 
+代码支持：Python, CPP
+
+Python Code:
+
 ```python
 class Solution:
     def largestRectangleArea(self, heights: List[int]) -> int:
@@ -84,6 +88,39 @@ class Solution:
 
 ```
 
+CPP Code:
+
+```cpp
+class Solution {
+public:
+    int maximalRectangle(vector<vector<char>>& A) {
+        if (A.empty() || A[0].empty()) return 0;
+        int ans = 0, M = A.size(), N = A[0].size();
+        vector<int> left(N, 0), right(N, N), height(N, 0);
+        for (int i = 0; i < M; ++i) {
+            int curLeft = 0, curRight = N;
+            for (int j = 0; j < N; ++j) height[j] = A[i][j] == '1' ? height[j] + 1 : 0;
+            for (int j = 0; j < N; ++j) {
+                if (A[i][j] == '1') left[j] = max(left[j], curLeft);
+                else {
+                    left[j] = 0;
+                    curLeft = j + 1;
+                }
+            }
+            for (int j = N - 1; j >= 0; --j) {
+                if (A[i][j] == '1') right[j] = min(right[j], curRight);
+                else {
+                    right[j] = N;
+                    curRight = j;
+                }
+            }
+            for (int j = 0; j < N; ++j) ans = max(ans, (right[j] - left[j]) * height[j]);
+        }
+        return ans;
+    }
+};
+```
+
 **复杂度分析**
 
 - 时间复杂度：$$O(M * N)$$
diff --git a/problems/86.partition-list.md b/problems/86.partition-list.md
@@ -52,7 +52,7 @@ https://leetcode-cn.com/problems/partition-list/
 
 ## 代码
 
-- 语言支持: Javascript，Python3
+- 语言支持: Javascript，Python3, CPP
 
 ```js
 /**
@@ -129,6 +129,31 @@ class Solution:
         return first_node.next
 ```
 
+CPP Code:
+
+```cpp
+class Solution {
+public:
+    ListNode* partition(ListNode* head, int x) {
+        ListNode dummy, geHead, *ltTail = &dummy, *geTail = &geHead;
+        while (head) {
+            auto p = head;
+            head = head->next;
+            if (p->val < x) {
+                ltTail->next = p;
+                ltTail = p;
+            } else {
+                geTail->next = p;
+                geTail = p;
+            }
+        }
+        ltTail->next = geHead.next;
+        geTail->next = NULL;
+        return dummy.next;
+    }
+};
+```
+
 **复杂度分析**
 
 - 时间复杂度：$$O(N)$$
