class089 贪心经典题目专题1【左程云算法】
- 前言
- 版权
- 推荐
- class089 贪心经典题目专题1
- code1 179. 最大数
- code2 1029. 两地调度
- code3 1553. 吃掉 N 个橘子的最少天数
- code4 253. 会议室II
- code5 630. 课程表 III
- code6 1167. 连接棒材的最低费用(leetcode测试)
- code6 P1090 连接棒材的最低费用(洛谷测试)
- 最后
前言
2024-1-3 18:45:02
2024-4-29 11:42:59
很早之前看了，应该是2月28号开学火车上看的
今天回顾一下
以下内容源自《【左程云算法】》
仅供学习交流使用
版权
禁止其他平台发布时删除以下此话
本文首次发布于CSDN平台
作者是CSDN@日星月云
博客主页是https://jsss-1.blog.csdn.net
禁止其他平台发布时删除以上此话
推荐
算法讲解089【必备】贪心经典题目专题1
class089 贪心经典题目专题1
code1 179. 最大数
// 最大数
// 给定一组非负整数nums
// 重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数
// 测试链接 : https://leetcode.cn/problems/largest-number/
贪心思路：
按两个字符拼接排序，即(a, b) -> (b + a).compareTo(a + b)
再连接所有的字符串
证明排序是有效的，具有传递性：
证明：a.b≤b.a，b.c≤c.b ⇒ a.b≤c.a（.是连接操作）
连接操作可以看为左移操作
定义f(k)，某一进制它的[k长度]次方
此题中k是字符串，进制是26
a.b就可以表示a * f(b)+b
所以已知条件
a * f(b)+b ≤ b * f(b)+a ①
b * f©+c ≤ c * f(b)+b ②
①式两边先-b，在* c，变为
a * f(b) * c ≤ (b * f(a)+a-b) * c ③，乘以非负值，不等号不改变方向
②式两边先-b，在* a，变为
(b * f©+c-b) * a ≤ c * f(b)* a ④
③左边和④右边相等，因为满足乘法的交换律和结合律
所以(b * f( c )+c-b) * a ≤ (b * f(a)+a-b) * c，展开
b * f© * a+ac-ba ≤ b * f(a) * c+ac-bc
等价于f( c ) * a-a ≤ f(a) * c-c，操作：同时-ac再/b
等价于f( c ) * a+c ≤ f(a) * c+a，移项操作
等价于 a.b≤c.a。
证明完毕
如果排完序之后是
[… a m1 m2 m3 b …]，任意两个交换都会变大
[… m1 a m2 m3 b …]
[… m1 m2 a m3 b …]
[… m1 m2 a m3 b …]
[… m1 m2 m3 a b …]
[… m1 m2 m3 b a…]
[… m1 m2 b m3 a…]
[… m1 m2 b m3 a…]
[… m1 b m2 m3 a…]
[… b m1 m2 m3 a…]
每一步交换都是变得更大了，因为a.b<=b.a
所以排序完毕连接起来就是字典序最小的
way1是全排列之后，所有结果全部排序，得到最小的
way2是按照拼接排序，然后依次拼接，就能得到最小的
提交代码，排序策略是谁大谁在前，就能得到最大的
package class089;
import java.util.ArrayList;
import java.util.Arrays;
// 最大数
// 给定一组非负整数nums
// 重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数
// 测试链接 : https://leetcode.cn/problems/largest-number/
public class Code01_LargestNumber {
// strs中全是非空字符串，要把所有字符串拼接起来，形成字典序最小的结果
// 暴力方法
// 为了验证
// 生成所有可能的排列
// 其中选出字典序最小的结果
public static String way1(String[] strs) {
ArrayList<String> ans = new ArrayList<>();
f(strs, 0, ans);
ans.sort((a, b) -> a.compareTo(b));
return ans.get(0);
}
// 全排列代码，讲解038，常见经典递归过程解析
public static void f(String[] strs, int i, ArrayList<String> ans) {
if (i == strs.length) {
StringBuilder path = new StringBuilder();
for (String s : strs) {
path.append(s);
}
ans.add(path.toString());
} else {
for (int j = i; j < strs.length; j++) {
swap(strs, i, j);
f(strs, i + 1, ans);
swap(strs, i, j);
}
}
}
public static void swap(String[] strs, int i, int j) {
String tmp = strs[i];
strs[i] = strs[j];
strs[j] = tmp;
}
// strs中全是非空字符串，要把所有字符串拼接起来，形成字典序最小的结果
// 正式方法
// 时间复杂度O(n*logn)
public static String way2(String[] strs) {
Arrays.sort(strs, (a, b) -> (a + b).compareTo(b + a));
StringBuilder path = new StringBuilder();
for (int i = 0; i < strs.length; i++) {
path.append(strs[i]);
}
return path.toString();
}
// 为了验证
// 生成长度1~n的随机字符串数组
public static String[] randomStringArray(int n, int m, int v) {
String[] ans = new String[(int) (Math.random() * n) + 1];
for (int i = 0; i < ans.length; i++) {
ans[i] = randomString(m, v);
}
return ans;
}
// 为了验证
// 生成长度1~m，字符种类有v种，随机字符串
public static String randomString(int m, int v) {
int len = (int) (Math.random() * m) + 1;
char[] ans = new char[len];
for (int i = 0; i < len; i++) {
ans[i] = (char) ('a' + (int) (Math.random() * v));
}
return String.valueOf(ans);
}
// 为了验证
// 对数器
public static void main(String[] args) {
int n = 8; // 数组中最多几个字符串
int m = 5; // 字符串长度最大多长
int v = 4; // 字符的种类有几种
int testTimes = 2000;
System.out.println("测试开始");
for (int i = 1; i <= testTimes; i++) {
String[] strs = randomStringArray(n, m, v);
String ans1 = way1(strs);
String ans2 = way2(strs);
if (!ans1.equals(ans2)) {
// 如果出错了
// 可以增加打印行为找到一组出错的例子
// 然后去debug
System.out.println("出错了！");
}
if (i % 100 == 0) {
System.out.println("测试到第" + i + "组");
}
}
System.out.println("测试结束");
}
// 测试链接 : https://leetcode.cn/problems/largest-number/
public static String largestNumber(int[] nums) {
int n = nums.length;
String[] strs = new String[n];
for (int i = 0; i < n; i++) {
strs[i] = String.valueOf(nums[i]);
}
//这里是谁大谁在前
Arrays.sort(strs, (a, b) -> (b + a).compareTo(a + b));
if (strs[0].equals("0")) {
return "0";
}
StringBuilder path = new StringBuilder();
for (String s : strs) {
path.append(s);
}
return path.toString();
}
}
code2 1029. 两地调度
// 两地调度
// 公司计划面试2n个人，给定一个数组 costs
// 其中costs[i]=[aCosti, bCosti]
// 表示第i人飞往a市的费用为aCosti，飞往b市的费用为bCosti
// 返回将每个人都飞到a、b中某座城市的最低费用
// 要求每个城市都有n人抵达
// 测试链接 : https://leetcode.cn/problems/two-city-scheduling/
现在有两个人
a b 改b的代价
0: [5 10] 5
1: [12 20] 8
先假设都去a地，代价是17
现在1个去a，1个去b
就看谁改到b地的代价小，谁就去
所以0号去
贪心思路：
首先所有人都去a地
然后收集每个人a地改b地的费用
排序，收集前n和即可
如果改的代价是负数，更好
public static int twoCitySchedCost(int[][] costs) {
int n = costs.length;
int[] arr = new int[n];//a地改b地的代价
int sum = 0;//都去a
for (int i = 0; i < n; i++) {
arr[i] = costs[i][1] - costs[i][0];
sum += costs[i][0];
}
Arrays.sort(arr);//排序
int m = n / 2;
for (int i = 0; i < m; i++) {
sum += arr[i];//收集
}
return sum;
}
code3 1553. 吃掉 N 个橘子的最少天数
// 吃掉N个橘子的最少天数
// 厨房里总共有 n 个橘子，你决定每一天选择如下方式之一吃这些橘子
// 1) 吃掉一个橘子
// 2) 如果剩余橘子数 n 能被 2 整除，那么你可以吃掉 n/2 个橘子
// 3) 如果剩余橘子数 n 能被 3 整除，那么你可以吃掉 2*(n/3) 个橘子
// 每天你只能从以上 3 种方案中选择一种方案
// 请你返回吃掉所有 n 个橘子的最少天数
// 测试链接 : https://leetcode.cn/problems/minimum-number-of-days-to-eat-n-oranges/
题目是每天选择一个方案
n=0,结果是0
n=1,就选1)方案，吃一天，结果是1
n>=1，能按比例吃就按比例吃
n%2=0,就按2）方案，吃一天,后续n/2 按2)方案
n%2=1,额外吃一天，再按2)方案，吃一天，后续n/2 按2)方案
n%3=0,就按3）方案，吃一天，后续n/3 按3)方案
n%3=1,额外吃一天，再按3)方案，吃一天，后续n/3 按3)方案
n%3=2,额外吃二天，再按3)方案，吃一天，后续n/3 按3)方案
额外吃的天数就是模的值，当前天吃是1天，后续天数就是再调方法
时间复杂度：O(log2 n+log3 n)
package class089;
import java.util.HashMap;
// 吃掉N个橘子的最少天数
// 厨房里总共有 n 个橘子，你决定每一天选择如下方式之一吃这些橘子
// 1）吃掉一个橘子
// 2) 如果剩余橘子数 n 能被 2 整除，那么你可以吃掉 n/2 个橘子
// 3) 如果剩余橘子数 n 能被 3 整除，那么你可以吃掉 2*(n/3) 个橘子
// 每天你只能从以上 3 种方案中选择一种方案
// 请你返回吃掉所有 n 个橘子的最少天数
// 测试链接 : https://leetcode.cn/problems/minimum-number-of-days-to-eat-n-oranges/
public class Code03_MinimumNumberEatOranges {
// 所有的答案都填在这个表里
// 这个表对所有的过程共用
public static HashMap<Integer, Integer> dp = new HashMap<>();
//时间复杂度：O(log~2~ n+log~3~ n)
public static int minDays(int n) {
if (n <= 1) {
return n;
}
if (dp.containsKey(n)) {
return dp.get(n);
}
// 1) 吃掉一个橘子
// 2) 如果n能被2整除，吃掉一半的橘子，剩下一半
// 3) 如果n能被3正数，吃掉三分之二的橘子，剩下三分之一
// 因为方法2）和3），是按比例吃橘子，所以必然会非常快
// 所以，决策如下：
// 可能性1：为了使用2）方法，先把橘子吃成2的整数倍，然后直接干掉一半，剩下的n/2调用递归
// 即，n % 2 + 1 + minDays(n/2)
// 可能性2：为了使用3）方法，先把橘子吃成3的整数倍，然后直接干掉三分之二，剩下的n/3调用递归
// 即，n % 3 + 1 + minDays(n/3)
// 至于方法1)，完全是为了这两种可能性服务的，因为能按比例吃，肯定比一个一个吃快(显而易见的贪心)
int ans = Math.min(n % 2 + 1 + minDays(n / 2), n % 3 + 1 + minDays(n / 3));
dp.put(n, ans);
return ans;
}
}
code4 253. 会议室II
// 会议室II
// 给你一个会议时间安排的数组 intervals
// 每个会议时间都会包括开始和结束的时间intervals[i]=[starti, endi]
// 返回所需会议室的最小数量
// 测试链接 : https://leetcode.cn/problems/meeting-rooms-ii/
最多线段重合问题
哪一个时间点，线段的重合数最多
付费题：
253. 会议室II
给你一个会议时间安排的数组 intervals，每个会议时间都
会包括开始和结束的时间 intervals[i]=[starti,endi]
返回所需会议室的最小数量。
示例 1:
输入:intervals=[[0,30],[5,10],[15,20]]
输出:2
示例 2:
输入:intervals =[[7,10],[2,4]]
输出:1
可以看讲解027，题目2，去练习
https://www.nowcoder.com/practice/1ae8d0b6bb4e4bcdbf64ec491f63fc37
package class089;
import java.util.Arrays;
import java.util.PriorityQueue;
// 会议室II
// 给你一个会议时间安排的数组 intervals
// 每个会议时间都会包括开始和结束的时间intervals[i]=[starti, endi]
// 返回所需会议室的最小数量
// 测试链接 : https://leetcode.cn/problems/meeting-rooms-ii/
public class Code04_MeetingRoomsII {
//时间复杂度：O(n*log(n))
public static int minMeetingRooms(int[][] meeting) {
int n = meeting.length;
//会议按开始时间，从小到大排序
Arrays.sort(meeting, (a, b) -> a[0] - b[0]);
//结束时间的小根堆
PriorityQueue<Integer> heap = new PriorityQueue<>();
int ans = 0;
//从小到大遍历
for (int i = 0; i < n; i++) {
//如果最早结束小于当前的开始，就弹出。即没有重合
while (!heap.isEmpty() && heap.peek() <= meeting[i][0]) {
heap.poll();
}
//加入当前会议的结束时间
heap.add(meeting[i][1]);
//找到最大重合数
ans = Math.max(ans, heap.size());
}
return ans;
}
}
code5 630. 课程表 III
// 课程表III
// 这里有n门不同的在线课程，按从1到n编号
// 给你一个数组courses
// 其中courses[i]=[durationi, lastDayi]表示第i门课将会持续上durationi天课
// 并且必须在不晚于lastDayi的时候完成
// 你的学期从第 1 天开始
// 且不能同时修读两门及两门以上的课程
// 返回你最多可以修读的课程数目
// 测试链接 : https://leetcode.cn/problems/course-schedule-iii/
课程：[代价天数，截止日期]
最早截止时间优先
举例：
[4,10] [12,20] [5,20]
修完第一个，天数来到4
可以修第二个，因为4+12<=20
修完第二个，天数来的16
不可以修[5,20]
但是，既然收益都是多学一门课，但是代价不一样，自然要选择代价小的课程
如果修[5,20]而不是[12,20]，天数来到了9
如果time+代价<截止，就可修此课
如果time+代价>截止，看堆定收集的最大代价谁大
如果比其小，就弹出堆，进来小代价
package class089;
import java.util.Arrays;
import java.util.PriorityQueue;
// 课程表III
// 这里有n门不同的在线课程，按从1到n编号
// 给你一个数组courses
// 其中courses[i]=[durationi, lastDayi]表示第i门课将会持续上durationi天课
// 并且必须在不晚于lastDayi的时候完成
// 你的学期从第 1 天开始
// 且不能同时修读两门及两门以上的课程
// 返回你最多可以修读的课程数目
// 测试链接 : https://leetcode.cn/problems/course-schedule-iii/
public class Code05_CourseScheduleIII {
public static int scheduleCourse(int[][] courses) {
// 0 : 代价
// 1 : 截止
Arrays.sort(courses, (a, b) -> a[1] - b[1]);
// 大根堆
PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> b - a);
int time = 0;//当前天数
for (int[] c : courses) {
if (time + c[0] <= c[1]) {
heap.add(c[0]);
time += c[0];
} else {
// time + c[0] > c[1]
if (!heap.isEmpty() && heap.peek() > c[0]) {
time += c[0] - heap.poll(); //收益不变，淘汰代价高的，换为代价低的
heap.add(c[0]);
}
}
}
return heap.size();
}
}
code6 1167. 连接棒材的最低费用(leetcode测试)
// 连接棒材的最低费用(leetcode测试)
// 你有一些长度为正整数的棍子
// 这些长度以数组sticks的形式给出
// sticks[i]是第i个木棍的长度
// 你可以通过支付x+y的成本将任意两个长度为x和y的棍子连接成一个棍子
// 你必须连接所有的棍子，直到剩下一个棍子
// 返回以这种方式将所有给定的棍子连接成一个棍子的最小成本
// 测试链接 : https://leetcode.cn/problems/minimum-cost-to-connect-sticks/
举例：
13长度的金条，分为[1,3,9]，每次分承担当前金条长度的代价
如果这样分
13 ,承担13代价
/\
1 12 ,承担12代价
/\
3 9
总共25的代价
不如
13 ,承担13代价
/\
4 9 ,承担4代价
/\
1 3
总共17代价
类似哈夫曼编码
每次从原数组找最小的两个并删掉，合并这两个，将合并加入到原数组，
继续以上操作直到剩余1个
package class089;
import java.util.PriorityQueue;
// 连接棒材的最低费用(leetcode测试)
// 你有一些长度为正整数的棍子
// 这些长度以数组sticks的形式给出
// sticks[i]是第i个木棍的长度
// 你可以通过支付x+y的成本将任意两个长度为x和y的棍子连接成一个棍子
// 你必须连接所有的棍子，直到剩下一个棍子
// 返回以这种方式将所有给定的棍子连接成一个棍子的最小成本
// 测试链接 : https://leetcode.cn/problems/minimum-cost-to-connect-sticks/
public class Code06_MinimumCostToConnectSticks1 {
public static int connectSticks(int[] arr) {
// 小根堆
PriorityQueue<Integer> heap = new PriorityQueue<>();
for (int i = 0; i < arr.length; i++) {
heap.add(arr[i]);
}
int sum = 0;//记录总代价
int cur = 0;//记录当前代价
while (heap.size() > 1) {
cur = heap.poll() + heap.poll();//每次弹出最小的两个，合并
sum += cur;//记录
heap.add(cur);//放入
}
return sum;
}
}
code6 P1090 连接棒材的最低费用(洛谷测试)
// 连接棒材的最低费用(洛谷测试)
// 你有一些长度为正整数的棍子
// 这些长度以数组sticks的形式给出
// sticks[i]是第i个木棍的长度
// 你可以通过支付x+y的成本将任意两个长度为x和y的棍子连接成一个棍子
// 你必须连接所有的棍子，直到剩下一个棍子
// 返回以这种方式将所有给定的棍子连接成一个棍子的最小成本
// 测试链接 : https://www.luogu.com.cn/problem/P1090
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过
package class089;
// 连接棒材的最低费用(洛谷测试)
// 你有一些长度为正整数的棍子
// 这些长度以数组sticks的形式给出
// sticks[i]是第i个木棍的长度
// 你可以通过支付x+y的成本将任意两个长度为x和y的棍子连接成一个棍子
// 你必须连接所有的棍子，直到剩下一个棍子
// 返回以这种方式将所有给定的棍子连接成一个棍子的最小成本
// 测试链接 : https://www.luogu.com.cn/problem/P1090
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
public class Code06_MinimumCostToConnectSticks2 {
public static int MAXN = 10001;
public static int[] nums = new int[MAXN];
public static int n;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer in = new StreamTokenizer(br);
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
while (in.nextToken() != StreamTokenizer.TT_EOF) {
n = (int) in.nval;
for (int i = 0; i < n; i++) {
in.nextToken();
nums[i] = (int) in.nval;
}
out.println(minCost());
out.flush();
}
out.flush();
out.close();
br.close();
}
public static int minCost() {
size = 0;
for (int i = 0; i < n; i++) {
add(nums[i]);
}
int sum = 0;
int cur = 0;
while (size > 1) {
cur = pop() + pop();
sum += cur;
add(cur);
}
return sum;
}
// 手写小根堆
public static int[] heap = new int[MAXN];
// 堆的大小
public static int size;
public static void add(int x) {
heap[size] = x;
int i = size++;
while (heap[i] < heap[(i - 1) / 2]) {
swap(i, (i - 1) / 2);
i = (i - 1) / 2;
}
}
public static int pop() {
int ans = heap[0];
swap(0, --size);
int i = 0, l = 1, best;
while (l < size) {
best = l + 1 < size && heap[l + 1] < heap[l] ? l + 1 : l;
best = heap[best] < heap[i] ? best : i;
if (best == i) {
break;
}
swap(i, best);
i = best;
l = i * 2 + 1;
}
return ans;
}
public static void swap(int i, int j) {
int tmp = heap[i];
heap[i] = heap[j];
heap[j] = tmp;
}
}
最后
2024-4-29 12:42:19
迎着日光月光星光，直面风霜雨霜雪霜。
![K8S controller编写之Informer的原理+使用[drift]](https://img-blog.csdnimg.cn/direct/28de4fb771fb4b84bda3855ec838ea41.png)
