Skip to content

780. Reaching Points

780. Reaching Points

题目: https://leetcode.com/problems/reaching-points/

难度: Hard

题意:

  1. 给定一个点对(x,y),每次操作可以变换成(x,x+y)或者(x+y,y)
  2. 给定两个点对(sx, sy),和(tx, ty),问能否通过任意次操作,使前一个点对可以变换成后一个点对

思路:

  • 我们反正来,如果得到一个点对(x,y),最有可能是从哪些点对来的
  • 假设tx<ty,反之亦然
  • 那么点对可以从(tx,ty),(tx, ty-tx),(tx,ty-k*tx)。。。得来的
  • 我们可以得出一个递归方式
  • 如果sx>tx,直接返回false,因为sx不管怎么变换,都不能比sx小
  • 如果sx=tx,判断(ty-sy)是否不小于0,并且可以被sx整除
  • 如果sx<tx,那么我们需要判断(sx, sy)和(tx, ty % tx)是否可以变换
  • 这个算法叫做辗转相除法,也叫欧几里得算法,计算最大公约数也是这个算法

解法:

class Solution {
     private boolean solve(int sx, int sy, int tx, int ty) {
        if (tx < ty) {
            if (tx < sx) {
                return false;
            }
            if (tx == sx) {
                if (ty >= sy && (ty - sy) % sx == 0) {
                    return true;
                } else {
                    return false;
                }
            }
            return solve(sx, sy, tx, ty % tx);
        } else {
            if (ty < sy) {
                return false;
            }
            if (ty == sy) {
                if (tx >= sx && (tx - sx) % sy == 0) {
                    return true;
                } else {
                    return false;
                }
            }
            return solve(sx, sy, tx % ty, ty);
        }
    }

    public boolean reachingPoints(int sx, int sy, int tx, int ty) {
        return solve(sx, sy, tx, ty);
    }
}


回到顶部