原题链接:http://oj.leetcode.com/problems/divide-two-integers/这道题属于数值处理的题目,对于整数处理的问题,在Reverse
Integer中我有提到过,比较重要的注意点在于符号和处理越界的问题。对于这道题目,因为不能用乘除法和取余运算,我们只能使用位运算和加减法。比较直接的方法是用被除数一直减去除数,直到为0。这种方法的迭代次数是结果的大小,即比如结果为n,算法复杂度是O(n)。那么有没有办法优化呢? 这个我们就得使用位运算。我们知道任何一个整数可以表示成以2的幂为底的一组基的线性组合,即num=a_0*2^0+a_1*2^1+a_2*2^2+...+a_n*2^n。基于以上这个公式以及左移一位相当于乘以2,我们先让除数左移直到大于被除数之前得到一个最大的基。然后接下来我们每次尝试减去这个基,如果可以则结果增加加2^k,然后基继续右移迭代,直到基为0为止。因为这个方法的迭代次数是按2的幂知道超过结果,所以时间复杂度为O(logn)。代码如下:
public int divide(int dividend, int divisor) {
if(divisor==0)
return Integer.MAX_VALUE;
int res = 0;
if(dividend==Integer.MIN_VALUE)
{
res = 1;
dividend += Math.abs(divisor);
}
if(divisor==Integer.MIN_VALUE)
return res;
boolean isNeg = ((dividend^divisor)>>>31==1)?true:false;
dividend = Math.abs(dividend);
divisor = Math.abs(divisor);
int digit = 0;
while(divisor<=(dividend>>1))
{
divisor <<= 1;
digit++;
}
while(digit>=0)
{
if(dividend>=divisor)
{
dividend -= divisor;
res += 1<<digit;
}
divisor >>= 1;
digit--;
}
return isNeg?-res:res;
}
这种数值处理的题目在面试中还是比较常见的,类似的题目有Sqrt(x),Pow(x,
n)等。上述方法在其他整数处理的题目中也可以用到,大家尽量熟悉实现这些问题。
分享到:
相关推荐
The Divide-and-Conquer Strategy
概括 描述了分度和征服顺序蒙特卡罗(DC SMC)的两种实现方式 一个实现中有一个硬编码的特定模型,即上述预印本第5.2节中使用的具有二项式发射模型的分层模型。... (2017) Divide-and-conquer with sequential Monte
前端大厂最新面试题-divide-and-conquer.docx
计算模型与算法技术:4-Divide-and-Conquer.ppt
Finding Maximum Contiguous Subsequence Sum using divide-and-conquer approach
算法设计英文版课件:Chapter 4 The Divide-and-Conquer Strategy.ppt
超稳定超快速分治特征值分解_SuperDC Stable superfast divide-and-conquer eigenvalue decomposition.pdf
具有多项式独立项的半递归分治的显式解_Explicit solution of divide-and-conquer dividing by a half recurrences with polynomial independent term.pdf
python 实现 分治法 (Divide-and-conquer algorithm) 课程设计 代码 包括 Closest Pair Of Points Convex Hull Heaps Algorithm Heaps Algorithm Iterative Inversions Kth Order Statistic Max ...
leetcode双人赛LeetCode 问题分析 本文档总结了 LeetCode 问题的解决方案。 3Sum :首先对数组进行排序,然后创建三个指针 - i指向头部, j指向尾部, k指向枢轴。 if (a[i] + a[k] + a[j]) < 0, i++ else j-- 。...
归并排序:是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即...
A divide-and-conquer approach (DC for short) is adopted to calculate the optimal timetable of a given sequence. It decomposes the given sequences into several independent parts and conquers ...
Programming languages - C - Extensions to support embedded processors.
基于分而治之的行为识别,谭光华,苗瑞,近来深度卷积神经网络在行为识别领域取得了很大的突破。因为连续的视频帧存在大量的冗余信息,相比密集采样,稀疏采样神经网络也
leetcode 答案 【Leetcode】TASK 01: 分治 1.主要思想 ...divide_conquer(problem,param1,param2,...): #不断切分的终止条件 if problem is None: print_result return #准备数据 data=prepare_data(problem)
leetcode刷完300题 leetcode-beginner leetcode算法和数据结构初学者刷题记录 每个人的学习方法不同,找到最...(Divide and Conquer) 二分搜索(Binary Search) Bit (位运算) 刷题编程语言问题:推荐Java,c++,Python。
yarn add divide-up-square-in-parallel-slices 或者 npm install divide-up-square-in-parallel-slices --save 截图 应用程序接口 如前所述,您可以创建与平方面积成比例的平行切片。 computeSquareSlices(dataset...
Divide-and-Conquer-Problem-Solving
divide-by-guides.jsx A photoshop script to help people divide layout by guides 使用方法 打开你的 psd 文件,拉好参考线 双击 divide-by-guides.jsx,确定运行 配置 可以在你打开的 psd 目录下建立 divide.json...