Monthly Archives: August 2017

hihoCoder 1552-缺失的拼图

Leave a reply

hihoCoder 1552-缺失的拼图

#1552 : 缺失的拼图

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

小Hi在玩一个拼图游戏。如下图所示，整个拼图是由N块小矩形组成的大矩形。现在小Hi发现其中一块小矩形不见了。给定大矩形以及N-1个小矩形的顶点坐标，你能找出缺失的那块小矩形的顶点坐标吗？

输入

第一行包含一个整数，N。 第二行包含四个整数，(X0, Y0), (X‘0, Y‘0)，代表大矩形左下角和右上角的坐标。 以下N-1行每行包含四个整数，(Xi, Yi), (X‘i, Y‘i)，代表其中一个小矩形的左下角和右上角坐标。 对于30%的数据， 1 <= N <= 1000 对于100%的数据，1 <= N <= 100000 所有的坐标(X, Y)满足 0 <= X, Y <= 100000000

输出

输出四个整数(X, Y), (X‘, Y‘)代表缺失的那块小矩形的左下角和右上角的坐标。
样例输入
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
一个矩形由N个小矩形拼接而成，现在丢了一个小矩形，怎样才能找到这个小矩形呢。所有矩形都用左下角坐标和右上角坐标表示。 这一题也很有意思，丢掉的那个小矩形的坐标肯定是其他N-1个矩形的坐标中的某4个。我们可以统计每个坐标点出现的次数，如果出现偶数次，则这个点所在的矩形是出现过的，否则这个点就是缺失矩形的某个顶点。最后，从缺失的4个顶点中找出左下角坐标和右上角坐标。 完整代码如下： [cpp] #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; } [/cpp] 本代码提交AC，用时432MS。]]>

hihoCoder 1551-合并子目录

Leave a reply

hihoCoder 1551-合并子目录

#1551 : 合并子目录

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

小Hi的电脑的文件系统中一共有N个文件，例如： /hihocoder/offer22/solutions/p1 /hihocoder/challenge30/p1/test /game/moba/dota2/uninstall 小Hi想统计其中一共有多少个不同的子目录。上例中一共有8个不同的子目录： /hihocoder /hihocoder/offer22 /hihocoder/offer22/solutions /hihocoder/challenge30 /hihocoder/challenge30/p1 /game /game/moba /game/moba/dota2/

输入

第一行包含一个整数N (1 ≤ N ≤ 10000) 以下N行每行包含一个字符串，代表一个文件的绝对路径。保证路径从根目录”/”开始，并且文件名和目录名只包含小写字母和数字。 对于80%的数据，N个文件的绝对路径长度之和不超过10000 对于100%的数据，N个文件的绝对路径长度之和不超过500000

输出

一个整数代表不同子目录的数目。
样例输入
3
/hihocoder/offer22/solutions/p1
/hihocoder/challenge30/p1/test
/game/moba/dota2/uninstall
样例输出
8
给定很多个文件的绝对路径，问从这些文件的绝对路径中，我们可以知道其一共有多少个不同文件夹出现过。 常规思路很简单，直接解析每个文件所在的每一级文件夹路径，存到一个set里面，最后返回unordered_set的大小。但是这种方法TLE，看了一下，内存基本也用完了。因为对于100%的数据，路径长度太长了，hash的时间和空间都随之增长。 后来马上想到，路径问题是一层一层的，有可能很多文件的路径前缀都是相同的，那么我们可以构建一个Trie树，每个节点仅是当前文件夹的名称。最后我们统计一下构建好的Trie树的节点个数，就是文件夹的个数。 完整代码如下： [cpp] #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; } [/cpp] 本代码提交AC，用时126MS。]]>

hihoCoder 1550-顺序三元组

Leave a reply

hihoCoder 1550-顺序三元组

题目1 : 顺序三元组

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

给定一个长度为N的数组A=[A1, A2, … AN]，已知其中每个元素Ai的值都只可能是1, 2或者3。 请求出有多少下标三元组(i, j, k)满足1 ≤ i < j < k ≤ N且Ai < Aj < Ak。

输入

第一行包含一个整数N 第二行包含N个整数A1, A2, … AN。(1 ≤ Ai ≤ 3) 对于30%的数据，1 ≤ N ≤ 100 对于80%的数据，1 ≤ N ≤ 1000 对于100%的数据，1 ≤ N ≤ 100000

输出

一个整数表示答案
样例输入
6
1 3 2 1 2 3
样例输出
3
给定一个数组，只包含1,2,3这三个数，问数组中有多少个三元组下标(i,j,k)，满足a[i]<a[j]<a[k]。 我一开始的想法是，找出所有1,2,3出现的下标，对于每一个1的下标i，去2的下标数组中找一个lowerbound j，然后用j在3的下标数组中找一个lowerbound k，则3的下标数组中k往后的下标都是符合条件的。这需要两层循环，过了90%的数据，然后TLE了。 后来经过大神点拨，要想得到符合条件的三元组，则2一定要在中间，所以我们可以遍历原数组，对于每一个出现的2，用其左边的1的频数乘以其右边3的频数，就是这个2可以构成的合法三元组的个数。 为了不重复计算，我们可以提前算好每个位置左边和右边1和3的频数，到时候直接用left[1]*right[3]就好了。完整代码如下： [cpp] #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; } [/cpp] 本代码提交AC，用时18MS。]]>

LeetCode Find K Closest Elements

Leave a reply

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
给定一个有序数组，要从中找出k个和x最接近的元素，按升序排列输出。 首先在有序数组中用二分查找找到x的lowerbound，如果lowerbound指向begin()，则取开头k个元素即可；如果lowerbound指向end()，则取末尾k个元素；否则，令left指向lowerbound-1，right指向lowerbound，每次取left、right中和x差值最小的那个数，直到取够k个为止。最后对结果数组排序。 完整代码如下： [cpp] 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; } }; [/cpp] 本代码提交AC，用时143MS。]]>

LeetCode Judge Route Circle

Leave a reply

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
一个机器人，初始站在原点(0,0)，UDLR分别表示上下左右，给定一个机器人行走的轨迹字符串，问最终机器人能回到原点吗。 简单题，直接判断走过的水平和垂直方向的差值是否为0，代码如下： [cpp] 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; } }; [/cpp] 本代码提交AC，用时29MS。]]>