Skip to content

Commit 7626581

Browse files
dairongpengdairongpeng
committed
coffee time code refactor
1 parent 05e5abd commit 7626581

File tree

1 file changed

+110
-195
lines changed

1 file changed

+110
-195
lines changed

‎12-暴力递归到动态规划优化思路.md

Lines changed: 110 additions & 195 deletions
Original file line numberDiff line numberDiff line change
@@ -873,235 +873,150 @@ func lcse(str1, str2 string) int {
873873
例题：给定一个数组，代表每个人喝完咖啡准备刷杯子的时间，只有一台咖啡机，一次只能洗一个杯子，时间耗费a，洗完才能洗下一杯。每个咖啡杯也可以自己挥发干净，时间耗费b，咖啡杯可以并行挥发。返回让所有咖啡杯变干净的最早完成时间。三个参数：int[]arr , int a , int b（京东）
874874

875875

876-
```Java
877-
package class12;
876+
```Go
877+
package main
878878

879-
import java.util.Arrays;
880-
import java.util.Comparator;
881-
import java.util.PriorityQueue;
879+
import "math"
882880

883-
// 题目
884881
// 数组arr代表每一个咖啡机冲一杯咖啡的时间，每个咖啡机只能串行的制造咖啡。
885882
// 现在有n个人需要喝咖啡，只能用咖啡机来制造咖啡。
886883
// 认为每个人喝咖啡的时间非常短，冲好的时间即是喝完的时间。
887884
// 每个人喝完之后咖啡杯可以选择洗或者自然挥发干净，只有一台洗咖啡杯的机器，只能串行的洗咖啡杯。
888885
// 洗杯子的机器洗完一个杯子时间为a，任何一个杯子自然挥发干净的时间为b。
889886
// 四个参数：arr, n, a, b
890887
// 假设时间点从0开始，返回所有人喝完咖啡并洗完咖啡杯的全部过程结束后，至少来到什么时间点。
891-
public class Code06_Coffee {
892888

893-
// 方法一：暴力尝试方法
894-
public static int minTime1(int[] arr, int n, int a, int b) {
895-
int[] times = new int[arr.length];
896-
int[] drink = new int[n];
897-
return forceMake(arr, times, 0, drink, n, a, b);
898-
}
899-
900-
// 方法一，每个人暴力尝试用每一个咖啡机给自己做咖啡
901-
public static int forceMake(int[] arr, int[] times, int kth, int[] drink, int n, int a, int b) {
902-
if (kth == n) {
903-
int[] drinkSorted = Arrays.copyOf(drink, kth);
904-
Arrays.sort(drinkSorted);
905-
return forceWash(drinkSorted, a, b, 0, 0, 0);
906-
}
907-
int time = Integer.MAX_VALUE;
908-
for (int i = 0; i < arr.length; i++) {
909-
int work = arr[i];
910-
int pre = times[i];
911-
drink[kth] = pre + work;
912-
times[i] = pre + work;
913-
time = Math.min(time, forceMake(arr, times, kth + 1, drink, n, a, b));
914-
drink[kth] = 0;
915-
times[i] = pre;
889+
// 方法二，每个人暴力尝试用每一个咖啡机给自己做咖啡，优化成贪心
890+
func minTime2(arr []int, n, a, b int) int {
891+
heap := &Machines{
892+
Machines: make([]*Machine, 0),
916893
}
917-
return time;
918-
}
919894

920-
// 方法一，暴力尝试洗咖啡杯的方式
921-
public static int forceWash(int[] drinks, int a, int b, int index, int washLine, int time) {
922-
if (index == drinks.length) {
923-
return time;
895+
// 构造洗碗机加入堆中
896+
for i := 0; i < len(arr); i++ {
897+
heap.Push(&Machine{
898+
TimePoint: 0,
899+
WorkTime: arr[i],
900+
})
924901
}
925-
// 选择一：当前index号咖啡杯，选择用洗咖啡机刷干净
926-
int wash = Math.max(drinks[index], washLine) + a;
927-
int ans1 = forceWash(drinks, a, b, index + 1, wash, Math.max(wash, time));
928-
929-
// 选择二：当前index号咖啡杯，选择自然挥发
930-
int dry = drinks[index] + b;
931-
int ans2 = forceWash(drinks, a, b, index + 1, washLine, Math.max(dry, time));
932-
return Math.min(ans1, ans2);
902+
903+
drinks := make([]int, n)
904+
for i:=0; i<n; i++ {
905+
cur := heap.Pop().(*Machine)
906+
cur.TimePoint += cur.WorkTime
907+
drinks[i] = cur.TimePoint
908+
heap.Push(cur)
933909
}
934910

935-
// 方法二：稍微好一点的解法
936-
public static class Machine {
937-
public int timePoint;
938-
public int workTime;
911+
return processMachineTime(drinks, a, b, 0, 0)
912+
}
939913

940-
public Machine(int t, int w) {
941-
timePoint = t;
942-
workTime = w;
943-
}
944-
}
914+
// 方法二，洗咖啡杯的方式和原来一样，只是这个暴力版本减少了一个可变参数
915+
// process(drinks, 3, 10, 0,0)
916+
// a 洗一杯的时间 固定变量
917+
// b 自己挥发干净的时间 固定变量
918+
// drinks 每一个员工喝完的时间 固定变量
919+
// drinks[0..index-1]都已经干净了，不用你操心了
920+
// drinks[index...]都想变干净，这是我操心的，washLine表示洗的机器何时可用
921+
// drinks[index...]变干净，最少的时间点返回
922+
func processMachineTime(drinks []int, a, b, index, washLine int) int {
923+
if index == len(drinks) - 1 {
924+
return int(math.Min(math.Max(float64(washLine), float64(drinks[index] + a)), float64(drinks[index] + b)))
925+
}
926+
927+
// 剩不止一杯咖啡
928+
// wash是我当前的咖啡杯，洗完的时间
929+
wash := int(math.Max(float64(washLine), float64(drinks[index]))) + a // 洗，index一杯，结束的时间点
930+
// index+1...变干净的最早时间
931+
next1 := processMachineTime(drinks, a, b, index + 1, wash)
932+
// index....
933+
p1 := int(math.Max(float64(wash), float64(next1)))
934+
dry := drinks[index] + b // 挥发，index一杯，结束的时间点
935+
next2 := processMachineTime(drinks, a, b, index + 1, washLine)
936+
937+
p2 := int(math.Max(float64(dry), float64(next2)))
938+
return int(math.Min(float64(p1), float64(p2)))
939+
}
945940

946-
public static class MachineComparator implements Comparator<Machine> {
941+
// Machines 洗咖啡的机器构造堆结构
942+
type Machines struct {
943+
Machines []*Machine
944+
}
947945

948-
@Override
949-
public int compare(Machine o1, Machine o2) {
950-
return (o1.timePoint + o1.workTime) - (o2.timePoint + o2.workTime);
951-
}
946+
type Machine struct {
947+
TimePoint int
948+
WorkTime int
949+
}
952950

953-
}
951+
func (c Machines) Len() int {
952+
return len(c.Machines)
953+
}
954954

955-
// 方法二，每个人暴力尝试用每一个咖啡机给自己做咖啡，优化成贪心
956-
public static int minTime2(int[] arr, int n, int a, int b) {
957-
PriorityQueue<Machine> heap = new PriorityQueue<Machine>(new MachineComparator());
958-
for (int i = 0; i < arr.length; i++) {
959-
heap.add(new Machine(0, arr[i]));
960-
}
961-
int[] drinks = new int[n];
962-
for (int i = 0; i < n; i++) {
963-
Machine cur = heap.poll();
964-
cur.timePoint += cur.workTime;
965-
drinks[i] = cur.timePoint;
966-
heap.add(cur);
967-
}
968-
return process(drinks, a, b, 0, 0);
955+
// Less i对应的利润P的值大于j对应的值为true，则从大到小排序，即大根堆
956+
func (c Machines) Less(i, j int) bool {
957+
return (c.Machines[i].TimePoint + c.Machines[i].WorkTime) < (c.Machines[j].TimePoint + c.Machines[j].WorkTime)
958+
}
959+
960+
func (c Machines) Swap(i, j int) {
961+
c.Machines[i], c.Machines[j] = c.Machines[j], c.Machines[i]
962+
}
963+
964+
func (c *Machines) Push(h interface{}) {
965+
c.Machines = append(c.Machines, h.(*Machine))
966+
}
967+
968+
func (c *Machines) Pop() (x interface{}) {
969+
n := len(c.Machines)
970+
x = c.Machines[n-1]
971+
c.Machines = c.Machines[:n-1]
972+
return x
973+
}
974+
975+
// 方法三：最终版本，把方法二洗咖啡杯的暴力尝试进一步优化成动态规划
976+
func minTime3(arr []int, n, a, b int) int{
977+
heap := &Machines{
978+
Machines: make([]*Machine, 0),
969979
}
970980

971-
// 方法二，洗咖啡杯的方式和原来一样，只是这个暴力版本减少了一个可变参数
972-
973-
// process(drinks, 3, 10, 0,0)
974-
// a 洗一杯的时间 固定变量
975-
// b 自己挥发干净的时间 固定变量
976-
// drinks 每一个员工喝完的时间 固定变量
977-
// drinks[0..index-1]都已经干净了，不用你操心了
978-
// drinks[index...]都想变干净，这是我操心的，washLine表示洗的机器何时可用
979-
// drinks[index...]变干净，最少的时间点返回
980-
public static int process(int[] drinks, int a, int b, int index, int washLine) {
981-
if (index == drinks.length - 1) {
982-
return Math.min(Math.max(washLine, drinks[index]) + a, drinks[index] + b);
983-
}
984-
// 剩不止一杯咖啡
985-
// wash是我当前的咖啡杯，洗完的时间
986-
int wash = Math.max(washLine, drinks[index]) + a;// 洗，index一杯，结束的时间点
987-
// index+1...变干净的最早时间
988-
int next1 = process(drinks, a, b, index + 1, wash);
989-
// index....
990-
int p1 = Math.max(wash, next1);
991-
int dry = drinks[index] + b; // 挥发，index一杯，结束的时间点
992-
int next2 = process(drinks, a, b, index + 1, washLine);
993-
int p2 = Math.max(dry, next2);
994-
return Math.min(p1, p2);
981+
// 构造洗碗机加入堆中
982+
for i := 0; i < len(arr); i++ {
983+
heap.Push(&Machine{
984+
TimePoint: 0,
985+
WorkTime: arr[i],
986+
})
995987
}
996988

997-
public static int dp(int[] drinks, int a, int b) {
998-
if (a >= b) {
999-
return drinks[drinks.length - 1] + b;
1000-
}
1001-
// a < b
1002-
int N = drinks.length;
1003-
int limit = 0; // 咖啡机什么时候可用
1004-
for (int i = 0; i < N; i++) {
1005-
limit = Math.max(limit, drinks[i]) + a;
1006-
}
1007-
int[][] dp = new int[N][limit + 1];
1008-
// N-1行，所有的值
1009-
for (int washLine = 0; washLine <= limit; washLine++) {
1010-
dp[N - 1][washLine] = Math.min(Math.max(washLine, drinks[N - 1]) + a, drinks[N - 1] + b);
1011-
}
1012-
for (int index = N - 2; index >= 0; index--) {
1013-
for (int washLine = 0; washLine <= limit; washLine++) {
1014-
int p1 = Integer.MAX_VALUE;
1015-
int wash = Math.max(washLine, drinks[index]) + a;
1016-
if (wash <= limit) {
1017-
p1 = Math.max(wash, dp[index + 1][wash]);
1018-
}
1019-
int p2 = Math.max(drinks[index] + b, dp[index + 1][washLine]);
1020-
dp[index][washLine] = Math.min(p1, p2);
1021-
}
1022-
}
1023-
return dp[0][0];
989+
drinks := make([]int, n)
990+
for i := 0; i < n; i++ {
991+
cur := heap.Pop().(*Machine)
992+
cur.TimePoint += cur.WorkTime
993+
drinks[i] = cur.TimePoint
994+
heap.Push(cur)
1024995
}
1025996

1026-
// 方法三：最终版本，把方法二洗咖啡杯的暴力尝试进一步优化成动态规划
1027-
public static int minTime3(int[] arr, int n, int a, int b) {
1028-
PriorityQueue<Machine> heap = new PriorityQueue<Machine>(new MachineComparator());
1029-
for (int i = 0; i < arr.length; i++) {
1030-
heap.add(new Machine(0, arr[i]));
1031-
}
1032-
int[] drinks = new int[n];
1033-
for (int i = 0; i < n; i++) {
1034-
Machine cur = heap.poll();
1035-
cur.timePoint += cur.workTime;
1036-
drinks[i] = cur.timePoint;
1037-
heap.add(cur);
1038-
}
1039-
if (a >= b) {
1040-
return drinks[n - 1] + b;
1041-
}
1042-
int[][] dp = new int[n][drinks[n - 1] + n * a];
1043-
for (int i = 0; i < dp[0].length; i++) {
1044-
dp[n - 1][i] = Math.min(Math.max(i, drinks[n - 1]) + a, drinks[n - 1] + b);
1045-
}
1046-
for (int row = n - 2; row >= 0; row--) { // row 咖啡杯的编号
1047-
int washLine = drinks[row] + (row + 1) * a;
1048-
for (int col = 0; col < washLine; col++) {
1049-
int wash = Math.max(col, drinks[row]) + a;
1050-
dp[row][col] = Math.min(Math.max(wash, dp[row + 1][wash]), Math.max(drinks[row] + b, dp[row + 1][col]));
1051-
}
1052-
}
1053-
return dp[0][0];
997+
if a >= b {
998+
return drinks[n - 1] + b
1054999
}
10551000

1056-
// for test
1057-
public static int[] randomArray(int len, int max) {
1058-
int[] arr = new int[len];
1059-
for (int i = 0; i < len; i++) {
1060-
arr[i] = (int) (Math.random() * max) + 1;
1061-
}
1062-
return arr;
1001+
dp := make([][]int, n)
1002+
for i := 0; i < n; i++ {
1003+
dp[i] = make([]int, drinks[n - 1] + n * a)
10631004
}
10641005

1065-
// for test
1066-
public static void printArray(int[] arr) {
1067-
System.out.print("arr : ");
1068-
for (int j = 0; j < arr.length; j++) {
1069-
System.out.print(arr[j] + ", ");
1070-
}
1071-
System.out.println();
1006+
for i := 0; i < len(dp[0]); i++ {
1007+
dp[n - 1][i] = int(math.Min(math.Max(float64(i), float64(drinks[n - 1])) + float64(a), float64(drinks[n - 1] + b)))
10721008
}
10731009

1074-
public static void main(String[] args) {
1075-
int[] test = { 1, 1, 5, 5, 7, 10, 12, 12, 12, 12, 12, 12, 15 };
1076-
int a1 = 3;
1077-
int b1 = 10;
1078-
System.out.println(process(test, a1, b1, 0, 0));
1079-
System.out.println(dp(test, a1, b1));
1080-
1081-
int len = 5;
1082-
int max = 9;
1083-
int testTime = 50000;
1084-
for (int i = 0; i < testTime; i++) {
1085-
int[] arr = randomArray(len, max);
1086-
int n = (int) (Math.random() * 5) + 1;
1087-
int a = (int) (Math.random() * 5) + 1;
1088-
int b = (int) (Math.random() * 10) + 1;
1089-
int ans1 = minTime1(arr, n, a, b);
1090-
int ans2 = minTime2(arr, n, a, b);
1091-
int ans3 = minTime3(arr, n, a, b);
1092-
if (ans1 != ans2 || ans2 != ans3) {
1093-
printArray(arr);
1094-
System.out.println("n : " + n);
1095-
System.out.println("a : " + a);
1096-
System.out.println("b : " + b);
1097-
System.out.println(ans1 + " , " + ans2 + " , " + ans3);
1098-
System.out.println("===============");
1099-
break;
1100-
}
1010+
for row := n - 2; row >= 0; row-- { // row 咖啡杯的编号
1011+
washLine := drinks[row] + (row + 1) * a
1012+
for col := 0; col < washLine; col++ {
1013+
wash := int(math.Max(float64(col), float64(drinks[row]))) + a
1014+
dp[row][col] = int(math.Min(math.Max(float64(wash), float64(dp[row + 1][wash])),
1015+
math.Max(float64(drinks[row] + b), float64(dp[row + 1][row]))))
11011016
}
1102-
11031017
}
1104-
1018+
1019+
return dp[0][0]
11051020
}
11061021
```
11071022

0 commit comments

Comments
 (0)