JAVA

[TOC]

总结一下常见面试。

5.1.2 问题： 给出使用地位优先的字符串排序算法处理下面这些键的轨迹 no is th ti fo al go pe to co to th ai of th pa Give a trace for LSD string sort for the keys: no is th ti fo al go pe to co to th ai of th pa 分析： LSD 适用于字符等长的数组排序。 从右往左，依次数组中每个元素对位置d的字符使用key-indexed counting排序。 平均数组访问次数7WN+3WR。额外空间N+R。 N 对应aux数组，R对应count数组。 对于一般的应用LSD线性时间复杂度。 public static void sort(String[] a, int w) { int N = a.length; int R = 256; String[] aux = new String[N]; for (int d = w - 1; d >= 0; d--) { // sort by key-indexed counting on dth char show(a); int[] count = new int[R + 1]; for (int i = 0; i < N; i++) { count[a[i].

2.4.24 问题： Priority queue with explicit links. Implement a priority queue using a heap- ordered binary tree, but use a triply linked structure instead of an array. You will need three links per node: two to traverse down the tree and one to traverse up the tree. Your implementation should guarantee logarithmic running time per operation, even if no maximum priority-queue size is known ahead of time. 使用链表的优先队列。使用二叉树实现一个优先队列。每个结点都需要三个链接：两个向下，一个向上。你的实现需要保证在无法预知队列大小的情况下也能保证优先队列的基本操作所需要的时间为对数级别。 分析： 插入\删除 ：

2.4.2 问题： 2.4.22 Array resizing. Add array resizing to MaxPQ, and prove bounds like those of Proposition Q for array accesses, in an amortized sense. 调整数组的大小。在MaxPQ中加入调整数组大小的代码，并和命题Q一样证明对于一般性长度为N的队列数组访问的上限。 分析： 在MaxHeap类中新增方法 resize(int max)，当堆的中元素个数等于key数组容量满的时候，key数组增大两倍，当堆的元素个数等于key数组长度的1/4时，key数组长度变为原来的1/2. public _MaxMQ(){ this(1); } private void resize(int max){ assert max > N; Comparable[] temp = new Comparable[max]; for(int i=1; i<=N; i++){ temp[i] = pq[i]; } pq = (Key[]) temp; } public Key delMax(){ Key max = pq[1]; pq[1] = pq[N--]; // 使用 pq[N] 作为哨兵 sink(1); pq[N + 1] = null; if(N==(pq.

2.4.21 问题： 2.4.21 Elementary data structures. Explain how to use a priority queue to implement the stack, queue, and randomized queue data types from Chapter 1 分析： 题目要求使一个优先队列。 假设使用MaxPQ优先队列的操作有 insert delMax isEmpty size Stack： 那么对于Stack LIFO 的实现我们需要指定被后插入的元素的priority比之前插入的元素priority大。 Queue: 对于Queue FIFO 的实现，需要后插入元素的priority小于之前插入元素的priority。 randomized queue： 随机队列需要指定一个随机的priority，其余实现和处理Queue的方法一样。 问题是怎么样生成一个不重复的随机数呢？我的思路是使用一个Set保存随机数。 public int random() { int num = 0; while (!numSet.contains(num)) { num = StdRandom.uniform(1, Integer.MAX_VALUE); numSet.add(num); break; } return num; } 另外要提到的是对于使用MaxPQ实现的Stack和Queue，插入删除元素的时间复杂度都是lgN。 class IKey implements Comparable<IKey>{ Key value; int priority; @Override public int compareTo(IKey another) { return compare(this.

2.4.20 问题： Prove that sink-based heap construction uses fewer than 2N compares and fewer than N exchanges. 证明基于下沉方法建立堆使用少于2N次的比较和N次交换。 分析： 官方网站解答：https://algs4.cs.princeton.edu/24pq/ 假设为堆是完美的。 我们将树中节点的高度定义为以该节点为根的子树的高度。 一个高度为k的节点，下沉最多交换k次，对于每一层，有： $$ \begin{eqnarray} h + 2(h-1) + 4(h-2) + 8(h-3) + \ldots + 2^h (0) & = & 2^{h+1} - h - 2 \ & = & n - (h+1) \ & \le & n \end{eqnarray} $$ 第一项使用等比数列求和公式，第二项错位相减法。 参考： 沈星繁

2.4.19 问题： 2.4.19 Implement the constructor for MaxPQ that takes an array of items as argument, using the bottom-up heap construction method described on page 323 in the text. 实现一个MaxPQ的构造函数，接受一个数组做为参数，使用323页中描述的自底向上的方法构建堆。 分析： 将数组做为参数构建堆，可以选择从左到右扫描，使用swim()方法。 但更明智的方法是使用从右往左扫描的方式，sink()。 这个方法的想法是如果一个结点的两个子结点的树都是堆的话，sink(k)之后，两个子树就合并成了以k为根结点的子树 public MaxPQ(Key[] a){ N = a.length; pq = (Key[]) new Comparable[N+1]; for(int i=0; i<a.length; i++){ pq[i+1] = a[i]; } int k = N / 2; while (k >= 1){ sink(k); k --; } assert isMaxHeap(); show(); } 参考： 课本官网的实现MaxPQ

2.4.18 问题： 2.4.18 In MaxPQ, suppose that a client calls insert() with an item that is larger than all items in the queue, and then immediately calls delMax(). Assume that there are no duplicate keys. Is the resulting heap identical to the heap as it was before these op- erations? Answer the same question for two insert() operations (the first with a key larger than all keys in the queue and the second for a key larger than that one) followed by two delMax() operations.

2.4.17 问题： 2.4.17 Prove that building a minimum-oriented priority queue of size k then doing N - k replace the minimum (insert followed by remove the minimum) operations leaves the k largest of the N items in the priority queue. 分析： 题意是insert followed by remove the minimum，先插入后删除。 例如 N=10, 元素为：0,2,4,6,8,1,3,5,7,9 k=3， qp = 0 2 4 N-k = 10 - 3 = 7，将要进行7次操作 pq = 0 2 4 count = 1 insert 6, pq = 0 2 4 6 remove 0, pq = 2 4 6 count = 2 insert 8, pq = 2 4 6 8 remove 2, pq = 4 6 8 count =3 insert 1, pq = 1 4 6 8 remove 1, pq = 4 6 8 .

2.4.10 问题： 2.4.10 Suppose that we wish to avoid wasting one position in a heap-ordered array pq[], putting the largest value in pq[0], its children in pq[1] and pq[2], and so forth, proceeding in level order. Where are the parents and children of pq[k]? 分析： 略 答案： 子节点：$ 2k+1, 2k+2 $，父节点： $ \lfloor \frac{k-1}{2} \rfloor $ 参考：