feat: cpp code

lucifer · lucifer · commit 1ec5d6d9bcb3 · 2021-01-12T19:27:57.000+08:00
diff --git a/README.md b/README.md
@@ -157,6 +157,7 @@ leetcode 题解，记录自己的 leetcode 解题之路。
 - [最大公约数](./thinkings/GCD.md)
 - [并查集](./thinkings/union-find.md)
 - [平衡二叉树专题](./thinkings/balanced-tree.md)
+- [蓄水池抽样](./thinkings/reservoid-sampling.md) 🆕
 - [单调栈](./thinkings/monotone-stack.md) 🆕
 
 ### 精选题解（9 篇）
diff --git a/SUMMARY.md b/SUMMARY.md
@@ -24,6 +24,7 @@
     * [最大公约数](thinkings/GCD.md)
     * [并查集](thinkings/union-find.md)
     * [平衡二叉树专题](thinkings/balanced-tree.md)
+    * [蓄水池抽样](thinkings/reservoid-sampling.md) 🆕
     * [单调栈](thinkings/monotone-stack.md)
 
 
diff --git a/problems/1.two-sum.md b/problems/1.two-sum.md
@@ -53,7 +53,7 @@ https://leetcode-cn.com/problems/two-sum
 
 ## 代码
 
-- 语言支持：JS, Go
+- 语言支持：JS, Go，CPP
 
 ```js
 /**
@@ -90,14 +90,30 @@ func twoSum(nums []int, target int) []int {
 }
 ```
 
+CPP Code:
+
+```cpp
+class Solution {
+public:
+    vector<int> twoSum(vector<int>& A, int target) {
+        unordered_map<int, int> m;
+        for (int i = 0; i < A.size(); ++i) {
+            int t = target - A[i];
+            if (m.count(t)) return { m[t], i };
+            m[A[i]] = i;
+        }
+        return {};
+    }
+};
+```
+
 **复杂度分析**
 
 - 时间复杂度：$$O(N)$$
 - 空间复杂度：$$O(N)$$
 
-更多题解可以访问我的LeetCode题解仓库：https://github.com/azl397985856/leetcode  。 目前已经37K star啦。
+更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
 
 关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
 
