2.4.2 查找和排序

查找相对简单：不外乎顺序查找，二分查找，哈希查找和二叉排序树查找。

不管是循环还是递归，面试官都期待应聘者能信手拈来写出完整正确的二分查找代码。

一定要对各种排序算法的特点烂熟于胸。

如果面试题要求在排序的数组（或者部分排序的 数组）中查找一个数字或者统计某个数字出现的次数，都可以尝试使用二分查找算法.

2020-05-18

T13 机器人的运动范围

心得：和12题矩阵 相像。

①总结回溯法

②13题应该不是回溯法，

• ③递归的时间复杂度计算 后面要背下来 待分析这2道题

2.4.5位运算

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

①造成死循环的解法： 循环让数n与1相与，然后右移；当n为负数时，右移因为要左边补符号位1，会造成死循环。也就是这种方法只能适用于正数。

②常规解法：循环让n与2的0 一直到32次方做与运算，这样判断每一位是不是1. int型只需要32次

③给面试官带来惊喜的解法：把1个整数减去1之后再和原来的整数做与运算，得到的结果相当于把整数的二进制表示中最右边的1变成0. 1 的个数就是这个操作的次数。（很多二进制的问题可以用这种思路解决）

• 第二章小结 描述了重点。

  数据结构

• 数组和字符串是两种最基本的数据结构

• 链表是面试题中使用频率最高的一种数据结构

• 如果面试官想加大难度，他很有可能会选用树相关的面试题

• 栈与递归调用密切相关，队列在图包括树的层次（宽度）优先遍历中需要用到，也哟啊掌握

  算法

• 查找（特别是二分）和排序（特别是快排和归并）是面试中常考算法，一定要熟练掌握

• 回溯法很适合解决迷宫及其类似问题

• 如果面试题是求一个问题的最优解，可以尝试动态规划

• 如果在动态规划分析问题时发现每一步都存在一个能得到最优解的选择，那么考虑贪心算法

• 另外还要掌握分析时间复杂度的方法

• 很多时候会使用自上而下的递归思路分析问题，却会基于自下而上的循环实现代码

T53 在排序数组中查找数字

要点：

二分查找

①最好分大于小于和等于分别处理，逻辑清晰

②下一轮要Mid+1或者小于1比较好

③面试中能递归尽量递归

高质量代码：如何设计测试用例？

①功能测试②边界测试③特殊输入测试null

T53-2 0-1中缺失的数字

• 未发现规律：因为0~n-1在数组中排好序的，0在0的位置，缺失的m正好是数组中第一个数值和下标不想打的下标，问题转化为在排序数组中找出第一个值和下标不想打的元素。注意边界。

T33 二叉搜索树的后序遍历序列

思路：递归的去处理，其实不难。

①先找到根，起始 >根 则没有左子树

②右子树也只用检查 它是否每个值都大于根，当小于的的时候直接返回false

③题目保证数组中没有相同的元素》

T36 二叉搜索树转为双向链表

任然采用递归（也写得出来）

• 将二叉搜索树的左孩子指向前驱，右孩子指向后继，采用中序递归遍历来操作.

• 把二叉树看成三部分，根，左子树，右子树

• 把左右子树转换成双链表后和根节点接起来，根节点的前驱指向左子树中序遍历的最后一个结点；

  根节点的后继指向右子树的最小结点，转换右子树前先存起来它的最小结点

注：解决的关键在于把1个大问题分解成几个小问题，然后递归地处理.

2020-05-19

T9 用两个队列实现栈

Stack类的api要记住

T16 数值的整数次方

• 书上用全局变量标识了求0的倒数这样一种错误情况
• 要考虑指数是负数和0的情况
• 求a的n次方的高效做法：分为奇数和偶数，（二分去乘）减少了很多的乘法次数，用递归来很容易实现；
  • 同时判断奇数和偶数用与运算实现，效率比求mod高很多

主要还是考察全面性，这题本身不难。

T30 包含min函数的栈

注：在面试的时候很多应聘者都止步于添加一个变量保存最小元素的思路。其实只要举个例子，多做几次入栈出栈的操作就能看出问题。用辅助栈也是一种办法，不要怕。

