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);
    }
}
回到顶部