Number & Bit questions
- Single Number
- Single Number II
- Single Number III
- Single Number IV
- Majority Number
- Majority Number II
- Majority Number III
Subarray questions
Always using the idea of 前缀和.
- Best Time to Buy and Sell Stock - 贪心法
- Best Time to Buy and Sell Stock II
- Best Time to Buy and Sell Stock III
- Maximum Subarray
- Minimum Subarray
- Maximum Subarray II
- Subarray with 0 Sum
- Subarray with Particular Sum
- Subarray with Sum Closest
N Sum questions
- Two Sum - difficult
- 3 Sum
- 3 Sum Closest
- 4 Sum - doing a O(n3) solution is good enough.
- k sum questions are basically solved with O(nk-1) time. Faster solution is available but too complex.
L 家最爱
Additional questions
Code
Number questions
Single Number
public int singleNumber(int[] A) {
int x = 0;
for (Integer a: A) {
x = x ^ a;
}
return x;
}
Single Number II
Last time, I used an array of size 32 to store count, but it’s actually not necessary.
public int singleNumber(int[] A) {
int ans = 0;
for (int i = 0; i < 32; i++) {
int count = 0;
for (Integer a: A) {
count += ((a >> i) & 1);
}
ans |= (count % 3) << i;
}
return ans;
}
Subarray questions
Best Time to Buy and Sell Stock
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
int min = prices[0];
int profit = 0;
for (Integer p: prices) {
min = Math.min(min, p);
profit = Math.max(profit, p - min);
}
return profit;
}
Best Time to Buy and Sell Stock II
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
int pre = prices[0];
int profit = 0;
for (Integer p: prices) {
if (p > pre) {
profit += p - pre;
}
pre = p;
}
return profit;
}
Best Time to Buy and Sell Stock III
It’s important to note the 2nd last line of the code, where we consider the corner case of doing only 1 transaction.
It’s always best to list a simple test case and walk it thru before submitting the code.
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
int len = prices.length;
int[] dpLeft = new int[len];
int leftMin = prices[0];
for (int i = 1; i < len; i++) {
dpLeft[i] = Math.max(dpLeft[i - 1], prices[i] - leftMin);
leftMin = Math.min(leftMin, prices[i]);
}
int[] dpRight = new int[len];
int rightMax = prices[len - 1];
for (int i = len - 2; i >= 0; i--) {
dpRight[i] = Math.max(dpRight[i + 1], rightMax - prices[i]);
rightMax = Math.max(rightMax, prices[i]);
}
// now iterate the 2 DP array and find out the largest possible profit
int profit = 0;
for (int i = 0; i < len - 1; i++) {
profit = Math.max(profit, dpLeft[i] + dpRight[i + 1]);
}
int oneTransaction = Math.max(dpLeft[len - 1], dpRight[0]);
return Math.max(profit, oneTransaction);
}
Maximum Subarray
public int maxSubArray(int[] A) {
if (A == null || A.length == 0) {
return 0;
}
int max = Integer.MIN_VALUE;
int pre = 0;
// the largest sum ending at previous position in the array
for (Integer a: A) {
max = Math.max(max, pre + a);
pre = Math.max(0, pre + a);
}
return max;
}
3Sum questions
Two Sum
This solution is O(nlgn) time.
Alternatively, we can use HashMap to solve this problem with O(n) time.
public int[] twoSum(int[] numbers, int target) {
// write your code here
int[] ans = new int[2];
if (numbers == null || numbers.length == 0) {
return ans;
}
int len = numbers.length;
Pair[] pairs = new Pair[len];
for (int i = 0; i < len; i++) {
pairs[i] = new Pair(numbers[i], i + 1);
}
Arrays.sort(pairs);
int left = 0;
int right = len - 1;
while (left < right) {
if (pairs[left].num + pairs[right].num == target) {
ans[0] = pairs[left].index;
ans[1] = pairs[right].index;
Arrays.sort(ans);
break;
} else if (pairs[left].num + pairs[right].num > target) {
right--;
} else {
left++;
}
}
return ans;
}
class Pair implements Comparable<Pair> {
int num;
int index;
public Pair(int a, int b) {
num = a;
index = b;
}
public int compareTo(Pair another) {
return this.num - another.num;
}
}
3 Sum
public ArrayList<ArrayList<Integer>> threeSum(int[] numbers) {
ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
if (numbers == null || numbers.length == 0) {
return ans;
}
Arrays.sort(numbers);
int len = numbers.length;
for (int i = 0; i < len; i++) {
if (i > 0 && numbers[i - 1] == numbers[i]) {
continue;
}
int left = i + 1;
int right = len - 1;
// find 2 numbers that sums to - number[i]
while (left < right) {
int diff = numbers[left] + numbers[right] + numbers[i];
if (diff == 0) {
ArrayList<Integer> triplet = new ArrayList<Integer>();
triplet.add(numbers[i]);
triplet.add(numbers[left]);
triplet.add(numbers[right]);
ans.add(triplet);
}
if (diff <= 0) {
left++;
while (left < len && numbers[left - 1] == numbers[left]) {
left++;
}
}
if (diff >= 0) {
right--;
while (right >= 0 && numbers[right + 1] == numbers[right]) {
right--;
}
}
}
}
return ans;
}
3 Sum Closest
public int threeSumClosest(int[] numbers, int target) {
if (numbers == null || numbers.length == 0) {
return 0;
}
Arrays.sort(numbers);
int sum = 0;
int diff = Integer.MAX_VALUE;
int len = numbers.length;
for (int i = 0; i < len; i++) {
int left = i + 1;
int right = len - 1;
while (left < right) {
int triple = numbers[left] + numbers[right] + numbers[i];
if (triple == target) {
return target;
} else if (triple < target) {
left++;
} else {
right--;
}
if (Math.abs(target - triple) < diff) {
diff = Math.abs(target - triple);
sum = triple;
}
}
}
return sum;
}
4 Sum
public ArrayList<ArrayList<Integer>> fourSum(int[] numbers, int target) {
ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
if (numbers == null || numbers.length == 0) {
return ans;
}
Arrays.sort(numbers);
int len = numbers.length;
for (int i = 0; i < len - 3; i++) {
if (i > 0 && numbers[i - 1] == numbers[i]) {
continue;
}
for (int j = i + 1; j < len - 2; j++) {
if (j > i + 1 && numbers[j - 1] == numbers[j]) {
continue;
}
int left = j + 1;
int right = len - 1;
while (left < right) {
int diff = numbers[left] + numbers[right] + numbers[i] + numbers[j] - target;
if (diff == 0) {
ArrayList<Integer> triplet = new ArrayList<Integer>();
triplet.add(numbers[i]);
triplet.add(numbers[j]);
triplet.add(numbers[left]);
triplet.add(numbers[right]);
ans.add(triplet);
}
if (diff <= 0) {
left++;
while (left < len && numbers[left - 1] == numbers[left]) {
left++;
}
}
if (diff >= 0) {
right--;
while (right >= 0 && numbers[right + 1] == numbers[right]) {
right--;
}
}
}
}
}
return ans;
}
L 家最爱
Pow(x,n)
It’s important to note that in Line 16, wrting ‘while (pow * 2 <= y)’ would not work (because of overflow). It took me a long time to find this bug.
public double pow(double x, int n) {
if (n < 0) {
return 1.0 / helper (x, 0 - n);
} else {
return helper(x, n);
}
}
private double helper(double x, int y) {
if (y == 0) {
return 1.0;
}
int pow = 1;
double num = x;
while (pow <= y / 2) {
num *= num;
pow <<= 1;
}
return num * helper(x, y - pow);
}
Sqrt(x)
Note that in Line 8, we must declare left and right as ‘long’, not ‘int’, otherwise there will be overflow problems. It took me a long time to find this bug.
public int sqrt(int x) {
if (x < 0) {
return -1;
} else if (x < 2) {
return x;
}
long left = 1;
long right = x;
while (left + 1 < right) {
long mid = left + (right - left) / 2;
if (mid * mid < x) {
left = mid;
} else if (mid * mid > x) {
right = mid;
} else {
return (int) mid;
}
}
return (int) left;
}
Additional
Sort Color
public void sortColors(int[] A) {
if (A == null || A.length == 0) {
return;
}
int len = A.length;
partition(A, 0, len - 1, 0);
int p = 0;
while (p < len && A[p] == 0) {
p++;
}
partition(A, p, len - 1, 1);
}
private void partition(int[] A, int start, int end, int target) {
// find the target and put it on the left side of the array
while (start < end) {
while (start < A.length && A[start] == target) {
start++;
}
while (end >= 0 && A[end] != target) {
end--;
}
if (start > end) {
break;
} else {
int temp = A[start];
A[start] = A[end];
A[end] = temp;
}
}
}