• Stack的操作
• LinkedList的操作
• Queue的操作，offer和add的区别，poll,peek,pop,push,remove的区别

T32 层次遍历二叉树

• 通过具体的例子（画个表格逐步分析）找出其中的规律并想到基于队列的算法，是解决这个问题的关键所在。

扩展

• 还要掌握分行打印

  • 简单，增加2个变量，当前层结点数量初始为1，下一层结点数量初始为0

• 还要掌握之字形打印

  • 分析知道用单个队列，不加其他额外操作不行（保证结点只遍历1次）

  • 分析知道只用单个栈也不行

  • 要用2个栈,1个栈用于暂存顺序输出的结点，1个栈用于逆序输出的结点，分奇偶层存入不同的stack;

    同时分奇偶层去取出结点(有点难度的)

  序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。

T31 栈的压入、弹出序列

• 关键在举例子一步步分析，压栈弹出的过程，从中找出规律
• 光看代码是写不出来的

2020-05-20

T26 树的子结构:

树的问题采用递归解法的关键在于：在左右子树各看成一个整体。

算法思想：

• 以根节点为当前结点，当前结点的值与第二颗树的根节点的值不同时，返回false
• 当前结点相同时，判断以当前结点为根的子树是否符合题意（又是一个递归去判断），是的话返回true
  • 否则，递归去判断左子树是不是
    • 左子树不是的时候，递归去判断右子树是不是，返回结果

注 : 在面试的时候，我们一定要注意边界条件检查，即检查空指针。如果没有检查并进行相应的处理，程序非常容易崩溃，这是面试时非常忌讳的事情。

在写遍历树的代码的时候一定要高度警惕，有没有可能是Null,null怎么处理.

double类型的比较要注意。

T20 顺时针打印矩阵

算法思想：

• 一圈一圈打印，左上角起点为一圈的开始，发现循环条件的规律 2 * start < rows && 2 * start < cols；

• 打印一圈：

  • 左到右，肯定是要有的
  • 上到下：前提是至少有2行
  • 右到左：前提是至少有2行2列
  • 下到上：前提是至少有3行2列

关键：画图举例法，找出规律，注意边界条件。

2020-06-04

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

要考虑大数问题。

①用字符数组模拟数字加法

②注意，判断是否到达最大的n位数，用compareto是O(n)调用n遍， 应该用个标志位

​ 第1位产生进位即表示最大

③打印的话，碰到第1个不是0的才开始打印

2020-06-07

面试题20

将数值分为3部分整数，小数，指数，3部分都是可选的，但是没有整数时，一定有小数。

解法同时也分为解法同时也分为3步，每步返回一个结果，可覆盖前面的结果
扫描前检查index是否已到边界,满足条件才往后扫描
1.扫描整数部分:(如果是正负号，指针+1)扫描无符号整数
2.扫描小数点后:扫描无符号整数 ;这步结果 与上步结果
3.扫描e|E后:扫描无符号整数

2020-06-08(第五章)

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

解法零：排序O(nlgn) 拿不到offer

解法一：基于partition函数的时间复杂度O(n)的算法(会改变原数组)

• 排序后，待求数字必然在中间的位置上

• 那么根据随机快排的划分函数，1次划分后的位置若> n/2，则在左边找， < n/2右边找,=就找到了

  算法导论中有证明，这样的时间复杂度是O(n)

解法二：根据数组特点找出的O(n)的算法 暂时跳过

面试题40：最小的k个数

解法零：最直观的，拍个序O(nlgn)，不是面试官想要的。

解法一：【可以修改原数组时】平均时间复杂度O(n)

• 同样基于partition函数, partition()返回1个index
• 当index != k-1时，循环
• index > k - 1,往左边找，index < k - 1，往右边找
• 循环退出时，输出0 - k-1的数

解法二：O(nlgk)的算法，特别适合处理海量数据;空间复杂度O(k)

• 创建大小为k的容器(treeset)
• 遍历数组，
  • 容器没满，直接插入
  • 容器已满，找到容器中的最大值，若遍历到的数比最大值要小，则替换，否则跳过
  • 遍历下一个

