|
2 | 2 |
|
3 | 3 | publicclass_29 { |
4 | 4 |
|
5 | | -publicstaticclassSolution1 { |
6 | | -publicintdivide(intdividend,intdivisor) { |
7 | | -if (divisor ==0 || (dividend ==Integer.MIN_VALUE &&divisor == -1)) { |
8 | | -returnInteger.MAX_VALUE; |
9 | | - } |
10 | | -if (dividend !=Integer.MIN_VALUE |
11 | | - &&Math.abs(dividend) <Math.abs(divisor)) { |
12 | | -return0; |
13 | | - } |
14 | | -if (divisor ==Integer.MIN_VALUE) { |
15 | | -return (dividend ==Integer.MIN_VALUE) ?1 :0; |
16 | | - } |
| 5 | +publicstaticclassSolution1 { |
| 6 | +/** |
| 7 | + * credit: https://leetcode.com/problems/divide-two-integers/solution/ solution 1 |
| 8 | + * <p> |
| 9 | + * Key notes: |
| 10 | + * 1. dividend = Integer.MAX_VALUE and divisor = -1 is a special case which will be handled separately; |
| 11 | + * 2. because within the given range, [-2_31 to 2_31 - 1], every positive integer could be mapped to a corresponding negative integer while the opposite is not true |
| 12 | + * because of the smallest number: Integer.MIN_VALUE = -2147483648 doesn't have one (Integer.MAX_VALUE is 2147483647). So we'll turn both dividend and divisor into negative numbers to do the operation; |
| 13 | + * 3. division, in its essence, is subtraction multiple times until it cannot be subtracted any more |
| 14 | + * <p> |
| 15 | + * Time: O(n) |
| 16 | + * Space: O(1) |
| 17 | + */ |
| 18 | +publicintdivide(intdividend,intdivisor) { |
| 19 | +if (dividend ==Integer.MIN_VALUE &&divisor == -1) { |
| 20 | +returnInteger.MAX_VALUE; |
| 21 | + } |
| 22 | +intnegativeCount =0; |
| 23 | +if (dividend <0) { |
| 24 | +negativeCount++; |
| 25 | + }else { |
| 26 | +dividend = -dividend; |
| 27 | + } |
| 28 | +if (divisor <0) { |
| 29 | +negativeCount++; |
| 30 | + }else { |
| 31 | +divisor = -divisor; |
| 32 | + } |
17 | 33 |
|
18 | | -booleanflag = (dividend <0) ^ (divisor <0); |
19 | | -dividend = -Math.abs(dividend); |
20 | | -divisor = -Math.abs(divisor); |
21 | | -int[]num =newint[40]; |
22 | | -int[]multiple =newint[40]; |
23 | | -num[1] =divisor; |
24 | | -multiple[1] =1; |
25 | | - |
26 | | -for (inti =2;i <32 &&num[i -1] <0; ++i) { |
27 | | -num[i] =num[i -1] <<1; |
28 | | -multiple[i] =multiple[i -1] <<1; |
29 | | - } |
| 34 | +intquotient =0; |
| 35 | +while (dividend <=divisor) { |
| 36 | +dividend -=divisor; |
| 37 | +quotient++; |
| 38 | + } |
| 39 | +if (negativeCount ==1) { |
| 40 | +quotient = -quotient; |
| 41 | + } |
| 42 | +returnquotient; |
| 43 | + } |
| 44 | + } |
30 | 45 |
|
31 | | -intresult =0; |
32 | | -intindex =1; |
33 | | -while (num[index] <0) { |
34 | | - ++index; |
35 | | - } |
36 | | -index -=1; |
| 46 | +publicstaticclassSolution2 { |
| 47 | +/** |
| 48 | + * credit: https://leetcode.com/problems/divide-two-integers/solution/ solution 2 |
| 49 | + * <p> |
| 50 | + * 1. exponetial growth to check to speed up |
| 51 | + * 2. we still turn all numbers into negatives because negatives are a superset of all numbers in the positives. |
| 52 | + * <p> |
| 53 | + * Time: O(log2n) |
| 54 | + * Space: O(1) |
| 55 | + */ |
| 56 | +privatestaticfinalintHALF_INT_MIN =Integer.MIN_VALUE /2; |
37 | 57 |
|
38 | | -while (dividend <=divisor) { |
39 | | -while (dividend <=num[index]) { |
40 | | -result +=multiple[index]; |
41 | | -dividend -=num[index]; |
| 58 | +publicintdivide(intdividend,intdivisor) { |
| 59 | +if (dividend ==Integer.MIN_VALUE &&divisor == -1) { |
| 60 | +returnInteger.MAX_VALUE; |
| 61 | + } |
| 62 | +intnegativeCount =0; |
| 63 | +if (dividend <0) { |
| 64 | +negativeCount++; |
| 65 | + }else { |
| 66 | +dividend = -dividend; |
| 67 | + } |
| 68 | +if (divisor <0) { |
| 69 | +negativeCount++; |
| 70 | + }else { |
| 71 | +divisor = -divisor; |
| 72 | + } |
| 73 | +intquotient =0; |
| 74 | +while (dividend <=divisor) { |
| 75 | +intpowerOfTwo = -1; |
| 76 | +intvalue =divisor; |
| 77 | +while (value >=HALF_INT_MIN &&value +value >=dividend) { |
| 78 | +value +=value; |
| 79 | +powerOfTwo +=powerOfTwo; |
| 80 | + } |
| 81 | +quotient +=powerOfTwo; |
| 82 | +dividend -=value; |
| 83 | + } |
| 84 | +if (negativeCount !=1) { |
| 85 | +quotient = -quotient; |
| 86 | + } |
| 87 | +returnquotient; |
42 | 88 | } |
43 | | - --index; |
44 | | - } |
45 | | -return !flag ?result : -result; |
46 | 89 | } |
47 | | - } |
48 | 90 | } |