算法通关村第十七关 | 白银 | 贪心高频问题

1.区间问题

1.1 判断区间是否重叠

原题：力扣252.

public boolean canAttendMeetings(int[][] intervals) {
    // 按照会议开始时间升序排序
	Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
    for (int i = 1; i < intervals.length; i++) {
        // 比较上一个会议的结束时间和下一个会议的开始时间
        if (intervals[i][0] < intervals[i - 1][1]) {
            return false;
        }
    }
    return true;
}

1.2 合并区间

原题：力扣56.

public int[][] merge(int[][] intervals) {
	Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
    int[][] res = new int[intervals.length][2];
    int index = -1;
    for (int[] interval : intervals) {
        if (index == -1 || interval[0] > res[index][1]) {
            res[++index] = interval;
        } else {
            res[index][1] = Math.max(res[index][1], interval[1]);
        }
    }
    return Arrays.copyOf(res, index + 1);
}

1.3 插入区间

原题：力扣57.

public int[][] insert(int[][] intervals, int[] newInterval) {
	int[][] res = new int[intervals.length + 1][2];
    int index = 0;
    int i = 0;
    // 插入区间前
    while (i < intervals.length && intervals[i][1] < newInterval[0]) {
        res[index++] = intervals[i++];
    }
    // 插入区间
    while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = Math.min(intervals[i][0], newInterval[0]);
        newInterval[1] = Math.max(intervals[i][1], newInterval[1]);
        i++;
    }
    res[index++] = newInterval;
    // 插入区间后
    while (i < intervals.length) {
        res[index++] = intervals[i++];
    }
    return Arrays.copyOf(res, index);
}

2.字符串分割

原题：力扣763.

统计字符的最远出现下标当作分割点。

public List<Integer> partitionLabels(String s) {
	List<Integer> list = new LinkedList<>();
	int[] edge = new int[26];
	char[] chars = s.toCharArray();
	for (int i = 0; i < chars.length; i++) {
        edge[chars[i] - 'a'] = i;
    }

	int index = 0;
	int last = -1;
	for (int i = 0; i < chars.length; i++) {
        index = Math.max(index, edge[chars[i] - 'a']);
        if (i == index) {
            list.add(i - last);
            last = i;
        }
    }
	// list 存储的是分割字符串后每个字符串的长度
	return list;
}

3.加油站问题

原题：力扣134.

首先要总油量大于等于消耗量，保证能跑完一圈。

然后计算路过每个加油站的剩余量，即该加油站的汽油量减去到下一个加油站要用的量。负数代表不能作为起始位置，正数有可能为起始位置。

public int canComplateCircuit(int[] gas, int[] cost) {
	int curSum = 0;
    int totalSum = 0;
    int start = 0;
    for (int i = 0; i < gas.length; i++) {
        // 计算每个加油站的剩余量
        curSum += gas[i] - cost[i];
        // 计算总剩余量
        totalSum += gas[i] - cost[i];
        if (curSum < 0) {
            // 移动起始位置
            start = i + 1;
            curSum = 0;
        }
    }
    if (totalSum < 0) {
        return -1;
    }
    return start;
}

如果对您有帮助，请点赞关注支持我，谢谢！?
如有错误或者不足之处，敬请指正！?
个人主页：星不易 ?
算法通关村专栏：不易|算法通关村 ?