"剑指offer思路整理"

  "剑指offer整理"

Posted by Xu on April 9, 2018

剑指offer题目整理

数据结构

数组

面试题三:找重复数字

  • 找出数组中重复的数字,在长度为n的数组中数字大小的范围在0~n-1之间。

思路:本身原数组就是一个长度为n的数组,所以原数组自身就可以当成哈希表来存放数据,遍历数组,将每一个元素存放到和下标对应的位置,如果该位置已经存在该数则说明重复,直接输出。

  • 不修改数组找出重复的数字,长度为n+1的数组里所有的数字都在1~n的范围内,所以数组中至少有一个数字是重复的,找出任意一个重复的数字

思路:利用二分查找,将1-n的数据范围分为两部分(假设n=8),分为1-4和5-8,再统计1-4和5-8这两个范围出现的次数,如果次数大于4,则说明该范围内出现重复,所以对该范围继续进行二分查找,比如1-4这个范围的数出现的次数超过4则将1-4分为1-2和3-4,然后如此循环二分下去,直到分到成一个元素并且出现次数多于两次。

面试题四:二维数组中的查找(对顺序容器的访问)

  • 二维数组从左到右,以及从上到下满足递增关系,输入一个整数,判断该二维数组有没有该整数

offer1

由于从第一行第一列的元素开始,往右和往下均是递增的方向,所以并不能缩小搜索范围,所以我们可以考虑从第一行最后一列(图中9)的右上角元素开始,往下递增,往左递减,这样可以根据我们想搜索的整数和当前元素的大小关系来缩小范围。

代码:

public:
    bool Find(int target, vector<vector<int> > array) {
        if(array.empty()){
            return false;
        }
        long len_i = array.size();
        long len_j = array[0].size();
        long i=0,j=len_j-1;
        while (true) {
            if(array[i].size()!=len_j){
                return false;
            }
            if(array[i][j]>target){
                j--;
                if (j<0) {
                    return false;
                }
            }else if(array[i][j]<target){
                i++;
                if (i>=len_i) {
                    return false;
                }
            }else{
                return true;
            }
        }
    }

字符串

C/C++常常将常量字符串存放在一个单独的内存区域(常量存储区)

  • 用常量字符串给字符数组赋值时,先分配内存后复制
  • 用常量字符串给字符指针赋值时是将常量存储区中的地址赋给该指针,所以给多个指针赋值的地址都相同。

面试题五:替换空格(memcpy的使用)

  • 将一个数组中的字符串中的空格用%20代替。

思路:遍历该字符串,遇到空格,则添加%20,将其后字符串全部后移,如此循环处理每一个空格

进阶:按上面的思路,后面的字符会进行多次后移,时间复杂度太高O(n^2),所以我们可以先计算空格数量,将整个字符串向后移到合适的位置,然后用两个指针来将所有字符串向前移动一次到合适的位置即可,这样的时间复杂度为O(n)

offer2

代码:

public:
    void replaceSpace(char *str,int length) {
        if(str==nullptr){
            return;
        }
        
        int count=0;
        //计算空格数量
        for(int i=0;i<length;i++){
            if(str[i]==' '){
                count++;
            }
        }
        char * p_front = str;
        char * p_back = str+2*count;
        //字符串后移
        memcpy(p_back, p_front, length+1);
        //字符串向前拷贝
        for (int i=0; i<length+1; i++) {
            if( *p_back == ' '){
                memcpy(p_front, "%20", 3);
                p_front+=3;
            }else{
                *p_front = *p_back;
                p_front++;
            }
            p_back++;
        }
    }

链表

面试题6:从尾到头打印链表

思路:

  1. 递归

  • 树的三种遍历:前序,中序和后序
  • 还有基于队列的层级遍历
  • 两个特殊的树:堆和红黑树,set,multiset,map,multimap等数据结构都是基于红黑树来实现的

面试题7:重建二叉树

  • 输入某二叉树的前序遍历和中序遍历的结果,重建该二叉树

思路:前序遍历的根节点在头部,中序遍历的序列可以根据根节点很容易得到左右子树的中序遍历序列,所以可以得到左右子树的前序和中序遍历的序列,然后进行递归即可

面试题8:二叉树的下一个节点

  • 给定一棵二叉树和其中一个节点,每个节点不仅有指向左右节点的指针还有一个指向父节点的指针,找出该节点在中序遍历中的下一个节点。

思路:

  • 中序节点的下一个节点要么是右子树的最左孩子
  • 没有右子树的话,则是第一个使得该节点所在的子树是其左子树的父节点

栈和队列

面试题9:用两个栈实现队列

思路:使用两个栈,一个栈作为压入栈,一个栈作为弹出栈,当压入数据时,将所有数据先压入压入栈再进行压入操作,同理弹出数据时,将所有数据先压入弹出栈然后进行弹出操作。

算法和数据操作

  • 递归和循环的比较,递归简洁但性能不如循环
  • 排序算法:二分查找,归并排序,快速排序,哈希排序,堆排序,选择排序,插入排序
  • 回溯法
  • 动态规划:可以理解为递归过程中后半部分的操作,即将子问题求解后,由下至上解决问题

一般优化思路:递归 -(优化)-》动态规划 -(优化)-》 分解子问题(贪婪选择)

递归和循环

斐波拉契数列

  • 求斐波拉契数列的第n项

思路:F(n) = F(n-1)+F(n-2);递归求解,性能低,导致很多重复计算

思路二:动态规划,利用一个数组f[n],从1,2开始循环记下第n项的数字O(n)。

