面试题3——数组中重复的数字    

使用LinkedHashMap，有序存放。

面试题4——二维数组中的查找

首先选取数组中右上角的数字。如果该数字等于要查找的数字，则查找过程结束；如果该数字大于要查找的数字，则剔除这个数字所在的列；如果该数字小于要查找的数字，则剔除这个数字所在的行。

面试题5——替换空格

思路三：时间复杂度O(n)，从后向前替换。P1指针指向字符串末尾，P2指针指向替换之后(未真正替换)的字符串末尾。依次复制字符串的内容，直到P1指针指到第一个空格，此时将P2位置的3个字符依次替换成"%20“，重复此操作直到字符串开始位置。

思路二：以空间换时间，思路简单，直接重新定义一个StringBuffer类。

思路一：replace替换，注意s重新赋值！

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

思路一：非递归，用栈

思路二：递归

面试题7——重建二叉树

前序遍历序列的第一个数字是根节点，在中序遍历序列中找到根节点的位置，确定左右子树节点的数量。然后在前序和中序中划分出左右子树节点，再递归构建左右子树。整体前序遍历的思想。

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

从当前节点找到根节点，中序遍历节点序列存入list中，再取出下一个节点。

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

栈2为空的时候，栈1中的数据才进栈。否则先将栈2中数据出栈。

面试题10——斐波那契数列、跳台阶、变态跳台阶、矩形覆盖

递归、非递归

面试题11——旋转数组的最小数字

分段有序数组，仍为有序数组，使用二分法O(logn)进行查找。

设置两个指针left和right，初始状态分别指向数组的第一个元素和最后一个元素。如果中间指针mid所指元素大于等于left所指元素，将left移动到mid处，如果中间指针mid所指元素小于等于right所指元素，将right移动到mid处，从而缩小查找范围。始终保证left和right仍在自己最初所在递增序列中，那么两指针相邻时，right所指元素即为最小数字。这种情况的条件array[left]>=array[right]，即旋转数组要分段有序。

注意旋转数组仍为数组本身的情况，即整体增序，此时第一个元素为最小数字，与上面情况区分出来。

面试题12——矩阵中的路径

回溯法。首先在矩阵上任选一个格子作为路径的起点。

假设矩阵中某个格子的字符为c，并且这个格子将对应于路径上的第i个字符。如果路径上的第i个字符不是c，那么这个格子不可能处在路径上的第i个位置。如果路径上的第i个字符正好是c，那么到相邻的格子寻找路径上的第i+1个字符。

除矩阵边界上的格子之外，其他格子都有4个相邻的格子。重复这个过程，直到路径上的所有字符都在矩阵中找到相应的位置。

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

回溯法。机器人从(0,0)开始移动。

首先准备进入(i,j)格子时，通过检查坐标的数位和来判断是否能够进入。

如果机器人能够进入(i,j)，则再判断是否进入4个相邻格子(i-1,j)、(i+1,j)、(i,j-1)、(i,j+1)。

面试题14——减绳子

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

把一个整数减去1，再和原整数做与运算&，会把整数最右边的1变成0，即 n&=(n-1)。那么一个整数的二进制表示中有多少个1，就可以进行多少次这样的操作。

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

指数可为0，1，负数，正数。若为负数，做特殊处理，最后结果取倒数。

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

面试题18——删除链表中重复的节点

面试题19——正则表达式匹配

面试题20——表达数值的字符串【正则表达式】

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

统计数组中奇数个数k，那么偶数开始的位置坐标即为k，奇数开始的位置坐标为0。新建一个copy数组，遍历该数组，判断奇偶存入原始数组中。

面试题22——链表中倒数第K个节点

快慢指针。快指针比慢指针先走k-1步，再一起走，快指针走到结尾时，此时慢指针所指节点即为倒数第K个节点。

注意边界条件：输入值合法。快指针先走k-1步合法。快慢指针一起走合法（快指针的下个节点是否为null）。

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

1.先判断是否有环。快慢指针，快指针每次走2步，慢指针每次走1步，若相遇则有环。

2.根据相遇点确定环长度。

3.快慢指针重新遍历，快指针先走环长步数，再一起走。相遇即为环的入口节点。

面试题24——反转链表

在原链表上翻转（原地翻转），直接遍历交换指针。设置两个指针pre、next，pre指向新链表的头节点，next指向旧链表头头指针的下一个节点，以便去遍历后面的节点。

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

新建头节点，最后返回头节点的下一个节点。

面试题26——树的子结构

先在树A中找到和树B根节点值一样的节点R，再判断A中以R为根节点的子树是否包含和树B一样的结构。

面试题27——二叉树的镜像

前序遍历的应用。

面试题28——对称的二叉树

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

转圈存储，从左到右，上到下，右到左，下到上。注意数组下标，易写错。

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

建立最小值辅助栈minStack。在把元素压入数据栈dataStack中的同时，每次都把最小元素压入辅助栈，那么就能保证辅助栈的栈顶一直都是最小元素。当最小元素从数据栈内被弹出之后，同时弹出辅助栈的栈顶元素，此时辅助栈的新栈顶元素就是下一个最小值。

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

建立辅助栈，把输入的第一个序列中的数字依次压入该辅助栈，并按照第二个序列的顺序依次从该栈中弹出数字。如果下一个弹出的数字刚好是栈顶数字，那么直接弹出；如果下一个弹出的数字不在栈顶，则把压栈序列中还没有入栈的数字压入辅助栈，直到把下一个需要弹出的数字压入栈顶为止；如果所有数字都压入栈后仍然没有找到下一个弹出的数字，那么该序列不可能是一个弹出序列。

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

使用队列。非递归层次遍历。

把二叉树打印多行

之字形打印二叉树

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

在后序遍历序列中，最后一个数字是树的根节点值。数组中前面的数字可分为两部分：第一部分是左子树节点的值，它们都比根节点的值小；第二部分是右子树节点的值，它们都比根节点的值大。

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

前序遍历访问到某一个节点，将该节点添加到路径上，并累加该节点的值。如果该节点为叶子节点，并且

中节点值的和刚好等于输入的整数，则当前路径符合要求，打印出来。如果当前节点不是叶子节点，则继续访问它的子节点。当前节点访问结束后，递归函数将自动回退到它的父节点。因此在函数退出之前要在路径上删除当前节点并减去当前节点的值，以确保返回父节点时路径刚好是从根节点到父节点。

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

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

把左右子树都转化成排序双向链表之后再与根结点连接起来，整棵二叉搜索树也就转化成了排序双向链表。

面试题37——序列化二叉树

面试题38——字符串的全排列

回溯法

第一步：求出所有可能出现在第一个位置的字符，即把第一个字符和后面的字符交换。

第二步：固定第一个字符，求后面所有字符的全排列。

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

HashMap

面试题40——最小的k个数

优先队列实现小顶堆 PriorityQueue<Integer> minHeap=new PriorityQueue<>();

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

注意：数据流中数据的数目是变化的。将数据容器分割成两部分。保证数据容器左边的数据都小于右边的数据，即使左右两边内部无序，也可以根据左边最大数及右边最小数得到中位数。最大堆实现左边的数据容器，最小堆实现右边的数据容器。向堆中插入数据时间为O(logn)，查找时间为O(l)。

滑动窗口的最大值

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

total记录累计值，max记录和最大。对于一个数A，若是A的左边累计数大于0，那么加上A能使得值更大。如果左边累计值小于0，则认为有害于总和，那么total更新为当前值。此时若total大于max，max=total。时间复杂度O(n)。

面试题43——1-n整数中1出现的次数

将数字转化为字符串，再将字符串转化为字符判断‘1’。

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

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

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

面试题47——礼物的最大值

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

思路：使用动态规划，记录当前字符之前的最长非重 复子字符串长度f(i-1)，其中i为当前字符的位置。每次遍历当前字符时，分两种情况：1）若当前字符第一次出现，则最长非重复子字符串长度f(i) = f(i-1)+1。 2）若当前字符不是第一次出现，则首先计算当前字符与它上次出现位置之间的距离d。若d大于f(i-1)，即说明前一个非重复子字符串中没有包含当前字符，则可以添加当前字符到前一个非重复子字符串中，所以，f(i) = f(i-1)+1。若d小于或等于f(i-1)，即说明前一个非重复子字符串中已经包含当前字符，则不可以添加当前字符，所以，f(i) = d。

关键点：动态规划，两个重复字符的距离

面试题49——丑数

只用比较3个数：用于乘2的最小的数、用于乘3的最小的数，用于乘5的最小的。

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

HashMap

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

归并排序的改进——合并时候指针均从最后面遍历，而原始归并从开始遍历。

先把数组分割成子数组，先统计出子数组内部的逆序对的数目，然后再统计出两个相邻子数组之间的逆序对的数目。在统计逆序对的过程中，还需要对数组进行排序 ，以避免重复统计。

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

首先判断两个链表是否相交。通过遍历链表是否相同的尾节点，同时记录链表长度。

然后从头节点重新遍历，找公共节点，长链表先走长度差距，长短链表指针再一起走，相遇即为首个公共节点。

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

数字在排序数组中出现的次数。

二分查找数字第一次出现的位置、最后一次出现的位置。位置之差+1即为该数字出现的次数。

二分查找算法总是先拿数组中间的数字和k作比较。

如果中间的数字比k大，那么k只有可能出现在数组的前半段，下一轮只在数组的前半段查找。如果中间的数字比k小，那么k只有可能出现在数组的后半段，下一轮只在数组的后半段查找。如果中间的数字与k相等，先判断这个数字是不是第一个k。如果中间数字的前面一个数字不是k，那么此时中间的数字刚好就是第一个k；如果中间数字的前面也是k，那么第一个k肯定在数组的前半段，下一轮仍然需要在数组的前半段查找。同样思路，找出最后一次出现的位置。时间复杂度O(logn)。

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

中序遍历

面试题55——二叉树的深度、平衡二叉树

递归

平衡二叉树-每个节点左右子树高度差的绝对值不超过1。

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

LinkedHashMap有序

面试题57——和为s的数字

和为s的连续整数序列

面试题58——翻转字符串

翻转单词顺序(单词内字符的顺序不变)  I am a student.——student. a am I

两次翻转字符串。第一步翻转句子中所有的字符；第二步再翻转每个单词中字符的顺序。

左旋转字符串 abcXYZdef——XYZdefabc

三次翻转字符串。分别翻转前后两部分(cba|fedZYX)，再翻转整个字符串(XYZdefabc)。

面试题59——队列的最大值

面试题60——n个篩子的点数

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

面试题62——圆圈中最后剩下的数字

面试题63——股票的最大利润【思路同：42连续子数组的最大和】

（2次买卖，动态规划，待解决）https://www.nowcoder.com/practice/3e8c66829a7949d887334edaa5952c28?tpId=49&&tqId=29317&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking

思路：定义函数max(i)为当卖出价为数组中第i个数字时可能获得的最大利润。当卖出价固定时，买入价越低获得的利润越大。

扫描到数组中的第i个数字时，只要知道之前的i-1个数字中的最小值，就能算出在当前价位卖出时可能得到的最大利润。只需扫描数组一次，时间复杂度为O(n)，比蛮力法( O(n^2) )的效率高。

面试题64——求1+2+。。。+n

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

面试题66——构建乘积数组

将数组画成矩阵，拆分成上下三角，分别计算上下三角连乘。

面试题67——把字符串转换成整数

非法输入，除了数字之外的字符判定。if(c<'0'||c>'9')

字符从高位逐次拼接成整型数字。num=num*10+(c-'0')

面试题68——树中两个节点的最低公共祖先

二叉搜索树

二叉搜索树中左子树的节点都比父节点小，位于右子树的节点都比父节点大。要找最低的公共祖先节点，从根节点开始进行比较。若当前节点的值比两个节点的值都大，那么最低的祖先节点一定在当前节点的左子树中，则遍历当前节点的左子节点；反之，若当前节点的值比两个节点的值都小，那么最低的祖先节点一定在当前节点的右子树中，则遍历当前节点的右子节点；这样，直到找到一个节点，位于两个节点值的中间，则找到了最低的公共祖先节点。即root.val>p.val&&root.val>q.val，在root.left继续搜索；root.val<p.val&&root.va<q.val，在root.right继续搜索；其他情况，返回root。

普通二叉树

从根节点开始遍历，如果node1和node2中的任一个和root匹配，那么root就是最低公共祖先。

如果都不匹配，则分别递归左、右子树。

如果有一个节点出现在左子树，并且另一个节点出现在右子树，则root就是最低公共祖先.  如果两个节点都出现在左子树，则说明最低公共祖先在左子树中，否则在右子树。

链表排序 

时间O(nlogn)  空间复杂度O(1)