[LeetCode]Reaching Points

从题目的意思中就可看出来，给定了root和target，这是一个二叉树找节点的问题，DFS是一个方法，但是考虑到输入的范围，时间复杂度肯定太大，我们需要换一个方法。DP也是一个很容易想到的优化，DP[i][j]表示能否从初始节点达到(i, j)，我们有递推公式：

• DP[i][j] = DP[i - j][j] if i > j
• DP[i][j] = DP[i][j - 1] if j > i

但是因为输入太大显然没有足够的空间。但是这给我们提供了另外一个思路，那就是从target开始去搜root，以为给定的起始和目标点xy轴都是大于0的，那代表如果我们从target回溯找父节点，我们每次找到的是唯一的，只有一种可能，我们要保证父节点的坐标也都大于0。那么从target开始找起始点就可以让时间复杂度大大减小，假设目标节点为(x, y)，时间复杂度为O(max(x, y))，因为最坏的情况可以是(1, 1000000000)，从这个wosrt case来看应该还是过不了所有test case，但是我们先给出代码，之后再考虑优化：

	class Solution {
	public:
	bool reachingPoints(int sx, int sy, int tx, int ty) {
	while (tx > 0 && ty > 0)
	{
	if (tx < sx || ty < sy)return false;
	if (tx == sx && ty == sy)return true;
	if (ty >= tx)ty -= tx;
	else if (tx > ty) tx -= ty;
	}
	return false;
	}
	};

view raw Reaching Points_tle.cpp hosted with ❤ by GitHub

可以看出这个算法的瓶颈在于如果x和y相差的太多，那么时间复杂度还是很高。那么我们完全可以缩短这个过程，不需要y -= x或者x-=y，直接x%=y, y%=x即可，同时注意答案是否在(x, [y % x, y])或者([x, x%y], y)的范围中即可。时间复杂度O(log(max(x, y)))，分析和Euclid Algorithm也即是求GCD的辗转相除法是一样的，具体可以参考这个分析。代码如下：

	class Solution {
	public:
	bool reachingPoints(int sx, int sy, int tx, int ty) {
	while (tx >= 0 && ty >= 0)
	{
	if (tx < sx || ty < sy)return false;
	if (ty > tx)
	{
	ty %= tx;
	if (tx == sx && sy > ty && (sy - ty) % tx == 0)return true;
	}
	else
	{
	tx %= ty;
	if (ty == sy && sx > tx && (sx - tx) % ty == 0)return true;
	}
	}
	return false;
	}
	};

view raw Reaching Points_ac.cpp hosted with ❤ by GitHub