文档章节

29. Divide Two Integers - LeetCode

yysue
 yysue
发布于 07/06 20:45
字数 441
阅读 13
收藏 0

Question

29. Divide Two Integers

Solution

题目大意:给定两个数字,求出它们的商,要求不能使用乘法、除法以及求余操作。

思路:说下用移位实现的方法

7/3=2,7是被除数,3是除数
除数左移,假设移动了n次后,移到最接近被除数,这时被除数=被除数-除数,商的一部分为2^n
如果被除数>除数,则继续循环
除数左移,又移动了m次后,移到最接近被除数,这时被除数=被除数-除数,商的一部分为2^m
最后商为2^n+2^m+...

Java实现:

法1:如果可以用除法,一步就可以了

public int divide2(int dividend, int divisor) {    
    // overflows
    if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
    // 给定两个数字,求出它们的商,要求不能使用乘法、除法以及求余操作。
    return dividend / divisor;
}

法2:下面是用减法实现的,执行超时

public int divide2(int dividend, int divisor) {
    // overflows
    if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;

    int ans = 0;
    boolean negative = !((dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0));
    dividend = Math.abs(dividend);
    divisor = Math.abs(divisor);
    dividend -= divisor;
    while (dividend >= 0) {
        ans++;
        dividend -= divisor;
    }
    return negative ? -ans : ans;
}

法3:用移位实现

public int divide(int dividend, int divisor) {
    // 防止溢出
    if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;

    // 获取最终结果的符号
    int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;
    long dvd = Math.abs((long) dividend);
    long dvs = Math.abs((long) divisor);
    int ans = 0;
    while (dvd >= dvs) {
        long tmp = dvs, multiple = 1;
        while (dvd >= (tmp << 1)) {
            tmp <<= 1;
            multiple <<= 1;
        }
        dvd -= tmp;
        ans += multiple;
    }
    return sign == 1 ? ans : -ans;
}

© 著作权归作者所有

共有 人打赏支持
yysue
粉丝 19
博文 217
码字总数 134384
作品 0
济南
程序员
Leetcode日记7

(2015/1/2) LeetCode 318 Maximum Product of Word Lengths 题目: 1)求一个字符串数组中,两个不同的字符串的长度乘积的最大值。 2)这两个字符串不能共同拥有同一个字符。(两个字符串的...

fxdhdu
2016/01/03
48
0
LeetCode 461 Hamming Distance

LeetCode 排列组合 题目汇总 LeetCode 数字 题目汇总 LeetCode 动态规划 题目分类汇总 干货!LeetCode 题解汇总 题目描述 The Hamming distance between two integers is the number of pos...

被称为L的男人
2017/12/10
0
0
Leetcode_Problem 16_3 Sum Closest

题目 问题网址: https://leetcode.com/problems/3sum-closest/description/ 问题描述: Given an array S of n integers, find three integers in S such that the sum is closest to a giv......

quiet_girl
03/09
0
0
Leetcode——Divide Two Integers

题目 Divide two integers without using multiplication, division and mod operator. If it is overflow, return MAXINT. 解体思路 首先明确要求:在此题当中,我们不能使用乘法、除法和取...

wikison
2016/02/29
29
0
LeetCode刷算法题 - 53. Maximum Subarray

写在前面: 程序员分两种,会算法的程序员和不会算法的程序员。几乎没有一个一线互联网公司招聘任何类别的技术人员是不考算法的,程序猿们都懂的,现在最权威流行的刷题平台就是 LeetCode。 ...

蓝色小石头
05/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

vue+element-ui操作删除(单行和批量删除)

页面展示: <template><!-- 表格内容 --><el-table :data="packData" border style="width: 100%" ref="multipleTable" @selection-change="handleSelectionChange"><el-tab......

琴妹
15分钟前
0
0
基于vue(element ui) + ssm + shiro 的权限框架

zhcc 基于vue(element ui) + ssm + shiro 的权限框架 引言 心声 现在的Java世界,各种资源很丰富,不得不说,从分布式,服务化,orm,再到前端控制,权限等等玲琅满目,网上有句话说,语言框架...

DarrenHu_吴邪
22分钟前
2
1
数据库水平切分(MyCat分片)

范围分片 io.mycat.route.function.AutoPartitionByLong 自动范围分片 Function名称:rang-long(配置文件默认) 枚举分片 io.mycat.route.function.PartitionByFileMap 枚举分片 Funtion名称...

这很耳东先生
23分钟前
0
0
读《HeadFirst设计模式》笔记之外观模式

外观模式:提供了一个统一的接口,用来访问子系统中的一群接口。外观定义了一个高层接口,让子系统更容易使用。 举个栗子: 建了一个家庭影院,但是每次享受家庭影院时,你发现需要执行 将灯...

suyain
25分钟前
0
0
MongoDB分片配置

简单注解: mongos 路由进程, 应用程序接入mongos再查询到具体分片,监听端口默认27017 config server 路由表服务, 每一台都具有全部chunk的路由信息 shard为数据存储分片, 每一片都可以是...

LUIS1983
32分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部