[LeetCode]Reach a Number

Brute Force做法BFS，每次都可以朝两个方向搜索。时间复杂度O(2^d), d为搜索的深度，显然TLE。DP也不太可行，如果我们用dp[i][k]表示能否在步长为k的时候到达i，那么dp[i][k]的值是取决于i的两边的点的，这样我们并不好通过子问题构建出更大的问题。所以我们还是尝试math的解法，也就是推导出解的公式。这道题要求的是从[1, k]的范围中找出一部分的数，前面加上负号，从而让sum(-/+1, -/+k)的值为输入的n。当然k要满足条件sum(1, k) >= n。假设m满足条件sum(1, m)为大于n的最小值：

1. 如果diff = sum(1, m) - n为偶数，那么diff / 2为整数，我们一定可以在[1,k]中找到一部分数其和为diff / 2，这样可以让和变为n。 所以k步即可。
2. 如果diff = sum(1, m) - n为奇数，那么我们找不到这样的集合改符号后让和变为n。所以我们再加上m + 1
• 如果m为偶数，m + 1为奇数，diff = sum(1, m + 1) - n为偶数，变为情况1。所以需要k + 1步
• 如果m为奇数，m + 1为奇数，diff = sum(1, m + 1) - n仍然为奇数。那我们再加上m + 2，这又变为上面的情况了。需要k + 2步。

序列1+ 2 + 3 + ... + m = m * (m + 1) / 2 <= n，所以时间复杂度为O(sqrt(n))，代码如下：

	class Solution {
	public:
	int reachNumber(int target) {
	target = abs(target);
	int k = 0, sum = 0;
	while (sum < target)sum += ++k;
	if (sum == target)return k;
	return (sum - target) % 2 ? k + 1 + k % 2 : k;
	}
	};

view raw Reach a Number.cpp hosted with ❤ by GitHub