2018-5-21
1.3.43 # 解答 # C# 中可以用 Directory 类里面的几个方法来获得文件路径和文件名。
代码 # // 获取当前目录 var path = Directory.GetCurrentDirectory(); path = Directory.GetParent(path).FullName; path = Directory.GetParent(path).FullName; // 获取文件 Console.WriteLine(path + "中的所有文件"); Search(path, 0); static void Search(string path, int tabs) { var dirs = Directory.GetDirectories(path); var files = Directory.GetFiles(path); foreach (var p in dirs) { for (var i = 0; i < tabs; i++) { Console.Write(" "); } Console.WriteLine(p.Split('\\').Last()); Search(p, tabs + 1); } foreach (var f in files) { for (var i = 0; i < tabs; i++) { Console.
...
2018-5-21
1.3.44 # 解答 # 这里我们使用两个栈来模拟缓冲区。
向左/向右移动 = 从左/右栈弹出相应数量的元素并压入另外一个栈。
插入/删除 = 左栈压入/弹出一个元素。
字符数量 = 左栈数量 + 右栈数量。
代码 # internal class Buffer { private readonly Stack<char> _leftside; private readonly Stack<char> _rightside; /// <summary> /// 建立一个文本缓冲区。 /// </summary> public Buffer() { _leftside = new Stack<char>(); _rightside = new Stack<char>(); } /// <summary> /// 在光标位置插入字符 c。 /// </summary> /// <param name="c">要插入的字符。</param> public void Insert(char c) { _leftside.Push(c); } /// <summary> /// 删除并返回光标位置的字符。 /// </summary> /// <returns></returns> public char Delete() { return _leftside.
...
2018-5-22
1.3.45 # 解答 # 书上已经给出了思路，简单说明一下。
第一问是给定输入判断是否会下溢出，只要记录栈中元素的数量即可，一旦为负数则返回 true。
第二问是给定输出判断是否可能。
对于输出序列中的每一个数，如果栈顶为空或者栈顶数字小于当前输出序列的数，那么就从输入序列中输入数字，直到栈顶数字和当前输出序列中的数字相等。
如果当前输出序列中的数字和栈顶元素相等，从栈中弹出相应元素。
最后如果栈为空则可能，否则不可能。
可以结合习题 1.3.3 的解答查看。
通用解法见下一题。
代码 # // 给定输入序列，判断是否会出现下溢出。 var input = "- 0 1 2 3 4 5 6 7 8 9 - - - - - - - - -"; Console.WriteLine(IsUnderflow(input.Split(' '))); //True input = "0 - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 -"; Console.WriteLine(IsUnderflow(input.Split(' '))); //False // 给定输出序列，判定是否可能。 int[] output = { 4, 3, 2, 1, 0, 9, 8, 7, 6, 5 }; Console.
...
2018-5-22
1.3.46 # 解答 # 这道题的解答参考了这篇博文：http://ceeji.net/blog/forbidden-triple-for-stack-generability/。
显然书中的解答已经十分明确，这里简单说明一下：
首先有结论：对于栈顶元素 Sn，栈中所有小于 Sn 的值都以递减形式保存（已经输出的不算）。
表现在输出序列中，Sn 输出之后，如果有小于 Sn 的值输出，其顺序必定是递减的。
例如序列 4 3 2 1 0 9 8 7 6 5
4 输出之后，3 2 1 0 递减输出；9 输出之后，8 7 6 5 递减输出。
依次验证其中的每个值都能满足结论。
而对于序列 4 6 8 7 5 3 2 9 0 1
对于 4，之后的 3 2 1 0 并不是以递减顺序输出的，因此这个序列是不合法的。
2018-5-22
1.3.47 # 解答 # 这里用的都是链式结构，头尾相接即可。
代码 # Queue # /// <summary> /// 在当前队列之后附加一个队列。 /// </summary> /// <param name="q1">需要被附加的队列。</param> /// <param name="q2">需要附加的队列（将被删除）。</param> public static Queue<Item> Catenation(Queue<Item> q1, Queue<Item> q2) { if (q1.IsEmpty()) { q1.first = q2.first; q1.last = q2.last; q1.count = q2.count; } else { q1.last.next = q2.first; q1.last = q2.last; q1.count += q2.count; } q2 = null; return q1; } Stack # /// <summary> /// 将两个栈连接。 /// </summary> /// <param name="s1">第一个栈。</param> /// <param name="s2">第二个栈（将被删除）。</param> /// <returns></returns> public static Stack<Item> Catenation(Stack<Item> s1, Stack<Item> s2) { if (s1.
...
2018-5-23
1.3.48 # 解答 # 按照双向队列原本的操作就可以实现，需要维护两个栈的长度以防越界。（左侧栈弹出了右侧栈栈底的内容）
代码 # public class DeStack<TItem> : IEnumerable<TItem> { private class DoubleNode<T> { public T Item; public DoubleNode<T> Next; public DoubleNode<T> Prev; } private DoubleNode<TItem> _first; private DoubleNode<TItem> _last; private int _leftCount; private int _rightCount; /// <summary> /// 默认构造函数，建立一个双端栈。 /// </summary> public DeStack() { _first = null; _last = null; _leftCount = 0; _rightCount = 0; } /// <summary> /// 检查左侧栈是否为空。 /// </summary> /// <returns></returns> public bool IsLeftEmpty() { return _leftCount == 0; } /// <summary> /// 检查右侧栈是否为空。 /// </summary> /// <returns></returns> public bool IsRightEmpty() { return _rightCount == 0; } /// <summary> /// 返回左侧栈中元素的数量。 /// </summary> /// <returns></returns> public int LeftSize() { return _leftCount; } /// <summary> /// 返回右侧栈中元素的数量。 /// </summary> /// <returns></returns> public int RightSize() { return _rightCount; } /// <summary> /// 向左端添加一个元素。 /// </summary> /// <param name="item">要添加的元素。</param> public void PushLeft(TItem item) { var oldFirst = _first; _first = new DoubleNode<TItem> { Item = item, Prev = null, Next = oldFirst }; if (oldFirst == null) { _last = _first; } else { oldFirst.
...
2018-5-23
1.3.49 # 解答 # 那么这里就使用六个栈来解决这个问题。 这个算法来自于这篇论文。
原文里用的是 Pure Lisp，不过语法很简单，还是很容易看懂的。
先导知识——用两个栈模拟一个队列 # 如何使用两个栈来模拟一个队列操作？
这是一道很经典的题目，答案也有很多种，这里只介绍之后会用到的一种方法。
首先我们有两个栈，H 和 T，分别用作出队和入队用。
这样，入队操作等同于向 T 添加元素，T 的入栈操作只需要 O(1) 时间。
如果 H 不为空，出队操作等同于 H 出栈，H 的出栈操作也只需要 O(1) 时间。
但如果 H 为空，则需要将 T 中的元素依次弹出并压入到 H 中，这是一个 O(n) 的操作。
下图分别展示了这三种情况。
显然，这种方式中，出队操作的最坏时间复杂度是 O(n)，并不满足题目要求。
分摊 O(n) # 那么，怎么解决这个问题呢？
一个很自然的想法是，如果在栈 H 变为空之前，我们就能逐步将栈 T 的内容弹出并压入到另一个栈 H’ 中，等到栈 H 为空时，直接交换 H 和 H’ 即可。
假设目前的队列状态是这样，有三个元素等待出队，还有三个元素等待入队。
现在依次让三个元素出队，与此同时我们让栈 T 中的元素依次进入 H’ 中。
每一次出队都执行两个操作，元素出队和元素复制（Pop & Push），时间复杂度 O(1) + O(1) + O(1) = O(1)。
...
2018-5-23
1.3.50 # 解答 # 初始化迭代器的时候记录栈已经进行过的 Pop 和 Push 数，迭代的时候检查这两个值是否改变，一旦改变就抛出异常。
代码 # private class StackEnumerator : IEnumerator<Item> { private Stack<Item> s; private int popcount; private int pushcount; private Node<Item> current; public StackEnumerator(Stack<Item> s) { this.s = s; this.current = s.first; this.popcount = s.popcount; this.pushcount = s.pushcount; } Item IEnumerator<Item>.Current => current.item; object IEnumerator.Current => current.item; void IDisposable.Dispose() { this.current = null; this.s = null; } bool IEnumerator.MoveNext() { if (s.popcount !
...
2018-5-23
1.4.1 # 解答 # 即为证明组合计算公式：
$C(N, 3)$
$= N! / [(N - 3)! × 3!]$
$= [(N - 2) * (N - 1) * N] / 3!$
$= N(N - 1)(N - 2) / 6$
显然 N 必须大于等于 3。
$N = 3$ 时公式正确，只有一种组合。
$N = 4$ 时公式正确，只有四种组合。
扩展到 $N+1$ 个数，将 $N = N + 1$ 代入，可得：
$(N + 1)N(N - 1) / 6$
$N + 1$ 个数能组成的三位数组合可以这样理解
前 N 个数中取三个数的所有组合 +多出的一个数和前 N 个数中的任意取两个数的所有组合
...
2018-5-23
1.4.2 # 解答 # 将 a[i] + a[j] + a[k] 改为 (long)a[i] + a[j] + a[k] 即可。
此时整个式子将按照精度最高（也就是 long）的标准计算。
long.MaxValue = 9223372036854775807 > int.MaxValue * 3 = 6442450941 代码 # /// <summary> /// 计算和为零的三元组的数量。 /// </summary> /// <param name="a">输入数组。</param> /// <returns>和为零的三元组的数量。</returns> public static int Count(int[] a) { var n = a.Length; var count = 0; for (var i = 0; i < n; i++) { for (var j = i + 1; j < n; j++) { for (var k = j + 1; k < n; k++) { if ((long)a[i] + a[j] + a[k] == 0) { count++; } } } } return count; } 另请参阅 # Measurement 库