H.y's Blog clrs

10.1-6

Q:说明如何用两个栈来实现一个队列，并分析有关队列操作的运行时间。

A:栈是先进后出，而队列是先进先出，一种自然的想法是，用一个栈来存储队列的元素，入队就和如栈一样； 出队的时候先将这个栈的元素依次压出另一个栈内，然后将栈顶元素(即队首)弹出，然后再依次倒回原先的栈内。 这样入队为O(1)，出队为O(n)。仔细想想，并不需要每次都将当前所有元素在两个栈内倒来倒去， 只需要入队用一个栈，出队用另一个栈: 入队操作即在第一个栈上执行入栈；出队操作时，若第二个栈不为空，则在第二个栈上执行出栈， 若第二个栈为空，则将第一个栈内的元素依次全部压入第二个栈内。这样入队出队操作都为O(1)的复杂度。

10.1-7

Q:说明如何用两个队列来实现一个栈，并分析有关栈操作的运行时间。

A:一种自然的想法，类似于上一题，用一个队存储，另一个队列作为临时空间。入栈时就向第一个队列中插入元素； 出栈时，先将第一个队列中除队尾(栈顶)的元素依次出队后进入第二个队列，然后将队尾(栈顶 ...

15.2-2

Q:请给出一个递归算法MATRIX-CHAIN-MULTIPLY(A,s,i,j)，使之在给出矩阵序列<A1,A2,...,An>，和由MATRIX-CHAIN-ORDER计算出的表s， 以及下标i和j后，能得出一个最有的矩阵链乘法。(初始调用为MATRIX-CHAIN-MULTIPLY(A,s,1,n))。

A:模仿PRINT-OPTIMAL-PARENS(s,i,j)即可。伪代码:

MATRIX-CHAIN-MULTIPLY(A,s,i,j)
{
    if i=j then return Ai;
    else
        return MATRIX-CHAIN-MULTIPLY(A,s,i,s[i ...

6.5-6

Q:说明如何使用优先级队列来实现一个先进先出队列，另说明如何用优先级队列来实现栈。

A:队列的性质是先进先出，所以维护一个最小优先级队列，给先进队的元素赋一个小的优先级，每插入一个新的元素优先级加1。 出队时取优先级最小的元素并维护优先级队列即可。栈的实现同理。

6.5-7

Q:HEAP-DELETE(A,i)操作将结点i中的项从堆A中删去。对含n个元素的最大堆，请给出时间为O(lgn)的HEAP-DELETE的实现。

A:类似于堆排序时做的操作，将要删除的结点和堆的最后一个结点交换，将其删除后维护堆的性质。伪代码:

HEAP-DELETE(A,i)
{
    A[i] = A[heap-size[A]];
    heap-size[A] = heap-size[A] - 1;
    key = A[i];
    if key ...

2.3-7

Q:请给出一个运行时间为O(nlgn)的算法，使之能在一个由n个整数构成的集合S和另一个整数X时，判断出S中是否存在有两个其和等于X的元素。

A:首先将这n个数进行排序，然后依次对每个数查找是否存在另一个数与其的和为x，查找使用二分查找法。伪代码:

checkSums(s,x)  //s为存放n个整数的集合
{
    sort(s);    //排序

    for i = 1 to n do
        if binarySearch(s,x-s[i]) then  //二分查找
            return true;

    return false;
}

排序的复杂度为nlgn，二分查找的复杂度为lgn，执行n次就是nlgn，所以该算法的复杂度为O(nlgn)。

2-4 逆序对

Q:设A[1..n]是一个包含n个不同数的数组 ...