LeetCode 2019 力扣杯全国秋季编程大赛

示例 1：
输入：guess = [1,2,3], answer = [1,2,3]
输出：3
解释：小A 每次都猜对了。
 
示例 2：
输入：guess = [2,2,3], answer = [3,2,1]
输出：1
解释：小A 只猜对了第二次。

限制：
guess的长度 = 3
answer的长度 = 3
guess的元素取值为 {1, 2, 3} 之一。
answer的元素取值为 {1, 2, 3} 之一。

class Solution {
public:
    int game(vector<int>& guess, vector<int>& answer) {
        int count = 0;
        for(int i = 0; i < 3; ++i)
        {
        	if(guess[i] == answer[i])
        		++count;
        }
        return count;
    }
};

示例 1：
输入：cont = [3, 2, 0, 2]
输出：[13, 4]
解释：原连分数等价于3 + (1 / (2 + (1 / (0 + 1 / 2))))。注意[26, 8], [-13, -4]都不是正确答案。

示例 2：
输入：cont = [0, 0, 3]
输出：[3, 1]
解释：如果答案是整数，令分母为1即可。

限制：
cont[i] >= 0
1 <= cont的长度 <= 10
cont最后一个元素不等于0
答案的n, m的取值都能被32位int整型存下（即不超过2 ^ 31 - 1）。

class Solution {
public:
    vector<int> fraction(vector<int>& cont) {
        int up = 1, down = cont.back(), i;
        for(i = cont.size() - 1; i >= 1; --i)
        {
        	up = down*cont[i-1]+up;
        	swap(up, down);
        }
        return {down, up};
    }
};

示例 1：
输入：command = "URR", obstacles = [], x = 3, y = 2
输出：true
解释：U(0, 1) -> R(1, 1) -> R(2, 1) -> U(2, 2) -> R(3, 2)。

示例 2：
输入：command = "URR", obstacles = [[2, 2]], x = 3, y = 2
输出：false
解释：机器人在到达终点前会碰到(2, 2)的障碍物。

示例 3：
输入：command = "URR", obstacles = [[4, 2]], x = 3, y = 2
输出：true
解释：到达终点后，再碰到障碍物也不影响返回结果。
 

限制：
2 <= command的长度 <= 1000
command由U，R构成，且至少有一个U，至少有一个R
0 <= x <= 1e9, 0 <= y <= 1e9
0 <= obstacles的长度 <= 1000
obstacles[i]不为原点或者终点

class Solution {// 超时 代码
public:
    bool robot(string command, vector<vector<int>>& obstacles, int x, int y) {
        int ax = 0, by = 0;
        unordered_multimap<int,int> m;
        for(auto it = obstacles.begin(); it != obstacles.end(); it++)
        {
        	m.insert(make_pair((*it)[0],(*it)[1]));//建立哈希表
        }
        for(int i = 0; i < command.size(); i++)
        {
        	if(ax > x || by > y)
        		break;//走过了，肯定达到不了终点
        	if(command[i] == 'U')
        		by += 1;
        	else
        		ax += 1;
        	if(ax == x && by == y)
        		return true;//达到终点
            if(i == command.size()-1)
        		i = -1;//循环执行
        	auto range = m.equal_range(ax);
 			auto it = range.first;
        	while(it != range.second)//查找当前坐标是否是障碍物
        	{
        		if(by == (*it).second)
        			return false;
                ++it;
        	}   
        }
        return false;
    }
};

class Solution {
public:
    bool robot(string command, vector<vector<int>>& obstacles, int x, int y) {
        int ax = 0, by = 0, circle, px, py;
        unordered_map<int,unordered_set<int>> m;
        m[0].insert(0);
        for(int i = 0; i < command.size(); i++)
        {
        	if(command[i] == 'U')
        		by += 1;
        	else
        		ax += 1;
        	m[ax].insert(by);//一串指令走过的点
        }
        circle = min(x/ax, y/by);//循环次数
        px = x-ax*circle;
        py = y-by*circle;
        if(!m.count(px) || !m[px].count(py))
            return false;//终点不在路径上
        for(int i = 0; i < obstacles.size(); ++i)
        {
            if(obstacles[i][0] > x || obstacles[i][1] > y)
                continue;//障碍物在终点范围外
            circle = min(obstacles[i][0]/ax, obstacles[i][1]/by);
            px = obstacles[i][0]-ax*circle;
            py = obstacles[i][1]-by*circle;
        	if(m.count(px) && m[px].count(py))
                return false;//路径包含障碍物
        }
        return true;
    }
};