侧边栏壁纸
博主头像
阿里灰太狼博主等级

You have to believe in yourself . That's the secret of success.

  • 累计撰写 104 篇文章
  • 累计创建 50 个标签
  • 累计收到 12 条评论

目 录CONTENT

文章目录

leetcode-29. 两数相除

阿里灰太狼
2022-09-15 / 0 评论 / 1 点赞 / 722 阅读 / 873 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-09-15,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

29. 两数相除0
29. 两数相除1

JAVA解法

class Solution {
    public int divide(int dividend, int divisor) {
        // 被除数为 0 直接返回结果
        if(dividend == 0){
            return 0;
        }
        // 防止溢出
        if(dividend == Integer.MIN_VALUE && divisor == -1){
            return Integer.MAX_VALUE;
        }
        // 设置一个判断是否异号的标志位,true 则为异号
        boolean flag;
        // 利用异或来判断两个数是否异号
        flag = (dividend ^ divisor) < 0;
        // 将两个数强转为 long 型并取绝对值
        long d = Math.abs((long)dividend);
        long r = Math.abs((long)divisor);
        // 定义存储最终结果的变量
        int result = 0;
        /**
            这里是逆向思维:先把被除数左移 i 位,i 的值从 31 开始递减,
                当 被除数/2^i 的值刚好出现大于等于除数的时候,说明这时
                候要求的商已经出现,并且大于除数的部分就是余数。这时候,
                2^i 就是商,但是此时循环要怎么退出来呢,比较好的方法就
                是控制被除数 d 的值,用 d -= r << i 这个式子让 if 的
                条件 (d >> i) >= r 不满足,for 也就执行到 i < 0 退出。
                最后再根据上边 flag 的正负情况用三目表达式返回结果即可。
         */
        for(int i = 31;i >= 0;i--){
            if((d >> i) >= r){
                d -= r << i;
                result += 1 << i;
            }
        }
        return flag ? -result : result;
    }
}

题解分析

  根据题目的要求,我们先判断被除数是否为 0,若为 0 直接返回结果。由于 Integer.MIN_VALUE/-1 会导致溢出,因此价格判断,若遇到这种情况,则直接返回 Integer.MAX_VALUE。
  设置一个正负标志位,假设为 true 则为负数。巧妙用被除数和除数的异或来与 0 比较,其实这个就单纯判断是否异号,跟异或本身运算结果没多大意义,这里选择异或运算符还是挺可以的。接下来将两个数强转为 long 型并取绝对值,为了防止溢出,用 long 类型来接收,再定义存储最终结果的变量。
  接下来是一个 for 循环,几行代码,但是信息量挺大,功能很强,我赞叹这几行代码现在,一个字就是绝!这里是逆向思维:先把被除数左移 i 位,i 的值从 31 开始递减,当 被除数/2^i 的值刚好出现大于等于除数的时候,说明这时候要求的商已经出现,并且大于除数的部分就是余数。
  这时候,2^i 就是商,但是此时循环要怎么退出来呢,比较好的方法就是控制被除数 d 的值,就是将除数 r 左移 i 位,然后被除数减去此时左移完数值跟被除数相近的除数的值,目的是用 d -= r << i 这个式子让 if 的条件 (d >> i) >= r 不满足,因为被除数 d 被减后的值再右移 i 位后肯定小于除数的(篇幅有限可自行证明,不难),for 也就执行到 i < 0 时成功退出。最后再根据上边 flag 的正负情况用三目表达式返回结果即可。非常巧妙,做题愉快!

leetcode原题:29. 两数相除

1

评论区