第三章 基础算法和数据结构高频题 I
区间类问题
1 Missing Interval
public List<String> findMissingRanges(int[] nums, int lower, int upper) { List<String> res = new ArrayList<>(); if (nums == null || nums.length == 0) { return res; } addRange(res, lower, (long)nums[0] - 1); for (int i = 1; i < nums.length; i++) { addRange(res, (long)nums[i - 1] + 1, (long)nums[i] - 1); } addRange(res, (long)nums[nums.length - 1] + 1, upper); return res; } void addRange(List<String> res, long l, long r) { if (l > r) { return; } if (l == r) { res.add(l + ""); return; } res.add(l + "->" + r); }
2 Merge intervals
public List<Interval> merge(List<Interval> inte) { List<Interval> res = new ArrayList<>(); inte.sort(Comparator.comparing(i -> i.start)); Interval last = null; for (Interval item : inte) { if (last == null || last.end < item.start) { res.add(item); last = item; } else { last.end = Math.max(item.end, last.end); } } return res; }