MyDataSource
diff --git a/‎435. Find All Duplicates in an Array/README.md
Lines changed: 29 additions & 0 deletions b/‎435. Find All Duplicates in an Array/README.md
Lines changed: 29 additions & 0 deletions
diff --git a/‎435. Find All Duplicates in an Array/main.cc
Lines changed: 14 additions & 0 deletions b/‎435. Find All Duplicates in an Array/main.cc
Lines changed: 14 additions & 0 deletions
diff --git a/‎435. Find All Duplicates in an Array/solution.h
Lines changed: 15 additions & 0 deletions b/‎435. Find All Duplicates in an Array/solution.h
Lines changed: 15 additions & 0 deletions
diff --git a/‎630. Maximum Binary Tree/README.md
Lines changed: 17 additions & 0 deletions b/‎630. Maximum Binary Tree/README.md
Lines changed: 17 additions & 0 deletions
diff --git a/‎630. Maximum Binary Tree/main.cc
Lines changed: 36 additions & 0 deletions b/‎630. Maximum Binary Tree/main.cc
Lines changed: 36 additions & 0 deletions
diff --git a/‎630. Maximum Binary Tree/solution.h
Lines changed: 28 additions & 0 deletions b/‎630. Maximum Binary Tree/solution.h
Lines changed: 28 additions & 0 deletions
@@ -0,0 +1,29 @@
+这道题一定要审题，LeetCode 的特点是，题目言简意赅。那么就一定要从字字品味，获取思路。
+
+首先，拿到这道题，如果没有这俩限制，是相当简单的：
+
+1. without extra space
+2. O(n) runtime
+
+其一不让你多用空间，其二只允许一次遍历。这还让不让人活了？算法不就是空间与时间的游戏吗？俩都不让步，怎么玩。
+
+沮丧之余，**只好再多读几遍题**。终于发现有几个奇怪的设定：
+
+1. some elements appear **twice** and others appear **once**
+2. `1 <= a[i] <= n` (n = size of array)
+
+其一，简化场景，数组里要么出现两次，要么出现一次。其二，数组里的数字，肯定大于等于 1，并小于等于**数组长度**。
+
+这时候该笑出声了，暗示的不能再明显了。不让你用多余的空间，因为数组里的数，可以无缝转化为 index. 不让你用多余的时间，因为要么两次，要么一次，一次迭代完全足够了。
+
+既然数组里每一个数字，都可以映射为 index（这个 index 可以想象成坑位），那么我们就得想，怎么对坑位做个标记，知道这个坑位已经来过人了。
+
+这个标记，你大可以按自己喜好来，就是个简单的加密解密思维，取余？+n/-n？都可以，这里最直观的标记，是正负号。为什么呢？因为数字肯定大于1，那么一定是正数，如果出现负数，就可以证明该坑位被用过。
+
+于是这道所谓 Medium 的题，就成了 easy 档次的，3行就搞定了：
+
+```cpp
+int index = abs(nums[i]) - 1;
+if (nums(index) < 0) ret.push_back(index + 1);
+nums[index] = -nums[index];
+```
@@ -0,0 +1,14 @@
+#define CATCH_CONFIG_MAIN
+#include "../Catch/single_include/catch.hpp"
+#include "solution.h"
+
+TEST_CASE("Find All Duplicates in an Array", "[findDuplicates]")
+{
+    SECTION( "as question" )
+    {
+        std::vector<int> vec{4,3,2,7,8,2,3,1};
+        std::vector<int> ret{2,3};
+        Solution s;
+        REQUIRE( s.findDuplicates(vec) == ret );
+    }
+}
@@ -0,0 +1,15 @@
+#include <vector>
+using std::vector;
+
+class Solution {
+public:
+    vector<int> findDuplicates(vector<int>& nums) {
+        vector<int> ret;
+        for (size_t i = 0; i != nums.size(); ++i) {
+            size_t id = static_cast<size_t>(std::abs(nums[i]) - 1);
+            if (nums[id] < 0) ret.push_back(id + 1);
+            nums[id] = -nums[id];
+        }
+        return ret;
+    }
+};
@@ -0,0 +1,17 @@
+好久不来做题，为什么百忙之中来写这道题呢。。。
+
+因为这被用来作为我司的面试题，而我却竟然还没做过。。。然后一看，果然比较基础，所以在这里写出来也无妨。
+
+虽然被标记为 Medium，但实际是 easy 难度的。因为读题就能发现其递归特性。root... left... right...
+
+所以如果面试遇到这个，你要笑开花了，用最直观的方式，按着题意写递归就好了。
+
+首先将原函数拆解为递归形式：`constructMaximumBinaryTree(Iter beg, Iter end)`, 然后实现如下：
+
+1. root = max(beg, end);
+2. root.left = constructMaximumBinaryTree(beg, root_pos)
+3. root.right = constructMaximumBinaryTree(root_pos + 1, end)
+
+完。
+
+对算法比较有追求的童鞋可以看下 [Cartesian tree](https://en.wikipedia.org/wiki/Cartesian_tree)，这道题的灵感应该是从这里来的。
@@ -0,0 +1,36 @@
+#include "solution.h"
+#include <iostream>
+#include <queue>
+#include <algorithm>
+
+void print_bfs(TreeNode* p)
+{
+    if (!p) return;
+    std::vector<std::string> retv;
+    std::queue<TreeNode *> q;
+    q.push(p);
+    do {
+        TreeNode *node = q.front(); q.pop();
+        if (node) 
+            retv.push_back(std::to_string(node->val));
+        else {
+            retv.push_back("#");
+            continue;
+        }
+        q.push(node->left); 
+        q.push(node->right);
+    } while (!q.empty());
+    
+    auto found = std::find_if(retv.rbegin(), retv.rend(), [](const std::string &s){ return s != "#"; });
+    retv.erase(found.base(), retv.end());
+    for (const auto &s : retv)
+        std::cout << s << ",";
+    std::cout << "\b " << std::endl; 
+}
+
+int main() 
+{
+  Solution s;
+  std::vector<int> array{3,2,1,6,0,5};
+  print_bfs(s.constructMaximumBinaryTree(array));
+}
@@ -0,0 +1,28 @@
+#include <vector>
+using std::vector;
+#include <algorithm>
+
+struct TreeNode {
+    int val;
+    TreeNode *left;
+    TreeNode *right;
+    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
+};
+
+class Solution {
+public:
+    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
+        return constructMaximumBinaryTree(nums.cbegin(), nums.cend());
+    }
+private:
+    using Iter = vector<int>::const_iterator;
+    TreeNode* constructMaximumBinaryTree(Iter beg, Iter end) {
+        if (beg == end) return nullptr;
+        auto max = std::max_element(beg, end);
+        TreeNode* root = new TreeNode(*max);
+        auto max_pos = std::distance(beg, max);
+        root->left = constructMaximumBinaryTree(beg, max);
+        root->right = constructMaximumBinaryTree(std::next(max), end);
+        return root;
+    }
+};