思路三:矩阵的乘法,F(n) = [1 1 / 1 0]的n-1次方,然后根据a^n = (a^(n/2))^2可以简化运算,从而得到O(logn)的解法

  • 青蛙跳台阶,可以跳一阶,也可以跳两阶,问有多少中跳法跳到第n阶。同上

  • 矩形覆盖问题:用2*1的小矩形横着或数着去覆盖更大的矩形,请问用8个该小矩形有多少中方法覆盖2*8的大矩形?同为斐波拉契问题

offer3

查找和排序

  • 二分查找通常用于排好序的数组
  • 哈希表可以在O(1)时间内查找某一个元素,但需要额外的空间

面试题11:旋转数组的最小数字(二分查找很好的例子)

  • 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序数组的旋转,然后输出该旋转数组的最小整数。

思路:该数组排好序,可以使用二分查找,递归查找到较小的一半,同时需要考虑边界情况,当旋转的个数为0时,数组元素个数为1时。

还需要考虑到数组元素出现重复的情况,当二分查找的过程中发生两个数大小相同时,我们不得不采用顺序查找的方式去寻找最小值

offer4

代码:

递归实现

public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        if(rotateArray.empty()){
            return NULL;
        }
        int end = rotateArray.size()-1;
        return binarySearch(rotateArray,0,end,end/2);
    }
    
    int binarySearch(vector<int> &arr,int start,int end,int mid){
        if(start >= end){
            return arr[start];
        }
        int min,mid_tmp = mid;
        if(arr[mid]<arr[end]||(arr[mid]==arr[end]&&arr[mid]!=arr[start])){
            end = mid-1;//这里必需要减1,否则容易陷入死循环
            mid = (start + end)/2;
            min = this->binarySearch(arr,start,end,mid);
            min = arr[mid_tmp]<min?arr[mid_tmp]:min;
        }else if(arr[mid]>arr[end]){
            start = mid+1;//这里必需要加1,否则容易陷入死循环
            mid = (end+start)/2;
            min = this->binarySearch(arr,start,end,mid);
        }else if(arr[mid]==arr[end]){
            min = arr[start];
            for(int j=start;j<=end;j++){
                if(arr[j]<min){
                    min = arr[j];
                }
            }
        }
           return min;
           
           }

循环实现

public int minNumberInRotateArray(int [] array) {
        int low = 0 ; int high = array.length - 1;   
        while(low < high){
            int mid = low + (high - low) / 2;        
            if(array[mid] > array[high]){
                low = mid + 1;//同上
            }else if(array[mid] == array[high]){
                high = high - 1;//同上
            }else{
                high = mid;
            }   
        }
        return array[low];
    }

二分查找的注意点:

  • 当查找范围对半,需要缩进一个单位lo = mid+1 hi= mid-1,防止进入死循环。
  • 循环结束条件:lo>=hi。
  • 为什么我想要查找的元素一定在低位lo:因为mid取值是向下取整
    • 当最后是lo向后移动的时候只有可能出现lo==hi,这种情况,我们查找的元素肯定在lo位置
    • 当最后是hi向前移动一个单位时如lo=5,hi=6,mid=(5+6)/2=5时,hi以mid为起始点向前移动一个单位,就很有可能出现lo>hi,此时明显lo还位于我们之前的有效范围(5-6),hi无效,因为是hi在移动。所以也是在lo位置

回溯法

回溯法可以看做蛮力法的升级版,回溯法解决的问题的所有选项可以形象的用树状结构表示

所以回溯法必须要先确定一个起点,然后由该起点进行各方向的发散,满足条件就深度优先,否则回溯到父节点后,选择另一个方向孩子节点进行条件测试

面试题12:矩阵中的路径

  • 设计一个函数,用来判断矩阵中包含该字符串所有字符的路径
  1. 先找到该字符串首字符出现的节点位置
  2. 找到起点后根据该字符串后续字符进行条件测试,用一个访问表来记录节点是否被访问,满足条件测试的标记一访问,否则去掉访问标记。
  3. 每个节点都有四个方向可以供选择,满足条件则进入该节点,否则选择其它方向

面试题13:机器人的运动范围

  • 地上有一个m*n的方格,机器人只能进入节点坐标的数位之和小于或等于于k的节点,如k为18,则能进入(35,37)方格,因为3+5+3+7=18,但不能进入方格(35,38)因为3+5+3+8=19。问机器人可以到达多少个格子。

思路:回溯法

  1. 同样,先确定起点在(0,0),然后根据不同的方向选择节点进入
  2. 只要访问到了就标记为访问,不再去掉,与12题有所区别,因为这里的节点是独立作用的,和路径上节点出现的先后顺序无关。
  3. 访问过程其实就是一个深度优先(满足条件),然后广度覆盖的访问顺序。

动态规划与贪婪算法

可以动态规划的几大条件:

  1. 大问题是否可以化成小问题求解
  2. 大问题的最优解是否依赖小问题的最优解
  3. 相互重叠的更小子问题,当求解两个子问题时发现对一个更小子问题有重复求解的过程,就适合使用动态规划
  4. 从下往上计算最优解并存储下来。

所以动态规划的求解步骤:

  1. 找出大问题的最优解与子问题的最优解之间的依赖关系
  2. 初始化最小子问题的最优解
  3. 根据依赖关系从下往上求解最优解并存储到对应数据结构

面试题14:剪绳子

  • 有一根长度为n的绳子,剪成m段,(m,n都为整数)每段长度为k[0],k[1]…k[m]。问这些长度的最大乘积为多少。

