forked from dairongpeng/algorithm-note
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path09.md
More file actions
673 lines (530 loc) · 20.5 KB
/
09.md
File metadata and controls
673 lines (530 loc) · 20.5 KB
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
- [1 贪心算法](#1)
* [1.1 基本概念](#11)
+ [1.2.1 贪心算法解释](#121)
+ [1.2.2 贪心算法的证明问题](#122)
* [1.2 贪心算法求解思路](#12)
+ [1.2.1 标准求解过程](#121)
+ [1.2.2 贪心算法解题套路](#122)
* [1.3 贪心算法套路解题实战](#13)
+ [1.3.1 例一：会议日程安排问题](#131)
+ [1.3.2 例二：居民楼路灯问题](#132)
+ [1.3.3 例三：哈夫曼树问题](#133)
+ [1.3.4 例四：项目花费和利润问题](#134)
<h1 id='1'>1 贪心算法</h1>
<h2 id='11'>1.1 基本概念</h2>
1、最自然智慧的算法
2、用一种局部最功利的标准，总是能做出在当前看来是最好的选择
3、难点在于证明局部最优解最功利的标准可以得到全局最优解
4、对于贪心算法的学习主要是以增加阅历和经验为主
<h3 id='121'>1.2.1 贪心算法解释</h3>
正例：通过一个例子来解释，假设一个数组中N个正数，第一个挑选出来的数乘以1，第二个挑选出来的数乘以2，同理，第N次挑选出来的数乘以N，总的加起来是我们的分数。怎么挑选数字使我们达到最大分数？
> 数组按从小到大的顺序排序，我们按顺序依次挑选，最终结果就是最大的。本质思想是因子随着挑选次数的增加会增大，我们尽量让大数去结合大的因子。
==贪心算法有时是无效的，后面会贪心算法无效的例子==
<h3 id='122'>1.2.2 贪心算法的证明问题</h3>
如何证明贪心算法的有效性？
> 一般来说，贪心算法不推荐证明，很多时候证明是非常复杂的。通过下面例子来说明贪心算法证明的复杂性，从头到尾讲一道利用贪心算法求解的题目。
例子：给定一个由字符串组成的数组strs，必须把所有的字符串拼接起来，返回所有可能的拼接结果中，字典序最小的结果。
> 字典序概念：直观理解，两个单词放到字典中，从头开始查找这个单词，哪个先被查找到，哪个字典序小。
> 字典序严格定义，我们把字符串当成k进制的数，a-z当成26进制的正数，字符长度一样，abk>abc，那么我们说abk的字典序更大。字符长度不一样ac和b，那么我们要把短的用0补齐，0小于a的accil，那么ac<b0，高位b>a即可比较出来大小。
Java中字符串的ComparTo方法，就是比较字典序。
本题思路1：按照单个元素字典序贪心，例如在[ac,bk,sc,ket]字符串数组中，我们拼接出来最终的字符串字典序最小，那么我们依次挑选字典序最小的进行拼接的贪心策略得到acbkketsc。
==但是这样的贪心不一定是正确的，例如[ba,b]按照上述思路的贪心结果是bba，但是bab明显是最小的结果==
本题思路2：两个元素x和y，x拼接y小于等于x拼接y，那么x放前，否则y放前面。例如x=b,y=ba。bba大于bab的字典与，那么ba放前面
证明：
我们把拼接当成k进制数的数学运算，把a-z的数当成26进制的数，'ks'拼接'ts'实质是ks * 26^2 + te。
目标先证明我们比较的传递性：证明a拼接b小于b拼接a，b拼接c小于等于c拼接b，推出a拼接c小于等于c拼接a。
a拼接b等于a乘以k的b长度次方 + b。我们把k的x长度次方这个操作当成m(x)函数。所以：
```math
a * m(b) + b <= b * m(a) + a
b * m(c) + c <= c * m(b) + b
=>
a * m(b) * c <= b * m(a) * c + ac - bc
b * m(c) * a + ca - ba <= c * m(b) * a
=>
b * m(c) * a + ca - ba <= b * m(a) * c + ac - bc
=>
m(c) * a + c <= m(a) * c + a
```
至此，我们证明出我们的排序具有传递性质。
根据我们排序策略得到的一组序列，证明我们任意交换两个字符的位置，都会得到更大的字典序。
例如按照思路二得到的amnb序列，我们交换a和b。我们先把a和m交换，由于按照思路二得到的序列，满足a.m <= m.a 那么所以manb > amnb，同理得到amnb < bmna。
再证明任意三个交换都会变为更大的字典序，那么最终数学归纳法，得到思路二的正确性
==所以贪心算法的证明实质是比较复杂的，我们大可不必每次去证明贪心的正确性==
```Java
package class09;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
public class Code01_LowestLexicography {
// 暴力法穷举，排列组合
public static String lowestString1(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
ArrayList<String> all = new ArrayList<>();
HashSet<Integer> use = new HashSet<>();
process(strs, use, "", all);
String lowest = all.get(0);
for (int i = 1; i < all.size(); i++) {
if (all.get(i).compareTo(lowest) < 0) {
lowest = all.get(i);
}
}
return lowest;
}
// strs里放着所有的字符串
// 已经使用过的字符串的下标，在use里登记了，不要再使用了
// 之前使用过的字符串，拼接成了-> path
// 用all收集所有可能的拼接结果
public static void process(String[] strs, HashSet<Integer> use, String path, ArrayList<String> all) {
// 所有字符串都是用过了
if (use.size() == strs.length) {
all.add(path);
} else {
for (int i = 0; i < strs.length; i++) {
if (!use.contains(i)) {
use.add(i);
process(strs, use, path + strs[i], all);
use.remove(i);
}
}
}
}
public static class MyComparator implements Comparator<String> {
@Override
public int compare(String a, String b) {
return (a + b).compareTo(b + a);
}
}
// 思路二，贪心解法
public static String lowestString2(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
Arrays.sort(strs, new MyComparator());
String res = "";
for (int i = 0; i < strs.length; i++) {
res += strs[i];
}
return res;
}
// for test
public static String generateRandomString(int strLen) {
char[] ans = new char[(int) (Math.random() * strLen) + 1];
for (int i = 0; i < ans.length; i++) {
int value = (int) (Math.random() * 5);
ans[i] = (Math.random() <= 0.5) ? (char) (65 + value) : (char) (97 + value);
}
return String.valueOf(ans);
}
// for test
public static String[] generateRandomStringArray(int arrLen, int strLen) {
String[] ans = new String[(int) (Math.random() * arrLen) + 1];
for (int i = 0; i < ans.length; i++) {
ans[i] = generateRandomString(strLen);
}
return ans;
}
// for test
public static String[] copyStringArray(String[] arr) {
String[] ans = new String[arr.length];
for (int i = 0; i < ans.length; i++) {
ans[i] = String.valueOf(arr[i]);
}
return ans;
}
public static void main(String[] args) {
int arrLen = 6;
int strLen = 5;
int testTimes = 100000;
String[] arr = generateRandomStringArray(arrLen, strLen);
System.out.println("先打印一个生成的字符串");
for (String str : arr) {
System.out.print(str + ",");
}
System.out.println();
System.out.println("test begin");
for (int i = 0; i < testTimes; i++) {
String[] arr1 = generateRandomStringArray(arrLen, strLen);
String[] arr2 = copyStringArray(arr1);
if (!lowestString1(arr1).equals(lowestString2(arr2))) {
for (String str : arr1) {
System.out.print(str + ",");
}
System.out.println();
System.out.println("Oops!");
}
}
System.out.println("finish!");
}
}
```
> 全排列的时间复杂度为：O(N!)
> 每一种贪心算法有可能都有属于他自身的特有证明，例如哈夫曼树算法，证明千变万化
==贪心策略算法，尽量不要陷入复杂的证明==
<h2 id='12'>1.2 贪心算法求解思路</h2>
<h3 id='121'>1.2.1 标准求解过程</h3>
1、分析业务
2、根据业务逻辑找到不同的贪心策略
3、对于能举出反例的策略，直接跳过，不能举出反例的策略要证明有效性，这往往是比较困难的，要求数学能力很高且不具有统一的技巧性
<h3 id='122'>1.2.2 贪心算法解题套路</h3>
1、实现一个不依靠贪心策略的解法X,可以用暴力尝试
2、脑补出贪心策略A,贪心策略B,贪心策略C......
3、用解法X和对数器，用实验的方式得知哪个贪心策略正确
4、不要去纠结贪心策略的证明
> 贪心类的题目在笔试中，出现的概率高达6到7成，而面试中出现贪心的概率不到2成。因为笔试要的是淘汰率，面试要的是区分度。由于贪心的解决完全取决于贪心策略有没有想对，有很高的淘汰率但是没有很好的区分度
<h2 id='13'>1.3 贪心算法套路解题实战</h2>
<h3 id='131'>1.3.1 例一：会议日程安排问题</h3>
一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目宣讲。给你每个项目的开始时间和结束时间，你来安排宣讲的日程，要求会议室进行宣讲的场数最多。
返回最多的宣讲场次。
> 思路：本题常见的几种贪心策略，一种是按照谁先开始安排谁，第二种按照持续时间短的先安排，第三种按照谁先结束安排谁。
> 通过验证，无需证明得出第三种贪心策略是正确的
```Java
package class09;
import java.util.Arrays;
import java.util.Comparator;
public class Code04_BestArrange {
public static class Program {
public int start;
public int end;
public Program(int start, int end) {
this.start = start;
this.end = end;
}
}
// 暴力穷举法，用来做对数器
public static int bestArrange1(Program[] programs) {
if (programs == null || programs.length == 0) {
return 0;
}
return process(programs, 0, 0);
}
// 还剩什么会议都放在programs里
// done 之前已经安排了多少会议的数量
// timeLine表示目前来到的时间点是多少
// 目前来到timeLine的时间点，已经安排了done多的会议，剩下的会议programs可以自由安排
// 返回能安排的最多会议数量
public static int process(Program[] programs, int done, int timeLine) {
// 没有会议可以安排，返回安排了多少会议的数量
if (programs.length == 0) {
return done;
}
// 还有会议可以选择
int max = done;
// 当前安排的会议是什么会，每一个都枚举
for (int i = 0; i < programs.length; i++) {
if (programs[i].start >= timeLine) {
Program[] next = copyButExcept(programs, i);
max = Math.max(max, process(next, done + 1, programs[i].end));
}
}
return max;
}
public static Program[] copyButExcept(Program[] programs, int i) {
Program[] ans = new Program[programs.length - 1];
int index = 0;
for (int k = 0; k < programs.length; k++) {
if (k != i) {
ans[index++] = programs[k];
}
}
return ans;
}
// 解法2：贪心算法
public static int bestArrange2(Program[] programs) {
Arrays.sort(programs, new ProgramComparator());
// timeline表示来到的时间点
int timeLine = 0;
// result表示安排了多少个会议
int result = 0;
// 由于刚才按照结束时间排序，当前是按照谁结束时间早的顺序遍历
for (int i = 0; i < programs.length; i++) {
if (timeLine <= programs[i].start) {
result++;
timeLine = programs[i].end;
}
}
return result;
}
// 根据谁的结束时间早排序
public static class ProgramComparator implements Comparator<Program> {
@Override
public int compare(Program o1, Program o2) {
return o1.end - o2.end;
}
}
// for test
public static Program[] generatePrograms(int programSize, int timeMax) {
Program[] ans = new Program[(int) (Math.random() * (programSize + 1))];
for (int i = 0; i < ans.length; i++) {
int r1 = (int) (Math.random() * (timeMax + 1));
int r2 = (int) (Math.random() * (timeMax + 1));
if (r1 == r2) {
ans[i] = new Program(r1, r1 + 1);
} else {
ans[i] = new Program(Math.min(r1, r2), Math.max(r1, r2));
}
}
return ans;
}
public static void main(String[] args) {
int programSize = 12;
int timeMax = 20;
int timeTimes = 1000000;
for (int i = 0; i < timeTimes; i++) {
Program[] programs = generatePrograms(programSize, timeMax);
if (bestArrange1(programs) != bestArrange2(programs)) {
System.out.println("Oops!");
}
}
System.out.println("finish!");
}
}
```
<h3 id='132'>1.3.2 例二：居民楼路灯问题</h3>
给定一个字符串str，只由‘X’和‘.’两中国字符构成。
‘X’表示墙，不能放灯，也不需要点亮，‘.’表示居民点，可以放灯，需要点亮。
如果灯放在i位置，可以让i-1，i和i+1三个位置被点亮，返回如果点亮str中所需要点亮的位置，至少需要几盏灯
例如： X..X......X..X. 需要至少5盏灯
```Java
package class09;
import java.util.HashSet;
public class Code02_Light {
// 纯暴力，用来做对数器。点的位置放灯和不放灯全排列
public static int minLight1(String road) {
if (road == null || road.length() == 0) {
return 0;
}
return process(road.toCharArray(), 0, new HashSet<>());
}
// str[index....]位置，自由选择放灯还是不放灯
// str[0..index-1]位置呢？已经做完决定了，那些放了灯的位置，存在lights里
// 要求选出能照亮所有.的方案，并且在这些有效的方案中，返回最少需要几个灯
public static int process(char[] str, int index, HashSet<Integer> lights) {
// index来到结束位置的时候，当前方案准备结束
if (index == str.length) {
// 检查当前方案能否把所有居民楼都照亮
for (int i = 0; i < str.length; i++) {
// 当前位置是点的话
if (str[i] != 'X') {
if (!lights.contains(i - 1)
&& !lights.contains(i)
&& !lights.contains(i + 1)) {
return Integer.MAX_VALUE;
}
}
}
// 经过for循环的检查，任意点的位置都被照亮了，返回当前有效的一种解
return lights.size();
} else { // str还没结束
// i位置不管是 X 或者 . 都可以选择不放灯
int no = process(str, index + 1, lights);
int yes = Integer.MAX_VALUE;
// 只有在i位置是.的时候，才可以选择放灯
if (str[index] == '.') {
lights.add(index);
yes = process(str, index + 1, lights);
lights.remove(index);
}
return Math.min(no, yes);
}
}
// 贪心解法
public static int minLight2(String road) {
char[] str = road.toCharArray();
// index从0出发
int index = 0;
// 当前灯的个数
int light = 0;
while (index < str.length) {
// 当前i位置是X，直接跳到下一个位置做决定
if (str[index] == 'X') {
index++;
// i 位置是 . 不管i+1是X还是.当前区域需要放灯
} else {
light++;
// 接下来没字符了，遍历结束
if (index + 1 == str.length) {
break;
} else {
// 如果i+1位置是X，在i位置放灯，去i+2位置做决定
if (str[index + 1] == 'X') {
index = index + 2;
// i位置是. i+1也是. 那么不管i+2是什么，都在i+1位置放灯，到i+3去做决定
} else {
index = index + 3;
}
}
}
}
return light;
}
// for test
public static String randomString(int len) {
char[] res = new char[(int) (Math.random() * len) + 1];
for (int i = 0; i < res.length; i++) {
res[i] = Math.random() < 0.5 ? 'X' : '.';
}
return String.valueOf(res);
}
public static void main(String[] args) {
int len = 20;
int testTime = 100000;
for (int i = 0; i < testTime; i++) {
String test = randomString(len);
int ans1 = minLight1(test);
int ans2 = minLight2(test);
if (ans1 != ans2) {
System.out.println("oops!");
}
}
System.out.println("finish!");
}
}
```
<h3 id='133'>1.3.3 例三：哈夫曼树问题</h3>
一根金条切成两半，是需要花费和长度值一样的铜板的。
比如长度为20的金条，不管怎么切，都需要花费20个铜板。一群人想整分整块金条，怎么分最省铜板？
例如：给定数组[10,20,30]，代表一共三个人，整块金条长度为60，金条要分成10,20,30三个部分。
如果先把长度为60的金条分成10和50，花费60；再把长度为50的金条分成20和30，花费50；一共需要花费110个铜板。但是如果先把长度为60的金条分成30和30，花费60;再把30的金条分成10和20,花费30；一共花费90个铜板。
输入一个数组，返回分割的最小代价。
> 小根堆，大根堆，排序。是贪心策略最常用的手段，coding代码量很少。因为堆天然就具备根据我们自定义的排序规则重新组织数据
```Java
package class09;
import java.util.PriorityQueue;
public class Code03_LessMoneySplitGold {
// 暴力解法
public static int lessMoney1(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
return process(arr, 0);
}
public static int process(int[] arr, int pre) {
if (arr.length == 1) {
return pre;
}
int ans = Integer.MAX_VALUE;
// 穷举任意两个结合后的后续
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
ans = Math.min(ans, process(copyAndMergeTwo(arr, i, j), pre + arr[i] + arr[j]));
}
}
return ans;
}
public static int[] copyAndMergeTwo(int[] arr, int i, int j) {
int[] ans = new int[arr.length - 1];
int ansi = 0;
for (int arri = 0; arri < arr.length; arri++) {
if (arri != i && arri != j) {
ans[ansi++] = arr[arri];
}
}
ans[ansi] = arr[i] + arr[j];
return ans;
}
// 贪心解法，建立一个小根堆，把所有数扔进去
public static int lessMoney2(int[] arr) {
PriorityQueue<Integer> pQ = new PriorityQueue<>();
for (int i = 0; i < arr.length; i++) {
pQ.add(arr[i]);
}
int sum = 0;
int cur = 0;
while (pQ.size() > 1) {
// 每一次弹出两个数，合并成一个数
// 合成的数一定输非叶子节点
cur = pQ.poll() + pQ.poll();
// 把合成的数累加到sum中去
sum += cur;
// 把合成的数加入小根堆中
pQ.add(cur);
}
return sum;
}
// for test
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) (Math.random() * (maxValue + 1));
}
return arr;
}
public static void main(String[] args) {
int testTime = 100000;
int maxSize = 6;
int maxValue = 1000;
for (int i = 0; i < testTime; i++) {
int[] arr = generateRandomArray(maxSize, maxValue);
if (lessMoney1(arr) != lessMoney2(arr)) {
System.out.println("Oops!");
}
}
System.out.println("finish!");
}
}
```
<h3 id='134'>1.3.4 例四：项目花费和利润问题</h3>
输入：正数数组costs，正数数组profits,正数K,正数M
costs[i]表示i号项目的花费，profits[i]表示i号项目在扣除花费之后还能挣到的钱（利润）
K表示你只能串行的最多K个项目，M表示你的初始资金。
说明：每做完一个项目，马上获得收益，可以支持你去做下一个项目。不能并行的做项目。
输出：你最后获得的最大钱数。
```Java
package class09;
import java.util.Comparator;
import java.util.PriorityQueue;
public class Code05_IPO {
public static int findMaximizedCapital(int K, int W, int[] Profits, int[] Capital) {
// 由花费组织的小根堆
PriorityQueue<Program> minCostQ = new PriorityQueue<>(new MinCostComparator());
// 由利润组织的大根堆
PriorityQueue<Program> maxProfitQ = new PriorityQueue<>(new MaxProfitComparator());
// 把所有项目加入到由花费组织的小根堆里
for (int i = 0; i < Profits.length; i++) {
minCostQ.add(new Program(Profits[i], Capital[i]));
}
// 做k轮项目
for (int i = 0; i < K; i++) {
// 小根堆不为空，且堆顶的花费被我当前启动资金cover住
while (!minCostQ.isEmpty() && minCostQ.peek().c <= W) {
// 小根堆的堆顶扔到大根堆中去
maxProfitQ.add(minCostQ.poll());
}
// 大根堆没有可以做的项目，直接返回所有钱数
if (maxProfitQ.isEmpty()) {
return W;
}
// 大根堆不为空，堆顶元素的利润直接加到我们的总钱数上
// 大根堆弹出堆顶元素
W += maxProfitQ.poll().p;
}
return W;
}
// 项目实体类
public static class Program {
public int p;
public int c;
public Program(int p, int c) {
this.p = p;
this.c = c;
}
}
// 根据花费组织的小根堆的比较器
public static class MinCostComparator implements Comparator<Program> {
@Override
public int compare(Program o1, Program o2) {
return o1.c - o2.c;
}
}
// 根据利润组织的大根堆的比较器
public static class MaxProfitComparator implements Comparator<Program> {
@Override
public int compare(Program o1, Program o2) {
return o2.p - o1.p;
}
}
}
```