Problems

经典题目

29 Divide Two Integers

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

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

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].

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

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

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

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

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

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

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

1. 处理无理数时，keep 一个 hashmap，防止出现无限循环小数

2. 处理overflow时，比如-2147483648 / -1，-1 / -2147483648，转换成Long类型

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

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.

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

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

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

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);
}