算法

反转数组 该问题是“给定一个数组，将其元素按从右到左重新排列，比如输入\([1,2,3]\)，应该得到\([3,2,1]\)。要求在原数组上反转，且只能占用常数额外空间”。这个问题可通过以中心为对称轴，从最外层开始反转，比如\([1,2,3,4,5]\)，会先变成\([5,2,3,4,1]\)，然后变成\([5,4,3,2,1]\)，两轮即可完成。然后考虑问题的边界，当数组有奇数个元素，两索引最后会在中心元素处相遇，当数组有偶数个元素，两索引最后会出现右边小于左边的情况。所以当右边的索引小于等于左边的索引时就意味着算法结束。该算法的时间复杂度是\(O(n)\)，其中\(n\)为数组中元素的个数。具体程序实现如下。 Python def reverse(arr): i, j = 0, len(arr) - 1 while… 阅读全文

反转链表该问题是“给定链表(表头节点)，将链表逆序，要求原地完成(由原节点构成)且只占常数额外空间”。先考虑递归程序，思路是递归进入到链表尾，然后在每次递归退出时，让外层递归把当前节点原后继的\(next\)反过来指向当前节点。需注意最后一次递归结束后，其当前节点的\(next\)没有发生变化，所以要特别的将其指向空，那为了方便干脆在每轮递归结束前都加一步把当前节点的\(next\)指向空。然后是如何记录新表头，上述递归没有用到函数返回值，可以一层层返回新表头。 Python def f(node): if not node.next: return node newHead = f(node.next) node.next.next = node node.next = None return newHead 1234567 def… 阅读全文

栈的最小值 该问题是“实现一个空栈存储数值，其支持一般的\(push,pop\)，以及用于求当前栈中最小值的\(min\)运算，要求3个运算的时间复杂度都是\(O(1)\)”。问题要求找最小值的代价是\(O(1)\)，那只能在\(push,pop\)的过程中用额外空间维护一些关于最小值的信息。假设栈只有\(push\)运算，那只需1个额外变量就能记录栈中的最小值，但当存在\(pop\)运算时，如果最小值元素被\(pop\)了，那就只能遍历寻找新的最小值，代价就不再是\(O(1)\)。这里就需要注意到栈的一个性质，即“每次\(pop\)后栈会回到最后一次\(push\)前的状态”。这说明如果用一个结构顺序记录每次\(push\)后的“历史最小值”，那么\(pop\)后的最小值就是这个结构中的倒数第2条记录，然而倒数第一条记录因为\(pop\)结束已经没意义了，应从中删除，这又说明这个结构也很适合用栈实现。… 阅读全文

两个栈实现队列 该问题是“有2个空栈\(s_1,s_2\)，出入栈运算都是\(O(1)\)代价的，要求用这2个栈实现一个队列，出入队运算都是\(O(1)\)摊还代价的”。用2个栈实现队列的思路很简单，把一组元素入栈\(s_1\)再出栈入栈到\(s_2\)就能把\(s_1\)的栈底变成\(s_2\)的栈顶，进而就能实现队头的出队。这里具体来看如何实现，首先对于入队运算，直接入栈\(s_1\)即可，对于出队运算，当\(s_2\)为空时把\(s_1\)的元素全部出栈并依次入栈\(s_2\)，最后弹出\(s_2\)的栈顶作为队头出队。当\(s_2\)非空，直接弹出\(s_2\)的栈顶作为队头出队即可。 上述过程中，每个元素的入队都是1次\(s_1\)的入栈，出队都是3次的\(s_1\)出栈、\(s_2\)入栈、\(s_2\)出栈操作。对于\(2n\)次队列操作，最好的情况是发生\(2n\)次入队操作，最坏的情况是发生\(n\)次入队、\(n\)次出队，对于最坏的情况，也仅意味着发生了\(4n\)次栈操作。所以此时的总代价是\(O(n)\)，每次操作的摊还代价是\(O(1)\)。下面是具体程序实现。… 阅读全文

计数排序(Count Sort) 计数排序是最简单的基于哈希表的排序算法，常用的排序算法是比较排序，但基于哈希表的排序一般都属于非比较排序。这类排序算法的特点是牺牲空间来换取更低的时间复杂度，这个时间复杂度甚至低于比较排序的理论极限\(O(n\lg n)\)。但这类排序对输入的数有限制、并且可能会占用相当多的空间，所以应用并不如比较排序广。 计数排序要求输入的每个数都必须是整数，算法流程是先创建空哈希表，然后遍历输入找到最大值\(max\)和最小值\(min\)，再在哈希表中依次插入关键字\(min, min+1,…,max\)并让每个关键字关联一个值用来表示“关键字在输入中的个数”，所以值初始都为0。然后遍历输入并在哈希表统计各数的出现次数，最后根据\(max\)和\(min\)按\(min,… 阅读全文