当前位置: 首页 > news >正文

LCR 001 两数相除

一.题目:
. - 力扣(LeetCode)
二.原始解法-超时:
class Solution:
    def divide(self, a: int, b: int) -> int:
        # 1)分析:
        # 除法计算,不能使用除法符号,可以理解为实现除法
        # 除法原理是减法次数,a/b可以理解为a-b重复多次至结果小于0,假设此时余数为c
        # 由于注意事项第一点已说明直接截取余数部分保留整数,返回重复次数即可,如果a,b正负不同,返回负数,否则返回正数
        # 如果返回结果不在[−231, 231−1]范围,则返回231 − 1
        # 2)判断输入有效性
        if b == 0:
            return
        ## 这里有一个易忘记知识点:python内置函数-幂计算x的n次方为x ** n
        if a < -2 ** 31 or a > 2 ** 31 - 1 or b < -2 ** 31 or b > 2 ** 31 - 1:
            return
        if a == 0:
            return 0
        # 3)判断返回符号:
        if a > 0 and b < 0 or a < 0 and b > 0:
            symbol = -1
        else:
            symbol = 1
        # 4) 使用while循环计算,按绝对值计算除法
        ## 这里有一个易忘知识点:python内置函数-绝对值为abs(-x)=x
        current_a = abs(a)
        abs_b = abs(b)
        result = 0
        while current_a - abs_b >= 0:
            current_a = current_a - abs_b # 被除数刷新为差
            result += 1
        # 5)赋值符号
        result = -result if symbol == -1 else result
        # 6)判断结果溢出
        if result < -2 ** 31 or result > 2 ** 31 - 1:
            return 2 ** 31 - 1
        else:
            return result
