数据结构-贪心算法笔记

前言：贪心无套路，狠狠刷就完事

分发饼干

455. 分发饼干 - 力扣（LeetCode）

class Solution {/*** 找出最多有多少个孩子可以得到糖果。** @param g 一个数组，表示每个孩子对糖果大小的满意度。* @param s 一个数组，表示每个糖果的大小。* @return 可以得到糖果的孩子的最大数量。*/public int findContentChildren(int[] g, int[] s) {// 初始化得到糖果的孩子数量为0int 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;}
}

摆动序列

376. 摆动序列 - 力扣（LeetCode）

class Solution {/*** 找出给定数组中最长的摆动序列的长度。** @param nums 一个整数数组。* @return 最长摆动序列的长度。*/public int wiggleMaxLength(int[] nums) {// 如果数组长度小于或等于1，摆动序列的最大长度就是数组的长度if (nums.length <= 1) {return nums.length;}// 初始化前一个差值为0int preDiff = 0;// 初始化当前差值为0int 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;}
}

最大子序和

53. 最大子数组和 - 力扣（LeetCode）

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;// 初始化当前子数组的和为0int 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) {// 初始化总利润为0int sum = 0;// 遍历价格数组，从第二个元素开始，因为我们需要比较前一天的价格for(int i = 1; i < prices.length; i++){// 对于每一天，我们计算与前一天的差价// 如果差价是正数，说明今天的价格比昨天高，我们可以卖出股票获得利润// 如果差价是负数，我们不进行操作，因为卖出会亏损// Math.max函数确保我们不会添加负数的利润sum += Math.max(prices[i] - prices[i - 1], 0);}// 返回计算出的总利润return sum;}
}

跳跃游戏（可达问题）

55. 跳跃游戏 - 力扣（LeetCode）

class Solution {/*** 判断是否能够跳到最后一个位置。** @param nums 一个非递减的整数数组，表示在每个位置可以跳跃的最大步数。* @return 如果可以跳到最后一个位置，返回true；否则返回false。*/public boolean canJump(int[] nums) {// 如果数组只有一个元素，那么可以直接到达最后一个位置，返回trueif(nums.length == 1){return true;}// 初始化可到达的最远范围int coverRange = 0;// 遍历数组，尝试找到能够到达最远位置的跳跃点for(int i = 0 ; i <= coverRange ; i++){// 更新可到达的最远范围，取当前位置加上该位置可跳跃的步数与已有的最远范围的最大值coverRange = Math.max(i + nums[i], coverRange);// 如果更新后的最远范围已经能够到达或超过最后一个位置，返回trueif(coverRange >= nums.length - 1){return true;}}// 如果遍历完数组后，仍然无法到达最后一个位置，返回falsereturn false;}
}

跳跃游戏 II（可达问题）

45. 跳跃游戏 II - 力扣（LeetCode）

class Solution {// 定义一个方法 jump，接收一个整数数组 nums 作为参数，返回一个整数public int jump(int[] nums) {// 如果数组长度为 1，即只有一个位置，不需要跳跃，返回 0if(nums.length == 1){return 0;}// 初始化当前跳跃位置 curJump 为 0int curJump = 0;// 初始化下一个跳跃位置 nextJump 也为 0int 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 加 1result++;// 更新当前跳跃位置为下一个跳跃位置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;}
}

加油站

134. 加油站 - 力扣（LeetCode）

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，意味着油量不足以完成整个旅程，返回-1if(sum < 0){return -1;}// 初始化当前油量总和为0int curSum = 0;// 初始化起始加油站的索引为0int 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;}
}

分发糖果（两个维度）

分两个维度，那么一个维度一个维度来

135. 分发糖果 - 力扣（LeetCode）

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;}
}

柠檬水找零

860. 柠檬水找零 - 力扣（LeetCode）

class Solution {// 方法lemonadeChange用于检查是否能够为给定的钞票数组提供正确的找零public boolean lemonadeChange(int[] bills) {// 初始化计数器，five用来记录5美元钞票的数量，ten用来记录10美元钞票的数量int five = 0;int ten = 0;// 遍历输入的钞票数组billsfor (int i = 0; i < bills.length; i++) {// 如果当前钞票是5美元if (bills[i] == 5) {// 增加5美元钞票的计数five++;}// 如果当前钞票是10美元if (bills[i] == 10) {// 如果没有足够的5美元钞票来找零，返回falseif(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 {// 如果无法找零，返回falsereturn false;}}}// 如果遍历完所有钞票后，没有返回false，说明所有找零都成功了，返回truereturn true;}
}

根据身高重建队列（记）（两个维度）

注意LinkedList的插入add方法，还有排序实现comparetor接口是怎么实现的

我们使用list.toArray()来将集合转化为数组，注意转化为二维数组的实现

406. 根据身高重建队列 - 力扣（LeetCode）

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;}
}

无重叠区间

435. 无重叠区间 - 力扣（LeetCode）

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()来将集合转化为数组，注意转化为二维数组的实现

这里自己实现转化集合为二维数组会超出内存限制

56. 合并区间 - 力扣（LeetCode）

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()方法时，需要指定数组的大小，否则会抛出ArrayStoreExceptionreturn list.toArray(new int[list.size()][intervals[0].length]);}
}

划分字母区间

763. 划分字母区间 - 力扣（LeetCode）

import java.util.List; // 导入List接口
import java.util.ArrayList; // 导入ArrayList类class Solution {// 主方法，接收一个字符串spublic 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<>();// 再次遍历字符串sfor (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;}
}

单调递增的数字

738. 单调递增的数字 - 力扣（LeetCode）

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位置开始，将所有后续的数字都设置为9for (int i = start; i < strChar.length; i++) {strChar[i] = '9';}// 将修改后的字符数组转换回字符串，然后转换为整数并返回return Integer.parseInt(String.valueOf(strChar));}
}

监控二叉树

968. 监控二叉树 - 力扣（LeetCode）

class Solution {// result用于记录覆盖二叉树所需的最少摄像头数量int result = 0;// minCameraCover是主函数，接收二叉树的根节点rootpublic 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;}
}