目录
第2章 面试需要的基础知识
2.3 数据结构
2.3.1 数组：二维数组中的查找
2.3.2 字符串：替换空格
2.3.3 链表：从尾到头打印链表
2.3.4 树：重建二叉树
2.3.5 栈和队列：用两个栈实现队列
2.4 算法和数据结构
2.4.1 查找和排序
2.4.2 递归和循环
2.4.3 位运算
第3章 高质量的代码
3.1 代码的完整性
3.1.1 数值的整数次方
3.1.2 调整数组顺序使奇数位于偶数前面
3.2 代码的鲁棒性
3.2.1 链表中倒数第k个节点
3.2.2 反转链表
3.2.3 合并两个排序的链表
3.2.4 树的子结构
第4章 解决面试题的思路
4.1 面试官谈面试思路
4.1.1 二叉树的镜像
4.2 画图让抽象问题具体化
4.2.1 顺时针打印矩阵
注：牛客网有对应的算法题目
2.3 数据结构
2.3.1 数组：二维数组中的查找
这一题一看到是有序的数组立刻想到二分法查找，后来才发现直接套用一维的二分法便会在while循环中跳不出来，这里直接就是使用简单的数字特性即可其时间复杂度为O(n)。
public boolean Find(int target, int [][] array) {
int row = 0,col = array[0].length;
return find(array,0,col,target);
}
private boolean find(int[][] array, int row, int col,int target) {
if (row >= array.length || col < 0){
return false;
}
if (array[row][col] == target){
return true;
}else if (array[row][col] > target){
return find(array,row,col-1,target);
}else {
return find(array,row+1,col,target);
}
} 非递归写法如下：
public boolean Find(int target, int [][] array) {
int row = 0,col = array[0].length-1;
while (row < array.length && col > 0){
if (array[row][col] == target){
return true;
}else if (array[row][col] > target){
col = col-1;
}else {
row = row+1;
}
}
return false;
} 2.3.2 字符串：替换空格
public String replaceSpace(StringBuffer str) {
StringBuffer stringBuffer = new StringBuffer();
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i)==' '){
stringBuffer.append("%20");
}else {
stringBuffer.append(str.charAt(i));
}
}
return stringBuffer.toString();
} 上面是自己写的代码，可以看到额外开辟了一个空间，那么能否不使用额外的空间那，如果直接使用Java的replace方法是可以直接在原字符串上进行修改的。
return str.toString().replaceAll(" " , "%20"); 在这里可以认为自己写一个Java的replaceAll方法，且不使用额外的存储空间，算法的时间复杂度还有足够好。如果不适用额外的存储空间那么使用从前向后的顺序替换字符串如下图所示：
这样前面没替换一次后面的字符顺序就要改变一次，需要两层循环一层遍历空格一层修改遇到空格后后面的字符，那么时间复杂度为O(n^2)那么是否可以使用降低时间复杂度。这里效率的底下主要是因为前面的修改影响了后面，如果修改不会影响维修改的字符那么时间复杂度就会立刻下降，这里使用从后向前的遍历方式：
先计算出把空格修改后的新字符串的长度，再从后向前进行遍历修改即可。
public class Solution {
public String replaceSpace(StringBuffer str) {
if (str == null){
return null;
}
// 计算空格数
int spaceNum =0;
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == ' '){
spaceNum++;
}
}
// 替换前字符串的下标
int indexOld = str.length() - 1;
// 替换后字符串的长度
int newLength = str.length() + spaceNum*2;
// 替换后新的字符串的下标
int indexNew = newLength - 1;
// 设定新的字符串长度
str.setLength(newLength);
// 进行遍历修改，indexOld < newLength这个条件可以不用要的，这里只是为了防止意外情况
for (;indexOld >= 0 && indexOld < newLength; indexOld--){
if (str.charAt(indexOld) == ' '){
// 遇到空格便进行替换
str.setCharAt(indexNew--,'0');
str.setCharAt(indexNew--,'2');
str.setCharAt(indexNew--,'%');
}else {
// 没有遇到空格就直接复制
str.setCharAt(indexNew--,str.charAt(indexOld));
}
}
return str.toString();
}
} 注：合并两个数组(包括字符串)时，如果从前往后复制每个数字(或字符)需要重复移动数字(或字符)多次，那么我们可以考虑从后往前复制，这样就能减少移动的次数，从而提高效率
2.3.3 链表：从尾到头打印链表
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> arrayList = new ArrayList<>();
while (listNode != null){
arrayList.add(listNode.val);
listNode = listNode.next;
}
for (int i = 0; i < arrayList.size()/2; i++) {
int temp = arrayList.get(i);
arrayList.set(i,arrayList.get(arrayList.size()-i-1));
arrayList.set(arrayList.size()-i-1,temp);
}
return arrayList;
} 对于链表似乎没有办法从后先前遍历，因此才有了开辟一个集合从前向后遍历并保存数据，再反转集合的方法，但是如果使用递归的话完全可以不用反转集合，如果不清楚可以思考回溯法是怎么实现的。
public class Solution {
private ArrayList<Integer> arrayList=new ArrayList<Integer>();
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
if(listNode!=null){
// 采用递归一直遍历到链表的尾部
printListFromTailToHead(listNode.next);
// 遍历的尾部后，添加元素
arrayList.add(listNode.val);
}
return arrayList;
}
} 2.3.4 树：重建二叉树
这道题目首先要明白如何根据遍历得到的结果构建出二叉树：对一棵二叉树进行遍历，我们可以采取3中顺序进行遍历，分别是前序遍历、中序遍历和后序遍历，这三种方式是以访问父节点的顺序来进行命名的。假设父节点是N，左节点是L，右节点是R，那么对应的访问遍历顺序如下：
所以，对于以下这棵树，三种遍历方式的结果是
已知二叉树的前序遍历和中序遍历，如何得到它的后序遍历
其实，只要知道其中任意两种遍历的顺序，我们就可以推断出剩下的一种遍历方式的顺序，这里我们只是以：知道前序遍历和中序遍历，推断后序遍历作为例子，其他组合方式原理是一样的。要完成这个任务，我们首先要利用以下几个特性：
我们以一个例子做一下这个过程，假设：前序遍历的顺序是: CABGHEDF 中序遍历的顺序是: GHBACDEF
第一步，我们根据特性A，可以得知根节点是C，然后，根据特性C，我们知道左子树是：GHBA，右子树是：DEF。
C
/ \
GHBA DEF
第二步，取出左子树，左子树的前序遍历是：ABGH，中序遍历是：GHBA，根据特性A和C，得出左子树的父节点是A，并且A没有右子树。
C
/ \
A DEF
/
GBH
第三步，使用同样的方法，前序是BGH，中序是GHB，得出父节点是B，GH是左子树,没有右子树。
C
/ \
A DEF
/
B
/
GH
第四步,前序是GH, 中序是GH, 所以 G是父节点, H是右子树, 没有左子树.
C
/ \
A DEF
/
B
/
G
\
H
第四步，回到右子树，它的前序是EDF，中序是DEF，依然根据特性A和C，得出父节点是E，左右节点是D和F。
C
/ \
A E
/ / \
B D F
/
G
\
H
至此变得到了完整的二叉树，那么其后序遍历就是 : HGBADFEC
根据上面的描述在本题中可画图如下，那么就是递归不断的进行分割左右子树的过程。
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
TreeNode root=reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
return root;
}
//前序遍历{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
private TreeNode reConstructBinaryTree(int [] pre,int startPre,int endPre,int [] in,int startIn,int endIn) {
// 递归的终止条件，当前序或中序数组有一方结束，递归便终止
if(startPre>endPre||startIn>endIn){
return null;
}
TreeNode root=new TreeNode(pre[startPre]);
for(int i=startIn;i<=endIn;i++) {
if (in[i] == pre[startPre]) {
// 左子树递归，联系两个数组确定起始和终止位置
root.left = reConstructBinaryTree(pre, startPre + 1, startPre + i - startIn, in, startIn, i - 1);
// 右子树递归，联系两个数组确定起始和终止位置
root.right = reConstructBinaryTree(pre, i - startIn + startPre + 1, endPre, in, i + 1, endIn);
break;
}
}
return root;
}
} 2.3.5 栈和队列：用两个栈实现队列
本题与LeetCode 232 题目基本一致，这里给出的代码是左程云的程序员面试指南一书中的答案，但基本思路是一致的都是一个先用一个栈存储，出队时再用另一栈进行转换。
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
stack1.push(node);
}
public int pop() {
if(stack1.empty()&&stack2.empty()){
throw new RuntimeException("Queue is empty!");
}
if(stack2.empty()){
while(!stack1.empty()){
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
} 2.4 算法和数据操作
2.4.1 查找和排序
这个小节虽是查找和排序但主要还是查找。查找有：顺序查找、二分法、哈希表、二叉树排序查找。在一个有序或者部分有序的数组中查找一个数字或者是统计数字出现的频率都可以采用二分法查找的。
（1）旋转数组的最小数字。
旋转数组这是一个部分有序的数组，可以考虑二分法的思路：利用两个指针分别指向数组的第一个和最后一个元素，那么按照旋转规则，第一个元素应该是大于或等于后一个元素的(这其实不完全对，还有特例，后面再加以讨论)。接着我们可以找到数组中间的元素。如果该中间元素位于前面的递增子数组，那么它应该大于或者等于第一个指针指向的元素。此时数组中最小的元素应该位于该中间元素的后面。我们可以把第一个指针指向该中间元素，这样可以缩小寻找的范围。移动之后的第一个指针仍然位于前面的递增子数组之中。
同样，如果中间元素位于后面的递增子数组，那么它应该小于或者等于第二个指针指向的元素。此时该数组中最小的元素应该位于该中间元素的前面。我们可以把第二个指针指向该中间元素，这样也可以缩小寻找的范围。移动之后的第二个指针仍然位于后面的递增子数组之中。不管是移动第一个指针还是第二个指针，査找范围都会缩小到原来的半。接下来我们再用更新之后的两个指针，重复做新一轮的査找。按照上述的思路，第一个指针总是指向前面递增数组的元素，而第二个指针总是指向后面递增数组的元素。最终第一个指针将指向前面子数组的最后一个元素，而第二个指针会指向后面子数组的第一个元素。也就是它们最终会指向两个相邻的元素，而第二个指针指向的刚好是最小的元素。这就是循环结束的条件上述过程如下图所示：
特例：对数字{0, 1, 1, 1, 1}的两个旋转{1, 0, 1, 1, 1}、{1, 1, 1, 0, 1}如下图所示：
在这两个数组中，第一个数字、最后一个数字和中间数字都是1我们无法确定中间的数字1属于第一个递增子数组还是属于第二个递增子数组。因此前面的子数组中。因此，当两个指针指向的数字及它们中间的数字三者相同的时候，我们无法判断中间的数字是位于前面的子数组中还是后面的子数组中，也就无法移动两个指针来缩小查找的范围。也即当数组中有重复数字时采用二分查找的思路已经不合适了，不得不采用顺序查找的方法。
public class Solution {
public int minNumberInRotateArray(int [] array) {
if (array == null){
return 0;
}
int left = 0,right = array.length - 1;
int mid = 0;
//
while (array[left] >= array[right]){
// 分界点
if (right - left == 1){
mid = right;
break;
}
mid = left + (right-left)/2;
// 无法确定中间元素是属于前面还是后面的递增子数组时只能顺序查找
if (array[left] == array[right] && array[mid] == array[left]){
return minOrder(array,left,right);
}
// 中间元素位于前面的递增子数组，此时最小元素位于中间元素的后面
if (array[mid] >= array[left]){
left = mid;
}else {
// 中间元素位于后面的递增子数组，此时最小元素位于中间元素的前面
right = mid;
}
}
return array[mid];
}
// 顺序查找
private int minOrder(int[] array, int left, int right) {
int res = array[left];
for (int i = left+1; i < right; i++) {
if (array[i] < res){
res = array[i];
}
}
return res;
}
} 2.4.2 递归和循环
这里分别对应着牛客网题目：斐波那契数列、跳台阶、变态台阶，其本质都是动态规划，在博客中https://www.cnblogs.com/youngao/p/11453374.html已经有记录过了，在这里记录下变态跳台阶，对于4阶楼梯其递归图如下：
那么递推公式为：
f(n) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2) + f(n-1) = f(n-1) + f(n-1)
f(n-1) = f(0) + f(1)+f(2)+f(3) + ... + f((n-1)-1) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2)
那么可以推出：
f(n) = 2*f(n-1)。其动态规划写法为：
public int JumpFloorII(int target) {
if (target == 1){
return 1;
}
int[] arr = new int[target+1];
arr[1] = 1;
for (int i = 2; i <= target ; i++) {
arr[i] = 2*arr[i-1];
}
return arr[target];
} 对于举行覆盖这个题目，和上面类似，但问题的关键是如何理解题目，此时的f(2)、f(1)不再是单纯的数字了而是代表一种状态或者一种情况。
f(1)代表1*2、f(2)代表着2*2的情况，有2种情况。对于f(3)可以先竖着然后是f(2)也可以先横着然后是f(1)，因此所有的情况为f(1)+f(2)，对于后面的情况也是如此，对于代码部分其实是和前面的斐波那契数列是一样的因此不再记录代码。
2.4.3 位运算
本题一开始自己写的代码如下，出现的问题也比较多。
public int NumberOf1(int n) {
int count = 0;
while (n != 0){
if (n%2 == 1){
count++;
}
n = n/2;
}
return count;
} 首先n=n/2这一步完全可以用为运算代替的，其次，n%2这一步也可以考虑位运算的，还有整个算法只适合n大于0的情况，当n小于n时由于补码的原因是不能直接这样算法的。
public int NumberOf1(int n) {
int count = 0;
// 当为负数时使用补码符号位为1,移位的时候符号位也要移位的最后再补1，那么最后的结果就是0xffffffff，陷入了死循环中
if (n < 0){
n = n &0x7fffffff;
count++;
}
while (n != 0){
// 这里不再取余，直接与1与获取最低位是否为1
count = count + (n&1);
n = n>>1;
}
return count;
} 3.1 代码的完整性
3.1.1 数值的整数次方
public double Power(double base, int exponent) {
double res = 1.0;
if (exponent == 0){
return 1;
}
if (exponent > 0){
for (int i = 1; i <= exponent; i++) {
res = res * base;
}
}else {
for (int i = 1; i <= -exponent; i++) {
res = res * base;
}
return 1.0/res;
}
return res;
} 上面的代码虽然可以解决问题，但是效率不高，完全可以提升的。提升代码如下：
3.1.2 调整数组顺序使奇数位于偶数前面
题目中有提示：相对位置不变--->保持稳定性；奇数位于前面，偶数位于后面 --->存在判断，挪动元素位置。那么根据这两点便可以借用插入排序的思想，两两比较，一下的代码其是就是插入排序的代码，只不过是把判断条件给修改了一下。
public class Solution {
public void reOrderArray(int [] array) {
//判断需不需要排序
if (array == null || array.length < 2) {
return;
}
//外层控制起始位置，内层从起始位置向前遍历
for (int i = 0; i < array.length-1; i++) {
// 为了效率的提高，对2取余的操作变成了与0x01相与，为0便是偶数为1便是奇数
for (int j = i ; j >= 0 && ((array[j] & 0x01)==0) && ((array[j + 1] & 0x01) ==1); j--) {
swap(array, j, j + 1);
}
}
}
private void swap(int[] arr,int m,int n){
int temp = arr[m];
arr[m] = arr[n];
arr[n] = temp;
}
} 3.2 代码的鲁棒性
鲁棒性：程序能够判断输入是否合乎规范要求，并对不合要求的输入予以处理。
3.2.1 链表中倒数第k个节点
这道题目中为了说清楚举例如下：1、2、3、4、5那么倒数第2个节点便是4。这道题目和LeetCode 19（算法面试3--链表 4）删除链表倒数第N个节点是类似的使用双指针遍历即可，当不同之处这里要处理k大于链表节点长度的情况，因此还是稍有不同，注意其判断条件。
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
ListNode p1 = head;
ListNode p2 = head;
// 当链表为空或者k为0时返回空
if (head == null || k == 0){
return null;
}
while (--k != 0 ){
p2 = p2.next;
if (p2 == null){
return null;
}
}
// 终止条件的修改是关键
while (p2.next != null){
p1 = p1.next;
p2 = p2.next;
}
return p1;
}
} 3.2.2 反转链表
这道题目和LeetCode 206（算法面试3--链表 1）是一样的。
3.2.3 合并两个排序的链表
这道题目和LeetCode 21是一样的。
3.2.4 树的子结构
例子如下，查找过程可以分为两步，第一步找到相同的根节点，第二部判断根节点的子节点是否相同。在第一步找到相同的根节点可以认为是树的遍历操作可以用递归来实现，对于第二步的判断也可以用递归来实现。
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
boolean res = false;
//当Tree1和Tree2都不为零的时候，才进行比较。否则直接返回false
if (root1 != null && root2 != null){
//如果找到了对应Tree2的根节点的点
if (root1.val == root2.val){
//以这个根节点为为起点判断是否包含Tree2
res = doesTree1HaveTree2(root1,root2);
}
//如果找不到，那么就再去root的左儿子当作起点，去判断时候包含Tree2
if (!res){
res = HasSubtree(root1.left,root2);
}
//如果找不到，那么就再去root的右儿子当作起点，去判断时候包含Tree2
if (!res){
res = HasSubtree(root1.right,root2);
}
}
return res;
}
// 判断以根节点为起点的子树是否包含Tree2
private boolean doesTree1HaveTree2(TreeNode node1, TreeNode node2) {
//如果Tree2已经遍历完了都能对应的上，返回true
if (node2 == null){
return true;
}
//如果Tree2还没有遍历完，Tree1却遍历完了。返回false
if (node1 == null){
return false;
}
//如果其中有一个点没有对应上，返回false
if (node1.val != node2.val){
return false;
}
//如果根节点对应的上，那么就分别去子节点里面匹配
return doesTree1HaveTree2(node1.left,node2.left) && doesTree1HaveTree2(node1.right,node2.right);
}
} 4.1 面试官谈面试思路
总结：在写代码前要想清楚思路和设计，并分析好边界条件。对于问题的分析一般有：画图、举例、分解三种方法。
4.2 画图让抽象问题具体化
4.2.1 二叉树的镜像
本题与LeetCode 226题目类似，在博客算法面试5--1 二叉树中有代码讲解。
4.2.2 顺时针打印矩阵
4.2.3 包含min函数的栈
本题的虽然有入栈，出栈，获取最小值，但关键还是如何入栈，因为时间复杂度要求O(1)，出栈的时候还要按照压入的顺序出栈因此需要用一个辅助栈来保存每添加一个新的数字后得到的最小值，这样出栈操作正常进行，当需要获取最小值时直接从最小栈获取即可。
// 数据栈用来保存每次存入的数据
private Stack<Integer> data = new Stack<>();
// 最小栈，用来保存每次存入新数据后的当前最小值
private Stack<Integer> min = new Stack<>();
public void push(int node) {
// 存放数据
data.add(node);
if (min.size() == 0 || node < min.peek()){
// 当最小栈为空或者栈顶元素大时，把新的最小值存放入最小栈中
min.add(node);
}else {
min.add(min.peek());
}
} 4.2.4 栈的压入、弹出序列
4.2.5 从上往下打印二叉树
本题与LeetCode 102一样的，
4.2.6 二叉搜索树的后序遍历序列
4.2.7 二叉树中和为某一值的路径
4.3 分解让复杂问题简单化
4.3.1 复杂链表的复制
4.3.2 二叉搜索树与双向链表
4.3.3 字符串的排列
0
转载于:https://www.cnblogs.com/youngao/p/11588782.html