780.到达终点

发表于： 分类于：
字数： 1009 阅读：≈ 3分钟

🏁 780.到达终点

给定四个整数 sx , sy ，tx 和 ty，如果通过一系列的转换可以从起点 (sx, sy) 到达终点 (tx, ty)，则返回 true，否则返回 false。

从点 (x, y) 可以转换到 (x, x+y) 或者 (x+y, y)。

思路

基本思想

看到题的第一想法就是像遍历二叉树一样遍历每一步所形成的新的坐标，从新的坐标出发，每次可以形成两个下一步的坐标，这就像是二叉树的遍历，只要遍历途中遇到了(tx,ty)那么就一路向上返回true，当某个坐标的x或者y大于tx或者ty时，这一个分支不再向下，这种思路是正确的，但是会超时，因为二叉树太过庞大，所形成的代码为：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    //模仿二叉树的遍历，但是会超时
    public boolean reachingPoints(int sx, int sy, int tx, int ty) {
        return help(sx,sy,tx,ty);
    }
    private boolean help(int left,int right,int tx,int ty){
        if(left==tx&&right==ty){
            return true;
        }
        else if(left>tx||right>ty)
            return false;
        else{
            int sum=left+right;
            return help(sum,right,tx,ty)||help(left,sum,tx,ty);
        }
    }
}

超时之后使用了逆向思维，既然从(sx,sy)到(tx,ty)会超时，那么我们就从(tx,ty)到(sx,sy)，由于(tx,ty)的上一步要么是(sx+sy,sy)，要么是(sx,sx+sy)，相当于要么是x的位置加了一个sy，要么是y的位置加了一个sx，于是我们每次向前返回一步，不再盲目的进行搜索，每次计算出上一步到底是什么，计算的代码为：

1
2
3
4
5

if(tx>ty){
	tx-=Math.max((tx-sx)/ty,1)*ty;
}else{
	ty-=Math.max((ty-sy)/tx,1)*tx;
}

由于要找到上一步，所以需要回退，回退时需要注意，从上一步到当前这一步是由于相加，所以变化的一定是更大的一个，而另外一个不变，例如(3,1)到(3,4)，变化的是这个4，而变化的量就是这个不变的3，所以4-3就可以得到上一步的(3,1)，如果有n步都是y在变化而x不变，那么我们可以通过(tx-sx)/ty或者(ty-sy)/tx来找到x或者y最多变化了几步，这样就可以减少搜索的次数

核心就是从盲目的搜索变成了搜索上一步

执行流程

  1. 从(tx,ty)出发，不停地找上一步是谁
  2. 一旦找到就返回true
  3. 如果当前这一步的上一步小于(sx,sy)，那么就说明从(sx,sy)到达不了(tx,ty)，此时返回false

代码 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public boolean reachingPoints(int sx, int sy, int tx, int ty) {
        while(tx>=sx&&ty>=sy){
            if(tx==sx&&ty==sy)
                return true;
            if(tx>ty){
                //tx比sx大了多少，最多能减去多少个ty
                tx-=Math.max((tx-sx)/ty,1)*ty;
            }else{
                //ty比sy大了多少，最多能减去多少个tx
                ty-=Math.max((ty-sy)/tx,1)*tx;
            }
        }
        return false;
    }
}

总结

主要就是要形成逆向思维，从起点到终点正向求解会出现很多盲目的遍历路径，从而导致超时，所以我们从终点向起点进行遍历，每次向前移动n步，这一步都是确定的，并不是盲目的，从而减小了代码的运行时间，重要的是理解：

1
2
3
4
5

if(tx>ty){
	tx-=Math.max((tx-sx)/ty,1)*ty;
}else{
	ty-=Math.max((ty-sy)/tx,1)*tx;
}