三.正确解法及好的讲解、力扣解法参考:
好的讲解:《剑指 Offer》专项突破版 - 面试题 1 : 整数除法_输入2个int型整数,它们进行除法计算并返回商-CSDN博客
Python实现易于理解版本: . - 力扣(LeetCode)
四.对这个标准解法自己的消化分析:
首先被除数和除数的边界在 [−2 31 , 2 31 −1]范围中,题目描述中提到溢出情况,就是指商的数值超出了这个范围,那么什么情况下商会超出这个范围呢?可以把这个范围画到数轴上看一下,如下图:
上面这个图红色箭头表示超出范围的数值部分,推出了两种可能的不等式组,即
当商x<=0时,|x|>-a 或者 当商x>=0时,|x|>b。这两个不等式如果至少要成立一个,就得满足|x|大于-a和b的最小值,如果连这个条件都不满足,那么这个不等式组是不成立的。即|x|>min( 2 31 2 31 −1 ),也就是|x|> 2 31 −1,那么为什么要用|x|而不是直接用x判断呢,因为除法的符号是根据除数和被除数是否符号一致判断的,为了使分析简单,可以先忽略符号。那么知道了溢出时候商x的最小值,看下当被除数和除数满足这个范围 [−2 31 , 2 31 −1] 时,是否会出现一个商处于这个溢出范围,也就是商的绝对值比 2 31 −1大,即|x|> 2 31 −1;
因为这是整数除法,所以商的绝对值一定小于被除数,又得到一个不等式:|a|/|b|=x且a、b皆为整数则|x|<|a|,再结合上面的结论,可以推出|x|的取值范围: 2 31 −1 < |x|<|a|,那么是否存在这种情况呢?只要判断是否存在 2 31 −1< |a|,有的,当|a|= 2 31 时,此时如果|b|=1,那么|x| = 2 31 了。
那么就是a = 2 31 时,b=1或-1;或a=- 2 31 时,b=1或-1,但是因为a的范围在 [−2 31 , 2 31 −1]之间,所以只有一种可能, a=- 2 31 ,b=-1结果是此时商会溢出,需要特殊处理。那么就在初始化的时候拦截这种输入,直接处理特殊场景即可,边界问题分析完了,现在看非特殊场景下求商绝对值的算法(刚才说了,商的符号先放到一边不考虑)
上面我的原始解法是最直观的根据除法的原理是减法来计算的,但是超时了,因为极端情况下当被除数为 2 31 −1,除数为1时,需要减 2 31 −1次,计算次数太多了。那么有没有简单办法呢?可以考虑刚才说的这种极端情况,如果每次减的不是除数,而是除数的N倍,然后商再加上这个N倍,就相当于减少了计算次数,其实就是利用除数膨胀N倍的时候,商会缩小N倍,这个N最好是2的n次方,这样计算次数就更少了。也就是说,用a和b的 2 31 倍数比较,如果a比这个小,就减少倍数为2的30次,这样一直减少到a比b扩大2的某次方要大,说明a-b一定大于2的某次方,那么a除以b的2的某次方的商一定大于1,也就是a除以b一定大于商乘以2的某次放,举个例子:17/1=17,如果用原始减法算,需要计算17次,如果用17-1*2的4次方,发现此时差大于0,那么17/1的商一定大于2的4次方,因为17就是比1大那么多倍,即商=16,然后计算17-1*2的4次方=1,此时差=除数,商再加1直到差<除数。即上面力扣解法中的这部分核心代码:
temp是2的n次方的n,从31次方开始倒推,只要a比b*2的n次方大,a就减去当前被扩大了的除数(其实还是用了除法的原理是减法,只是除数膨胀了),quo是商,当除数膨胀了的时候,商也要膨胀,因为计算次数被减少了,膨胀的数值就是b扩大的倍数
同时这道题扩大n倍由于题目要求不能使用乘法,只能使用位移,Python中的左移<<就是扩大2的n次方,又因为要判断a,b的输入值处理溢出,需要了解python中2的n次方运算符是**
五.实现如下:
class Solution:
    def divide(self, a: int, b: int) -> int:
        # 处理a,b是否在题目范围,及除数是否为0非法,退出计算
        if a < -2**31 or a > 2**31 +1 or b < -2**31 or b > 2**31 +1 or b == 0:
            return
        # 处理会导致商溢出的情况 a=-2**31,b=1或-1,直接按题目要求返回溢出默认值
        if a == -2**31 and b == -1:
            return 2**31 - 1
        # 处理被除数为0,直接返回0
        if a == 0:
            return 0
        # 处理非特殊情况,先简化除法为绝对值,flag为商的符号,然后a,b取绝对值
        flag = True if (a > 0 and b > 0) or (a < 0 and b <0) else False
        a,b = abs(a),abs(b)
        # temp为2的n次幂的n,即除数左移位数,初始化为题目最大值31,quo为商,当temp为最大值时,商初始化为最小值0
        temp,quo = 31,0
        # 开始用除法原理减法+除数倍数膨胀计算
        while temp >= 0:
            if a >= b << temp:#此时可以处理商和被除数了
                a -= b << temp
                quo += 1 << temp
            temp -= 1
       
        # 计算完成,给商赋符号
        if not flag:
            quo = -quo
        return quo

相关文章:

LCR 001 两数相除

一.题目&#xff1a; . - 力扣&#xff08;LeetCode&#xff09; 二.原始解法-超时&#xff1a; class Solution: def divide(self, a: int, b: int) -> int: # 1&#xff09;分析&#xff1a; # 除法计算&#xff0c;不能使用除法符号&#xff0c;可以理解为实现除法 # 除法…...

数据库、数据仓库、数据湖、数据中台、湖仓一体的概念和区别

数据库、数据仓库、数据湖、数据中台和湖仓一体是数据管理和分析领域的不同概念&#xff0c;各自有不同的特点和应用场景。以下是它们的主要区别&#xff1a; 1. 数据库&#xff08;Database&#xff09; 定义&#xff1a;结构化的数据存储系统&#xff0c;用于高效地存储、检…...

vue 的生命周期函数

Vue 生命周期函数&#xff08;生命周期钩子&#xff09;是 Vue 实例从创建到销毁过程中&#xff0c;不同阶段所触发的特定函数。理解这些生命周期函数对于开发 Vue 应用至关重要&#xff0c;因为它们让你在不同的生命周期阶段执行代码&#xff0c;比如数据初始化、DOM 渲染完成…...

