我一直在拖着 实在是拖不下去了 我实在是不好意思
之前跟领导狗叫了 说我一天一题...
其实这之前 领导已经打电话催我一次了 但是我搪塞过去了 这次实在是说不过去了
没办法 赶紧回去找了题.
领导看后会利用上班时间跟我review我的题目
①无重叠区间：给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
注意:
可以认为区间的终点总是大于它的起点。
区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
示例 1:
输入: [ [1,2], [2,3], [3,4], [1,3] ]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
示例 2:
输入: [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:
输入: [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
:首先对区间数组按照结束位置进行升序排序 遍历后续的区间，如果当前区间的开始位置小于或等于前一个保留区间的结束位置，说明有重叠，则跳过当前区间。如果当前区间与前一个保留的区间没有重叠，则将其计入保留的区间中，并更新当前保留的区间的结束位置 最后返回需要移除的区间数量，即总区间数量减去保留的区间数量。
import java.util.*;
class Solution {
// 给定一个Interval数组，返回移除重叠区间后剩余区间的数量
public int eraseOverlapIntervals(Interval[] intervals) {
int len = intervals.length;
// 如果区间数量小于等于1，则不存在重叠区间，直接返回0
if (len <= 1) return 0;
// 按照区间的结束位置进行升序排序
// 这样排序的目的是为了优先保留结束位置较早的区间，以便后续的区间有更多的空间不被重叠
Arrays.sort(intervals, (a, b) -> a.end - b.end);
int count = 1; // 保留的区间数量，初始化为1，因为至少有一个区间不需要被移除
int end = intervals[0].end; // 当前保留的区间的结束位置
// 从第二个区间开始遍历
for (int i = 1; i < intervals.length; i++) {
// 如果当前区间的开始位置小于或等于前一个保留区间的结束位置，说明有重叠
// 则跳过当前区间，不将其计入保留的区间中
if (intervals[i].start < end) {
continue;
}
// 如果当前区间与前一个保留的区间没有重叠，则将其计入保留的区间中
count++;
// 更新当前保留的区间的结束位置
end = intervals[i].end;
}
// 返回需要移除的区间数量，即总区间数量减去保留的区间数量
return len - count;
}
}
class Interval {
int start;
int end;
Interval() { start = 0; end = 0; }
Interval(int s, int e) { start = s; end = e; }
}用最少数量的箭引爆气球
在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以y坐标并不重要，因此只要知道开始和结束的x坐标就足够了。开始坐标总是小于结束坐标。平面内最多存在104个气球。
一支弓箭可以沿着x轴从不同点完全垂直地射出。在坐标x处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。
Example:
输入:
[[10,16], [2,8], [1,6], [7,12]]
输出:
2解释:
对于该样例，我们可以在x = 6（射爆[2,8],[1,6]两个气球）和 x = 11（射爆另外两个气球）。
:
本题是求不重叠区域的个数，上一题是求要删除重叠区域的个数。题中[1,2][2,3]也算是重叠区域
import java.util.Arrays;
class Solution {
public int findMinArrowShots(int[][] points) {
// 如果气球数组为空或只有一个气球，则不需要射箭
if (points.length <= 1) {
return points.length;
}
// 按照气球的结束坐标进行排序
Arrays.sort(points, (a, b) -> a[1] - b[1]);
int end = points[0][1]; // 当前箭能够覆盖的最远结束坐标
int cnt = 1; // 箭的数量
for (int i = 1; i < points.length; i++) {
// 如果下一个气球的开始坐标在当前箭的覆盖范围内
// 则这个气球可以被当前箭引爆，不需要额外的箭
if (points[i][0] <= end) {
continue;
}
// 否则，需要额外的箭来引爆这个气球
end = points[i][1]; // 更新当前箭能够覆盖的最远结束坐标
cnt++; // 增加箭的数量
}
return cnt;
}
}
455.分发饼干：
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 sj 。如果 sj >= gi ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
注意：
你可以假设胃口值为正。
一个小朋友最多只能拥有一块饼干。
示例 1:
输入: [1,2,3], [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。
示例 2:
输入: [1,2], [1,2,3]
输出: 2
解释:
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.
先用量小的饼干满足胃口小的:
计数器 count 为0，用于记录可以满足的数量
两个数组都未遍历完的情况下，当前的食物可以满足当前胃口时，两个数组都向前移动，并增加计数器；如果不能满足，则只移动食物数组的指针
public int findContentChildren(int[] g, int[] s) {
int count = 0;
Arrays.sort(g);
Arrays.sort(s);
int i = 0,j = 0;
while (i < g.length && j < s.length) {
if (g[i] <= s[j]) {
i ++;
j ++;
count ++;
}else {
j ++;
}
}
return count;
}种花问题
假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
给定一个花坛（表示为一个数组包含0和1，其中0表示没种植花，1表示种植了花），和一个数 n 。能否在不打破种植规则的情况下种入 n 朵花？能则返回True，不能则返回False。
示例 1:
输入: flowerbed = [1,0,0,0,1], n = 1
输出: True
示例 2:
输入: flowerbed = [1,0,0,0,1], n = 2
输出: False
注意:
数组内已种好的花不会违反种植规则。
输入的数组长度范围为 [1, 20000]。
n 是非负整数，且不会超过输入数组的大小。
思路：算出花坛中一共有几个空位，看看是否大于等于花的数量 从头到尾找到符合0 0 0情况的个数 数组两边的特殊情况处理 0 0 当长度大于1时处理即可
class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
int cnt = 0; // 计数器，记录已经放置的花的数量
// 处理特殊情况：如果花坛只有一个位置
if (flowerbed.length == 1 && flowerbed[0] == 0) {
// 如果这个位置是空的，并且只需要放置一朵或不需要花，则返回true
return n <= 1;
}
// 处理首尾位置（花坛长度大于等于2时）
if (flowerbed.length >= 2) {
// 如果花坛的第一个位置和第二个位置都是空的，可以在第一个位置放置一朵花
if (flowerbed[0] == 0 && flowerbed[1] == 0) {
flowerbed[0] = 1; // 修改花坛状态（但实际上这个修改不影响最终结果）
cnt++; // 计数器加1
}
// 如果花坛的最后一个位置和倒数第二个位置都是空的，可以在最后一个位置放置一朵花
if (flowerbed[flowerbed.length - 1] == 0 && flowerbed[flowerbed.length - 2] == 0) {
flowerbed[flowerbed.length - 1] = 1; // 修改花坛状态（但实际上这个修改不影响最终结果）
cnt++; // 计数器加1
}
}
// 从第二个位置开始到倒数第二个位置遍历花坛
for (int i = 1; i < flowerbed.length - 1; ) {
// 如果当前位置的前一个、当前位置和后一个位置都是空的
if (flowerbed[i - 1] == 0 && flowerbed[i] == 0 && flowerbed[i + 1] == 0) {
flowerbed[i] = 1; // 在当前位置放置一朵花（但实际上这个修改不影响最终结果）
cnt++; // 计数器加1
// 跳过下一个位置，因为下一个位置已经作为当前位置的后一个位置被检查过
i = i + 2;
} else {
// 如果当前位置不满足条件，则检查下一个位置
i++;
}
}
// 返回结果：如果已经放置的花的数量大于或等于需要放置的花的数量，则返回true，否则返回false
return cnt >= n;
}
}分类颜色
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
进阶：
一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗？
分类颜色
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
进阶：
一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗？:
使用三个指针：low、mid 和 high。low 指针指向当前红色区域的末尾（即下一个0应该放置的位置），mid 指针用于遍历数组，high 指针指向当前蓝色区域的开始（即下一个2应该放置的位置）。
当 nums[mid] == 0 时，我们将 nums[mid] 与 nums[low] 交换，并将 low 和 mid 都向前移动一位。
当 nums[mid] == 1 时，不需要任何操作，因为1已经在正确的位置（即红色和蓝色之间），只需要将 mid 向前移动一位。
当 nums[mid] == 2 时，我们将 nums[mid] 与 nums[high] 交换，但只将 high 向前移动一位，因为 mid 指向的元素可能是0或1，需要再次检查。
我查到的 这个解法网上说叫荷兰国旗解法 : 荷兰国旗问题（Dutch National Flag problem）的解法，这是一种仅使用常数空间的一趟扫描算法
public class Solution {
public void sortColors(int[] nums) {
if (nums == null || nums.length <= 1) {
return;
}
int low = 0; // 指向红色区域的末尾
int mid = 0; // 当前遍历的指针
int high = nums.length - 1; // 指向蓝色区域的开始
while (mid <= high) {
if (nums[mid] == 0) {
// 交换low和mid，并将两个指针都向前移动
swap(nums, low++, mid++);
} else if (nums[mid] == 1) {
// 当前元素是白色，不需要交换，mid指针向前移动
mid++;
} else {
// 交换mid和high，但只移动high指针
swap(nums, mid, high--);
// 这里不移动mid指针，因为交换过来的元素可能是0或1，需要再次检查
}
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}