[剑指Offer] 第2章课后题详解
目录
- 剑指Offer 第2章课后题详解
- 目录
- 有序数组的插入
- 分析
- 正常解法
- 非主流解法
- 两个队列实现栈
- 分析
- 解法
- 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;
}