8000 add 435 and 630 · MyDataSource/LeetCode@feaec0b · GitHub
[go: up one dir, main page]
Skip to content

Commit feaec0b

Browse files
author
pezy
committed
add 435 and 630
1 parent 4229c6e commit feaec0b

File tree

6 files changed

+139
-0
lines changed

6 files changed

+139
-0
lines changed

‎435. Find All Duplicates in an Array/README.md

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
这道题一定要审题，LeetCode 的特点是，题目言简意赅。那么就一定要从字字品味，获取思路。
2+
3+
首先，拿到这道题，如果没有这俩限制，是相当简单的：
4+
5+
1. without extra space
6+
2. O(n) runtime
7+
8+
其一不让你多用空间，其二只允许一次遍历。这还让不让人活了？算法不就是空间与时间的游戏吗？俩都不让步，怎么玩。
9+
10+
沮丧之余，**只好再多读几遍题**。终于发现有几个奇怪的设定：
11+
12+
1. some elements appear **twice** and others appear **once**
13+
2. `1 <= a[i] <= n` (n = size of array)
14+
15+
其一，简化场景，数组里要么出现两次，要么出现一次。其二，数组里的数字，肯定大于等于 1，并小于等于**数组长度**。
16+
17+
这时候该笑出声了，暗示的不能再明显了。不让你用多余的空间，因为数组里的数，可以无缝转化为 index. 不让你用多余的时间，因为要么两次，要么一次，一次迭代完全足够了。
18+
19+
既然数组里每一个数字，都可以映射为 index（这个 index 可以想象成坑位），那么我们就得想，怎么对坑位做个标记，知道这个坑位已经来过人了。
20+
21+
这个标记，你大可以按自己喜好来，就是个简单的加密解密思维，取余？+n/-n？都可以，这里最直观的标记，是正负号。为什么呢？因为数字肯定大于1，那么一定是正数，如果出现负数，就可以证明该坑位被用过。
22+
23+
于是这道所谓 Medium 的题，就成了 easy 档次的，3行就搞定了：
24+
25+
```cpp
26+
int index = abs(nums[i]) - 1;
27+
if (nums(index) < 0) ret.push_back(index + 1);
28+
nums[index] = -nums[index];
29+
```

‎435. Find All Duplicates in an Array/main.cc

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
#define CATCH_CONFIG_MAIN
2+
#include "../Catch/single_include/catch.hpp"
3+
#include "solution.h"
4+
5+
TEST_CASE("Find All Duplicates in an Array", "[findDuplicates]")
6+
{
7+
SECTION( "as question" )
8+
{
9+
std::vector<int> vec{4,3,2,7,8,2,3,1};
10+
std::vector<int> ret{2,3};
11+
Solution s;
12+
REQUIRE( s.findDuplicates(vec) == ret );
13+
}
14+
}

‎435. Find All Duplicates in an Array/solution.h

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
#include <vector>
2+
using std::vector;
3+
4+
class Solution {
5+
public:
6+
vector<int> findDuplicates(vector<int>& nums) {
7+
vector<int> ret;
8+
for (size_t i = 0; i != nums.size(); ++i) {
9+
size_t id = static_cast<size_t>(std::abs(nums[i]) - 1);
10+
if (nums[id] < 0) ret.push_back(id + 1);
11+
nums[id] = -nums[id];
12+
}
13+
return ret;
14+
}
15+
};

‎630. Maximum Binary Tree/README.md

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
好久不来做题，为什么百忙之中来写这道题呢。。。
2+
3+
因为这被用来作为我司的面试题，而我却竟然还没做过。。。然后一看，果然比较基础，所以在这里写出来也无妨。
4+
5+
虽然被标记为 Medium，但实际是 easy 难度的。因为读题就能发现其递归特性。root... left... right...
6+
7+
所以如果面试遇到这个，你要笑开花了，用最直观的方式，按着题意写递归就好了。
8+
9+
首先将原函数拆解为递归形式：`constructMaximumBinaryTree(Iter beg, Iter end)`, 然后实现如下：
10+
11+
1. root = max(beg, end);
12+
2. root.left = constructMaximumBinaryTree(beg, root_pos)
13+
3. root.right = constructMaximumBinaryTree(root_pos + 1, end)
14+
15+
完。
16+
17+
对算法比较有追求的童鞋可以看下 [Cartesian tree](https://en.wikipedia.org/wiki/Cartesian_tree)，这道题的灵感应该是从这里来的。

‎630. Maximum Binary Tree/main.cc

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
#include "solution.h"
2+
#include <iostream>
3+
#include <queue>
4+
#include <algorithm>
5+
6+
void print_bfs(TreeNode* p)
7+
{
8+
if (!p) return;
9+
std::vector<std::string> retv;
10+
std::queue<TreeNode *> q;
11+
q.push(p);
12+
do {
13+
TreeNode *node = q.front(); q.pop();
14+
if (node)
15+
retv.push_back(std::to_string(node->val));
16+
else {
17+
retv.push_back("#");
18+
continue;
19+
}
20+
q.push(node->left);
21+
q.push(node->right);
22+
} while (!q.empty());
23+
24+
auto found = std::find_if(retv.rbegin(), retv.rend(), [](const std::string &s){ return s != "#"; });
25+
retv.erase(found.base(), retv.end());
26+
for (const auto &s : retv)
27+
std::cout << s << ",";
28+
std::cout << "\b " << std::endl;
29+
}
30+
31+
int main()
32+
{
33+
Solution s;
34+
std::vector<int> array{3,2,1,6,0,5};
35+
print_bfs(s.constructMaximumBinaryTree(array));
36+
}

‎630. Maximum Binary Tree/solution.h

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
#include <vector>
2+
using std::vector;
3+
#include <algorithm>
4+
5+
struct TreeNode {
6+
int val;
7+
TreeNode *left;
8+
TreeNode *right;
9+
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10+
};
11+
12+
class Solution {
13+
public:
14+
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
15+
return constructMaximumBinaryTree(nums.cbegin(), nums.cend());
16+
}
17+
private:
18+
using Iter = vector<int>::const_iterator;
19+
TreeNode* constructMaximumBinaryTree(Iter beg, Iter end) {
20+
if (beg == end) return nullptr;
21+
auto max = std::max_element(beg, end);
22+
TreeNode* root = new TreeNode(*max);
23+
auto max_pos = std::distance(beg, max);
24+
root->left = constructMaximumBinaryTree(beg, max);
25+
root->right = constructMaximumBinaryTree(std::next(max), end);
26+
return root;
27+
}
28+
};

0 commit comments

Comments
 (0)
0