feat(ml): cpp

lucifer · lucifer · commit 291f61a4d1ca · 2021-02-08T18:30:08.000+08:00
diff --git a/problems/142.Linked-List-Cycle-II.md b/problems/142.Linked-List-Cycle-II.md
@@ -111,7 +111,7 @@ return fast
 
 ### 代码
 
-- 语言支持: JS, Go, PHP
+- 语言支持: JS, Go, PHP, CPP
 
 JS Code：
 
@@ -209,6 +209,28 @@ class Solution
 }
 ```
 
+CPP Code:
+
+```cpp
+class Solution {
+public:
+    ListNode *detectCycle(ListNode *head) {
+        if (!head) return NULL;
+        auto p = head, q = head;
+        while (p && p->next) {
+            p = p->next->next;
+            q = q->next;
+            if (p == q) break;
+        }
+        if (!p || !p->next) return NULL;
+        p = head;
+        for (; p != q; p = p->next, q = q->next);
+        return p;
+    }
+};
+
+```
+
 **复杂度分析**
 
 - 时间复杂度：$O(N)$
diff --git a/problems/145.binary-tree-postorder-traversal.md b/problems/145.binary-tree-postorder-traversal.md
@@ -62,6 +62,10 @@ https://leetcode-cn.com/problems/binary-tree-postorder-traversal/
 
 ## 代码
 
+代码支持：JS, CPP
+
+JS Code:
+
 ```js
 /**
  * Definition for a binary tree node.
@@ -111,6 +115,33 @@ var postorderTraversal = function (root) {
 };
 ```
 
+CPP Code:
+
+```cpp
+class Solution {
+public:
+    vector<int> postorderTraversal(TreeNode* root) {
+        vector<int> ans;
+        stack<TreeNode*> s;
+        TreeNode *prev = NULL;
+        while (root || s.size()) {
+            while (root) {
+                s.push(root);
+                root = root->left;
+            }
+            root = s.top();
+            if (!root->right || root->right == prev) {
+                ans.push_back(root->val);
+                s.pop();
+                prev = root;
+                root = NULL;
+            } else root = root->right;
+        }
+        return ans;
+    }
+};
+```
+
 **复杂度分析**
 
 - 时间复杂度：$O(N)$
diff --git a/problems/146.lru-cache.md b/problems/146.lru-cache.md
@@ -36,7 +36,7 @@ lRUCache.get(3);    // 返回 3
 lRUCache.get(4);    // 返回 4
 ```
 
-### 思路: 哈希法
+### 思路
 
 1. 确定需要使用的数据结构
    1. 根据题目要求,存储的数据需要保证顺序关系(逻辑层面) ===> 使用数组,链表等保证顺序关系
@@ -66,7 +66,7 @@ lRUCache.get(4);    // 返回 4
       2. 返回该节点的值
    2. 节点不存在, 返回 null
 
-- 伪代码
+伪代码如下：
 
 ```js
 var LRUCache = function(capacity) {
@@ -103,7 +103,9 @@ function put (key, value) {
 };
 ```
 
-- 语言支持: JS, Go, PHP
+## 代码
+
+语言支持: JS, Go, PHP, CPP
 
 JS Code:
 
@@ -375,6 +377,38 @@ class DoubleList
 }
 ```
 
+CPP Code:
+
+```cpp
+class LRUCache {
+private:
+  list<pair<int, int>> data;
+  unordered_map<int, list<pair<int, int>>::iterator> m;
+  int capacity;
+public:
+  LRUCache(int capacity) : capacity(capacity) {}
+
+  int get(int key) {
+    if (!m.count(key)) return -1;
+    data.splice(data.begin(), data, m[key]);
+    m[key] = data.begin();
+    return data.front().second;
+  }
+
+  void put(int key, int value) {
+    if (get(key) == -1) {
+      if (data.size() == capacity) {
+        auto p = data.back();
+        m.erase(p.first);
+        data.pop_back();
+      }
+      data.emplace_front(key, value);
+      m[key] = data.begin();
+    } else data.front().second = value;
+  }
+};
+```
+
 **复杂度分析**
 
 - 时间复杂度：$O(1)$
diff --git a/problems/147.insertion-sort-list.md b/problems/147.insertion-sort-list.md
@@ -147,7 +147,7 @@ class Solution:
 
 ## 代码
 
-代码支持：Python3，Java，JS
+代码支持：Python3，Java，JS, CPP
 
 Python Code:
 
@@ -209,6 +209,26 @@ var insertionSortList = function (head) {
 };
 ```
 
+CPP Code:
+
+```cpp
+class Solution {
+public:
+    ListNode* insertionSortList(ListNode* head) {
+        ListNode dummy, *p;
+        while (head) {
+            auto *n = head;
+            head = head->next;
+            p = &dummy;
+            while (p->next && p->next->val < n->val) p = p->next;
+            n->next = p->next;
+            p->next = n;
+        }
+        return dummy.next;
+    }
+};
+```
+
 **复杂度分析**
 
 - 时间复杂度：$O(N^2)$，其中 N 为链表长度。
diff --git a/problems/150.evaluate-reverse-polish-notation.md b/problems/150.evaluate-reverse-polish-notation.md
@@ -1,6 +1,5 @@
-
-
 ## 题目地址(150. 逆波兰表达式求值)
+
 https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/
 
 ## 题目描述
@@ -32,7 +31,7 @@ https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/
 
 输入: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
 输出: 22
-解释: 
+解释:
 该算式转化为常见的中缀算术表达式为：
   ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
 = ((10 * (6 / (12 * -11))) + 17) + 5
@@ -66,11 +65,12 @@ https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/
 - 腾讯
 
 ## 思路
+
 逆波兰表达式又叫做后缀表达式。在通常的表达式中，二元运算符总是置于与之相关的两个运算对象之间，这种表示法也称为`中缀表示`。
 
-波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法，按此方法，每一运算符都置于其运算对象之后，故称为`后缀表示`。
+波兰逻辑学家 J.Lukasiewicz 于 1929 年提出了另一种表示表达式的方法，按此方法，每一运算符都置于其运算对象之后，故称为`后缀表示`。
 
-> 逆波兰表达式是一种十分有用的表达式，它将复杂表达式转换为可以依靠简单的操作得到计算结果的表达式。例如(a+b)*(c+d)转换为ab+cd+*
+> 逆波兰表达式是一种十分有用的表达式，它将复杂表达式转换为可以依靠简单的操作得到计算结果的表达式。例如(a+b)_(c+d)转换为 ab+cd+_
 
 思路就是：
 
@@ -84,15 +84,15 @@ https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/
 
 1. 栈的基本用法
 
-2. 如果你用的是JS的话，需要注意/ 和 其他很多语言是不一样的
+2. 如果你用的是 JS 的话，需要注意/ 和 其他很多语言是不一样的
 
-3. 如果你用的是JS的话，需要先将字符串转化为数字。否则有很多意想不到的结果
+3. 如果你用的是 JS 的话，需要先将字符串转化为数字。否则有很多意想不到的结果
 
 4. 操作符的顺序应该是 先出栈的是第二位，后出栈的是第一位。 这在不符合交换律的操作中很重要， 比如减法和除法。
 
 ## 代码
 
-代码支持：JS，Python，Java
+代码支持：JS，Python，Java, CPP
 
 JS Code:
 
@@ -101,7 +101,7 @@ JS Code:
  * @param {string[]} tokens
  * @return {number}
  */