-
 ![](https://tva1.sinaimg.cn/large/007S8ZIlly1gfcuzagjalj30p00dwabs.jpg)
diff --git a/problems/15.3sum.md b/problems/15.3sum.md
@@ -53,6 +53,10 @@ https://leetcode-cn.com/problems/3sum/
 
 ## 代码
 
+代码支持 ： JS，CPP
+
+JS Code:
+
 ```js
 /**
  * @param {number[]} nums
@@ -98,7 +102,38 @@ var threeSum = function (nums) {
 };
 ```
 
+CPP Code:
+
+```cpp
+class Solution {
+public:
+    vector<vector<int>> threeSum(vector<int>& A) {
+        sort(begin(A), end(A));
+        vector<vector<int>> ans;
+        int N = A.size();
+        for (int i = 0; i < N - 2; ++i) {
+            if (i && A[i] == A[i - 1]) continue;
+            int L = i + 1, R = N - 1;
+            while (L < R) {
+                int sum = A[i] + A[L] + A[R];
+                if (sum == 0) ans.push_back({ A[i], A[L], A[R] });
+                if (sum >= 0) {
+                    --R;
+                    while (L < R && A[R] == A[R + 1]) --R;
+                }
+                if (sum <= 0) {
+                    ++L;
+                    while (L < R && A[L] == A[L - 1]) ++L;
+                }
+            }
+        }
+        return ans;
+    }
+}
+```
+
 **复杂度分析**
+
 - 时间复杂度：$$O(N^2)$$
 - 空间复杂度：取决于排序算法的空间消耗
 
diff --git a/problems/4.median-of-two-sorted-arrays.md b/problems/4.median-of-two-sorted-arrays.md
@@ -196,6 +196,8 @@ var findMedianSortedArrays = function (nums1, nums2) {
 
 _解法二 - 二分查找（Binary Search)_
 
+JS Code:
+
 ```js
 /**
  * 二分解法
@@ -234,6 +236,8 @@ var findMedianSortedArrays = function (nums1, nums2) {
 };
 ```
 
+Java Code:
+
 ```java
 class MedianSortedTwoArrayBinarySearch {
   public static double findMedianSortedArraysBinarySearch(int[] nums1, int[] nums2) {
@@ -278,6 +282,30 @@ class MedianSortedTwoArrayBinarySearch {
 }
 ```
 
+CPP Code:
+
+```cpp
+class Solution {
+public:
+    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
+        if (nums1.size() > nums2.size()) swap(nums1, nums2);
+        int M = nums1.size(), N = nums2.size(), L = 0, R = M, K = (M + N + 1) / 2;
+        while (true) {
+            int i = (L + R) / 2, j = K - i;
+            if (i < M && nums2[j - 1] > nums1[i]) L = i + 1;
+            else if (i > L && nums1[i - 1] > nums2[j]) R = i - 1;
+            else {
+                int maxLeft = max(i ? nums1[i - 1] : INT_MIN, j ? nums2[j - 1] : INT_MIN);
+                if ((M + N) % 2) return maxLeft;
+                int minRight = min(i == M ? INT_MAX : nums1[i], j == N ? INT_MAX : nums2[j]);
+                return (maxLeft + minRight) / 2.0;
+            }
+        }
+    }
+};
+
+```
+
 **复杂度分析**
 
 - 时间复杂度：$$O(log(min(m, n)))$$
diff --git a/problems/5.longest-palindromic-substring.md b/problems/5.longest-palindromic-substring.md
@@ -51,14 +51,13 @@ if (s[i] === s[j] && dp[i + 1][j - 1]) {
 }
 ```
 
-
 ## 关键点
 
 - ”延伸“（extend）
 
 ## 代码
 
-代码支持：Python，JavaScript：
+代码支持：Python，JavaScript，CPP
 
 Python Code：
 
@@ -127,7 +126,37 @@ var longestPalindrome = function (s) {
 };
 ```
 
-**_复杂度分析_**
+CPP Code:
+
+```cpp
+class Solution {
+private:
+    int expand(string &s, int L, int R) {
+        while (L >= 0 && R < s.size() && s[L] == s[R]) {
+            --L;
+            ++R;
+        }
+        return R - L - 1;
+    }
+public:
+    string longestPalindrome(string s) {
+        if (s.empty()) return s;
+        int start = 0, maxLen = 0;
+        for (int i = 0; i < s.size(); ++i) {
+            int len1 = expand(s, i, i);
+            int len2 = expand(s, i, i + 1);
+            int len = max(len1, len2);
+            if (len > maxLen) {
+                start = i - (len - 1) / 2;
+                maxLen = len;
+            }
+        }
+        return s.substr(start, maxLen);
+    }
+};
+```
+
+**复杂度分析**
 
 - 时间复杂度：$$O(N^2)$$
 - 空间复杂度：$$O(N^2)$$
diff --git a/thinkings/README.md b/thinkings/README.md
@@ -27,4 +27,5 @@
 - [最大公约数](GCD.md)
 - [并查集](union-find.md)
 - [前缀和](prefix.md)
+- [蓄水池抽样](reservoid-sampling.md)
 - [平衡二叉树专题](balanced-tree.md)
diff --git a/thinkings/reservoid-sampling.md b/thinkings/reservoid-sampling.md
@@ -0,0 +1,62 @@
+# 蓄水池抽样
+
+力扣中关于蓄水池抽样问题官方标签是 2 道，根据我的做题情况来看，可能有三四道。比重算是比较低的，大家可以根据自己的实际情况选择性掌握。
+
+蓄水池抽样的算法思维很巧妙，代码简单且容易理解，就算不掌握它，作为了解也是很不错的。
+
+## 问题描述
+
+给出一个数据流，我们需要在此数据流中随机选取 k 个数。由于这个数据流的长度很大，因此需要边遍历边处理，而不能将其一次性全部加载到内存。
+
+请写出一个随机选择算法，使得数据流中所有数据被**等概率**选中。
+
+这种问题的表达形式有很多。比如让你随机从一个矩形中抽取 k 个点，随机从一个单词列表中抽取 k 个单词等等，要求你等**概率随机抽取**。不管描述怎么变，其本质上都是一样的。今天我们就来看看如何做这种题。
+
+## 算法描述
+
+这个算法叫蓄水池抽样算法（reservoid sampling）。
+
+其基本思路是：
+
+- 构建一个大小为 k 的数组，将数据流的前 k 个元素放入数组中。
+- 对数据流的前 k 个数**先**不进行任何处理。
+- 从数据流的第 k + 1 个数开始，在 [1, i] 之间选一个数 rand，其中 i 表示当前是第几个数。
+- 如果 rand 大于等于 k 什么都不做
+- 如果 rand 小于 k， 将 rand 和 i 交换，也就是说选择当前的数代替已经被选中的数（备胎）。
+- 最终返回幸存的备胎即可
+
+这种算法的核心在于先以某一种概率选取数，并在后续过程以另一种概率换掉之前已经被选中的数。因此实际上每个数被最终选中的概率都是**被选中的概率 \* 不被替换的概率**。
+
+伪代码：
+
+> 伪代码参考的某一本算法书，并略有修改。
+
+```py
+Init : a reservoir with the size： k
+for i= k+1 to N
+    if(random(1, i) < k) {
+        SWAP the Mth value and ith value
+    }
+```
+
+这样可以保证被选择的数是等概率的吗？答案是肯定的。
+
+- 当 i <= k ，i 被选中的概率是 1。
+- 到第 k + 1 个数时，第 k + 1 个数被选中的概率（走进上面的 if 分支的概率）是 $\frac{k}{k+1}$，到第 k + 2 个数时，第 k + 2 个数被选中的概率（走进上面的 if 分支的概率）是 $\frac{k}{k+2}$，以此类推。那么第 n 个数被选中的概率就是 $\frac{k}{n}$
+- 上面分析了被选中的概率，接下来分析不被替换的概率。到第 k + 1 个数时，前 k 个数被替换的概率是 $\frac{1}{k}$。到前 k + 2 个数时，第 k + 2 个数被替换的概率是 $\frac{1}{k}$，以此类推。也就是说所有的被替换的概率都是 $\frac{1}{k}$。知道了被替换的概率，那么不被替换的概率其实就是 1 - 被替换的概率。
+
+因此对于前 k 个数，最终被选择的概率都是 1 \* 不被 k + 1 替换的概率 \* 不被 k + 2 替换的概率 \* ... 不被 n 替换的概率，即 1 \* (1 - 被 k + 1 替换的概率) \* (1 - 被 k + 2 替换的概率) \* ... (1 - 被 n 替换的概率)，即 $1 \times (1 - \frac{k}{k+1} \times \frac{1}{k}) \times (1 - \frac{k}{k+2} \times \frac{1}{k}) \times ... \times (1 - \frac{k}{n} \times \frac{1}{k}) = \frac{k}{n} $。
+
+对于 第 i (i > k) 个数，最终被选择的概率是 第 i 步被选中的概率 \* 不被第 i + 1 步替换的概率 \* ... \* 不被第 n 步被替换的概率， 即 $\frac{k}{k+1} \times (1 - \frac{k}{k+2} \times \frac{1}{k}) \times ... \times (1 - \frac{k}{n} \times \frac{1}{k}) = \frac{k}{n} $。
+
+总之，不管是哪个数，被选中的概率都是 $\frac{k}{n}$，满足概率相等的需求。
+
+## 相关题目
+
+- [382. 链表随机节点](https://leetcode-cn.com/problems/linked-list-random-node/ "382. 链表随机节点")
+- [398. 随机数索引](https://leetcode-cn.com/problems/random-pick-index/ "398. 随机数索引")
+- [497. 非重叠矩形中的随机点](https://leetcode-cn.com/problems/random-point-in-non-overlapping-rectangles/ "497. 非重叠矩形中的随机点")
+
+## 总结
+
+蓄水池抽样算法核心代码非常简单。但是却不容易想到，尤其是之前没见过的情况下。其核心点在于每个数被最终选中的概率都是**被选中的概率 \* 不被替换的概率**。于是我们可以采取某一种动态手段，使得每一轮都有概率选中和替换一些数字。 上面我们有给出了概率相等的证明过程，大家不妨自己尝试证明一下。之后结合文末的相关题目练习一下，效果会更好。
