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

代码语言：javascript复制

#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;
}

不出意外，直接超时

反向搜索

与正向搜索相比，反向搜索虽然同样是指数增长的，但可能要小一些。

代码语言：javascript复制

#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>tytx % ty。

当反向操作不成立的时候，根据tx和ty的情况分别进行判断：

tx=sx且ty=sy，此时已经达到起点，因此存在转换。
tx=sx且ty!=sy，如果此时ty通过减小能够达到sy，则成立；反之不成立。
tx!=sx且ty=sy，同2。
tx!=sx且ty!=sy，则不可能。

代码语言：javascript复制

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;
        }
    }
};

leetcode

0 人点赞