LeetCode 780. Reaching Points

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

题意：给定操作可以使点(x,y)变为点(x+y,y)或者点(x,x+y)。现已知初始点(sx,sy)和目标点(tx,ty)，问是否能使用该变换使得(sx，sy)变为(tx,ty)。变换次数不限。\(1\leq sx,sy,tx,ty \leq1e9\)

最简单的方法是BFS，但是数据范围BFS会超时，当tx大于sx时，应该不断从tx中减去ty直到tx不大于sx或者tx不大于ty。反之如果ty比tx大亦然。

class Solution {

public:

	bool reachingPoints(int sx, int sy, int tx, int ty) {

		int cnt = 0;

		while (tx-sx>=ty||ty-sy>=tx) {

			if (tx>ty&&tx>sx)

				tx = tx-(tx - sx)/ ty*ty;

			if (ty>tx&&ty>sy)

				ty = ty - (ty - sy)/ tx * tx ;

		}

		return tx == sx&&ty == sy;

	}

};

巴特西

LeetCode 780. Reaching Points

最新文章

热门文章