首页 > ACM题库 > LeetCode > LeetCode-Divide Two Integers
2014
07-17

LeetCode-Divide Two Integers

Divide two integers without using multiplication, division and mod operator.

原题链接: http://oj.leetcode.com/problems/divide-two-integers/

对于这道题目,因为不能用乘除法和取余运算,我们只能使用位运算和加减法。比较直接的方法是用被除数一直减去除数,直到为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)。

需要注意的是,整数的溢出问题,例如 divide(-2147483648, 2)。我这里问了方便,直接使用了long类型,java代码如下:

public class Solution {
    	 public static int divide(int dividend, int divisor) {
		 return (int)divideL(dividend,divisor);
	 }

	 public static long divideL(long dividend,long divisor){
		 if(divisor == 1) return dividend;
		 if(divisor < 0) return -divideL(dividend, -divisor);
		 if(dividend < 0) return -divideL(-dividend, divisor);
		 if(divisor > dividend) return 0;
		 if(divisor == 0) return Integer.MAX_VALUE;
		 long d = divisor;
		 long bitcnt = 1;
		 long ans = 0;
		 while(d < dividend ){
			 d <<= 1;
			 bitcnt <<= 1;
		 }
		 while(d >= divisor){
			 while(dividend >= d){
				 dividend -= d;
				 ans += bitcnt;
			 }
			 d >>= 1;
			 bitcnt >>= 1;
		 }
		 return ans;
	 }
}

参考:http://blog.csdn.net/linhuanmars/article/details/20024907

 

 


  1. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧

  2. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的