29.两数相除
思路:
class Solution {public int divide(int dividend, int divisor) {//考察被除数为最小值的情况if(dividend == Integer.MIN_VALUE){//被除数为最小值,除数是1,返回最小值if(divisor == 1){return Integer.MIN_VALUE;}//除数是-1,产生了溢出,返回最大值if(divisor == -1){return Integer.MAX_VALUE;}}//考察除数为最小值的情况if(divisor == Integer.MIN_VALUE){ //如果被除数是最小值,返回1,否则返回0return dividend == Integer.MIN_VALUE ? 1:0;}//考虑被除数为0的情况if(dividend == 0){return 0;}//将所有正数取相反数,将所有的数都变为负数,避免溢出的问题boolean rev = false;if(dividend > 0){dividend = - dividend;rev = !rev;}if (divisor > 0) {divisor = -divisor;rev = !rev;}List<Integer> candidates = new ArrayList<Integer>();candidates.add(divisor);int index = 0;//注意溢出//不断将Y乘以2,用加法实现,将这些结果放入数组中while(candidates.get(index) >= dividend - candidates.get(index)){ //这里大于是因为都是负数candidates.add(candidates.get(index) + candidates.get(index));++index;}int ans = 0;//对数组进行逆向遍历,遍历到第i项,如果其大于等于X,将答案增加2^i,并将X中减去这一项的值for(int i = candidates.size() - 1; i>= 0;i--){if(candidates.get(i) >= dividend){ans += 1 << i;dividend -= candidates.get(i);}}return rev ? -ans : ans;}
}