思路:

  1. 分解子问题,将一个绳子分为两段,在所有分段的情况中使得l1和l2最大乘积的乘积最大及为长度为n的最大乘积,在分段过程中将长度为n的绳子求最大乘积的问题化解为了求两个长度小于n的最大乘积问题,所以缩小了问题规模。所以我们需要比较将绳子分为1和n-1的最大乘积之和,2和n-2,3和n-3…这些所有分段的最大乘积之和的最大值。
  2. 初始化最小子问题,初始化长度为0,1,2,3的最大乘积之和
  3. 然后由下至上,进行比较后得到最大值然后记录下来。直到求解到长度为n的最大乘积之和

优化:贪婪算法

  1. 当n>=5时竟可能多的剪长度为3的绳子,因为当n>=5时,3(n-3) >= 2(n-2)
  2. 所以只要当n>=5时,逐个剪长度为3的绳子,直到n<5,当n=4时,剪两段长度为2的绳子

位运算

  • 移位运算符优于乘除运算符

面试题15:二进制中1的个数

  • 实现一个函数,输入一个整数,输出该数的二进制表示中1的个数。

思路:将数不断右移一位,移动一位后和1做与运算,如果结果为1说明该移位后的数的最后一位为1。

思路二:为防止死循环,(因为出现负数时,右移会不断进位1)我们可以将1不断左移然后和原数做与运算

思路三:将输入数减1,因为减1相当于把该数最右边第一个为1的位数后面所有位做取反操作,如10010100减1后得到10010011,最右边第一个为1是第三位,所以相当于第三位右边的位全做取反操作,然后和原数做相与的操作得到10010000相当于去除掉了最右边的1,如此循环减1然后和原数进行与操作,从右到左逐个把所有1消除掉,直到该数为0,得到1的个数

代码:

public:
    int  numberOf1(int n) {
        if(n==0){
            return 0;
        }
        int i = 1,count = 0;
        while(i!=0){
            if(n&i)
                count++;
            i = i<<1;//位运算
        }
        return count;
    }

高质量的代码

代码的完整性

三个测试

  • 功能测试
  • 边界测试
  • 负面测试

面试题16:数值的整数次方

double Power(double base,int exponent);不需要考虑大数问题

边界考虑:实现很简单,但是我们必须要对边境进行限定和考虑,比如当exponent为负数,为0时我们都要考虑在内

代码优化的思路(类似于二分求解): a^n = (a ^(n/2))*(a ^(n/2)) (n为偶数)

a^n = (a ^((n-1)/2))*(a ^((n-1)/2))*a(n为基数)

并且(位运算符优于乘除运算):

  1. 用位与运算来判断n是否为偶数
  2. 用右移运算符来将n除以2

代码:

public:
    double Power(double base, int exponent) {
        if(exponent==0){
            return 1;
        }
        if(exponent == 1){
            return base;
        }
        bool flag = true;
        if(exponent<0){
            flag = false;
            exponent = -exponent;
        }
        
        double result = 0 ;
        double tmp = Power(base,exponent/2);//这里不能使用右移,这样失去/的隐性向下取整的规则
        tmp = tmp*tmp;
        if(exponent&1){//这里用位与运算符判断是否为偶数,很有特点
            result = tmp*base;
        }else{
            result = tmp;
        }
        if(flag){
            return result;
        }else{
            return (double)1/result;
        }
    }

面试题17:打印从1到最大的n位数

  • 输入数字n,按顺序打印从1到最大的n位十进制输。比如输入3,则打印1,2,3一直到最大的三位数999.

边界考虑:

  1. n不能小于0
  2. n过大时,考虑大数问题

思路:用字符串存放数据,然后字符串模拟数字加法,逐个加1并打印

思路2: 使用递归求解,相当于n位数字的从0-9的全排列,用递归实现该全排列,从第n位开始,每一位从0开始,然后从n-1…到最后一位时开始打印。

面试题18:删除链表的节点

  • 给定单向链表的头指针和一个节点指针,定义一个函数在O(1)时间内删除该节点。

难点:单向节点,不能找到该节点指针的上一个节点,且时间复杂度为O(1),不能顺序遍历。

思路:将该节点的值改为下一个节点的值并删除下一个节点。

边界考虑:

  1. 当该节点没有下一个节点时
  2. 删除的节点指针是否在链表上。
  3. 链表只有一个节点时

面试题19:正则表达式的匹配

  • 实现一个函数来包含’.’和’*’,’.’可以代表任意一个字符,‘*’代表它前面的字符可以出现任意次(包含0次),匹配是指字符串中所有字符匹配整个模式。如字符串’aaa’与模式”a.a”和”ab*ac*a”匹配,和”aa.a”以及”ab*a”不匹配。

思路:递归,逐个字符进行匹配,当模式中遇到.时则跳过任意一个字符进行匹配,遇到*比较复杂,分三种情况,1. 前面的字符出现0次 2. 前面的字符出现1次 3.前面的字符出现多次(多于两次)。返回三种情况的匹配情况。

边界考虑:当字符串或模式字符串为空时

面试题20:表示数值的字符串

  • 请实现一个函数判断字符串是否表示数值.如+100 5e2 -123 3.1416 -1E-16都表示数值,12e 1a3.14这些就不表示数值
规律:表示数值字符串遵循模式A[.[B]][e EC]
  1. 一个数值第一部分为一个有符号数
  2. **第二部分可以是’.’,也可以是’e|E’,但’.’后面必须跟一个无符号数,且e|E后面跟一个有符号数 **

边界考虑: 1.输入字符串为空时

面试题21:调整数组顺序使奇数位于偶数前面

  • 输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,偶数位于后半部分。

思路:和快排类似,将一类数据排到前面,一类数据排到后面维护两个指针,一个向前滑动一个向后滑动,遇到不满足当前区域的数据类型停止,然后进行数据交换。

