倍增乘法(快速乘法)

所謂倍增乘法，簡(jiǎn)單理解就是每次用被除數(shù)減去[除數(shù)的最大的2x]，這樣可以極大地增加處理的速度。

?/** ? ? * 兩數(shù)相除 ? ? * ? ? * @param dividend 被除數(shù) ? ? * @param divisor 除數(shù) ? ? * @return 商（不包含小數(shù)） ? ? */ ? ?public static int divide(int dividend, int divisor) { ? ? ? ?long result = 0; ? ? ? ?long x = dividend; ? ? ? ?long y = divisor; ? ? ? ?boolean negative = (x < 0 && y > 0) || (x > 0 && y < 0); ? ? ? ?if (x < 0) { ? ? ? ? ? ?x = -x; ? ? ? ?} ? ? ? ?if (y < 0) { ? ? ? ? ? ?y = -y; ? ? ? ?} ? ? ? ?// 由于x/y的結(jié)果肯定在[0,x]范圍內(nèi)，所以對(duì)x使用二分法 ? ? ? ?long left = 0; ? ? ? ?long right = x; ? ? ? ?while (left < right) { ? ? ? ? ? ?long mid = left + right + 1 >> 1; ? ? ? ? ? ?if (quickMulti(mid, y) <= x) { ? ? ? ? ? ? ? ?// 相乘結(jié)果不大于x，左指針右移 ? ? ? ? ? ? ? ?left = mid; ? ? ? ? ? ?} else { ? ? ? ? ? ? ? ?right = mid - 1; ? ? ? ? ? ?} ? ? ? ?} ? ? ? ?result = negative ? -left : left; ? ? ? ?// 判斷是否溢出 ? ? ? ?if (result < Integer.MIN_VALUE || result > Integer.MAX_VALUE) { ? ? ? ? ? ?return Integer.MAX_VALUE; ? ? ? ?} ? ? ? ? ? ? ? ?return (int)result; ? ?} /** ? ? * 快速乘法 ? ? * ? ? * @param a 乘數(shù) ? ? * @param b 被乘數(shù) ? ? * @return 積 ? ? */ ? ?public static long quickMulti(long a, long b) { ? ? ? ?long result = 0; ? ? ? ?while (b > 0) { ? ? ? ? ? ?if ((b & 1) == 1) { ? ? ? ? ? ? ? ?// 當(dāng)前最低位為1，結(jié)果里加上a ? ? ? ? ? ? ? ?result += a; ? ? ? ? ? ?} ? ? ? ? ? ?// 被乘數(shù)右移1位，相當(dāng)于除以2 ? ? ? ? ? ?b >>= 1; ? ? ? ? ? ?// 乘數(shù)倍增，相當(dāng)于乘以2 ? ? ? ? ? ?a += a; ? ? ? ?} ? ? ? ?return result; ? ?}

34 在排序數(shù)組中尋找第一個(gè)和最后一個(gè)位置

? public int[] searchRange(int[] nums, int target) { ? int[] res = new int[] {-1,-1}; ? int n = nums.length; ? ? ? ? ? ?if(n==0) return ?res; ? ? ? ? ? ?if(n==1) { ? ? ? ? ? ? ? ?if(nums[0]==target) return new int[]{0,0}; ? ? ? ? ? ? ? ?else return res; ? ? ? ? ? ?} ? int l =0,r=n-1; ? int mid; ? while(l<r) { ? mid = l+r>>1; ? if(nums[mid]>=target) { ? r = mid; ? }else { ? l = mid+1; ? } ? } ? if(nums[l]==target) { ? res[0] = l; ? } ? while(l<n&&nums[l]==target) { ? res[1] = l; ? ? ? ? ? ? ? ? ?l++; ? } ? return res; ? ?}