剑指offer 刷(看)题记录
面试题7:重建二叉树
题目:输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树(假设没有重复数字)。节点定义如下:
struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) :val(x), left(nullptr), right(nullptr) {}};
思路:
- 前序遍历的第一个数字总是树的根节点的值。但在中序遍历中,根节点的值在序列的中间,其中左子树的节点的值位于根节点的值的左边,右子树的节点的值位于根节点的值的右边。要扫描中序遍历序列,才能找到根节点的值。
- 又因为前序遍历总是在根节点后先遍历完左子树,才会遍历右子树,所以由后续遍历推断出左子树中节点的数目之后,前序遍历中根节点之后的相同数目的值都是左子树的节点的值。剩下的就是右子树的值。这样就分别找到了左右子树序列。
- 分别确定了根节点和左右子树的前序、中序遍历,我们可以用同样的方法构建左右子树,剩下的可以用递归来完成。
面试题15:二进制中1的个数
题目:请实现一个函数,输入是一个整数,输出该数二进制表示中1的个数。例如,把9表示成二进制是1001,有2位是1。因此,如果输入9,则该函数输出为2。
1、可能引起死循环的解法:
基本思路:先判断整数二进制表示中最右边一位是不是1,接着把输入的整数右移一位,此时原来处于从右边数起第二位被移到最右边了,再判断是不是1,这样每移次动一位,知道整个整数变成0为止。
那么,如何判断一个整数的最右边是不是1呢? 如果一个整数与1做与运算的结果是1,则表示该整数最右边一位是1,否则是0。
//每次判断最高位,右移
int NumberOf1(int n){
int count = 0;
while(n){
if(n & 1)
count++;
n = n >> 1;
}
return count;
}
注意:(1)把整数右移一位相当于把整数除以2,因为除法的效率比移位运算低得多,在编程中尽量使用移位代替乘除法。
(2)如果输入一个负数,如果最高位是1,右移时并不是简单地把最高位的1移到第二位,这是因为移位前是一个负数,仍然要保证移位后还是一个负数,所以移位后的最高位会设为1。如果一直右移,可能会陷入死循环,变成了0xFFFFFFFF。
2、常规解法:
首先把n和1做位与运算,判断n的最低位是不是1,接着把1左移一位得到2,再和n做与运算,判断n的次低位是不是1。这样反复左移。
//先判断n的最低位, 左移
class Solution {
public:
int NumberOf1(int n) {
int count = 0;
unsigned int flag = 1;
while(n){
if(n & flag)
count++;
flag = flag << 1;
}
return count;
}
};
循环次数等于整数二进制的位数(如32位)。
3、更好的解法:(整数中有几个1就只需要循环几次)
把一个整数减去1,都是把最右边的1变成0,如果他的右边还有0,则所有的0都变成1,而他左边的所有位都保持不变。把一个整数减去1再和原整数做与运算,相当于把它最右边的1变成0。
思路:把一个整数减去1,再和原整数做与运算,会把该整数最右边的1变成0.那么一个整数的二进制表示中有多少个1,就可以进行多少次这样的操作。
class Solution {
public:
int NumberOf1(int n) {
int count = 0;
while(n){
++count;
n = (n-1) & n;
}
return count;
}
};
面试题16:数值的整数次方
实现函数double Power(double base,int exponent),求base的exponent次方。不需要考虑大数问题。
解题思路:
- 这个题目看起来很简单,但其实考察的是考虑到边界问题和错误输入
- 应该分别分析底数和指数大于0、等于0、小于0的情况
两种最特殊的情况:
- 当底数为0而指数为负数的时候,是错误输入。
- 当指数为负数的时候,需要求倒数。
其他就是快速幂。
double recursivePower(double base,int exponent)
{
if(exponent == 0)return 1;
if(exponent == 1)return base;
double tmp = recursivePower(base,exponent>>1);
double resu = tmp*tmp;
//指数为奇数的情况
if(exponent&0x1){
resu *= base;
}
return resu;
}
面试题41:数据流中的中位数
面试题57:和为s的连续正数序列
题目:输入一个正数s,打印出所有和为s的连续正数序列(至少含有两个数)。例如输入15,由于1+2+3+4+5=4+5+6=7+8=15,所以结果打印出3个连续序列1~5、4~6和7~8。
思路:和为s的连续序列,根据等差和公式可得,中间的那个数一定为(s-1)/2,枚举输出。
面试题65: 不用加减乘除做加法
题目:写一个函数,求两个整数之和,要求在函数体内不得使用加减乘除四则运算符。
思路:
1. 各位相加但是不计进位,两个1和两个0相加的结果都为0,1和0相加的结果为1,这里可以使用异或来计算。
2. 第二步计算进位,只有1+1会产生进位,所以可以用于&来进行计算,但是计算后进位还在原位置,所以还需要将其左移一位;
3. 最后再求和与进位的和,一直循环直到进位为0。
面试题66:构建乘积数组
题目:给定一个数组A[0, 1, …, n-1],请构建一个数组B[0, 1, …, n-1],其中B中的元素B[i] =A[0]×A[1]×… ×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
思路: 保存两个数,一个是当前位置的前序乘积,一个是当前位置的后续乘积,相乘即可。
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!