CS-Wiki CS-Wiki
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
  • 刷题模板汇总
  • 一些刷题小技巧
  • 整数 and 位运算

    • 整数理论基础
    • 整数除法
      • 📃 题目描述
      • 🔔 解题思路
        • 暴力
        • 优化
      • 💥 复杂度分析
    • 二进制加法
    • 剑指 Offer 15 - 二进制中 1 的个数
    • 前 n 个数字二进制中 1 的个数
    • 只出现一次的数字
    • 只出现一次的数字II
    • 只出现一次的数字 III
    • 剑指 Offer 39 - 数组中出现次数超过一半的数字
    • 剑指 Offer 16 - 数值的整数次方:快速幂模板
    • 剑指 Offer 43 - 1~n 整数中 1 出现的次数
  • 数组

  • 链表

  • 哈希表

  • 字符串

  • 栈

  • 队列

  • 二叉树

  • 前缀树

  • 二分查找

  • 双指针法

  • 区间求和问题

  • 排序

  • 回溯算法

  • 贪心算法

  • 动态规划

  • 图

  • 数学

  • 自动机

  • 海量数据和空间限制

  • 05-数据结构与算法
  • 整数 and 位运算
小牛肉
2022-03-30
目录

整数除法

# 📃 题目描述

题目链接:

  • 剑指 Offer II 001. 整数除法 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
  • 29. 两数相除 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)

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

注意:

整数除法的结果应当截去(truncate)其小数部分,例如:truncate(8.345) = 8 以及 truncate(-2.7335) = -2 假设我们的环境只能存储 32 位有符号整数,其数值范围是 [−231, 231−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

# 🔔 解题思路

# 暴力

最简单的,不断循环做减法

另外,,int型整数的除法只有一种情况会导致溢出,即 ()(),而最大的正数只有

class Solution {
    public int divide(int a, int b) {
        // 边界条件
        if (a == Integer.MIN_VALUE && b == -1) {
            return Integer.MAX_VALUE;
        }

        // 符号
        int sign = 1;
        if ((a < 0 && b > 0) || (a > 0 && b < 0)) {
            sign = -1;
        }
        
        int res = 0;

        // 全都变成负数做运算,因为最小值的绝对值比最大值的绝对值要大 1
        a = (a > 0) ? -a : a;
        b = (b > 0) ? -b : b;
        

        while (a <= b) {
            a -= b;
            res ++;
        }

        return sign == 1 ? res : -res;
    }
}

时间复杂度 O(N)

# 优化

可以将上述解法稍做调整。当被除数大于除数时,继续比较判断被除数是否大于除数的2倍,如果是,则继续判断被除数是否大于除数的4倍、8倍等。如果被除数最多大于除数的 2^k 倍,那么将被除数减去除数的 2^k 倍,然后将剩余的被除数重复前面的步骤

由于每次将除数翻倍,因此优化后的时间复杂度是

下面以 15/2 为例讨论计算的过程

  • 15大于2,也大于2的2倍(即4),还大于2的4倍(即8),但小于2的8倍(即16),于是先将 15 减去8(2 的 4 倍),还剩余 7。由于减去的是除数的4倍,减去这部分对应的商是 4
  • 接下来对剩余的 7 和除数 2 进行比较,7 大于2,大于2的2倍(即4),但小于2的4倍(即8),于是将 7 减去 4(2的 2 倍),还剩余3。这一次减去的是除数2的2倍,对应的商是 2
  • 然后对剩余的 3 和除数 2 进行比较,3 大于2,但小于2的2倍(即4),于是将3减去2,还剩余 1。这一次减去的是除数的 1 倍,对应的商是 1。
  • 最后剩余的数字是1,比除数小,不能再减去除数了。于是 15/2 的商是 4+2+1,即 7
class Solution {
    public int divide(int a, int b) {
        // 边界条件
        if (a == Integer.MIN_VALUE && b == -1) {
            return Integer.MAX_VALUE;
        }

        // 符号
        int sign = 1;
        if ((a < 0 && b > 0) || (a > 0 && b < 0)) {
            sign = -1;
        }
        
        int res = 0;

        // 全都变成负数做运算,因为最小值的绝对值比最大值的绝对值要大 1
        a = (a > 0) ? -a : a;
        b = (b > 0) ? -b : b;
        
        while (a <= b) {
            // 除数每次翻倍
            int divisor = b;
            // 当前除数的倍数
            int quotient = 1;

            // 代码优化:如果 divisor 已经大于最小值的一半的话,那么退出本次 while 循环
            // 因为这个时候 divisor * 2 肯定会小于最小值,超过了题目给的范围
            while (divisor > Integer.MIN_VALUE >> 1 && a <= divisor + divisor) {
                // 除数翻倍
                quotient += quotient; 
                divisor += divisor;
            }

            res += quotient;
            a -= divisor;
        }

        return sign == 1 ? res : -res;
    }
}

# 💥 复杂度分析

  • 空间复杂度:
  • 时间复杂度:

🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~

帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10
整数理论基础
二进制加法

← 整数理论基础 二进制加法→

最近更新
01
关于编程满天星
02
让我来告诉你 Java 程序员是怎么一步一步从入行到被裁的
06-08
03
Vision Pro,未来已来
06-06
更多文章>
Theme by Vdoing | Copyright © 2019-2023 飞天小牛肉 | 皖ICP备2022008966号
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式