单片机UART协议相关知识

概念 UART&#xff08;Universal Asynchronous Receiver/Transmitter&#xff0c;通用异步收发传输器&#xff09; 是一种 异步 串行 全双工 通信协议&#xff0c;用于设备一对一进行数据传输&#xff0c;只需要两根线&#xff08;TX&#xff0c;RX&#xff09;。 异步&…...

【操作系统不挂科】<CPU调度(13)>选择题(带答案与解析)

前言 大家好吖&#xff0c;欢迎来到 YY 滴 操作系统不挂科 系列 &#xff0c;热烈欢迎&#xff01; 本章主要内容面向接触过C的老铁 本博客主要内容&#xff0c;收纳了一部门基本的操作系统题目&#xff0c;供yy应对期中考试复习。大家可以参考 本章为选择题题库&#xff0c;试…...

OpenCV笔记:图像去噪对比

图像去噪对比 1. 均值滤波&#xff08;Mean Filtering&#xff09; 方法&#xff1a;用像素周围的像素平均值替换每个像素值。适用场景&#xff1a;适用于去除随机噪声&#xff0c;如在不强调图像细节的场景中&#xff0c;如果图像细节较多时&#xff0c;可能会导致图像模糊。…...

A-B数对(二分查找)

#include<bits/stdc.h> using namespace std;using ll long long;int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n,c;cin>>n>>c;int nu[200000];for(int i0;i<n;i){cin>>nu[i]; // 输入数组元素}sort(nu,nun);ll cnt0; // 统计满…...

Vue 的各个生命周期

详解 Vue 的各个生命周期 文章目录 详解 Vue 的各个生命周期Vue 组件的生命周期1.1 创建阶段示例&#xff1a; 1.2 挂载阶段示例&#xff1a; 1.3 更新阶段示例&#xff1a; 1.4 销毁阶段示例&#xff1a; 生命周期总结生命周期钩子对比表参考链接 Vue 组件的生命周期 在 Vue …...

实现简易计算器 网格布局 QT环境 纯代码C++实现

问题&#xff1a;通过代码完成一个10以内加减法计算器。不需要自适应&#xff0c;界面固定360*350。 ""按钮90*140&#xff0c;其它按钮90*70。 参考样式 #define DEFULT_BUTTON_STYLE "\ QPushButton{\color:#000000;\border:1px solid #AAAAAA;\border-radi…...

后端开发详细学习框架与路线

&#x1f680; 作者 &#xff1a;“码上有前” &#x1f680; 文章简介 &#xff1a;后端开发 &#x1f680; 欢迎小伙伴们 点赞&#x1f44d;、收藏⭐、留言&#x1f4ac; 为帮助你合理安排时间&#xff0c;以下是结合上述学习内容的阶段划分与时间分配建议。时间安排灵活&a…...

2.langchain中的prompt模板 (FewShotPromptTemplate)

本教程将介绍如何使用 LangChain 库中的 PromptTemplate 和 FewShotPromptTemplate 来构建和运行提示&#xff08;prompt&#xff09;&#xff0c;并通过示例数据展示其应用。 安装依赖 首先&#xff0c;确保你已经安装了 langchain 和相关依赖&#xff1a; pip install lan…...

FairGuard游戏加固实机演示

此前&#xff0c;FairGuard对市面上部分游戏遭遇破解的案例进行了详细分析&#xff0c;破解者会采用静态分析与动态调试相结合的手段&#xff0c;逆向分析出代码逻辑并对其进行篡改&#xff0c;实现作弊功能&#xff0c;甚至是对游戏资源文件进行篡改&#xff0c;从而制售外挂。…...

Spark使用过程中的 15 个常见问题、详细解决方案

