-
12数据结构与算法刷题之【贪心】篇
前言
除了去年11月份以及今年近几月的算法刷题之外，只有在当时20年蓝桥杯准备的时候才刷过一些题，在当时就有接触到一些动归、递归回溯、贪心等等，不过那会也还是一知半解，做的题目也特别少，因为考虑到之后面试有算法题以及数据结构算法对于一个程序员十分重要，我也开始了刷题之路。
我目前的学习数据结构与算法及刷题路径：
1、学习数据结构的原理以及一些常见算法。
2、代码随想录：跟着这个github算法刷题项目进行分类刷，在刷题前可以学习一下对应类别的知识点，而且这里面每道题都讲的很详细。
3、牛客网高频面试101题：牛客网—面试必刷101题，在刷的过程中可以在leetcode同步刷一下。
4、接下来就是力扣上的专栏《剑指offer II》、《程序员面试金典（第 6 版）》…有对应的精选题单来对着刷即可。
5、大部分的高频面试、算法题刷完后，就可以指定力扣分类专栏进行一下刷题了。
刚开始刷的时候真的是很痛苦的，想到去年一道题可能就需要好几小时，真的就很难受的，不过熬过来一切都会好起来，随着题量的增多，很多题目你看到就会知道使用什么数据结构或者算法来去求解，并且思考对应的时间空间复杂度，并寻求最优解，我们一起加油！
我的刷题历程
截止2022.8.18：
1、牛客网101题(其中1题是平台案例有问题)：
2、剑指offerII：
力扣总记录数：
加油加油！
基础知识
啥是贪心？
贪心的本质是选择每一阶段的局部最优，从而达到全局最优。
例如，有一堆钞票，你可以拿走十张，如果想达到最大的金额，你要怎么拿？
指定每次拿最大的，最终结果就是拿走最大数额的钱。
每次拿最大的就是局部最优，最后拿走最大数额的钱就是推出全局最优。
再举一个例子如果是 有一堆盒子，你有一个背包体积为n，如何把背包尽可能装满，如果还每次选最大的盒子，就不行了。这时候就需要动态规划。
贪心的套路（什么时候用贪心）
贪心算法并没有固定的套路。
唯一的难点就是如何通过局部最优，推出整体最优。
如何验证可不可以用贪心算法呢？
- 最好用的策略就是举反例，如果想不到反例，那么就试一试贪心吧。
面试中基本不会让面试者现场证明贪心的合理性，代码写出来跑过测试用例即可，或者自己能自圆其说理由就行了。
举一个不太恰当的例子：我要用一下1+1 = 2，但我要先证明1+1 为什么等于2。严谨是严谨了，但没必要。
虽然这个例子很极端，但可以表达这么个意思：刷题或者面试的时候，手动模拟一下感觉可以局部最优推出整体最优，而且想不到反例，那么就试一试贪心。
例如刚刚举的拿钞票的例子，就是模拟一下每次拿做大的，最后就能拿到最多的钱，这还要数学证明的话，其实就不在算法面试的范围内了，可以看看专业的数学书籍！
所以这也是为什么很多同学通过（accept）了贪心的题目，但都不知道自己用了贪心算法，**因为贪心有时候就是常识性的推导，所以会认为本应该就这么做！
一般的解题步骤
贪心算法一般分为如下四步：
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
剑指offer
剑指 Offer 45. 把数组排成最小的数【中等】
题目内容：输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
思路：
1、排序+拼接，关键是依据x+y < y + x，来进行组成排序
复杂度分析：时间复杂度O(n.logn)，空间复杂度O(n)
class Solution { //以 a + b < b + a，合并为最小的来作为排序条件处理，最后来进行合并 public String minNumber(int[] nums) { //将nums处理为String数组这样的话，有利于之后快排根据指定条件规则 String[] numStrs = new String[nums.length]; for (int i = 0; i < nums.length; i++) { numStrs[i] = String.valueOf(nums[i]); } //排序：根据a+b < b+a quickSort(numStrs, 0, nums.length - 1); StringBuilder str = new StringBuilder(); for (String num: numStrs) { str.append(num); } return str.toString(); } public void quickSort(String[] nums, int l, int r) { if (l >= r) { return; } int j = l; for (int i = l + 1; i <= r; i++) { //若是返回为1，那么表示需要交换，前者更大 if ((nums[l] + nums[i]).compareTo(nums[i] + nums[l]) > 0) { j++; String temp = nums[j]; nums[j] = nums[i]; nums[i] = temp; } } String temp = nums[j]; nums[j] = nums[l]; nums[l] = temp; quickSort(nums, j + 1, r); quickSort(nums, l, j - 1); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
其中排序可以直接调用API：
//排序 Arrays.sort(numStrs, (a, b) -> (a + b).compareTo(b + a));- 1
- 2
牛客网
主持人调度（二）【中等】
问题
问题描述：针对于compator比较器中使用o1-o2与if (o1 > o2) return 1;xxx的区别？
对于o1-o2只有在数字为正数的时候才能够有升序效果，对于其中数字是负数时，这样就无效了！
public static void main(String[] args) { Test test = new Test(); int[] ans = new int[]{2,5,4,2,1}; int[][] startEnd = new int[][]{ {-2, 1}, {-1, 4}, {1, 3}, {3, 5} }; Comparator<Object> comparator1 = new Comparator<Object>() { public int compare(Object o1, Object o2) { int[] one = (int[]) o1; int[] two = (int[]) o2; if (one[0] > two[0]) return 1; if (one[0] == two[0]) return 0; else return -1; } }; Comparator<Object> comparator2 = new Comparator<Object>() { public int compare(Object o1, Object o2) { int[] one = (int[]) o1; int[] two = (int[]) o2; return one[0] - two[0]; } }; Arrays.sort(startEnd, comparator2); for (int[] ints : startEnd) { System.out.println(Arrays.toString(ints)); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
问题效果：
方案
思路1：排序+遍历。
将开始时间分为一组，结束时间分为一组，并对其进行排序。遍历start数组，实际上每进行一个比较就能够直接区分出是否要加主持（start>end，j++；start<=end，res++），res表示的就是主持的数量。
复杂度分析：
- 时间复杂度：O(nlogn)，两个sort+一个遍历
- 空间复杂度：O(n)
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 计算成功举办活动需要多少名主持人 * @param n int整型 有n个活动 * @param startEnd int整型二维数组 startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间 * @return int整型 */ public int minmumNumberOfHost (int n, int[][] startEnd) { //维护两个数组 int[] startArr = new int[startEnd.length]; int[] endArr = new int[startEnd.length]; for (int i = 0; i < startEnd.length; i++) { startArr[i] = startEnd[i][0]; endArr[i] = startEnd[i][1]; } //1、对开始时间以及结束时间来进行排序 Arrays.sort(startArr); Arrays.sort(endArr); //主持人 int res = 0; //2、遍历来进行调度分配 for (int i = 0, j = 0; i < startArr.length; i++) { //若是开始时间>=结束时间，那么无需分配一名新的主持 if (startArr[i] >= endArr[j]) { j++; }else { res++; } } return res; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
思路2：采用重载sort+大顶堆。
- 根据数组的start来进行排序，使用一个优先队列来不断的将最小的endtime来移到队列头部，同样也是对所有的周期进行了次遍历，与思路1大致相同，可以两者结合着理解。
复杂度分析：
- 时间复杂度：O(nlogn)，一个sort+队列中sort+遍历
- 空间复杂度：O(n)
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 计算成功举办活动需要多少名主持人 * @param n int整型 有n个活动 * @param startEnd int整型二维数组 startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间 * @return int整型 */ public int minmumNumberOfHost (int n, int[][] startEnd) { //根据start时间来进行排序 //举例：【1,3】，【2,4】，【1,5】 => 【1,3】，【1,5】，【2,4】 Arrays.sort(startEnd, (o1, o2)-> { if (o1[0] > o2[0]) { return 1; }else if (o1[0] < o2[0]) { return -1; } return 0; }); //维护一个优先队列（会将越小的放置在前，针对于endtime） PriorityQueue<Integer> queue = new PriorityQueue<Integer>(); //虚拟结点加入 queue.offer(Integer.MIN_VALUE); for (int i = 0; i < startEnd.length; i++) { //拿【1,3】，【1,5】，【2,4】来看，第二个1与前面的3来比较，很明显冲突了，所以需要添加1人（也就是不走poll()） //若是2与2来比较，则不冲突，那么就会走poll() if (queue.peek() <= startEnd[i][0]) { queue.poll(); } //将end时间添加 queue.offer(startEnd[i][1]); } return queue.size(); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
分糖果问题【中等】
题目链接：分糖果问题
题目内容：一群孩子做游戏，现在请你根据游戏得分来发糖果，要求如下：
-
每个孩子不管得分多少，起码分到一个糖果。
-
任意两个相邻的孩子之间，得分较多的孩子必须拿多一些糖果。(若相同则无此限制)
给定一个数组 arrarr 代表得分数组，请返回最少需要多少糖果。
思路1：贪心策略。使用一个数组来分别表示每个小孩获取的糖果数量，从左向右遍历一遍（右分>左分 -》 右边=左分+1），从右向左遍历一遍（左分>右分 && 左糖<=右糖 ==> 左边=右分+1）
复杂度分析：
- 时间复杂度：O(n)，三次遍历
- 空间复杂度：O(n)，一个数组的空间。
import java.util.*; public class Solution { /** * pick candy * @param arr int整型一维数组 the array * @return int整型 */ public int candy (int[] arr) { //定义一个数组，数组中的元素都初始化1，表示当前每个小朋友都能够分到一粒糖果 int[] nums = new int[arr.length]; Arrays.fill(nums, 1); //从左向右进行遍历，若是当前小朋友比左边小朋友得分高，那么为左边小孩得到糖果+1 for (int i = 1; i < arr.length; i++) { if (arr[i] > arr[i - 1]) { nums[i] = nums[i - 1] + 1; } } //从右向左遍历,若是左边的>右边小孩得分 && 左边的糖果数量 <= 右边的糖果数量，此时更新左边的小孩获得糖果数量=右边糖果数+1 for (int i = arr.length - 2; i >= 0; i--) { if (arr[i] > arr[i + 1] && nums[i] <= nums[i + 1]) { nums[i] = nums[i + 1] + 1; } } //统计糖果数量 int res = 0; for (int i = 0; i < nums.length; i++) { res += nums[i]; } return res; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
leetcode
455. 分发饼干【简单】
题目链接：455. 分发饼干
题目内容：
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。 对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。 示例 1: 输入: g = [1,2,3], s = [1,1] 输出: 1 解释: 你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。 虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。 所以你应该输出1。 示例 2: 输入: g = [1,2], s = [1,2,3] 输出: 2 解释: 你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。 你拥有的饼干数量和尺寸都足以让所有孩子满足。 所以你应该输出2. 提示： 1 <= g.length <= 3 * 104 0 <= s.length <= 3 * 104 1 <= g[i], s[j] <= 231 - 1- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
思路：
1、排序+贪心（先满足胃口小的）
思路： 先将饼干大小以及小孩子胃口大小按照从小到大排序，紧接着以小孩子为中心，来从前往后依次与饼干比对是否有满足的若是有的话饼干位置以及孩子位置往后一格，若是不满足仅仅移动饼干位置。
代码：
public int findContentChildren(int[] g, int[] s) { Arrays.sort(g); Arrays.sort(s); int count = 0; //childPos：孩子的位置 //sweetPos：糖果的位置 //从小胃口开始，优先喂给小胃口的。每次比对糖果数量位置必+1 for (int childPos = 0, sweetPos = 0; childPos < g.length && sweetPos < s.length; sweetPos++) { //能满足时，孩子位置+1，满足数量+1 if (g[childPos] <= s[sweetPos]) { count++; childPos++; } } return count; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
53.最大子序和【中等】
参考：leetcode官方题解
题目链接：53. 最大子序和
题目内容：
给你一个整数数组
nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。
速记：
①使用贪心，通过判断之前连续数组和是否>0来决定最新的连续子数组值。每次遍历都会进行最大值的比对来求取。 ②使用动规列出方程式*f*(*i*)=max{*f*(*i*−1)+*nums*[*i*],*nums*[*i*]}，通过不断比较最新合并值以及后一个值来判断是否继续相连，其实本质思想与上面的贪心思路都一致！只不过这里使用动规形式来体现。- 1
- 2
思路：
1、贪心。
[-2,1,-3,4,-1,2,1,-5,4] ans来表示最大值，sum用于临时存储连续子数组的和。 遍历一遍 1、如果sum>0，表示仍有增益，那么直接加上下面的元素。 2、如果sum<=0，那么无论后面的值为正数或小数，前面的其实都无效，此时直接sum=新值即可。 3、每遍历一个元素要与实际存储最大值的res进行比较来取出最大值赋值给res。- 1
- 2
- 3
- 4
- 5
- 6
复杂度分析：时间复杂度O(n)，空间复杂度O(1)
public int maxSubArray(int[] nums) { if(nums == null){ return 0; } int ans = nums[0]; int sum = 0; for (int i = 0; i < nums.length; i++){ //若是结果>0，那么直接加上新的元素 if ( sum > 0 ){ sum += nums[i]; }else{ //若是结果<=0，此时前面的的连续子数组不统一,直接设置新的值 sum = nums[i]; } //此时再将最新组合的数据与原本保留的最大值来进行比较 ans = Math.max( sum , ans); } return ans; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
2、动态规划
思路：连续子数组的最大和，以i下标的数与之前i-1个数相比较，通过对
nums[i]和f(i-1)+nums[i]的大小，来获取一个较大的数。若是前者大说明f(i-1)整和是负数那么直接从nums[i]重新开始，若是后者大表明连续的子数组和为最大即可与后面相连。f(i)=max{f(i−1)+nums[i],nums[i]}
复杂度分析：时间复杂度O(n)，空间复杂度O(1)
public int maxSubArray(int[] nums) { if (nums.length == 1){ return nums[0]; } int pre = nums[0], maxAns = nums[0]; for (int i = 1; i < nums.length; i++){ //动规式子：将前面连续的值记上nums[i]与nums[i]进行比较 pre = Math.max(pre + nums[i], nums[i]); maxAns = Math.max(pre, maxAns); } return maxAns; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
406. 根据身高重建队列【中等】
学习：贪心解法
题目链接：406. 根据身高重建队列
题目内容：
假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。
思路：
1、身高从高到低排序（贪心）
思路：按照每个人的身高从高到低排序，若是身高相同则按照排序位置升序；排序结束后每个人按照排序位置来插入到指定位置的链表即可。
[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] 排序：[[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]] 开始进行依次插入： 原始二维数组：[] 插入[7,0]：[[7,0]] 插入[7,1]：[[7,0],[7,1]] 插入[6,1]：[[7,0],[6,1],[7,1]] 插入[5,0]：[[5,0],[7,0],[6,1],[7,1]] 插入[5,2]：[[5,0],[7,0],[5,2],[6,1],[7,1]] 插入[4,4]：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
可以发现，之后插入的不同身高的数组信息都不会影响到之后的成员信息位置，因为他们的身高始终比进行移动的成员矮，那么每次新插入队列的成员直接插入指定排序位置即可！
复杂度分析：时间复杂度O(n2)，空间复杂度O(logn)
public int[][] reconstructQueue(int[][] people) { //第1关键词按照身高(o[0])降序排序，若是升高相同按照排名o[1]升序 Arrays.sort(people,(o1,o2)->{ if (o1[0] != o2[0]){ return o2[0] - o1[0]; } else { return o1[1] - o2[1]; } }); //排序结束之后，按照每组数的排名位置插入到链表中 LinkedList<int[]> queue = new LinkedList<>(); for (int[] person : people) { queue.add(person[1], person); } return queue.toArray(new int[people.length][]);//通过传递泛型参数来进行返回正确的类型 }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
135题:分发糖果【困难，与牛客2相同】
题目链接：分糖果问题
题目内容：一群孩子做游戏，现在请你根据游戏得分来发糖果，要求如下：
-
每个孩子不管得分多少，起码分到一个糖果。
-
任意两个相邻的孩子之间，得分较多的孩子必须拿多一些糖果。(若相同则无此限制)
给定一个数组 arrarr 代表得分数组，请返回最少需要多少糖果。
思路1：贪心策略。使用一个数组来分别表示每个小孩获取的糖果数量，从左向右遍历一遍（右分>左分 -》 右边=左分+1），从右向左遍历一遍（左分>右分 && 左糖<=右糖 ==> 左边=右分+1）
复杂度分析：
- 时间复杂度：O(n)，三次遍历
- 空间复杂度：O(n)，一个数组的空间。
class Solution { public int candy(int[] ratings) { int[] nums = new int[ratings.length]; Arrays.fill(nums, 1); for (int i = 1; i < nums.length; i++) { if (ratings[i] > ratings[i - 1]) { nums[i] = nums[i - 1] + 1; } } for (int i = nums.length - 2; i >= 0; i--) { //左分>右分 && 左糖 <= 右糖 if (ratings[i] > ratings[i + 1] && nums[i] <= nums[i + 1]) { nums[i] = nums[i + 1] + 1; } } int res = 0; for (int i = 0; i < nums.length; i++) { res += nums[i]; } return res; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
-
相关阅读:
国民技术N32G031系列单片机的AD采样
SELinux 介绍
“乘风破浪”的芒果超媒，能上岸吗？
Spring实战之有条件的加载bean/按某个条件加载bean
从零搭建微服务架构：Spring Boot与Nacos完美整合
被迫开始学习Typescript —— class
mysql性能分析
mysql事务
uniapp webview实现双向通信
微信小程序开发之会议oa（首页搭建）
- 原文地址：https://blog.csdn.net/cl939974883/article/details/126430223