-var evalRPN = function(tokens) {
+var evalRPN = function (tokens) {
   // 这种算法的前提是 tokens是有效的，
   // 当然这由算法来保证
   const stack = [];
@@ -121,7 +121,7 @@ var evalRPN = function(tokens) {
       if (token === "*") {
         stack.push(b * a);
       } else if (token === "/") {
-        stack.push(b / a >> 0);
+        stack.push((b / a) >> 0);
       } else if (token === "+") {
         stack.push(b + a);
       } else if (token === "-") {
@@ -132,10 +132,8 @@ var evalRPN = function(tokens) {
 
   return stack.pop();
 };
-
 ```
 
-
 Python Code:
 
 ```python
@@ -163,7 +161,6 @@ class Solution:
         return int(tokens[-1])
 ```
 
-
 Java Code:
 
 ```java
@@ -189,10 +186,35 @@ class Solution {
 }
 ```
 
+CPP Code:
+
+```cpp
+	class Solution {
+public:
+  int evalRPN(vector<string>& tokens) {
+    stack<int> s;
+    for (string t : tokens) {
+      if (isdigit(t.back())) s.push(stoi(t));
+      else {
+        int n = s.top();
+        s.pop();
+        switch(t[0]) {
+          case '+': s.top() += n; break;
+          case '-': s.top() -= n; break;
+          case '*': s.top() *= n; break;
+          case '/': s.top() /= n; break;
+        }
+      }
+    }
+    return s.top();
+  }
+};
+```
 
 ## 扩展
 
 逆波兰表达式中只改变运算符的顺序，并不会改变操作数的相对顺序，这是一个重要的性质。另外逆波兰表达式完全不关心操作符的优先级，这在中缀表达式中是做不到的，这很有趣，感兴趣的可以私下查找资料研究下为什么会这样。
 
+```
 
-
+```
diff --git a/problems/152.maximum-product-subarray.md b/problems/152.maximum-product-subarray.md
@@ -67,7 +67,7 @@ var maxProduct = function (nums) {
 
 ## 代码
 
-代码支持：Python3，JavaScript
+代码支持：Python3，JavaScript, CPP
 
 Python3 Code:
 
@@ -136,6 +136,24 @@ var maxProduct = function (nums) {
 };
 ```
 
+CPP Code:
+
+```cpp
+class Solution {
+public:
+    int maxProduct(vector<int>& A) {
+        int maxProd = 1, minProd = 1, ans = INT_MIN;
+        for (int n : A) {
+            int a = n * maxProd, b = n * minProd;
+            maxProd = max({n, a, b});
+            minProd = min({n, a, b});
+            ans = max(ans, maxProd);
+        }
+        return ans;
+    }
+};
+```
+
 **复杂度分析**
 
 - 时间复杂度：$O(N)$
diff --git a/problems/169.majority-element.md b/problems/169.majority-element.md
@@ -51,7 +51,7 @@ https://leetcode-cn.com/problems/majority-element/
 
 ## 代码
 
-- 语言支持：JS，Python
+- 语言支持：JS，Python, CPP
 
 Javascript Code:
 
@@ -89,6 +89,26 @@ class Solution:
         return majority
 ```
 
+CPP Code:
+
+```cpp
+class Solution {
+public:
+    int majorityElement(vector<int>& nums) {
+        int ans = 0, cnt = 0;
+        for (int n : nums) {
+            if (ans == n) ++cnt;
+            else if (cnt > 0) --cnt;
+            else {
+                ans = n;
+                cnt = 1;
+            }
+        }
+        return ans;
+    }
+};
+```
+
 **复杂度分析**
 
 - 时间复杂度：$O(N)$，其中 N 为数组长度
