Leetcode 780: 到达终点
目录
Leetcode 780 到达终点
22年4月9日每日一题
题目大意：给定起点(sx,sy)和终点(tx,ty)，询问是否能够通过一系列转换从起点到达终点。 从点(x,y)可以转换到(x+y,y)或者(x,x+y)。
一个初步的想法是动态规划扫一遍，对于给定的范围$0<x,y<n$，这个方法的复杂度为O(n^2)。从结果来看n为10^9，很可能会超时。 另一个简单的想法是直接从源头开始广搜，代价相对来说会小很多，但是仍然是指数增长的，对于超大规模时很可能会超时。
简单BFS
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct Point{
int x,y;
Point(int x, int y){
this->x = x;
this->y = y;
}
};
class Solution {
public:
bool reachingPoints(int sx, int sy, int tx, int ty) {
if(sx>tx || sy>ty){
return false;
}
queue<Point> q;
q.push(Point(sx,sy));
while(!q.empty()){
Point cur_node(q.front());
q.pop();
// 判断是否是
if(cur_node.x == tx && cur_node.y == ty){
return true;
}
// 如果不是，尝试加入
if(cur_node.x+cur_node.y <= tx){
q.push(Point(cur_node.x+cur_node.y,cur_node.y));
}
if(cur_node.x+cur_node.y <= ty){
q.push(Point(cur_node.x,cur_node.x+cur_node.y));
}
}
return false;
}
};
int main(void){
Solution s;
cout<<s.reachingPoints(1,1,2,2)<<endl;
return 0;
}不出意外，直接超时
反向搜索
与正向搜索相比，反向搜索虽然同样是指数增长的，但可能要小一些。
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct Point{
int x,y;
Point(int x, int y){
this->x = x;
this->y = y;
}
};
class Solution {
public:
bool reachingPoints(int sx, int sy, int tx, int ty) {
if(sx>tx || sy>ty){
return false;
}
queue<Point> q;
q.push(Point(tx,ty));
while(!q.empty()){
Point cur_node(q.front());
q.pop();
// 判断是否是
if(cur_node.x == sx && cur_node.y == sy){
return true;
}
// 如果不是，尝试加入
if(cur_node.x-cur_node.y > 0){
q.push(Point(cur_node.x-cur_node.y,cur_node.y));
}
if(cur_node.y-cur_node.x > 0){
q.push(Point(cur_node.x,cur_node.y-cur_node.x));
}
}
return false;
}
};
int main(void){
Solution s;
cout<<s.reachingPoints(1,1,2,2)<<endl;
return 0;
}虽然好一些，但是还是超时。对于部分特别小的结果来说，这个解法仍然不行。 这道题目肯定存在着更优的解法，10^9的限制基本意味着存在线性解。
辗转相除法
官方题解其实与反向方法类似，只是加了优化。 优化的具体操作是在反向操作中，当$tx>ty$时直接将tx的值更新为$tx % ty$。
当反向操作不成立的时候，根据tx和ty的情况分别进行判断：
- tx=sx且ty=sy，此时已经达到起点，因此存在转换。
- tx=sx且ty!=sy，如果此时ty通过减小能够达到sy，则成立；反之不成立。
- tx!=sx且ty=sy，同2。
- tx!=sx且ty!=sy，则不可能。
class Solution {
public:
bool reachingPoints(int sx, int sy, int tx, int ty) {
while (tx > sx && ty > sy && tx != ty) {
if (tx > ty) {
tx %= ty;
} else {
ty %= tx;
}
}
if (tx == sx && ty == sy) {
return true;
} else if (tx == sx) {
return ty > sy && (ty - sy) % tx == 0;
} else if (ty == sy) {
return tx > sx && (tx - sx) % ty == 0;
} else {
return false;
}
}
};