可扩展:这是一类问题,重点在于如何判断两个类型的数据,所以我们可以把判断类型部分抽象出来(解耦),适合该类型问题的通用求解

边界考虑:输入nullptr指针,输入的数组只包含一个数字。

代码的鲁棒性

程序要能够判断输入是否合乎规范要求,并对不符合要求的输入给予合理的处理

面试题22:链表中倒数第k个节点

  • 输入一个链表,输出该链表中倒数第k个节点的值。

思路:两个指针,一个指针先走k步,第二个指针再开始从头遍历,直到第一个指针达到链表末尾时,第二个指针指向倒数第k个节点。

考虑输入规范:

  1. 链表节点个数小于k个
  2. 链表为空
  3. k等于0时(k为无符号整数)

面试题23:链表中环的入口节点

  • 如果一个链表中包含环,如何找出环的入口节点。

思路:快慢指针,第二个指针每当第一个指针每移动两个节点时移动一个节点。如果出现环,则第一个快指针肯定会在某个时刻和第二个慢指针相遇,相遇时,第一个指针和第二个指针所走过的路程之差正好为环的长度,且快指针走的路程为慢指针的两倍。于是,再安排第三个指针从头开始,且速度和慢指针一致,那么这第三个指针一定会在环的入口和慢指针相遇,因为它们两之间的距离差为环的长度。

输入规范考虑:

  1. 链表中包含或者不包含环,链表中有多个节点或者一个节点
  2. 链表为空

面试题24:反转链表

  • 定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。

思路1:使用栈重新构建新的链表,空间复杂度为O(n)。

思路2:使用三个指针临时变量,分别记录前一个节点,当前节点和下一个节点。逐个反转。

输入规范:

  1. 链表为空,或只有一个节点
  2. 链表有多个节点

面试题25:合并两个排序的链表

  • 输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的

思路:构建一个新的链表,两个指针从两个链表的头节点开始遍历比较,然后添加到新链表中的节点

思路二:三个指针控制合并过程(还有一个指针指向合并链表的头节点,但不参与合并过程),一个指针指向已经合并的链表的尾部节点,两个指针分别指向两个链表还没有合并的头节点。

输入考虑:

  1. 两个链表有空节点,或只有一个节点
  2. 两个链表存在值相等的情况

面试题26:树的子结构

  • 输入两棵二叉树A,B判断B是不是A的子结构

思路:利用队列(入队父节点,当父节点弹出时,入队两个孩子节点)层级遍历,先匹配根节点,如果根节点匹配,再先序遍历匹配整棵子树。匹配的过程可以用递归实现。

输入规范:

当两棵树为空时

解决面试题的思路

画图然后抽象问题形象化

面试题27:二叉树的镜像

  • 请完成一个函数,输入一棵二叉树,该函数输出它的镜像。

思路:前序遍历该二叉树的节点,只要有孩子节点则交换左右孩子节点,如此递归到每一个叶节点。

输入规范:考虑到输入的节点为空,或者没有左子树,没有右子树的情况

面试题28:对称的二叉树

  • 实现一个函数用来判断一棵二叉树是不是对称的

思路1: 根据面试题27经验先获取一棵二叉树的镜像,然后比较该镜像和原二叉树的结构是否一致

思路2: 前序遍历和前序对称遍历的序列一致,对称遍历是先访问右节点再访问左节点,且在序列化中用#代替空孩子节点,使得该树为作为一棵满二叉树来遍历。通过比较两个序列是否一致即可判断是否对称

输入规范:

输入二叉树为空时

面试题29:顺时针打印矩阵

  • 输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。例如,如下矩阵

offer5

思路:每打印完一圈后,会面对一个长宽分别减小2的相同类型的矩阵顺时针打印,所以可以递归解决该打印的问题。

优化:所有递归都可以用循环解决

初始化条件判断:有几个初始化条件需要注意,有的矩形打印只需要1步,2步或三步需要注意,需要四步打印的前提条件是至少有三行两列。

举例让问题更抽象化

面试题30 :包含min函数的栈

  • 定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的min函数,且调用min,push,pop的时间复杂度都是O(1)。

思路:定义两个栈,一个原栈保存数据,一个min栈保存当前最小值,每向原栈push压入数据时,和min栈的top元素进行比较如果小于该元素则push压入该min栈,否则只push压入原栈。当原栈pop弹出一个数据时,同样和min栈top元素进行比较,大于top元素,只弹出原栈数据,若相等则两个栈同时做pop操作。min函数简单,直接读取min栈的top元素

面试题31:栈的压入、弹出序列

  • 输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个顺序是否为该栈的弹出顺序,栈内所有元素值不相等。

思路:

  • 首先要注意弹出顺序并不是指全部元素压入后才全部弹出,在压入过程中也可以弹出。
  • 所以我们可以按压入序列将元素压入栈,压入过程中每压入一个元素和弹出序列进行比较,如果相同则弹出该元素,然后比较栈顶top元素和弹出序列的下一个首元素,相同继续弹出,不相同则压入栈,然后压入下一个元素重复该步骤
  • 当压入序列全部压入后,弹出序列也全部匹配成功,则说明该弹出序列是该压入序列的一个弹出顺序。若弹出序列还有元素没有成功匹配,说明不存在该弹出顺序

offer6

面试题32:从上到下打印二叉树

