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

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Appearance settings

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
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+
```
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+
}
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