# hihoCoder 1552-缺失的拼图

hihoCoder 1552-缺失的拼图

### 输出

```5
0 0 4 5
0 0 3 1
0 1 2 5
3 0 4 5
2 2 3 5```

`2 1 3 2`

```#include<algorithm>
#include<vector>
#include<iostream>
#include<unordered_map>
#include<unordered_set>
#include<string>
#include<set>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int, int> Point;
int main() {
//freopen("input.txt", "r", stdin);
int n;
scanf("%d", &n);
map<Point, int> hash;
int a, b, c, d;
while (n--) {
Point left_bottom, right_top;
scanf("%d %d %d %d", &left_bottom.first, &left_bottom.second, &right_top.first, &right_top.second);
Point left_top = Point(left_bottom.first, right_top.second), right_bottom = Point(right_top.first, left_bottom.second);
++hash[left_bottom];
++hash[right_top];
++hash[left_top];
++hash[right_bottom];
}
set<Point> ans;
for (auto p : hash) {
if (p.second % 2 == 1) {
ans.insert(p.first);
}
}
a = c = ans.begin()->first;
b = d = ans.begin()->second;
for (auto p : ans) {
a = min(a, p.first);
b = min(b, p.second);
c = max(c, p.first);
d = max(d, p.second);
}
printf("%d %d %d %d\n", a, b, c, d);
return 0;
}
```

# hihoCoder 1551-合并子目录

hihoCoder 1551-合并子目录

### 描述

/hihocoder/offer22/solutions/p1
/hihocoder/challenge30/p1/test
/game/moba/dota2/uninstall

/hihocoder
/hihocoder/offer22
/hihocoder/offer22/solutions
/hihocoder/challenge30
/hihocoder/challenge30/p1
/game
/game/moba
/game/moba/dota2/

### 输出

```3
/hihocoder/offer22/solutions/p1
/hihocoder/challenge30/p1/test
/game/moba/dota2/uninstall```

`8`

```#include<algorithm>
#include<vector>
#include<iostream>
#include<unordered_map>
#include<unordered_set>
#include<string>
#include<set>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
struct Node {
string key_;
map<string, Node*> children_;
Node(string key) :key_(key) {};
};
int main() {
//freopen("input.txt", "r", stdin);
int n;
scanf("%d\n", &n);
string line;
Node* root = new Node("");
while (n--) {
getline(cin, line);
int pre = 0;
int pos = line.find('//');
Node* cur = root;
while (pos != string::npos) {
if (pos != 0) {
string tmp = line.substr(pre + 1, pos - pre - 1);
if (cur->children_[tmp] == NULL) {
cur->children_[tmp] = new Node(tmp);
}
cur = cur->children_[tmp];
}
pre = pos;
pos = line.find('//', pos + 1);
}
}
ll ans = 0;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* cur = q.front();
q.pop();
++ans;
for (auto it : cur->children_) {
q.push(it.second);
}
}
printf("%lld\n", ans - 1);
return 0;
}
```

# hihoCoder 1550-顺序三元组

hihoCoder 1550-顺序三元组

### 输出

```6
1 3 2 1 2 3```

`3`

```#include<algorithm>
#include<vector>
#include<iostream>
#include<map>
using namespace std;
typedef long long ll;
int main() {
//freopen("input.txt", "r", stdin);
int n = 0;
scanf("%d", &n);
vector<int> nums(n, 0);
map<int, int> left, right;
for (int i = 0; i < n; ++i) {
scanf("%d", &nums[i]);
++right[nums[i]];
}
ll ans = 0;
for (int i = 0; i < n; ++i) {
--right[nums[i]];
if (nums[i] == 2) {
ans += left[1] * right[3];
}
++left[nums[i]];
}
printf("%lld\n", ans);
return 0;
}
```

# LeetCode Find K Closest Elements

LeetCode Find K Closest Elements
Given a sorted array, two integers `k` and `x`, find the `k` closest elements to `x` in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.
Example 1:

```Input: [1,2,3,4,5], k=4, x=3
Output: [1,2,3,4]
```

Example 2:

```Input: [1,2,3,4,5], k=4, x=-1
Output: [1,2,3,4]
```

Note:

1. The value k is positive and will always be smaller than the length of the sorted array.
2. Length of the given array is positive and will not exceed 104
3. Absolute value of elements in the array and x will not exceed 104

```class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
vector<int> ans;
int n = arr.size();
auto it = lower_bound(arr.begin(), arr.end(), x);
if (it == arr.begin()) {
while (ans.size() < k) {
ans.push_back(*it++);
}
return ans;
}
else if (it == arr.end()) {
while (ans.size() < k) {
ans.push_back(*--it);
}
return ans;
}
else {
int right = it - arr.begin();
int left = right - 1;
int left_diff = INT_MAX, right_diff = INT_MAX;
while (ans.size() < k) {
if (left >= 0)left_diff = abs(arr[left] - x);
else left_diff = INT_MAX;
if (right < n)right_diff = abs(arr[right] - x);
else right_diff = INT_MAX;
if (left_diff <= right_diff) {
ans.push_back(arr[left]);
--left;
}
else {
ans.push_back(arr[right]);
++right;
}
}
}
sort(ans.begin(), ans.end());
return ans;
}
};
```

# LeetCode Judge Route Circle

LeetCode Judge Route Circle
Initially, there is a Robot at position (0, 0). Given a sequence of its moves, judge if this robot makes a circle, which means it moves back to the original place.
The move sequence is represented by a string. And each move is represent by a character. The valid robot moves are `R` (Right), `L` (Left), `U` (Up) and `D` (down). The output should be true or false representing whether the robot makes a circle.
Example 1:

```Input: "UD"
Output: true
```

Example 2:

```Input: "LL"
Output: false```

```class Solution {
public:
bool judgeCircle(string moves) {
int horizon = 0, vertical = 0;
for (auto c : moves) {
if (c == 'U')++vertical;
else if (c == 'D')--vertical;
else if (c == 'L')--horizon;
else if (c == 'R')++horizon;
}
return horizon == 0 && vertical == 0;
}
};
```