层级遍历,使用队列结构,压入根节点然后弹出根节点,并压入根节点的左右孩子节点,继续弹出队列首元素,只要弹出一个节点,就要压入该节点的孩子节点。

  • 分行打印:分层打印每一层节点,记录并标记每一层的结束节点,每碰到该结束节点则换行打印。

  • Zigzag之字形打印二叉树:

    • 使用双端队列第一次从队尾压入元素,从队首弹出元素,同样弹出一个节点就要从压入它的孩子节点,但这次从队首压入,且为逆序压入(先压右孩子,再压左孩子)
    • 这里我们同样和分行打印一样需要记录每一行最后打印的节点,因为每打印完一层后,压入队列和弹出队列的方向就会发生颠倒,比如一层从队尾压入,队首弹出,下一层从队首压入,队尾弹出。

面试题33:二叉搜索树的后续遍历序列

  • 输入一个整数数组,判断该数组是不是某二叉树的后序遍历结果,如果是返回true,否则返回false

思路:后序遍历的特点是根节点在序列尾部,且序列前面的特点为一部分元素均小于根节点,后部分节点小于根节点,如果不满足该特点则不为二叉搜索树的后序遍历序列。然后对这两个部分进行递归判断。

面试题34:二叉树中和为某一值的路径

  • 输入一棵二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径

思路:先序遍历,用一个保存从根节点到当前节点路径的和,当该条路径的和不能满足该输入整数时,弹出栈内的第一个和元素值,然后计算下一个要遍历节点到根节点路径上的和,这样可以保证栈内存储的元素始终为一条路径上的所有和

分解让复杂问题简单化

面试题35:复杂链表的复制

  • 要完成对一个链表的复制,该链表除了有指向下一个节点的指针,还有一个执行该链表上任意一个节点的指针。

思路1:使用hash表,存放每个节点指向任意节点的指针

思路2:链表中每个节点在链表中复制一份,如下图所示:

offer7

然后复制的节点的任意指针只要指向原指针任意指针所指向节点的下一个节点即可,然后将复制的节点分离出来。

面试题36:二叉搜索树与双向链表

  • 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。

思路:二叉搜索树的中序遍历就是一个排好序的序列,所以我们直接用中序遍历可以构造一个排好序的双向链表。

面试题37:序列化二叉树

  • 请实现两个函数,分别用来序列话和反序列化二叉树。

思路:因为面试题7重建二叉树可以知道前序遍历和中序遍历的序列可以唯一构建一棵二叉树,所以我们可以记录一棵树的前序序列和中序序列,然后根据这两个序列进行恢复

限制:

  • 要求二叉树不能有数值重复的节点
  • 只有当两个序列构建成功后才能进行反序列化

思路2:对一棵完全满二叉树进行前序遍历序列化,所有为空的节点用特殊符号#来表示即可,这样根据前序遍历的序列也可以唯一确定一棵二叉树。

面试题38:字符串的排列

  • 输入一个字符串,打印出该字符串中所有的排列情况,如输入abc,则有abc,acb,bac,bca,cab,cba输出

思路:

  1. 对一个字符串abc,首先将a和a,b,c逐个进行交换,首先和a进行交换接下来对剩下的bc进行递归的全排列操作,如此递归到最后一个字符串打印。。
  2. 然后,a和b进行交换,对后面的字符串ac同样进行递归操作。递归的步骤也是循环步骤1和步骤2..
  3. 当a和最后一个字符c交换并处理完后结束递归,所有排列情况的序列均得到打印

优化时间和空间效率

时间效率

面试题39:数组中出现次数超过一半的数字

  • 给出一个数组,输出该数组中一个数字出现的次数超过数组长度一半的数字。

思路:因为该数字超过数组长度的一半所以排序后的数组中间的数一定为这个数。所以利用快排的思想来找到中间这个数。

思路2(很有特色):数组中有一个数字出现的次数超过数组长度的一半,也就是说它出现的次数比其他所有数字出现的次数的和还要多,所以我们可以在遍历数组的过程中保存两个值:一个是数组中的一个数字,另一个是次数(只要有两个不为该要输出数的数连在一起,就一定有两个相同的该输出数连在一起),遍历数组时,当下一个数字和当前保存的数字相同时,则次数加一,否则次数减一,当次数减为0时,则下一个数字替换当前保存的字符继续遍历,直到数组中所有元素遍历完后,我们保存的数就为出现次数超过一半的数。并且可以根据保存次数求出该数字出现的总次数

面试题40:最小的k个数

  • 输入n个整数,找出其中最小的k个数

思路1(O(n)):利用快排找出最小的k个数

思路2(O(nlogk)):利用容器,这里最好利用堆来存储最小的k个数,这个方法非常适合处理海量数据。遍历该数组,逐个添加到最大堆里面去,当堆的元素个数达到k个时则将新添加的元素和最大堆的根节点元素进行比较,如果大于该最大值,则不插入该堆,如果小于该最大值,则删除该根节点后,添加新值到该堆

* 并且这个容器我们可以用红黑树来代替,在C++中,multiset和set都是基于红黑树实现的。可以直接使用 	

面试题41:数据流中的中位数

  • 如何得到一个数据流中的中位数

  • 思路1:将数据流中的数字逐个插入到数组中去,插入过程需要O(N),在数组中寻找中位数只需要O(1)

  • 思路2:将数据流中的数字插入到链表,插入操作需要O(n),寻找中位数操作也需要O(N),但设置一个指针指向中位数,则只需要O(1)来寻找中位数。

  • 思路3:将数据流中的数字插入到二叉搜索树,插入时间减少为O(logn),每个节点添加一个表示子树节点数目的字段,这样就可以在O(logn)内找到中位数
    • 改进:使用AVL树,插入为O(logn),寻找中位数只需要O(1)
  • 思路4:用两个堆表示中位数的左右两部分,左边为最大堆,右边为最小堆,当数据流中数字的个数为奇数时,插入左边的最大堆,当个数为偶数时,插入右边的最小堆,但是当插入的数插入最大堆时大于最小堆的最小值,则要将最小堆的最小值插入到最大堆,然后将该值插入到最小堆,同理,当插入的数插入最小堆时小于最大堆的最大值,则要将最大堆的最大值插入到最小堆,然后将该值插入到最大堆

