[剑指Offer] 第2章课后题详解

目录

有序数组的插入

本题为《剑指Offer》“面试题4：替换空格”一节中的“相关题目”。

有两个排序的数组A1和A2，内存在A1的末尾有足够多的空余空间容纳A2。请实现一个函数，把A2中的所有数字插入到A1中并且所有数字是排序的。

分析

其实这道题就是实现一个归并排序，只是在数组中，数据是顺序存储的，如果在数组头部进行归并排序，每一次操作都会移动后面所有的数据，开销很大。所以应该从尾部进行操作。

正常解法

//两个数组的初始实际长度是固定，而数组a2也不需要进行改动，所以都可以声明为常量，进行保护。题目中已经说明空间足够，不然还需要再声明一个参数length，表示a1的维度，与a1，a2的初始长度之和进行比较，以防越界。
auto insertArray(int *a1, const int length1, const int *a2, const int length2) -> void{

    //i，j为a1，a2数组实际末尾下标，k为a1数组中进行归并位置的下标
    int i = length1 - 1, j = length2 - 1, k = length1 + length2 - 1;
    while(i >= 0 && j >= 0){
        //如果a1数组中未处理末尾的数大于或等于a2数组中未处理末尾的数，则将a1的该位置的数插入到a1数组末尾，否则插入a2该位置的数
        if(a1[i] >= a2[j]){
            a1[k--] = a1[i--];
        }
        else{
            a1[k--] = a2[j--];
        }
    }
    //如果数组a2中还有元素没有插入到数组a1中，则全部依次插入到数组a1前面位置
    while(j >= 0){
        a1[k--] = a2[j--];
    }
}

非主流解法

使用标准库中的vector（可变大小数组）和泛型算法会让代码变得相当简单，但相应地算法的时间复杂度会受到影响（因为会进行一次排序）。

//传入两个vector的引用
auto inserVector(vector<int> &a1, vector<int> &a2) -> void{
    //将a2的全部元素插入到a1的尾部
    a1.insert(a1.end(), a2.begin(), a2.end());
    //用泛型算法sort函数对a1进行排序
    sort(a1.begin(),a1.end());
}

两个队列实现栈

本题为《剑指Offer》“面试题7：用两个栈实现队列”一节中的“相关题目”。

栈声明如下：

template <typename T> class CStack{
public:
    void push(const T& node);
    T pop();
private:
    queue<T> queue1;
    queue<T> queue2;
    //标志目前元素存储在哪个队列中，1表示queue1，0表示queue2；
    bool flag = 1;
};

分析

根据队列的先进先出原则和栈的后进先出原则，可以进行如下设计：先将入栈元素依次加入到队列1中，出栈时，将队列1除队尾元素外依次加入到队列2中，再弹出队列1中的最后一个元素（队尾元素）。再有元素入栈时，就加入到队列2中，出栈时，将队列2除队尾元素外依次加入到队列1中，再弹出队列2中的最后一个元素（队尾元素）。之后元素入栈，又加入到队列1中，依此类推。

解法

template <typename T> void CStack<T>::push(const T& node){
    if (flag) {
        queue1.push(node);
    }
    else{
        queue2.push(node);
    }
}

template <typename T> T CStack<T>::pop(){
    if (flag) {
        //标志为1，队列1为空时，栈为空
        if (queue1.empty()) {
            throw new runtime_error("stack is empty");
        }
        //将队列1除队尾元素外依次加入到队列2中
        while (queue1.size() > 1) {
            T& data = queue1.front();
            queue1.pop();
            queue2.push(data);
        }
        //修改标志
        flag = 0;
        //弹出并返回队尾元素
        T head = queue1.front();
        queue1.pop();
        return head;
    }
    else{
        //标志为0，队列2为空时，栈为空
        if (queue2.empty()) {
            throw new runtime_error("stack is empty");
        }
        while (queue2.size() > 1) {
            T& data = queue2.front();
            queue2.pop();
            queue1.push(data);
        }
        flag = 1;

        T head = queue2.front();
        queue2.pop();

        return head;
    }
}

2的整数次方

本题为《剑指Offer》“面试题10：二进制中1的个数”一节中的“相关题目”。

用一条语句判断一个整数是不是2的整数次方。

分析

一个整数如果是2的整数次方，那么它的二进制表示中有且只有一位是1，而其他所有位都是0。把这个数减去1之后，原本为1的那一位会变成0，而在这一位之后的所有0都会变成1。把这个整数与它减一后的数做与运算则结果为0。

解法

auto isCubeOf2(const int n) -> bool{
    return !(n & (n - 1));
}

不同位数

本题为《剑指Offer》“面试题10：二进制中1的个数”一节中的“相关题目”。

输入两个整数m和n，计算需要改变m的二进制中多少位才能得到n。

分析

问题等价于m和n中有多少位不同，所以将m和n进行异或运算再计算结果二进制中的1的个数就完成求解。

解法

auto differentNumber(const int m, const int n) -> int{
    //tmp为m和n的异或结果
    int tmp = m ^ n;
    int count = 0;
    unsigned flag = 1;

    //依次检查tmp每一位是否为1
    while(flag){
        if(flag & tmp){
            ++count;
        }
        flag = flag << 1;
    }
    return count;
}