Leetcode29.两树相除

题目：29.两树相除
思路：搜索答案，使用二分。题目限定不能使用乘除取模，那么只能使用加减。最基础的想法就是不断的累加除数，直到累加的除数超过被除数时，前一个累加的除数就是结果。这种搜寻的过程可以使用二分方法。最开始的想法是设置一个数n，然后每累加除数（记作b），有n+=n; b+=b; 。然后当超过被除数（记作a）时（a < b），就开始减n。因为当下一次累加除数b会超过被除数a时，答案一定在[n, n+n]内。这样做虽然可以，但又做加法又做减法，过程繁琐=.=。而看题解时，知道可以使用迭代的过程代替减法步骤。让被除数a减去现有的除数b（记作c,c=a-b），那么就变成了求c被初始b整除的值m，又回到了原始的问题了，最后求得的答案就是n+m。
代码：

class Solution {
    public int divide(int dividend, int divisor) {
        long dividendL = Math.abs((long)dividend);
        long divisorL = Math.abs((long)divisor);
        int sign = dividend < 0 && divisor > 0 || dividend > 0 && divisor < 0 ? -1 : 1;
        long t;
        return (t = sign * helper(dividendL, divisorL)) < Integer.MIN_VALUE || t > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int)t;
    }

    private long helper(long a, long b){
        if(a < b) return 0;
        long n = 1, t = b;
        while(a >= (t+t)){
            n += n;
            t += t;
        }
        return n + helper(a - t, b);
    }
}

执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：35.5 MB, 在所有 Java 提交中击败了69.13%的用户

Leetcode29.两树相除

原文：https://www.cnblogs.com/liuyongyu/p/14196945.html