2.5.1
2019-1-3
2.5.1 # 解答 # 如果比较的两个 String 引用的是同一个对象，那么就直接返回相等，不必再逐字符比较。 一个例子： string s = "abcabc"; string p = s; Console.WriteLine(s.CompareTo(p));
Sort
2.5.2
2019-1-4
2.5.2 # 解答 # 将字符串数组 keywords 按照长度排序，于是 keywords[0] 就是最短的字符串。 组合词的最短长度 minLength = 最短字符串的长度 * 2 = keywords[0] * 2。 先找到第一个长度大于等于 minLength 的字符串，下标为 canCombine。 我们从 canCombine 开始，一个个检查是否是组合词。 如果 keywords[canCombine] 是一个组合词，那么它一定是由位于它之前的某两个字符串组合而成的。 组合词的长度一定等于被组合词的长度之和，因此我们可以通过长度快速判断有可能的组合词。 现在题目转化为了如何解决 ThreeSum 问题，即求 a + b = c 型问题，根据 1.4.41 中的解法求解。 keywords[canCombine] 的长度已知，i 从 0 到 canCombine 之间循环， 用二分查找确认 i 到 canCombine 之间有没有符合条件的字符串，注意多个字符串可能长度相等。 代码 # var keywords = Console.ReadLine().Split(' '); Array.Sort(keywords, new StringLengthComparer()); var minLength = keywords[0].Length * 2; // 找到第一个大于 minLength 的字符串 var canCombine = 0; while (keywords[canCombine]. ...
2.5.3
2019-1-4
2.5.3 # 解答 # 这样会破坏相等的传递性。 例如 a = 0.005, b=0.000, c=-0.005，则 a == b, c == b，但是 a != c。
2.5.4
2019-1-4
2.5.4 # 解答 # 先排序，然后用书中的代码进行去重。 static string[] Dedup(string[] a) { if (a.Length == 0) return a; var sorted = new string[a.Length]; for (var i = 0; i < a.Length; i++) { sorted[i] = a[i]; } Array.Sort(sorted); // sorted = sorted.Distinct().ToArray(); var distinct = new string[sorted.Length]; distinct[0] = sorted[0]; var j = 1; for (var i = 1; i < sorted.Length; i++) { if (sorted[i].CompareTo(sorted[i - 1]) != 0) distinct[j++] = sorted[i]; } return distinct; }
2.5.5
2019-1-4
2.5.5 # 解答 # 因为选择排序会交换不相邻的元素。 例如： B1 B2 A A B2 B1 此时 B1 和 B2 的相对位置被改变，如果将交换限定在相邻元素之间（插入排序）。 B1 B2 A B1 A B2 A B2 B2 此时排序就是稳定的了。
2.5.6
2019-1-7
2.5.6 # 解答 # 非递归官网实现见：https://algs4.cs.princeton.edu/23quicksort/QuickPedantic.java.html 原本是和快速排序一块介绍的，将数组重新排列，使得 a[k] 正好是第 k 小的元素，k 从 0 开始。 具体思路类似于二分查找， 先切分，如果切分位置小于 k，那么在右半部分继续切分，否则在左半部分继续切分。 直到切分位置正好等于 k，直接返回 a[k] 。 代码 # // 使 a[k] 变为第 k 小的数，k 从 0 开始。 // a[0] ~ a[k-1] 都小于等于 a[k], a[k+1]~a[n-1] 都大于等于 a[k] static T Select<T>(T[] a, int k, int lo, int hi) where T : IComparable<T> { if (k > a.Length || k < 0) throw new ArgumentOutOfRangeException(nameof(k), "select out of bound"); if (lo >= hi) return a[lo]; var i = Partition(a, lo, hi); if (i > k) return Select(a, k, lo, i - 1); if (i < k) return Select(a, k, i + 1, hi); return a[i]; } 另请参阅 # SortApplication 库
2.5.7
2019-1-7
2.5.7 # 解答 # 参考书中给出的快速排序性能分析方法（中文版 P186，英文版 P293）。 设 $C_n$ 代表找出 $n$ 个元素中的最小值所需要的比较次数。 一次切分需要 $n+1$ 次比较，下一侧的元素个数从 $0$ 到 $ n-1 $ 都有可能， 于是根据全概率公式，有： $$ \begin{eqnarray} C_n&=&\frac {1}{n} (n+1) +\frac{1}{n} (n+1+C_1)+ \cdots + \frac{1}{n}(n+1+C_{n-1}) \newline C_n&=&n+1+\frac{1}{n}(C_1+C_2+\cdots+C_{n-1}) \newline nC_n&=&n(n+1)+(C_1+C_2+\cdots+C_{n-1}) \newline nC_n-(n-1)C_{n-1}&=&2n+C_{n-1} \newline nC_n&=&2n+nC_{n-1} \newline C_n&=&2+C_{n-1} \newline C_n &=& C_1+2(n-1) \newline C_n &=& 2n-2 < 2n \end{eqnarray} $$ 测试结果符合我们的预期。 附加：找出第 $k$ 小的数平均需要的比较次数。 类似的方法也在计算快速排序的平均比较次数时使用，见 {% post_link 2-3-14.md %}。 首先和快速排序类似，select 方法的所有元素比较都发生在切分过程中。 接下来考虑第 $i$ 小和第 $j$ 小的元素（$x_i$ ，$x_j$）， ...
2.5.8
2019-1-8
2.5.8 # 解答 # 官网实现见：https://algs4.cs.princeton.edu/25applications/Frequency.java.html 用到的数据来自（右键另存为）：https://introcs.cs.princeton.edu/java/data/tale.txt 先把所有单词读入，然后排序，一样的单词会被放在一起， 接下来遍历一遍记录每个单词出现的次数。 然后按照频率排序，倒序输出即可。 定义了一个嵌套类 Record 来记录单词及出现次数，实现的比较器按照出现次数排序。 class Record : IComparable<Record> { public string Key { get; set; } // 单词 public int Value { get; set; } // 频率 public Record(string key, int value) { this.Key = key; this.Value = value; } public int CompareTo(Record other) { return this.Value.CompareTo(other.Value); } } 测试结果（前 1% 的单词）： 代码 # var filename = "tale.txt"; var sr = new StreamReader(File. ...
2.5.9
2019-1-8
2.5.9 # 解答 # 右侧给出的是道琼斯指数，官方数据（右键另存为）：DJI 设计一个类保存日期和交易量，然后按照交易量排序即可。 internal class Djia : IComparable<Djia> { public string Date { get; set; } public long Volume { get; set; } public Djia(string date, long vol) { Date = date; Volume = vol; } public int CompareTo(Djia other) { return Volume.CompareTo(other.Volume); } }
2.5.10
2019-1-8
2.5.10 # 解答 # 用一个 int 数组来保存版本号，按顺序进行比较。 如果两个版本号不等长且前缀相同，那么较长的版本号比较高，例如：1.2.1 和 1.2。 internal class Version : IComparable<Version> { private readonly int[] _versionNumber; public Version(string version) { var versions = version.Split('.'); _versionNumber = new int[versions.Length]; for (var i = 0; i < versions.Length; i++) { _versionNumber[i] = int.Parse(versions[i]); } } public int CompareTo(Version other) { for (var i = 0; i < _versionNumber.Length && i < other._versionNumber.Length; i++) { if (_versionNumber[i].CompareTo(other._versionNumber[i]) != 0) return _versionNumber[i]. ...