剑指offer001-整数除法

题目

给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。

注意：

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2³¹, 2³¹−1]。本题中，如果除法结果溢出，则返回 2³¹− 1

示例 1：

输入：a = 15, b = 2
输出：7
解释：15/2 = truncate(7.5) = 7

示例 2：

输入：a = 7, b = -3
输出：-2
解释：7/-3 = truncate(-2.33333..) = -2

示例 3：

输入：a = 0, b = 1
输出：0

示例 4：

输入：a = 1, b = 1
输出：1

提示:

-2³¹ <= a, b <= 2³¹ - 1
b != 0

注意：本题与主站 29 题相同：https://leetcode-cn.com/problems/divide-two-integers/

思路

最初的想法是基于二分查找，即a/b=c，我们已知a,b 求c

即b*c=a，c是未知的，我们可以从1-a中二分查找，我们可以统一正负数，用正数去处理

int left = 1;
int right = a;
while (left < right) {
    long mid = left + ((right - left) / 2); // 这边避免溢出
    int t = mid * b;
    if (t > a) {
        right = mid - 1;
    } else if (t < a) {
        left = mid + 1;
    } else {
        return mid;
    }
    return left;
}

很显然，乘法是不能存在的

所以，这边优化乘法计算，快速乘法

比如：5*53，可以将53作为二进制110101，最后计算只要计算5*(100000 + 10000 + 100 + 1)，这里不是十进制的乘法，而是二进制，即对5这个数字，5*（32 + 16 + 4 + 1），只要左移固定的位数就好

private int fastAdd(int x, int y) {
    int ans = 0;
    int step = 0;
    while (y > 0) {
        int l = y & 1; // 记录最后一位
        if (l == 1) { // 只有最后一位是1的时候
            int t = x << step; // 左移 step
            ans += t; // 累加
        }
        step += 1;
        y = y >> 1; // y 右移一位
    }
    return ans;
}

所以整体上，只要替换上面的乘法就好了，即int t = fastAdd(mid, b);

但是出现了一个问题，就是在计算int t = fastAdd(mid, b);的时候t会溢出，在整个二分法的过程中，其实我们不关心mid * b的大小，我们想知道它与a的大小关系

即我们关心mid * b - a > 0 ?

所以改造fastAdd方法

private int fastAdd(int x, int y, int a) {

    int ans = 0;
    int step = 0;
    while (y > 0) {
        int l = y & 1;
        if (l == 1) {
            int t = x << step;
            ans = ans + t;
        }
        step = step + 1;
        y = y >> 1;
        if (ans > a) {
            return 1;
        }
    }
    int delta = ans - a;
    if (delta > 0) {
        return 1;
    } else if (delta < 0) {
        return -1;
    } else {
        return 0;
    }
}

因此上述二分法可以改造为

int left = 1;
int right = a;
while (left <= right) {
    int mid = left + ((right - left) >> 1);
    int t = fastAdd(mid, b, a);
    if (t > 0) {
        right = mid - 1;
    } else if (t < 0) {
        left = mid + 1;
    } else {
        return mid;
    }
}
return left;

结合符号判断等，完成代码

class Solution {
    public int divide(int a, int b) {
        if (a == 0) {
            return 0;
        }
        if (b == 1) {
            return a;
        }
        if (a == Integer.MIN_VALUE && b == -1) {
            return Integer.MAX_VALUE;
        }
        int flag = 1;
        if (a < 0) {
            a = -a;
            flag = -flag;
        }
        if (b < 0) {
            b = -b;
            flag = -flag;
        }
        if (a < b) {
            return 0;
        }
        if (a == b) {
            return flag;
        }
        int left = 1;
        int right = a;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            int t = fastAdd(mid, b, a);
            if (t > 0) {
                right = mid - 1;
            } else if (t < 0) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return flag > 0 ? Math.min(left, right) : -Math.min(left, right);
    }
    private int fastAdd(int x, int y, int a) {

        int ans = 0;
        int step = 0;
        while (y > 0) {
            int l = y & 1;
            if (l == 1) {
                int t = x << step;
                ans = ans + t;
            }
            step = step + 1;
            y = y >> 1;
            if (ans > a) {
                return 1;
            }
        }
        int delta = ans - a;
        if (delta > 0) {
            return 1;
        } else if (delta < 0) {
            return -1;
        } else {
            return 0;
        }
    }
}

这边还是出现了问题，就是一开始输入的时候，系统输入-2147483648，我们一开始就直接转化为2147483648，直接溢出，导致错误。这边查看了其他人的方法，大部分是转为long计算，还有一开始将正数转为负数，直接用负数进行计算

这边觉得转为long可以避免这种情况，用正数做逻辑上比较清晰

代码

class Solution {
    public int divide(int x, int y) {

        long a = (long) x;
        long b = (long) y;
        if (a == 0) {
            return 0;
        }
        if (b == 1) {
            return (int) a;
        }

        if (a == Integer.MIN_VALUE && b == -1) {
            return Integer.MAX_VALUE;
        }

        int flag = 1;
        if (a < 0) {
            a = -a;
            flag = -flag;
        }
        if (b < 0) {
            b = -b;
            flag = -flag;
        }
        if (a < b) {
            return 0;
        }
        if (a == b) {
            return flag;
        }

        long left = 1;
        long right = a;
        while (left <= right) {
            long mid = left + ((right - left) >> 1);
            int t = fastAdd(mid, b, a);
            if (t > 0) {
                right = mid - 1;
            } else if (t < 0) {
                left = mid + 1;
            } else {
                return flag > 0 ? (int) mid : (int) -mid;
            }
        }

        return flag > 0 ? (int) Math.min(left, right) : (int) -Math.min(left, right);
    }
    private int fastAdd(long x, long y, long a) {

        long ans = 0;
        long step = 0;
        while (y > 0) {
            long l = y & 1;
            if (l == 1) {
                long t = x << step;
                ans = ans + t;
            }
            step = step + 1;
            y = y >> 1;
            if (ans > a) {
                return 1;
            }
        }
        int delta = (int) (ans - a);
        if (delta > 0) {
            return 1;
        } else if (delta < 0) {
            return -1;
        } else {
            return 0;
        }
    }
}

1
2
3

解答成功:
执行耗时:1 ms,击败了97.85% 的Java用户
内存消耗:35.5 MB,击败了61.03% 的Java用户

剑指offer001-整数除法

整数除法

剑指offer001-整数除法

题目

思路

代码

FEATURED TAGS

FRIENDS