Leetcode 780 到达终点 Link to heading

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 Link to heading

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

不出意外,直接超时

反向搜索 Link to heading

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

#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的限制基本意味着存在线性解。

辗转相除法 Link to heading

官方题解其实与反向方法类似,只是加了优化。 优化的具体操作是在反向操作中,当$tx>ty$时直接将tx的值更新为$tx % ty$。

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

  1. tx=sx且ty=sy,此时已经达到起点,因此存在转换。
  2. tx=sx且ty!=sy,如果此时ty通过减小能够达到sy,则成立;反之不成立。
  3. tx!=sx且ty=sy,同2。
  4. 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;
        }
    }
};