raitGroup1007
BAN USER/*
Merge Intervals in-place without using the 'new' operator.
Time: O(nlogn)
Space: O(1)
*/
private static void mergeIntervals(List<Interval> interval) {
if (interval == null) throw new IllegalArgumentException();
if (interval.size() == 0) return;
Collections.sort(interval, new Comparator<Interval>(){
@Override
public int compare(Interval a, Interval b) {
if (a == b) return b.end - a.end;
return a.start - b.start;
}
});
int i = 0;
while (i < interval.size() - 1) {
if (interval.get(i).end >= interval.get(i + 1).start) {
interval.get(i).end = Math.max(interval.get(i).end, interval.get(i + 1).end);
interval.remove(i + 1);
}
else i++;
}
}
@Stephen, since the question does not give a length for the subarray, applying Kadane's algorithm for Maximum subarray problem would be more optimal.
int getMaxSubarraySum(int[] a) {
if (a == null || a.length == 0) throw new IllegalArgumentException();
boolean allNegative = true;
int max = Integer.MIN_VALUE;
for (int i : a) {
max = Math.max(max, i);
if (i >= 0) {
allNegative = false;
break;
}
}
if (allNegative) return max;
int tempMax = a[0];
max = a[0];
for (int i = 1; i < a.length; i++) {
tempMax = Math.max(tempMax + a[i], 0);
max = Math.max(max, tempMax);
}
return max;
}
import java.util.*;
class GetCombs {
public static void main (String[] args) {
int sum = 16, n = 2;
List<List<Integer>> res = new ArrayList<List<Integer>>();
getCombs(res, new ArrayList<Integer>(), sum, n);
for (List<Integer> al : res) System.out.println(al);
}
private static void getCombs(List<List<Integer>> res, List<Integer> al, int sum, int n) {
if (n == 0) {
if (sum > 0) return;
res.add(new ArrayList<Integer>(al));
return;
}
for (int a = 0; a <= sum; a++) {
al.add(a);
getCombs(res, al, sum - a, n - 1);
al.remove(al.size() - 1);
}
}
}
Iterate through the original tree to find the target while being sure to apply the same moves on the deep copy tree.
- raitGroup1007 July 25, 2017