Problems
经典题目
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;
}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--;
}
}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();
}首先，两点确定一条直线。如果用斜率，则需要一个点和一个斜率。
所以，我们可以先确定一个点，再找另一个点，看在同一直直线上有多少个点。
需要注意的是，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
处理无理数时，keep 一个 hashmap，防止出现无限循环小数
处理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();
}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;
}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);
}Last updated