fix: 贪心

dairongpeng · dairongpeng · commit 831b790c9c75 · 2022-02-28T22:46:16.000+08:00
diff --git a/09-贪心算法解题思路.md b/09-贪心算法解题思路.md
@@ -8,44 +8,44 @@
 
 2、用一种局部最功利的标准，总是能做出在当前看来是最好的选择
 
-3、难点在于证明局部最优解最功利的标准可以得到全局最优解
+3、难点在于证明局部最优解可以最终得到全局最优解
 
-4、对于贪心算法的学习主要是以增加阅历和经验为主
+4、对于贪心算法的学习主要是以经验为主，尝试为主
 
 ### 1.2.1 贪心算法解释
 
 正例：通过一个例子来解释，假设一个数组中N个正数，第一个挑选出来的数乘以1，第二个挑选出来的数乘以2，同理，第N次挑选出来的数乘以N，总的加起来是我们的分数。怎么挑选数字使我们达到最大分数？
 
 > 数组按从小到大的顺序排序，我们按顺序依次挑选，最终结果就是最大的。本质思想是因子随着挑选次数的增加会增大，我们尽量让大数去结合大的因子。
 
-==贪心算法有时是无效的，后面会贪心算法无效的例子==
+> 贪心算法有时是无效的，下文会举贪心算法无效的例子
 
 ### 1.2.2 贪心算法的证明问题
 
 如何证明贪心算法的有效性？
 
-> 一般来说，贪心算法不推荐证明，很多时候证明是非常复杂的。通过下面例子来说明贪心算法证明的复杂性，从头到尾讲一道利用贪心算法求解的题目。
+> 一般来说，贪心算法不推荐证明，很多时候证明是非常复杂的。通过下面例子来说明贪心算法证明的复杂性；
 
 例子：给定一个由字符串组成的数组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。
+思路1：按照单个元素字典序贪心，例如在[ac,bk,sc,ket]字符串数组中，我们拼接出来最终的字符串字典序最小，那么我们依次挑选字典序最小的进行拼接的贪心策略得到acbkketsc。
 
-==但是这样的贪心不一定是正确的，例如[ba,b]按照上述思路的贪心结果是bba，但是bab明显是最小的结果==
+> 但是这样的贪心不一定是正确的，例如[ba,b]按照上述思路的贪心结果是bba，但是bab明显是最小的结果
 
-本题思路2：两个元素x和y，x拼接y小于等于x拼接y，那么x放前，否则y放前面。例如x=b,y=ba。bba大于bab的字典与，那么ba放前面
+思路2：两个元素x和y，x拼接y小于等于y拼接x，那么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小于b拼接a，b拼接c小于等于c拼接b，推导出a拼接c小于等于c拼接a。
 
 a拼接b等于a乘以k的b长度次方 + b。我们把k的x长度次方这个操作当成m(x)函数。所以：
 
@@ -79,135 +79,64 @@ m(c) * a + c <= m(a) * c + a
 
 再证明任意三个交换都会变为更大的字典序，那么最终数学归纳法，得到思路二的正确性
 
-==所以贪心算法的证明实质是比较复杂的，我们大可不必每次去证明贪心的正确性==
+> 所以贪心算法的证明实质是比较复杂的，我们大可不必每次去证明贪心的正确性
 
-```Java
-package class09;
+```Go
+package main
 
-import java.util.ArrayList;
-import java.util.Arrays;
-import java.util.Comparator;
-import java.util.HashSet;
+import (
+	"sort"
+	"strings"
+)
 
-public class Code01_LowestLexicography {
+// 方法1 暴力法穷举，排列组合。略
 
-        // 暴力法穷举，排列组合
-	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;
+// LowestStringByGreedy 方法2 贪心法
+func LowestStringByGreedy(strs []string) string {
+	if len(strs) == 0 {
+		return ""
 	}
 
-	// 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);
-				}
-			}
-		}
-	}
+	Sort(strs, func(a, b string) int {
+		return strings.Compare(a, b)
+	})
 
-	public static class MyComparator implements Comparator<String> {
-		@Override
-		public int compare(String a, String b) {
-			return (a + b).compareTo(b + a);
-		}
+	res := ""
+	for i := 0; i < len(strs); i++ {
+		res += strs[i]
 	}
+	return res
+}
 
-        // 思路二，贪心解法
-	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;
-	}
+type Comparator func(a, b string) int
 
-	// 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);
-	}
+func Sort(values []string, comparator Comparator) {
+	sort.Sort(sortable{values, comparator})
+}
 
-	// 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;
-	}
+type sortable struct {
+	values     []string
+	comparator Comparator
+}
 
-	// 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;
-	}
+func (s sortable) Len() int {
+	return len(s.values)
+}
 
-	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!");
-	}
+func (s sortable) Swap(i, j int) {
+	s.values[i], s.values[j] = s.values[j], s.values[i]
+}
 
+func (s sortable) Less(i, j int) bool {
+	return s.comparator(s.values[i], s.values[j]) < 0
 }
 ```
 
 > 全排列的时间复杂度为：O(N!)
 
 > 每一种贪心算法有可能都有属于他自身的特有证明，例如哈夫曼树算法，证明千变万化
 
-==贪心策略算法，尽量不要陷入复杂的证明==
+> 贪心策略算法，尽量不要陷入复杂的证明
 
 ## 1.2 贪心算法求解思路
 
