比起动态规划这位更是重量级。数学要求做题的人拥有更加发散的思维,同样地,将一个实际问题抽象成数学问题也是一个难点。一个较难的数学问题不单单是考的数学概念,数学逻辑。同样要求做题者拥有将各个算法融会贯通的能力。
到达终点数字(LeetCode 754)

为了简化问题,我们首先只考虑target>0的情况
同样地做法,拿到一个题没思路的时候我们可以先想一个暴力解法。令i从1开始往后累加,一直加到大于等于target时停止。然后再往回跳,枚举往回跳的次数,注意,这里往回跳时需要让步数*2,因为假如第一步往回跳,那么他的坐标就是-1,往前跳就是1,中间差了2。如果没有能正好等于target的步数,那么就继续往后跳,每跳一次枚举一次往回跳的情况,直到正好等于target为止。
这种暴力枚举的方法用到了贪心的思路,如果要跳最小步数,那么一定是尽量往前跳,万不得已再往回跳的。时间复杂度大约为O(target),从1累加到target是个等差数列,枚举的次数大约为根号target,然后对于往后的每一种情况都要再检查根号target次,最终时间复杂度为O(target)。
那么能不能在上述暴力解法的基础上优化呢?我们可以发现,如果想要往回跳,那么一定是在现有的基础上减去一个偶数的。关于这一点上面已经讲过,读者可以自行体会。那么其实我们就可以排除掉一些不可能的答案了,如果当前步数跟target相差为奇数,那么我们无论选择第几步往回跳一定都是不能跳到target的,所以要继续往前跳,直到与target相差为偶数为止。如果当前步数跟target相差为偶数t,那么我们选择第t/2步往回跳即可。
时间复杂度O(根号target),空间复杂度O(1)。
代码:
class Solution {
public:
int reachNumber(int target) {
int sum = 0;
int i = 1;
target = abs(target);
while(sum < target){
sum += i;
i++;
}
i--;
if(sum == target){
return i;
}
if((sum - target) % 2 == 0){
return i;
}
else{
i++;
while((sum-target)%2 != 0){
sum += i;
i++;
}
}
return i-1;
}
};

到达终点(LeetCode 780)

一道LeetCode的hard题(真的能算得上hard吗)。
按照惯例,先想一个暴力解法。这个题暴力解法非常容易想到,直接dfs一把梭。对于每对sx和sy的下一状态都存在2种可能。有点类似于八皇后问题了。直接dfs一波肯定能得到答案:
class Solution {
public:
bool reachingPoints(int sx, int sy, int tx, int ty) {
if(sx == tx && sy == ty) return true;
if(sx > tx || sy > ty) return false;
return reachingPoints(sx+sy,sy,tx,ty) || reachingPoints(sx,sx+sy,tx,ty);
}
};
空间复杂度是指数级的,而且tx和ty给的10^9,实在太大了,直接搜肯定会爆栈。

不出所料,只能过一半的数据。
如果硬要优化,那就可以用广搜来代替深搜。可以直接双向广搜。从sx、sy向后搜,从tx,ty向前搜。可以优化时间复杂度,但是空间复杂度仍为O(N)。对于这样的数据规模我们是无法接受的。
如何进行优化呢?上述暴力算法不可行的原因是:下一可能的状态实在是太多了。需要想个办法减少状态枚举。再来看看题目,下一状态为(sx+sy,sy)和(sx,sx+sy)。也就是说,对于每一种状态,我们都可以通过相减来枚举前一状态,即(sx-sy,sy),(sx,sy-sx),这样做有一个优点,前一状态的可能性要少很多。因为在状态转换的过程里,永远不会出现负数。所以我们相减的前提是避免负数。因为数据规模是10^9。所以不能一次一次的来减,我们可以直接循环取余,类似于辗转相除。
class Solution {
public:
bool reachingPoints(int sx, int sy, int tx, int ty) {
while(sx < tx && sy < ty){
if(tx < ty){
ty %= tx;
}
else{
tx %= ty;
}
}
if(tx < sx || ty < sy) return false;
return tx == sx ? (ty - sy) % tx == 0 : (tx - sx) % ty == 0;
}
};
时间复杂度为O(log max{tx,ty}),空间复杂度为O(1)。