面试题42:连续子数组的最大和

  • 输入一个整型数组,数组厘米有正数也有负数,求使得数组中的任意子数组的和最大的子数组,且要求时间复杂度为O(N)。

思路1:遍历该数组求和,当和小于等于0时则舍弃前面的部分,重新开始构建子数组,并且在构建过程当中记录并更新和的最大值以及该最大和子数组的下标范围信息。

思路2:动态规划

    • 首先分析最优解之间的依赖关系:以i结尾的最大和子数组(1)f(i) = f(i-1)+pData[i] (当f(i-1)>0且i!=0时) (2)f(i) = pData[i] (当f(i-1)<=0或i=0时)。
    • 然后初始化当i=0时f(0)
    • 然后根据依赖关系求出以每一个元素结尾的最大子数组和,并不断更新整个数组中最大子数组和的大小

面试题43:1~n整数中1出现的次数

  • 输入一个整数n,求1~n这n个整数的十进制表示中1出现的次数,如输入12,这些整数中包含1的数字有1,10,11,12一共出现了五次

思路:寻找数字规律,每10个,100个,1000个…为单位进行分析,比如1~21345,可以分为几部分1~1345 ,1346~11345 , 11346~21345,在后面两部分中1346~11345 , 11346~21345的后四位可以选一位为1,其他三位从0到9任意选择,根据排列组合规则,总共出现的次数为4(四位)*10*10*10(其他三位的选择),所以这两部分的后四位出现1的次数为2*4*10*10*10=8000次,然后在第一位出现1的次数达到10000次,在1~1345用同样的思路去递归求出现1的次数。

面试题44:数字序列中某一位的数字

  • 数字以0123456789101112131415…的格式序列化到一个字符序列中,求该序列中第n位数字是多少?

思路:寻找规律10以下需要10位,100以下10以上的序列需要180(90*2)位,1000以下100以上的序列需要2700位(900*3)。。。所以首先循环去判断n位于哪一个区间,然后判断n在该区间的第几个数,最后判断在该数的第几位上。

面试题45:把数组排成最小的数

  • 输入一个正整数数组,把数组中所有数字拼接起来排成一个数。如{3,32,321}组成的最小数字为321323

思路:

  • 任意两个数,有一个数放在高位一个数放在低位会使得构造的数小一点,在数组中的多个数也满足这个规律,所以我们依据这个规律将数组中所有数字进行排序

  • 排序比较的规则就是:两个数中,数x放在高位,数y放在低位构成的数,比数y放在高位,数x放在低位的数大,则x>y。然后我们得到一个从小到大排好序的数组,最后拼接起来就可以得到一个最小的拼接数

面试题46:把数字翻译成字符串

  • 给定一个数字,按照如下规则把他翻译为字符串:0翻译成”a”,1翻译成”b”…25翻译成”z”。且一个数字有多个翻译方法,如12258,有五种不同的翻译分别是”bccfi”,”bwfi”,”bczi”,”mcfi”,”mzi”。实现一个函数,计算一个数字有多少中翻译方法

思路:同菲波拉契数列,一个字符串可能单独作为一个字符,也有可能和后面的数字拼接起来作为一个字符,但和后面的数字拼接有条件限制,就是拼接的数字不能大于25。所以动态规划的依赖关系为f(i) = f(i+1)+g(i,i+1)*f(i+2)。当拼接的数大于25或小于10时g(i,i+1)=0,大于10小于25时g(i,i+1)=1。

面试题47:礼物的最大价值

  • 在一个m*n的棋盘中每一个都放有一个礼物,每个礼物都有一定价值,你可以从棋盘的左上角,通过向右或向下移动获取路上所有的礼物直到达到右下角。给定一个棋盘,求你最多可以拿价值为多少的礼物

offer8

思路:

  • 动态规划,因为从左上角移动到右下角,所以可以设计一张状态二维表,横坐标为列号从右到左编号(0-6),纵坐标为行号从下到上编号(0-4)。 offer9

  • 初始化第一行第一列,第一列
  • 状态转换方程:f(i,j) = max{f(i,j-1),f(i-1,j)}+gift(i,j);
  • 状态转换方程构建完成后f(4,4)即为礼物的最大价值。

优化:由于f(i,j) = max{f(i,j-1),f(i-1,j)}+gift(i,j);第i行的最优解只依赖于它上一行和上一列的元素,所以我们可以只用一维数组就可以记录状态变化过程。如下图,当计算到(3,2)时,后面表中的数据求解只依赖于图中灰色部分,一位数组就可以记录下来。

面试题48:最长不含重复字符的子字符串

  • 请从字符串中找出一个不包含重复字符穿的子字符串,计算该最长子字符串的长度。如字符串“arabcacfr”中最长的不含重复字符的子字符串是”acfr”长度为4

思路:递归解决,已知第n-1个字符结尾的最长字符串,在求以第n个字符串结尾的最长字符串,就要将第n个字符和n-1个字符串结尾的子字符串进行对比,是否有重复字符,如果有,则计算该重复字符之间的距离d,则f(n) = d。如果没有则f(n)=f(n-1)+1。

时间效率和空间效率的平衡

面试题49:丑数

  • 我们把只包含因子2,3,5的树称作丑数。求从小到大的顺序第1500个丑数。