在容器中的操作：

①找到最大值②删除最大数③插入1个数字

最大堆：面试手写时间不够。

红黑树：JDK中的TreeSet问能不能用

解法比较

• 基于partition的要快一些，但是修改了原数组
• 第二种虽然慢一点，但是没有修改原数组，第二个好处是适合海量数据的输入（很多公司喜欢与海量输入数据相关的问题） 适合n很大，k较小的问题。

	基于partition函数的解法	基于堆或者红黑树的解法
时间复杂度	O(n)	O(nlgk)
是否需要修改输入数组	是	否
是否适用于海量数据	否	是

总结：在一个没有排序的数组中利用partition函数找出数组第k个位置的数的平均时间复杂度是O(n)

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

长度是奇数个时，就是排序后中间位置的数；偶数时，是排序后中间两个数的平均值。

排序的链表：增加2个指向中间位置的指针，奇数时指向同一个位置。

二叉搜索树：增加一个属性，子树结点数目。

AVL树：大部分编程语言没有实现。

数据结构	插入的时间复杂度	得到中位数的时间复杂度
没有排序的数组	O(1)	O(n)
排序的数组	O(n)	O(1)
排序的链表	O(n)	O(1)
二叉搜索树	平均O(lgn)，最差O(n)	平均O(lgn)，最差O(n)
AVL树	O(lgn)	O(1)
最大堆和最小堆	O(lgn)	O(1)

对于最后1个方法：

• 排序后p1,p2为中间2个位置的指针，
• p1是最大值，p2是右边部分的最小值，左边是最大堆，右边是最小堆。
• 首先读入的可以先放入最小堆
• 为了保持2个堆的大小不超过1，奇数位置的放入最大堆，从0开始。

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

题目：输入1个整型数组，里面有正有负。要求时间复杂度O(n)

解法零：枚举所有子数组并求出他们的和

• 有n(n+1)/2个子数组。最快要O(n^2^)

解法一：举例（一步一步来这个方法很有用）分析数组规律O(n)

• 记录之前的子数组的和，初始为0

• 遍历数组，当前位置i,如果preSum <= 0,则以i开始的子数组的和比以前面开始的子数组的和要大，于是抛弃前面的，从i开始，preSum = array[i]

• 若preSum > max 则更新max ,max 初始为整数最小值。

• 遍历下1个

• public int FindGreatestSumOfSubArray(public int FindGreatestSumOfSubArray(int[] array) {
          if(array == null || array.length == 0){
              return 0;
          }
          int preSum = 0;
          int max = Integer.MIN_VALUE;
          for(int i = 0;i < array.length;i++){
              if(preSum <= 0){
                  preSum = array[i];
              }else{
                  preSum += array[i];
              }
              if(preSum > max){
                  max = preSum;
              }
          }
  
          return max;
      }
  
  

面试题55：二叉树的深度

题目一：二叉树的深度

• 递归

题目二：判断是否是平衡二叉树

• 后序遍历的递归形式

面试题56：考察位运算（略过）

面试题57: 和为s的数字

题目1：递增数组中找和为s的一对数。

• 解法一：Cn^2^对，O(n^2^)

• 解法二：要快，用双指针法，左边往右扫描，右边往左扫描.时间复杂度O(n)

题目2：和为s的连续正数序列

• 也是双指针，但是从前面2个开始
• 小于给定和，则big指针增大；=输出；大于则small指针增大
• 增加的上届怎么来？(要求是连续序列)
  • 奇数时，比如为19;19/2 = 9 9+10 = 19; s / 2 + (s+1)/2 = s
  • 所以增加到(s+1)/2停止

解法特点：都是用了双指针。

面试题58: 翻转字符串

题目一：翻转单词顺序

“I am a student.” ==> “student. a am I”

解法：二次翻转字符串的解法。（java中String类似乎是没有的）

要熟悉java字符串的操作. String StringBuilder

题目二：左旋字符串

相当于第一题的2个字符串的情况。

解法：调用三次字符串逆序函数. 思路巧妙.