# Problems

## 经典题目

[_29 Divide Two Integers_ ](https://leetcode.com/problems/divide-two-integers/description/)

For example, dividend = 15, divisor = 2

Each time, we try to remove k(max) times of divisor(2) from dividend(15), where k \* divisor <= dividend.

First time, 15 - divisor _2_ 2 = 7

Then, 7 - divisor \* 2 = 3

Then, 3 - divisor = 1

```java
public int divide(int dividend, int divisor) {
    // corner case
    if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
    if (dividend == 0) return 0;
    boolean isPos = ((dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0)) ? true : false;
    int res = 0;
    long dvd = Math.abs((long) dividend);
    long dvs = Math.abs((long) divisor);
    while (dvs <= dvd) {
        long tmp = dvs, multiple = 1;
        while (dvd >= (tmp << 1)) {
            tmp <<= 1;
            multiple <<= 1;
        }
        dvd -= tmp;
        res += multiple;
    }
    return isPos ? res : -res;
}
```



[_31 Next Permutation_ ](https://leetcode.com/problems/next-permutation/description/)

First, we observe that for any given sequence that is in descending order, no next larger permutation is possible.

We need to find the first pair of two successive numbers a\[i] and a\[i - 1], from the right, which satisfy a\[i] > a\[i - 1]. Now, all numbers to the right of a\[i - 1] are in descending order, which means no larger permutations is possible for that sequence. So we need to increment a\[i - 1] and we need to pick one number from a\[i] to a\[nums.length - 1] to replace with a\[i - 1]. That would be the first number greater than a\[i - 1] from the right. Then after the replacement, all the numbers to the right of a\[i - 1] still remain descending. So finally, we need to reverse all the numbers from a\[i] to a\[nums.length - 1].

```java
public void nextPermutation(int[] nums) {
    // find the first num in descending order from the tail
    int i = nums.length - 2;
    while(i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }
    if (i >= 0) {
        int j = nums.length - 1;
        while(j >= 0 && nums[j] <= nums[i]) {
            j--;
        }
        swap(nums, i, j);
    }
    reverse(nums, i + 1, nums.length - 1);
}

private void reverse(int[] nums, int start, int end) {
    while(start < end) {
        swap(nums, start, end);
        start++;
        end--;
    }
}
```



[_43 Multiply Strings_ ](https://leetcode.com/problems/multiply-strings/description/)

num\[i] \* num\[j] will be placed at indices `i + j` and `i + j + 1`

```java
public String multiply(String num1, String num2) {
    int n = num1.length(), m = num2.length();
    int[] pos = new int[n + m];
    for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            int cur = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
            int p1 = i + j;
            int p2 = i + j + 1;
            int sum = cur + pos[p2];
            pos[p2] = sum % 10;
            pos[p1] += sum / 10;
        }
    }
    StringBuilder sb = new StringBuilder();
    for (int p : pos) {
        if (!(sb.length() == 0 && p == 0)) {
            sb.append(p);
        }
    }
    return sb.length() == 0 ? "0" : sb.toString();
}
```



[_149 Max Points on a Line_ ](https://leetcode.com/problems/max-points-on-a-line/description/)

首先，两点确定一条直线。如果用斜率，则需要一个点和一个斜率。

所以，我们可以先确定一个点，再找另一个点，看在同一直直线上有多少个点。

需要注意的是，1. 相同的点的时候，即 same X && same Y。2. 直线斜率不存在的时候，即 same Y。3. 一般情况。

```java
class Pair {
    int diffY;
    int diffX;
    Pair (int diffY, int diffX) {
        this.diffY = diffY;
        this.diffX = diffX;
    }
    @Override
    public boolean equals(Object o) {
        if (o == this) return true;
        if (!(o instanceof Pair)) return false;
        Pair pair = (Pair) o;
        return this.diffY == pair.diffY && this.diffX == pair.diffX;
    }
    @Override
    public int hashCode() {
        return Objects.hash(diffY, diffX);
    }
}

public int maxPoints(Point[] points) {
    int res = 0;
    // Every line can be represented as one slope and one point.
    for (int i = 0; i < points.length; i++) {
        Point seed = points[i];
        // Different cases:
        // 1. same point
        // 2. infinite slope (same x)
        // 3. regular slope
        int same = 1;
        int sameX = 0;
        HashMap<Pair, Integer> cnt = new HashMap<>();
        int most = 0;
        for (int j = i + 1; j < points.length; j++) {
            Point tmp = points[j];
            if (tmp.x == seed.x && tmp.y == seed.y) {
                same++;
            } else if (tmp.x == seed.x) {
                sameX++;
            } else {
                // Instead of calculating slope directly (which will cause precision problem)
                // we treat slope as pair ((y2 - y1), (x2 - x1)) and reduce pair by their gcd before inserting into map
                
                int diffY = tmp.y - seed.y;
                int diffX = tmp.x - seed.x;
                
                int gcd = gcd(diffY, diffX);
                
                diffY /= gcd;
                diffX /= gcd;
                
                Pair pair = new Pair(diffY, diffX);
                
                cnt.put(pair, cnt.getOrDefault(pair, 0) + 1);
                most = Math.max(most, cnt.get(pair));
            }
        }
        most = Math.max(most, sameX) + same;
        res = Math.max(res, most);
    }
    return res;
}

private int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a%b);
}
```



[_166 Fraction to Recurring Decimal_ ](https://leetcode.com/problems/fraction-to-recurring-decimal/description/)

1. 处理无理数时，keep 一个 hashmap，防止出现无限循环小数
2. 处理overflow时，比如-2147483648 / -1，-1 / -2147483648，转换成Long类型

```java
public String fractionToDecimal(int numerator, int denominator) {
    StringBuilder sb = new StringBuilder();
    if (numerator < 0 ^ denominator > 0) {
        sb.append('-');
    }
    long nume = Math.abs(Long.valueOf(numerator));
    long deno = Math.abs(Long.valueOf(denominator));
    sb.append(nume / deno);
    long reminder = nume % deno;
    if (reminder == 0) {
        return sb.toString();
    }
    sb.append(".");
    // key: num
    // val: position
    HashMap<Long, Integer> map = new HashMap<>();
    while(reminder != 0) {
        if (map.containsKey(reminder)) {
            int pos = map.get(reminder);
            sb.insert(pos, '(');
            sb.append(')');
            break;
        }
        map.put(reminder, sb.length());
        reminder *= 10;
        sb.append(reminder / deno);
        reminder %= deno;
    }
    return sb.toString();
}
```



[_172 Factorial Trailing Zeroes_ ](https://leetcode.com/problems/factorial-trailing-zeroes/description/)

Because all trailing zeroes are from factors 2 \* 5. We just need to count how many 5s out there. But some number have multiple 5s, like 25 have 2, and 125 have 3, etc.

```java
public int trailingZeroes(int n) {
    if (n == 0) return 0;
    int res = 0;
    while (n > 0) {
        res += n / 5;
        n /= 5;
    }
    return res;
}
```



[_204 Count Primes_](https://leetcode.com/problems/count-primes/description/)

Mark all the evens, multiples of 3, multiples of 5, etc. as true. Then just count how many false are there.

```java
public int countPrimes(int n) {
    if (n <= 1) return 0;
    boolean[] isNotPrime = new boolean[n];
    isNotPrime[0] = true;
    isNotPrime[1] = true;
    int res = 0;
    for (int i = 2; i < n; i++) {
        if (isNotPrime[i]) {
            continue;
        }
        res += 1;
        for (int j = 2; j * i < n; j++) {
            isNotPrime[j * i] = true; 
        }
    }
    return res;
}
```



[_592 Fraction Addition and Subtraction_](https://leetcode.com/problems/fraction-addition-and-subtraction/description/)

```java
public String fractionAddition(String expression) {
    int ansNumerator = 0;
    int ansDenominator = 1;
    int sign = 1;
    if (expression.charAt(0) == '-') {
        sign = -1;
        expression = expression.substring(1);
    }
    for (int i = 0; i < expression.length(); i++) {
        // Get current numerator
        int numerator = 0;
        while (i < expression.length() && Character.isDigit(expression.charAt(i))) {
            numerator *= 10;
            numerator += expression.charAt(i) - '0';
            i++;
        }
        // Get current denominator
        i++;
        int denominator = 0;
        while (i < expression.length() && Character.isDigit(expression.charAt(i))) {
            denominator *= 10;
            denominator += expression.charAt(i) - '0';
            i++;
        }
        // Handle the expression
        ansNumerator = ansNumerator * denominator + sign * numerator * ansDenominator;
        ansDenominator *= denominator;
        // Update the ansNumerator and ansDenominator
        int gcd = gcd(ansNumerator, ansDenominator);
        if (gcd == 0) {
            ansNumerator = 0;
            ansDenominator = 1;
        } else if (gcd < 0) {
            ansNumerator /= (-gcd);
            ansDenominator /= (-gcd);
        } else {
            ansNumerator /= gcd;
            ansDenominator /= gcd;
        }
        // Update sign
        if (i < expression.length()) {
            sign = expression.charAt(i) == '+' ? 1 : -1;
        }
    }
    return ansNumerator + "/" + ansDenominator;
}
private int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a%b);
}
```