思路:在已经排好序的丑数序列中,我们记最大的丑数为M,则在M之前一定有一个数m2(比如第n个数)乘以2正好大于M(第n-1个数小于M),我们把m2乘以2的结果记为M2,同理对于因子3,5都有对应的m3,M3,m5,M5。而当前最大丑数的下一个丑数必然出现在M2,M3,M5之间的最小者。同时在每一次序列更新后,如M2最小,我们只需要更新m2的位置即可,然后如此循环不断获得后续的顺序丑数,直到找到第1500个丑数。

面试题50:第一个只出现一次的字符

  • 字符串中第一个只出现一次的字符

思路:使用hash表数组,第一次遍历记录每个字符出现的次数,第二次遍历根据hash表找出第一个只出现一次的字符

  • 字符流中第一个只出现一次的字符

思路:同样适用hash表,hash表纪录那些只出现一次的字符的所在位置,而出现多次的字符不用纪录位置,只需要标示-2来表示重复出现,所以获取第一次只出现一次的字符,我们只需要遍历hash表,找出所有只出现一次的最小下标位置

面试题51:数组中的逆序对

  • 在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对,输入一个数组,求出这个数组中逆序对的总数

思路:利用归并排序的过程,统计逆序对的数目,并进行排序,归并

面试题52:两个链表的第一个公共节点

  • 输入两个链表,找出它们第一个公共节点,链表节点定义如下

思路:利用栈,压入栈后,逐个弹出进行比较

思路2:想获取两个链表的长度差值,然后对齐长度之后,开始逐个节点进行比较

面试题53:在排序数组中查找数字

  • 统计一个数字在排序查找过程中出现的次数。

思路:在排序数组中计算一个数字出现的次数的首要结果是计算该数字起始位置和结束位置。由于数组是排序的,所以我们根据二分查找来确定这个起始位置和结束位置

  • 查找0~n-1中缺失的数字,一个长度为n-1的递增数组中,所有数组都是唯一的,并且每个数字都在范围0~n-1之内,在这个范围的n个数字中有且仅有一个数字不再该数组中,找出这个数字

思路:二分查找

面试题54:二叉搜索树的第k大节点

  • 给定一棵二叉搜索树,请找出其中第k大的节点。

思路:中序遍历后,找到倒数第k个节点。

面试题55:二叉树的深度

  • 给定一棵二叉树,求该树的深度

思路:递归求解,一个根节点的深度等于左子树的深度,和右子树的深度的最大值,所以递归求解左右子树的深度。

  • 平衡二叉树:输入一个根节点,判断是否是平衡二叉树

思路:后序遍历该二叉树,根据左右子树的高度差来判断是否是平衡二叉树。 问题:这里为什么不用递归,递归的过程中一棵子树的深度很有可能被多次重复计算,性能较低。

*面试题56:数组中数字出现的次数

  • 题目:数组中只出现一次的两个数字,一个整形数组中除了两个数字之外,其它数字都出现了两次,找出这两个只出现一次的数字。

思路:

  • 1.利用异或运算的性质,因为两个相同的数做异或运算得到0,所以我们先对数组中所有的树进行异或运算,相同的数都会消除掉,最后只剩下两个没有重复的数的异或结果
  • 2.如何区分这两个数,需要对所有的数分成两个组,并将两个只出现一次的数分在不同的组里面,这里我们根据上一步的异或结果中1出现的位置进行分组,所有该位置上为1的数为一组,为0的为一组,这两个数在该位置上必然一个为1,一个为0(异或运算)
  • 3.分组后,我们再拿第一步的异或结果和每组数进行异或就可以得到这两个数的大小

  • 题目2:数组中唯一只出现一次的数字,其它都出现了三次。

思路:根据出现三次这个特点,我们可以把二进制中每个位相加,相加的和为3的倍数则这个只出现一次的数字该位为0,否则,该位为1。由此为依据确定这个数每一位上的值。

*面试题57:和为s的数字。

  • 输入一个递增排序的数组和一个数字,在数组中查找两个数,使得它们的和正好是s。如果有多对,输出一对即可

思路:固定一个数,然后二分查找另外一个数使得两个数的和为s。O(NlogN)

思路2:两个指针,一个指针指向数组首元素,一个指向尾部元素,先将两个数相加,如果和大于s则将尾部指针向前移动,若小于s,则将首部指针向后移动,直到找到和为s的数对。

  • 和为s的连续正数序列,输入一个整数,打印出所有和为s且连续的正数序列。

思路:同上,只不过两个指针都从1开始向后滑动,当序列和大于s时,滑动首部指针,小于s时滑动尾部指针。结束的条件是首部指针(最小值)大于s的一半。

面试题58:翻转字符串

  • 输入一个英文句子,翻转句子中单词的顺序,但单词内的字符的顺序不变。如”I am a student”=>”student a am I”.

思路:首先我们定一个一个字符完全翻转的函数,翻转后=》“tneduts a ma I”。然后依然用这个翻转函数,根据空格指定翻转的范围,将每个单词翻转回来。

  • 左旋转字符串,就是将一个字符串中前面若干个字符串转移到字符串的尾部。如abcdefg和数字2,函数返回:cdefgab。

思路:同上,先将整个字符串翻转,然后将后面两个字符以及前面的字符分别翻转即可。

面试题59:队列的最大值

  • 题目1:给定一个数组和滑动窗口的大小,请找出所有滑动窗口里的最大值,例如,输入数组{2,3,4,2,6,2,5,1}以及滑动窗口大小3,则一共有6个滑动窗口,它们的最大值分别为{4,4,6,6,6,5}