目录 问题 1&#xff1a;Spark 作业超时问题描述解决方案Python 实现 问题 2&#xff1a;内存溢出问题描述解决方案Python 实现 问题 3&#xff1a;Shuffle 性能问题问题描述解决方案Python 实现 问题 4&#xff1a;Spark 作业调度不均问题描述解决方案Python 实现 问题 5&…...

算法【最长递增子序列问题与扩展】

本文讲解最长递增子序列以及最长不下降子序列的最优解&#xff0c;以及一些扩展题目。本文中讲述的是最优解&#xff0c;时间复杂度是O(n*logn)&#xff0c;空间复杂度O(n)&#xff0c;好实现、理解难度不大。这个问题也可以用线段树来求解&#xff0c;时间和空间复杂度和本节讲…...

k8s篇之flannel网络模型详解

在 Kubernetes (K8s) 中,Flannel 是一种常用的网络插件,用于实现容器之间的网络通信。Flannel 提供了一种覆盖网络(Overlay Network)模型,使得容器可以跨多个主机进行通信。 以下是 Flannel 在 Kubernetes 中的详细工作原理和覆盖网络模型的详解: 1.Flannel 简介 Flann…...

windows 和 linux检查操作系统基本信息

windows检查操作系统基本信息 systeminfolinux检查操作系统基本信息 获取系统位数 getconf LONG_BIT查询操作系统release信息 lsb_release -a查询系统信息 cat /etc/issue查询系统名称 uname -a...

Oracle OCP认证考试考点详解082系列22

题记&#xff1a; 本系列主要讲解Oracle OCP认证考试考点&#xff08;题目&#xff09;&#xff0c;适用于19C/21C,跟着学OCP考试必过。 105. 第105题&#xff1a; 题目 解析及答案&#xff1a; 题目翻译&#xff1a; 关于Oracle数据库中的事务请选择两个正确的陈述&#xf…...

线性回归 - 最小二乘法

线性回归 一 简单的线性回归应用 webrtc中的音视频同步。Sender Report数据包 NTP Timestamp&#xff08;网络时间协议时间戳&#xff09;&#xff1a;这是一个64位的时间戳&#xff0c;记录着发送SR的NTP时间戳&#xff0c;用于同步不同源之间的时间。RTP Timestamp&#xff1…...

Linux - 线程基础

文章目录 1.什么是线程2.线程vs进程3.线程调度4.线程控制4.1 POSIX线程库4.2创建线程4.3线程终止4.4线程等待4.5线程分离 5、线程封装 1.什么是线程 在Linux操作系统中&#xff0c;线程是进程内部的一个执行流。在Linux操作系统下&#xff0c;执行流统称为轻量级进程&#xff0…...

网络爬虫——分布式爬虫架构

分布式爬虫在现代大数据采集中是不可或缺的一部分。随着互联网信息量的爆炸性增长&#xff0c;单机爬虫在性能、效率和稳定性上都面临巨大的挑战。分布式爬虫通过任务分发、多节点协作以及结果整合&#xff0c;成为解决大规模数据抓取任务的核心手段。 本节将从 Scrapy 框架的…...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造&#xff0c;完美适配AGV和无人叉车。同时&#xff0c;集成以太网与语音合成技术&#xff0c;为各类高级系统&#xff08;如MES、调度系统、库位管理、立库等&#xff09;提供高效便捷的语音交互体验。 L…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

20个超级好用的 CSS 动画库

分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码&#xff0c;而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库&#xff0c;可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画&#xff0c;可以包含在你的网页或应用项目中。 3.An…...

MySQL JOIN 表过多的优化思路

当 MySQL 查询涉及大量表 JOIN 时&#xff0c;性能会显著下降。以下是优化思路和简易实现方法&#xff1a; 一、核心优化思路 减少 JOIN 数量 数据冗余&#xff1a;添加必要的冗余字段&#xff08;如订单表直接存储用户名&#xff09;合并表&#xff1a;将频繁关联的小表合并成…...

接口自动化测试:HttpRunner基础

相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具&#xff0c;支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议&#xff0c;涵盖接口测试、性能测试、数字体验监测等测试类型…...

Razor编程中@Html的方法使用大全

文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...