Divide and Conquer (Java) - ShuweiLeung/Thinking GitHub Wiki
1.（282:Hard）（非常非常经典题）Expression Add Operators
- This problem has a lot of edge cases to be considered:
- overflow: we use a long type once it is larger than Integer.MAX_VALUE or minimum, we get over it.
- 0 sequence: because we can't have numbers with multiple digits started with zero, we have to deal with it too.
- a little trick is that we should save the value that is to be multiplied in the next recursion.
- 需要明确的几点，只能在字符串中间插入操作符。我们在每次递归时，都将该层递归添加的值传入到下一层，这样为了避免在某一层以为添加2，但实际要添加23，此时需要在之前的基础上减去2，而且要再添加23。
- 该题思路请参看代码实现，有备注很清楚
2.（315:Hard）（非常非常经典题）Count of Smaller Numbers After Self
- 可以使用用二分搜索法，思路是将给定数组从最后一个开始，用二分法插入到一个新的数组，这样新数组就是有序的，那么此时该数字在新数组中的坐标就是原数组中其右边所有较小数字的个数。
public List<Integer> countSmaller(int[] nums) {
Integer[] ans = new Integer[nums.length];
List<Integer> sorted = new ArrayList<Integer>();
for (int i = nums.length - 1; i >= 0; i--) {
int index = findIndex(sorted, nums[i]);
ans[i] = index;
sorted.add(index, nums[i]);
}
return Arrays.asList(ans);
}
private int findIndex(List<Integer> sorted, int target) {
if (sorted.size() == 0) return 0;
int start = 0;
int end = sorted.size() - 1;
if (sorted.get(end) < target) return end + 1;
if (sorted.get(start) >= target) return 0;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (sorted.get(mid) < target) {
start = mid + 1;
} else {
end = mid;
}
}
if (sorted.get(start) >= target) return start;
return end;
}
3.（241:Hard）（非常非常经典题）Different Ways to Add Parentheses
- 其实是用recursive的方法，以操作符作为分界点，将字符串分为两部分，最后将两部分返回的所有可能结果进行合并计算，参考代码如下：
public List<Integer> diffWaysToCompute(String input) {
List<Integer> ret = new LinkedList<Integer>();
for (int i=0; i<input.length(); i++) {
if (input.charAt(i) == '-' ||
input.charAt(i) == '*' ||
input.charAt(i) == '+' ) {
String part1 = input.substring(0, i);
String part2 = input.substring(i+1);
List<Integer> part1Ret = diffWaysToCompute(part1);
List<Integer> part2Ret = diffWaysToCompute(part2);
for (Integer p1 : part1Ret) {
for (Integer p2 : part2Ret) {
int c = 0;
switch (input.charAt(i)) {
case '+': c = p1+p2;
break;
case '-': c = p1-p2;
break;
case '*': c = p1*p2;
break;
}
ret.add(c);
}
}
}
}
if (ret.size() == 0) { //说明传入的字符串没有操作符，只是单纯的数字
ret.add(Integer.valueOf(input));
}
return ret;
}
4.（973:Medium）（非常非常经典题）K Closest Points to Origin
- 一般的解法是将数组按照坐标距原点的远近进行排序，然后取前k个，代码如下：
public int[][] kClosest(int[][] points, int K) {
Arrays.sort(points, new Comparator<int[]>(){ //直接将数组排序后取前K个元素即可
@Override
public int compare(int[] one, int[] two){
double distOne = Math.sqrt(Math.pow(one[0],2) + Math.pow(one[1],2));
double distTwo = Math.sqrt(Math.pow(two[0],2) + Math.pow(two[1],2));
return Double.compare(distOne, distTwo);
}
});
int[][] ret = new int[K][2];
for(int i = 0; i < K; i++){
ret[i] = points[i];
}
return ret;
}
- 另外一个更高效的方法是利用quick sort，因为题目要求返回的k个点并没有要求是有序的，所以我们只需要返回k个距离最短的点即可，并不关心返回时他们之间的相对顺序
- In the quick sort, we will always choose a pivot to compare with other elements. After one iteration, we will get an array that all elements smaller than the pivot are on the left side of the pivot and all elements greater than the pivot are on the right side of the pviot (assuming we sort the array in ascending order). So, inspired from this, each iteration, we choose a pivot and then find the position p the pivot should be. Then we compare p with the K, if the p is smaller than the K, meaning the all element on the left of the pivot are all proper candidates but it is not adequate, we have to do the same thing on right side, and vice versa. If the p is exactly equal to the K, meaning that we've found the K-th position. Therefore, we just return the first K elements, since they are not greater than the pivot.
- Theoretically, the average time complexity is O(N) , but just like quick sort, in the worst case, this solution would be degenerated to O(N^2), and pratically, the real time it takes on leetcode is 15ms.
//利用quick sort的思想，因为题目不要求返回的k个数有序
public int[][] kClosest(int[][] points, int K) {
int len = points.length, l = 0, r = len - 1;
while (l <= r) {
int mid = helper(points, l, r);
if (mid == K) break;
if (mid < K) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return Arrays.copyOfRange(points, 0, K);
}
private int helper(int[][] A, int l, int r) {
int[] pivot = A[l];
while (l < r) {
while (l < r && compare(A[r], pivot) >= 0) r--;
A[l] = A[r];
while (l < r && compare(A[l], pivot) <= 0) l++;
A[r] = A[l];
}
A[l] = pivot;
return l;
}
private int compare(int[] p1, int[] p2) {
return p1[0] * p1[0] + p1[1] * p1[1] - p2[0] * p2[0] - p2[1] * p2[1];
}