思路:

  1. 遍历数组的时候,用队列保存可能的最大值,开始遍历的时候,窗口还没达到指定大小,则全部添加到队列,添加队列的过程中,将前面小于当前值的元素全部删除掉,直到遇到一个大于当前值或队列为空时,添加该元素如添加3时,队列中已经有元素2,则将2删除然后添加3。所以这个队列是一个递增的队列。
  2. 当窗口达到指定大小时,向后滑动一格,现将位于队首的元素进行过期校验,如果过期则丢弃,下一个位于队首的元素为当前最大值,如果没有过期则当前位于队首的元素就是窗口最大值。
  • 题目2:定义一个队列,并实现获取该队列最大值的函数。

思路:同上,定义一个最大值队列,添加元素push_back时,也按题目1的规则添加,当pop_front时,检验最大值队列的队首元素是否为这个要弹出的值,如果是则一起弹出,否则不用弹出。获取这个最大值的方法就是读取最大值队列的队首元素的值。

面试题60:n个骰子的总数

  • 题目:把n个骰子仍在地上,所有骰子朝上一面的点数之和为s,输入n,打印出s的所有可能的值出现的概率。

思路(先记录n~6n之间每个可能和出现的次数,然后除以6^n得到概率):

递归:同菲波拉契数列一样,f(s) = f(s-1)*(1/6)+f(s-2)*(1/6)+f(s-3)*(1/6)+f(s-4)*(1/6)+f(s-5)*(1/6)+f(s-6)*(1/6) 递归处理。

  • f(s)代表的是和为s的概率,等于前n-1个骰子和为f(s-1)出现的概率乘以当前筛子出现1的概率1/6,加上f(s-2)的概率乘以当前筛子出现2的概率…

动态规划:同样根据上面的公式,进行动态规划,利用数组纪录概率,然后初始化,根据子问题解决大问题。

面试题61:扑克牌中的顺子

  • 题目:从扑克牌中随机抽5张牌,判断是不是一个顺子。即这五张牌是不是连续的。2~10为数字本身,A为1,J(11),Q(12),K(13).大小鬼看做任意数字.

思路:我们将大小鬼看做0,然后将抽出的5张牌进行排序,排好序后,统计0的个数,然后统计相邻数字之间空缺的个数,如果空缺的总数小于或等于0的个数则是连续的,否则不连续

面试题62:约瑟夫问题。

思路1:用环形链表模拟节点删除过程

思路2:利用新的报数和旧的报数之间的关系计算最后留下来的元素下标,详见笔记本

面试题63:股票的最大利润

  • 题目:如何选择买卖股票的时间点让股票收益最大:如一只股票按时间先后顺序的价格为[9,11,8,5,7,12,16,14]。我们的目的就是选择在价格为5的时候买入,在价格为16的时候卖出。

思路:顺序扫描所有元素,求以每个元素i卖出时能获得的最大利润,所以我们需要纪录前i-1个元素的时候的最小值,然后求得以第i个元素卖出的最大利润。扫描一边数组后,我们就能得到最大利润。

PS:同面试题48,即所有当前元素的最优解与前面元素相关,然后根据所有元素的最优解获得整个数组的最优解。

发散思维

面试题64:求1+2+3+…+n

  • 不能使用乘除,for,while,if,else,switch,case等语句

思路1:利用构造函数求解,构造函数中设置静态变量N和Sum,构造一次N自增1,Sum+=N,所以构造n次,Sum就是我们要求的值。(用静态变量和构造过程替代循环过程)

思路2:利用虚函数求解,我们可以利用递归的思路,递归分为两部分,一部分向下递归,一部分则达到最小子问题直接返回,区分这两个部分则需要通过if来检测区分。这里我们将这两部分的内容分别放在父类和派生类中实现,然后根据递归过程中n的值来确定调用哪一个类的虚函数。n>0时,!!n为true,相当于下标为1的类,Array[1],n=0,!!n为false,相当于下标为0的类Array[0]。Array[]中存放的是父类的指针,只不过一个指向父类(实现最小子问题返回部分),一个指向派生类(实现递归部分)

思路3:同思路2,只不过我们用函数指针数组来代替类指针。

思路4:利用模版实现递归,最小子问题返回部分由特例化模版实现,模版匹配的过程相当于if检测语句

template<unsigned int n> struct Sum_Solution4
{
	enum{N=Sum_Solution4<n-1>::N+n};//递归部分
};

template<>struct Sum_Solution4<1>{
    enum{N=1};
};//特例化模版实现最小子问题返回部分。

*面试题65:不用加减乘除做加法

思路:位运算

  1. 将两个数进行异或运算,但异或不会进位
  2. 所以我们需要求哪些位需要进位,将两个数进行与运算,那些结果为1的位说明发生进位,将与运算的结果向左移动一位
  3. 将异或运算的结果和与运算的结果进行相加操作,相加的过程也就是重复步骤1-步骤3,直到没有进位产生,即与运算的结果为0时。

面试题66:构建乘积数组

见LeetCode238剩余数组乘积,类似于一种动态规划

  • 在A[0,1,…,n-1]数组中,构建一个数组B[0,1…n-1],其中B中的元素B[i]=A[0]xA[1]..xA[i-1]xA[i+1]..xA[n-1]。成绩中少乘A[i]。

思路:将这个乘积分为两部分:C[i] = A[0]xA[1]..xA[i-1],D[i] = A[i+1]..xA[n-1]。所以B[i]=C[i]xD[i],C[i]=C[i-1]xA[i-1],D[i] = D[i+1]xA[i+1]。构建这两个数组的时间复杂度为O(N)。所以构建B[i]的时间复杂度为O(N)。