数据结构-贪心算法笔记
前言：贪心无套路，狠狠刷就完事
分发饼干
class Solution {
/**
* 找出最多有多少个孩子可以得到糖果。
*
* @param g 一个数组，表示每个孩子对糖果大小的满意度。
* @param s 一个数组，表示每个糖果的大小。
* @return 可以得到糖果的孩子的最大数量。
*/
public int findContentChildren(int[] g, int[] s) {
// 初始化得到糖果的孩子数量为0
int sum = 0;
// 对孩子们的满意度进行排序
Arrays.sort(g);
// 对糖果的大小进行排序
Arrays.sort(s);
// 从最大的糖果开始遍历
int sIndex = s.length - 1;
// 从最不挑剔的孩子开始遍历
for (int i = g.length - 1; i >= 0 && sIndex >= 0; i--) {
// 如果当前糖果的大小至少能满足当前孩子
if (s[sIndex] >= g[i]) {
// 将这个糖果分配给当前孩子
sIndex--;
// 增加成功得到糖果的孩子数量
sum++;
}
}
// 返回可以得到糖果的孩子的最大数量
return sum;
}
}摆动序列
class Solution {
/**
* 找出给定数组中最长的摆动序列的长度。
*
* @param nums 一个整数数组。
* @return 最长摆动序列的长度。
*/
public int wiggleMaxLength(int[] nums) {
// 如果数组长度小于或等于1，摆动序列的最大长度就是数组的长度
if (nums.length <= 1) {
return nums.length;
}
// 初始化前一个差值为0
int preDiff = 0;
// 初始化当前差值为0
int curDiff = 0;
// 初始化摆动序列的当前长度为1，因为至少包含一个元素
int result = 1;
// 遍历数组，从第一个元素开始，直到倒数第二个元素
for (int i = 0; i < nums.length - 1; i++) {
// 计算当前元素与前一个元素的差值
curDiff = nums[i + 1] - nums[i];
// 如果当前差值与前一个差值异号（一个正一个负），说明形成了摆动
if ((curDiff < 0 && preDiff >= 0) || (curDiff > 0 && preDiff <= 0)) {
// 增加摆动序列的长度
result++;
// 更新前一个差值为当前差值
preDiff = curDiff;
}
}
// 返回最长摆动序列的长度
return result;
}
}最大子序和
class Solution {
/**
* 找出给定数组中最大子数组的和。
*
* @param nums 一个整数数组。
* @return 最大子数组的和。
*/
public int maxSubArray(int[] nums) {
// 如果数组只有一个元素，最大子数组的和就是该元素本身
if (nums.length == 1) {
return nums[0];
}
// 初始化最大和为Integer.MIN_VALUE，这是可能的最小整数
int max = Integer.MIN_VALUE;
// 初始化当前子数组的和为0
int count = 0;
// 遍历数组中的每个元素
for (int i = 0; i < nums.length; i++) {
// 将当前元素加到当前子数组的和中
count += nums[i];
// 更新最大子数组的和，取当前子数组的和和已知最大和中的较大者
max = Math.max(count, max);
// 如果当前子数组的和小于或等于0，则重置为0
// 这表示当前子数组不可能是最大子数组的一部分，因此重新开始计算新的子数组
if (count <= 0) {
count = 0;
}
}
// 返回最大子数组的和
return max;
}
}买卖股票的最佳时机 II
122. 买卖股票的最佳时机 II - 力扣（LeetCode）
class Solution {
/**
* 计算最大利润。
*
* @param prices 一个整数数组，表示每天的股票价格。
* @return 最大利润。
*/
public int maxProfit(int[] prices) {
// 初始化总利润为0
int sum = 0;
// 遍历价格数组，从第二个元素开始，因为我们需要比较前一天的价格
for(int i = 1; i < prices.length; i++){
// 对于每一天，我们计算与前一天的差价
// 如果差价是正数，说明今天的价格比昨天高，我们可以卖出股票获得利润
// 如果差价是负数，我们不进行操作，因为卖出会亏损
// Math.max函数确保我们不会添加负数的利润
sum += Math.max(prices[i] - prices[i - 1], 0);
}
// 返回计算出的总利润
return sum;
}
}跳跃游戏（可达问题）
class Solution {
/**
* 判断是否能够跳到最后一个位置。
*
* @param nums 一个非递减的整数数组，表示在每个位置可以跳跃的最大步数。
* @return 如果可以跳到最后一个位置，返回true；否则返回false。
*/
public boolean canJump(int[] nums) {
// 如果数组只有一个元素，那么可以直接到达最后一个位置，返回true
if(nums.length == 1){
return true;
}
// 初始化可到达的最远范围
int coverRange = 0;
// 遍历数组，尝试找到能够到达最远位置的跳跃点
for(int i = 0 ; i <= coverRange ; i++){
// 更新可到达的最远范围，取当前位置加上该位置可跳跃的步数与已有的最远范围的最大值
coverRange = Math.max(i + nums[i], coverRange);
// 如果更新后的最远范围已经能够到达或超过最后一个位置，返回true
if(coverRange >= nums.length - 1){
return true;
}
}
// 如果遍历完数组后，仍然无法到达最后一个位置，返回false
return false;
}
}跳跃游戏 II（可达问题）
class Solution {
// 定义一个方法 jump，接收一个整数数组 nums 作为参数，返回一个整数
public int jump(int[] nums) {
// 如果数组长度为 1，即只有一个位置，不需要跳跃，返回 0
if(nums.length == 1){
return 0;
}
// 初始化当前跳跃位置 curJump 为 0
int curJump = 0;
// 初始化下一个跳跃位置 nextJump 也为 0
int nextJump = 0;
// 初始化结果 result 为 0，表示跳跃次数
int result = 0;
// 遍历数组，从索引 0 开始，直到数组的最后一个元素
for(int i = 0 ; i < nums.length ; i++){
// 更新下一个跳跃位置为当前位置加上当前位置可以跳跃的最大长度的最大值
nextJump = Math.max(nextJump, nums[i] + i);
// 当当前位置 i 等于当前跳跃位置 curJump 时
if(i == curJump){
// 跳跃次数 result 加 1
result++;
// 更新当前跳跃位置为下一个跳跃位置
curJump = nextJump;
// 如果下一个跳跃位置已经到达或超过数组的最后一个位置，跳出循环
if(nextJump >= nums.length - 1){
break;
}
}
}
// 返回所需的最少跳跃次数
return result;
}
}K次取反后最大化的数组和
1005. K 次取反后最大化的数组和 - 力扣（LeetCode）
class Solution {
public int largestSumAfterKNegations(int[] nums, int k) {
// 对数组进行排序，以便更容易地进行取反操作
Arrays.sort(nums);
// 遍历数组，进行k次取反操作
for(int i = 0 ; i < nums.length && k > 0 ; i++){
// 如果当前元素是负数，则取反
if(nums[i] < 0){
nums[i] = -nums[i];
k--; // 减少剩余的取反次数
}
}
// 如果还有剩余的取反次数，并且k是奇数
if(k > 0){
if(k % 2 == 1){
// 再次对数组进行排序，以便找到最小的元素进行取反
Arrays.sort(nums);
// 取反最小的元素
nums[0] *= -1;
}
}
// 计算并返回数组元素之和
int sum = 0;
for(int t : nums){
sum += t;
}
return sum;
}
}加油站
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
// 计算整个旅程中油量和油耗的总差额
int sum = 0;
for(int i = 0 ; i < gas.length; i++){
sum += gas[i] - cost[i];
}
// 如果总差额小于0，意味着油量不足以完成整个旅程，返回-1
if(sum < 0){
return -1;
}
// 初始化当前油量总和为0
int curSum = 0;
// 初始化起始加油站的索引为0
int start = 0;
// 遍历每个加油站
for(int i = 0 ; i < gas.length; i++){
// 将当前加油站的油量和油耗差额加到当前油量总和上
curSum += gas[i] - cost[i];
// 如果当前油量总和小于0，意味着从上一个加油站开始的旅程油量不足
if(curSum < 0){
// 更新起始加油站的索引为当前加油站的下一个
start = i + 1;
// 重置当前油量总和为0，从下一个加油站重新开始计算
curSum = 0;
}
}
// 返回可以完成整个旅程的起始加油站的索引
return start;
}
}分发糖果（两个维度）
分两个维度，那么一个维度一个维度来
class Solution {
// candy方法接受一个整数数组ratings作为参数，返回一个整数，表示总共需要的糖果数量。
public int candy(int[] ratings) {
// 创建一个数组ret，用于存储每个孩子应该得到的糖果数量，初始值都为1。
int ret[] = new int[ratings.length];
ret[0] = 1; // 第一个孩子至少得到1个糖果。
// 从第二个孩子开始遍历ratings数组。
for(int i = 1 ; i < ratings.length ; i++){
// 如果当前孩子的评分大于前一个孩子的评分，那么他应该得到的糖果数量是前一个孩子的糖果数量加1。
// 否则，他至少得到1个糖果。
ret[i] = (ratings[i] > ratings[i - 1]) ? ret[i - 1] + 1 : 1;
}
// 从倒数第二个孩子开始遍历ratings数组，这次是逆向遍历。
for(int i = ratings.length - 2; i >= 0; i--){
// 如果当前孩子的评分大于后一个孩子的评分，那么他应该得到的糖果数量至少是后一个孩子的糖果数量加1。
// 这里使用Math.max函数来确保当前孩子的糖果数量不会少于之前计算的数量。
if(ratings[i + 1] < ratings[i]){
ret[i] = Math.max(ret[i], ret[i + 1] + 1);
}
}
// 初始化一个变量sum，用于累加所有孩子的糖果数量。
int sum = 0;
// 遍历ret数组，将每个孩子的糖果数量累加到sum变量中。
for(int s : ret){
sum += s;
}
// 返回总共需要的糖果数量。
return sum;
}
}柠檬水找零
class Solution {
// 方法lemonadeChange用于检查是否能够为给定的钞票数组提供正确的找零
public boolean lemonadeChange(int[] bills) {
// 初始化计数器，five用来记录5美元钞票的数量，ten用来记录10美元钞票的数量
int five = 0;
int ten = 0;
// 遍历输入的钞票数组bills
for (int i = 0; i < bills.length; i++) {
// 如果当前钞票是5美元
if (bills[i] == 5) {
// 增加5美元钞票的计数
five++;
}
// 如果当前钞票是10美元
if (bills[i] == 10) {
// 如果没有足够的5美元钞票来找零，返回false
if(five <= 0){
return false;
}
// 增加10美元钞票的计数，并减少一张5美元钞票
ten++;
five--;
}
// 如果当前钞票是20美元
if (bills[i] == 20) {
// 如果有10美元和5美元钞票，可以使用它们来找零
if (five > 0 && ten > 0) {
five--;
ten--;
// 如果没有10美元钞票，但有三张或更多的5美元钞票，也可以找零
} else if (five >= 3) {
five -= 3;
} else {
// 如果无法找零，返回false
return false;
}
}
}
// 如果遍历完所有钞票后，没有返回false，说明所有找零都成功了，返回true
return true;
}
}根据身高重建队列（记）（两个维度）
注意LinkedList的插入add方法，还有排序实现comparetor接口是怎么实现的
我们使用list.toArray()来将集合转化为数组，注意转化为二维数组的实现
import java.util.Arrays; // 导入Arrays类，用于数组排序
import java.util.LinkedList; // 导入LinkedList类，用于存储队列
class Solution {
// 主方法，接收一个二维数组people，其中每个子数组包含两个整数，分别表示人的身高和到达时间
public int[][] reconstructQueue(int[][] people) {
// 使用Arrays.sort方法对people数组进行排序，传入一个自定义的比较器
Arrays.sort(people, (a, b) -> {
// 如果两个人的身高相同，则按照到达时间升序排列
if(a[0] == b[0]){
return a[1] - b[1];
}
// 否则，按照身高降序排列
return b[0] - a[0];
});
// 创建一个LinkedList，用于模拟队列
LinkedList<int[]> list = new LinkedList<>();
// 遍历排序后的people数组
for(int[] p : people){
// 使用LinkedList的add方法，将元素插入到正确的位置，以保持队列的顺序
list.add(p[1], p);
}
return list.toArray(new int[list.size()][]);
}
}区间重叠问题
我这里统一对左边界进行排序
而且使用Integer.compare（）方法，防止数据溢出
我们使用list.toArray()来将集合转化为数组，注意转化为二维数组的实现
用最少数量的箭引爆气球
452. 用最少数量的箭引爆气球 - 力扣（LeetCode）
import java.util.Arrays; // 导入Arrays类，用于数组排序
class Solution {
// 主方法，接收一个二维数组points，其中每个子数组包含两个整数，分别表示气球的起始时间和结束时间
public int findMinArrowShots(int[][] points) {
// 使用Arrays.sort方法对points数组进行排序，传入一个自定义的比较器，按照气球的起始时间进行升序排序
Arrays.sort(points, (a, b) -> {
return Integer.compare(a[0], b[0]);
});
// 初始化计数器count为1，表示至少需要一支箭来射爆第一个气球
int count = 1;
// 从第二个气球开始遍历排序后的points数组
for(int i = 1 ; i < points.length; i++){
// 如果当前气球的起始时间小于或等于前一个气球的结束时间，说明它们有重叠
if(points[i][0] <= points[i - 1][1]){
// 更新当前气球的结束时间为两个气球结束时间的较小值，这样可以确保箭能射爆更多的气球
points[i][1] = Math.min(points[i][1], points[i - 1][1]);
}else{
// 如果当前气球的起始时间大于前一个气球的结束时间，说明它们没有重叠，需要额外的一支箭
count++;
}
}
// 返回总共需要的箭的数量
return count;
}
}无重叠区间
import java.util.Arrays; // 导入Arrays类，用于数组排序
class Solution {
// 主方法，接收一个二维数组intervals，其中每个子数组包含两个整数，分别表示一个区间的起始和结束时间
public int eraseOverlapIntervals(int[][] intervals) {
// 使用Arrays.sort方法对intervals数组进行排序，传入一个自定义的比较器，按照区间的起始时间进行升序排序
Arrays.sort(intervals, (a, b) -> {
return Integer.compare(a[0], b[0]); // 如果a的起始时间小于b的，则a排在前面
});
// 初始化ret为1，表示至少有一个区间可以被保留（即第一个区间）
int ret = 1;
// 从第二个区间开始遍历排序后的intervals数组
for (int i = 1; i < intervals.length; i++) {
// 如果当前区间的起始时间大于或等于前一个区间的结束时间，说明这两个区间不重叠，可以保留当前区间
if (intervals[i][0] >= intervals[i - 1][1]) {
ret++; // 增加可以保留的区间数量
} else {
// 如果当前区间与前一个区间重叠，更新当前区间的结束时间为两个区间结束时间的较小值，以尝试与其他区间形成不重叠的区间
intervals[i][1] = Math.min(intervals[i - 1][1], intervals[i][1]);
}
}
// 返回需要删除的区间数量，即总区间数量减去可以保留的区间数量
return intervals.length - ret;
}
}合并区间
我们使用list.toArray()来将集合转化为数组，注意转化为二维数组的实现
这里自己实现转化集合为二维数组会超出内存限制
import java.util.Arrays; // 导入Arrays类，用于数组排序
import java.util.ArrayList; // 导入ArrayList类
import java.util.List; // 导入List接口
class Solution {
// 主方法，接收一个二维数组intervals，其中每个子数组包含两个整数，分别表示一个区间的起始和结束时间
public int[][] merge(int[][] intervals) {
// 使用Arrays.sort方法对intervals数组进行排序，传入一个自定义的比较器，按照区间的起始时间进行升序排序
Arrays.sort(intervals, (a, b) -> {
return Integer.compare(a[0], b[0]); // 如果a的起始时间小于b的，则a排在前面
});
// 创建一个ArrayList，用于存储合并后的区间
List<int[]> list = new ArrayList<>();
// 将第一个区间添加到list中
list.add(intervals[0]);
// 从第二个区间开始遍历排序后的intervals数组
for (int i = 1; i < intervals.length; i++) {
// 获取list中最后一个区间
int[] lastInterval = list.get(list.size() - 1);
// 如果当前区间的起始时间小于或等于list中最后一个区间的结束时间，说明这两个区间有重叠
if (intervals[i][0] <= lastInterval[1]) {
// 合并这两个区间，更新结束时间为两者的较大值
lastInterval[1] = Math.max(lastInterval[1], intervals[i][1]);
} else {
// 如果当前区间与list中最后一个区间没有重叠，直接将当前区间添加到list中
list.add(intervals[i]);
}
}
// 将ArrayList转换为二维数组并返回
// 注意：这里使用list.toArray()方法时，需要指定数组的大小，否则会抛出ArrayStoreException
return list.toArray(new int[list.size()][intervals[0].length]);
}
}划分字母区间
import java.util.List; // 导入List接口
import java.util.ArrayList; // 导入ArrayList类
class Solution {
// 主方法，接收一个字符串s
public List<Integer> partitionLabels(String s) {
// 创建一个大小为26的数组hash，用于存储每个字母最后一次出现的位置，这里使用'a'到'z'，所以是27个位置（包括0）
int hash[] = new int[27];
// 遍历字符串s，将每个字符最后一次出现的位置存储在hash数组中
for (int i = 0; i < s.length(); i++) {
// 将字符转换为索引（'a'到'z'），并存储其在字符串中的位置
hash[s.charAt(i) - 'a'] = i;
}
// 初始化start和end变量，start用于记录当前子字符串的起始位置，end用于记录当前子字符串的结束位置
int start = 0;
int end = 0;
// 创建一个ArrayList，用于存储每个子字符串的长度
List<Integer> list = new ArrayList<>();
// 再次遍历字符串s
for (int i = 0; i < s.length(); i++) {
// 更新end为当前字符最后一次出现的位置，如果当前字符是之前出现过的字符，则end取当前字符最后一次出现的位置和之前end的较大值
end = Math.max(hash[s.charAt(i) - 'a'], end);
// 如果当前索引i等于end，则说明找到了一个子字符串的结束位置
if (i == end) {
// 将当前子字符串的长度添加到list中
list.add(end - start + 1);
// 更新start为下一个字符的位置，即当前end位置的下一个位置
start = i + 1;
}
}
// 返回包含所有子字符串长度的列表
return list;
}
}单调递增的数字
class Solution {
public int monotoneIncreasingDigits(int n) {
// 将整数n转换为字符串，以便可以逐位处理
String str = String.valueOf(n);
// 将字符串转换为字符数组，这样可以方便地修改每一位数字
char strChar[] = str.toCharArray();
// 初始化一个变量start，用于记录需要修改的起始位置
int start = strChar.length;
// 从右向左遍历字符数组，直到找到第一个不是单调递增的数字
for (int i = str.length() - 2; i >= 0; i--) {
// 如果当前位的数字大于下一位，说明不是单调递增的
if (strChar[i] > strChar[i + 1]) {
// 将当前位减1，以保证当前位小于等于下一位
strChar[i]--;
// 更新需要修改的起始位置为当前位的下一位
start = i + 1;
}
}
// 从start位置开始，将所有后续的数字都设置为9
for (int i = start; i < strChar.length; i++) {
strChar[i] = '9';
}
// 将修改后的字符数组转换回字符串，然后转换为整数并返回
return Integer.parseInt(String.valueOf(strChar));
}
}监控二叉树
class Solution {
// result用于记录覆盖二叉树所需的最少摄像头数量
int result = 0;
// minCameraCover是主函数，接收二叉树的根节点root
public int minCameraCover(TreeNode root) {
// 如果根节点为空，返回0个摄像头
if (root == null) {
return 0;
}
// 调用Demo函数进行深度优先搜索
if (Demo(root) == 0) {
// 如果根节点未被覆盖，需要在其上放置一个摄像头
result++;
}
// 返回所需的最少摄像头数量
return result;
}
// Demo是一个辅助函数，用于深度优先搜索二叉树
int Demo(TreeNode node) {
// 如果节点为空，返回1，表示该节点被覆盖
if (node == null) {
return 1;
}
// 对左子树和右子树进行深度优先搜索
int left = Demo(node.left);
int right = Demo(node.right);
// 如果左子树或右子树未被覆盖，则需要在当前节点放置摄像头
if (left == 0 || right == 0) {
result++;
// 返回2表示当前节点放置了摄像头，可以覆盖当前节点及其所有子孙节点
return 2;
}
// 如果左子树和右子树都被覆盖了，但当前节点未被覆盖
if (left == 1 && right == 1) {
// 返回0表示当前节点未被覆盖
return 0;
}
// 如果左子树或右子树有摄像头，则当前节点被覆盖
if (left == 2 || right == 2) {
// 返回1表示当前节点被覆盖
return 1;
}
// 这一行应该被删除，因为不可能到达这里
return -1;
}
}原文地址：https://blog.csdn.net/2302_80490510/article/details/143002946
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！