[LeetCode] 780. Reaching Points

2022-05-27 16:49:30
This post is also available in English and alternative languages.

题目大意

  • 给定源点 $(x_s, y_s)$ 和目标点 $(x_t, y_t)$
  • 定义点的移动方式 $P(x, y) \rightarrow P’(x+y, y)$ 和 $P(x, y) \rightarrow P’(x, x+y)$
  • 数据范围:$1 <= sx, sy, tx, ty <= 10^9$

问:源点经过任意次位移,是否有可能到达目标点?

分析

  • 从数据范围来看,显然是不允许暴力搜索求解的。因此,这是一道巧妙的数学题(或者脑筋急转弯)。
  • 两点都位于第一象限,$x, y$ 均为正整数,因此可以排除所有 $x_s > x_t$ 和 $y_s > y_t$ 的情况。
  • 根据移动方式可知,将 $P’(x, y)$ 中的较大值对对方取模,即可退回上个状态 $P(x_0, y_0)$。(这里思路不是很严谨)
    • $P’(x_1, y_0) = P’(x_0 + n\times y_0, y_0)$
    • $P’(x_0, y_1) = P’(x_0, x_0 + n\times y_0)$

求解

递归搜索的思路很简单,但会因为递归次数过多而栈溢出或因为搜索空间过大而超时。

1
2
3
4
5
6
7
bool reachingPoints(int sx, int sy, int tx, int ty) {
if (sx > tx || sy > ty)
return false;
if (sx == tx && sy == ty)
return true;
return reachingPoints(sx + sy, sy, tx, ty) || reachingPoints(sx, sx + sy, tx, ty);
}

根据点的状态转移关系,我们可以将目标点尽量逼近源点,然后只需对剩下一个轴坐标做判断即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool reachingPoints(int sx, int sy, int tx, int ty) {
if (sx > tx || sy > ty)
return false;

while (sx < tx && sy < ty) {
if (tx < ty)
ty %= tx;
else
tx %= ty;
}

// 每次循环只进行一次操作,因此循环结束时分两种情况
// 1. sx == tx:由于两点 x 不变,合法解只存在 ty = sy + n * sx
// 2. sy == ty:由于两点 y 不变,合法解只存在 tx = sx + n * sy
return (sx == tx && (ty - sy) % sx == 0) || (sy == ty && (tx - sx) % sy == 0);
}
Prev
2022-05-27 16:49:30
Next