数学

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

到达终点数字(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)。

点赞

发表回复

电子邮件地址不会被公开。必填项已用 * 标注