leetcode780. 到达终点
宋标 Lv5
  2022-04-09 16:13:35 2022-04-09 16:13    

题目

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

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

 

示例 1:

输入: sx = 1, sy = 1, tx = 3, ty = 5
输出: true
解释:
可以通过以下一系列转换从起点转换到终点：
(1, 1) -> (1, 2)
(1, 2) -> (3, 2)
(3, 2) -> (3, 5)

示例 2:

输入: sx = 1, sy = 1, tx = 2, ty = 2
输出: false

示例 3:

输入: sx = 1, sy = 1, tx = 1, ty = 1
输出: true  

提示:

  • 1 <= sx, sy, tx, ty <=

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reaching-points

题解

画出树状结构分析，正向计算会出现很多种状态，计算量复杂，本题应从反向计算，即从终点往起点推理。
假设

  • tx>ty
    (tx,ty)的上一个状态便是(tx-ty,ty);
  • tx<ty
    (tx,ty)的上一个状态便是(ty,ty-tx);
  • 至于这里为什么用mod模运算，是考虑存在tx特别小,ty特别大(或者tx特别大，ty特别小)的多次减法的情况，解决这种冗余的运算便是辗转相除法。
  • 结束条件：
    • sx==tx && sy==ty 起点可以到达终点
    • tx==sx时,判断 ty>tx && (ty-sy) % sx == 0 起点是否可以到达终点
    • ty==sy时,判断 tx>ty && (tx-sx) % sy == 0 起点是否可以到达终点
  • 解释：
    • tx==sx时,判断 ty>tx && (ty-sy) % sx == 0，当sx==tx且ty!=sy时，该数的上一个状态只能是(tx,ty-tx),所以ty要大于tx。
    • (ty-sy) % sx == 0时,解决ty大数的情况,如：sx=1,sx=6,tx=1,ty=100000。

递归解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool reachingPoints(int sx, int sy, int tx, int ty){
    if(tx<sx || ty<sy){
        return false;
    }
    if(tx==sx && ty==sy){
        return true;
    }
    if(tx==sx){
        return ty>tx && (ty-tx) % sy == 0;
    }
    if(ty==sy){
        return tx>ty && (tx-ty) % sx == 0;
    }
    if(tx>ty){
        return reachingPoints(sx,sy, tx%ty, ty);
    }
    return reachingPoints(sx,sy, tx, ty%tx);
}
 评论