当前位置: 首页> 游戏> 攻略 > 广告设计公司由哪个政府部门管理_宁波网站怎么建设_百度正版下载恢复百度_免费好用的crm软件

广告设计公司由哪个政府部门管理_宁波网站怎么建设_百度正版下载恢复百度_免费好用的crm软件

时间:2025/7/11 22:46:14来源:https://blog.csdn.net/qq_32882309/article/details/143737768 浏览次数:0次
广告设计公司由哪个政府部门管理_宁波网站怎么建设_百度正版下载恢复百度_免费好用的crm软件

本文目录

  • 1 中文题目
  • 2 求解方法:位运算
    • 2.1 方法思路
    • 2.2 Python代码
    • 2.3 复杂度分析
  • 3 题目总结

1 中文题目

给定两个整数,被除数 dividend 和除数 divisor。将两数相除,要求 不使用 乘法、除法和取余运算。

整数除法应该向零截断,也就是截去(truncate)其小数部分。例如,8.345 将被截断为 8 ,-2.7335 将被截断至 -2 。

返回被除数 dividend 除以除数 divisor 得到的

注意:假设环境只能存储 32 位 有符号整数,其数值范围是 [ − 2 31 , 2 31 − 1 ] [−2^{31}, 2^{31} − 1] [231,2311] 。本题中,如果商 严格大于 2 31 − 1 2^{31} − 1 2311 ,则返回 2 31 − 1 2^{31} − 1 2311 ;如果商 严格小于 − 2 31 -2^{31} 231 ,则返回 − 2 31 -2^{31} 231

示例:

输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = 3.33333.. ,向零截断后得到 3
输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = -2.33333.. ,向零截断后得到 -2

提示:

  • − 2 31 ≤ d i v i d e n d , d i v i s o r ≤ 2 31 − 1 -2^{31} \leq dividend, divisor \leq 2^{31} - 1 231dividend,divisor2311
  • divisor != 0

2 求解方法:位运算

2.1 方法思路

方法核心

  • 使用位运算实现除法
  • 通过倍增法快速逼近商

实现步骤

(1)符号处理:

  • 使用异或确定结果符号
  • 将被除数和除数转为正数处理

(2)快速逼近:

  • 使用位运算倍增除数
  • 通过减法求得商

(3)结果处理:

  • 应用正确的符号
  • 处理溢出情况

方法示例

输入:dividend = 10, divisor = 3过程演示:
1. 初始状态:dividend = 10, divisor = 3result = 02. 第一次循环:curr_divisor = 3multiple = 1位运算后:curr_divisor = 6, multiple = 2dividend = 10 - 6 = 4result = 23. 第二次循环:curr_divisor = 3multiple = 1dividend = 4 - 3 = 1result = 34. 结束循环:dividend < divisor返回:3

2.2 Python代码

class Solution:def divide(self, dividend: int, divisor: int) -> int:# 处理特殊情况INT_MIN, INT_MAX = -2**31, 2**31 - 1# 处理除数为0的情况if divisor == 0:return INT_MAX# 处理溢出情况if dividend == INT_MIN and divisor == -1:return INT_MAX# 记录结果的符号# 异或运算:相同为0,不同为1sign = -1 if (dividend > 0) ^ (divisor > 0) else 1# 将被除数和除数都转为正数dividend = abs(dividend)divisor = abs(divisor)# 结果result = 0# 使用位运算优化while dividend >= divisor:# 当前除数curr_divisor = divisor# 当前商(从1开始)multiple = 1# 快速逼近# dividend >= curr_divisor << 1 确保不会溢出while dividend >= (curr_divisor << 1) and (curr_divisor << 1) > 0:curr_divisor <<= 1  # 除数左移一位(乘2)multiple <<= 1      # 商左移一位(乘2)# 减去当前最大的可能值dividend -= curr_divisor# 添加到结果中result += multiple# 应用符号并处理溢出result = -result if sign == -1 else result# 确保结果在32位整数范围内if result > INT_MAX:return INT_MAXif result < INT_MIN:return INT_MINreturn result

2.3 复杂度分析

  • 时间复杂度:O(log n),n是被除数的大小
    • 每次循环被除数至少减半
  • 空间复杂度:O(1)
    • 只使用常数级别的额外空间

3 题目总结

题目难度:中等
数据类型:整数
应用算法:位运算

关键字:广告设计公司由哪个政府部门管理_宁波网站怎么建设_百度正版下载恢复百度_免费好用的crm软件

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: