1.1 确定字符互异
请实现一个算法，确定一个字符串的所有字符是否全都不同。这里我们要求不允许使用额外的存储结构。
思路:基于快速排序的partition，可以边排序边找重复
1.2 原串翻转
请实现一个算法，在不使用额外数据结构和储存空间的情况下，翻转一个给定的字符串(可以使用单个过程变量)。
1.3 确定两串乱序同构
给定两个字符串，请编写程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。这里规定大小写为不同字符，且考虑字符串重点空格。
思路:使用一个计数的数组来做
1.4 空格替换
请编写一个方法，将字符串中的空格全部替换为“%20”。假定该字符串有足够的空间存放新增的字符，并且知道字符串的真实长度(小于等于1000)，同时保证字符串由大小写的英文字母组成。
1.5 基本字符串压缩
利用字符重复出现的次数，编写一个方法，实现基本的字符串压缩功能。比如，字符串“aabcccccaaa”经压缩会变成“a2b1c5a3”。若压缩后的字符串没有变短，则返回原先的字符串。
思路:定义一个字符串数组用来放存在的字符和相应字符的数量
1.6 像素翻转
有一副由NxN矩阵表示的图像，这里每个像素用一个int表示，请编写一个算法，在不占用额外内存空间的情况下(即不使用缓存矩阵)，将图像顺时针旋转90度。
思路:
第一步：先将矩阵以次对角线互换 （如果是逆时针则为主对角线）
第二步：交换第i行到第n-i-1行
1.7 压缩空格
要求时间复杂度O(N)空间复杂度O(1)
思路: 定义两个游标，如果当前不是空格就把该处的值赋值给前面
1.8 清除行列
请编写一个算法，若MxN矩阵中某个元素为0，则将其所在的行与列清零。
思路:首先找到需要变为0的行和列号，
记录在矩阵row和col中，若需要变为0则记为1，反之记为0，最后清零
1.9 翻转子串
假定我们都知道非常高效的算法来检查一个单词是否为其他字符串的子串。请将这个算法编写成一个函数，给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成，要求只能调用一次检查子串的函数。
思路:s1拼接自己一次当作s3，s2如果是s1旋转来的就必定是s3的子串
2.0 求链表中倒数第k个数
输入一个链表，输出该链表中倒数第k个结点。
思路:第一次遍历链表，第一次求链表的长度length,第二次求第length-k+1个结点
2.1 访问单个节点的删除
实现一个算法，删除单向链表中间的某个结点，假定你只能访问该结点。
2.2 链表分割
编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前
思路一:小数链表和大数链表，最后完成后将两链表连接，注意头结点也有值
思路二:将链表的节点存放在数组中，进行快速排序的调整
2.3 链式A加B
有两个用链表表示的整数，每个结点包含一个数位。这些数位是反向存放的，也就是个位排在链表的首部。编写函数对这两个整数求和，并用链表形式返回结果
思路：这里对于不同长度的数字，我们通过将较短的数字补0来保证每一位都能相加
2.4 回文链表
思路一：申请一个栈，将节点全部压入，遍历节点和弹出的节点对比
思路二：申请一个栈，用快指针和慢指针同时遍历，慢指针遍历时，将节点压入栈中，当快指针走完，慢指针在中间，整个调整过程实际上是把左边的节点折过来和右边的比较
思路三：找到中间节点，右边逆序调整，然后两头开始判断
2.4.2 环形链表插值
有一个整数val，如何在节点值有序的环形链表中插入一个节点值为val的节点，并且保证这个环形单链表依然有序。给定链表的信息，及元素的值A及对应的nxt指向的元素编号同时给定val，请构造出这个环形链表，并插入该值
思路：如果val大于头节点的值则更新头节点，如果是中间位置，则需要防止断链
2.4.3 链表的k逆序
有一个单链表，请设计一个算法，使得每K个节点之间逆序，如果最后不够K个节点一组，则不调整最后几个节点。例如链表1->2->3->4->5->6->7->8->null，K=3这个例子。调整后为，3->2->1->6->5->4->7->8->null。因为K==3，所以每三个节点之间逆序，但其中的7，8不调整，因为只有两个节点不够一组。
思路一:可以使用栈存储k个节点，然后依次弹出
思路二:不使用栈，但是需要前一次调整后的最后一个节点指针下一组需要调整的最后一个节点
2.4.4 复杂链表的复制
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点）。
思路：每个节点分别拷贝一个在其后面，然后让原来的和拷贝random指向相对应的节点,最后分离
2.4.5 链表判环
如何判断一个单链表是否有环？有环的话返回进入环的第一个节点的值，无环的话返回-1。如果链表的长度为N，请做到时间复杂度O(N)，额外空间复杂度O(1)。
思路：快指针一次跳两个，如果为NULL，则没有环
有环时，当快指针和慢指针相遇时，让快指针等于头节点，
一次遍历一个,慢指针一次遍历一个，在进入环的第一个节点再次相遇
2.4.6 无环单链表判相交
现在有两个无环单链表，若两个链表的长度分别为m和n，请设计一个时间复杂度为O(n + m)，额外空间复杂度为O(1)的算法，判断这两个链表是否相交
思路 遍历两个链表得到长度，然后长链表先走差值，一样长时，再同步走，会同时到达相遇节点。
扩展: 有环单链表相交判断,单链表相交判断(注意结构,再结合链表判环和此题方法解即可)
2.5 集合栈
请实现一种数据结构SetOfStacks，由多个栈组成，其中每个栈的大小为size，当前一个栈填满时，新建一个栈。该数据结构应支持与普通栈相同的push和pop操作。
2.6 用两个栈实现队列
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
思路：进时，栈2是否为空，不为空，则栈2元素倒回到栈1，出时，将栈1元素全部弹到栈2中，直到栈1为空。
2.7 双栈排序
请编写一个程序，按升序对栈进行排序（即最大元素位于栈顶），要求最多只能使用一个额外的栈存放临时数据，但不得将元素复制到别的数据结构中。
思路：把numbers中的一个个元素拿出比较，放入临时栈help中，如果新的元素比help中的小，
便把help中大的取出放入numbers中，压入小的进help,再把大的从numbers取出压入help。
最后把help全部元素放入numbers,返回numbers。
2.8 猫狗收容所
有家动物收容所只收留猫和狗，但有特殊的收养规则，收养人有两种收养方式，第一种为直接收养所有动物中最早进入收容所的，第二种为选择收养的动物类型（猫或狗），并收养该种动物中最早进入收容所的。
思路：维护两个队列，一个队列存放放入的狗，一个队列存放放入的猫,每次把动物放入队列的时候，同时将一个递增的序号放入队列，这个序号就是一个时间序列
2.9 位运算_交换
请编写一个算法，不用任何额外变量交换两个整数的值
思路 结合率和交换率
3.0 位运算_比较
对于两个32位整数a和b，请设计一个算法返回a和b中较大的。但是不能用任何比较判断。若两数相同，返回任意一个。
给定两个整数a和b，请返回较大的数
思路 我们可以得到a-b的符号，根据该符号决定返回a或b
3.1 位运算_寻找奇数出现
有一个整型数组A，其中只有一个数出现了奇数次，其他的数都出现了偶数次，请打印这个数。要求时间复杂度为O(N)，额外空间复杂度为O(1)。给定整形数组A及它的大小n，请返回题目所求数字。
思路 异或运算
3.2位运算_寻找奇数出现2
给定一个整型数组arr，其中有两个数出现了奇数次，其他的数都出现了偶数次，找到这两个数。要求时间复杂度为O(N)，额外空间复杂度为O(1)
思路
比如出现奇数次的a,b
定义eO=0遍历arr依次异或，结果为eO=a^b
因为a、b互异，所有eO不等于0，设eO的第k位为1
定义变量eOhasOne = 0;与arr中第k位为1的值进行依次异或，结果eOhasOne = a或eOhasOne =b
通过eO^eOhasOne求得另外一个数
3.3位运算_二进制小数
有一个介于0和1之间的实数，类型为double，返回它的二进制表示。如果该数字无法精确地用32位以内的二进制表示，返回“Error”。
思路 乘二取整，顺序排列
3.4 数学基础_加法运算替代
请编写一个方法，实现整数的乘法、减法和除法运算(这里的除指整除)。只允许使用加号。
给定两个正整数int a,int b,同时给定一个int type代表运算的类型，1为求a ＊ b，0为求a ／ b，-1为求a － b。请返回计算的结果，保证数据合法且结果一定在int范围内
思路
- a*b：将问题转换成|b|个a相加，或者|a|个b相加，最后根据a、b的符号确定返回值的符号。
2. a-b：转化成a+[-b]补，而[b]补与[-b]补之间的转换关系：连同符号位一起按位取反，再加1
3.5 动态规划_最大子段和问题
N个整数组成的序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的连续子段和的最大值。当所给的整数均为负数时和为0。
例如：-2,11,-4,13,-5,-2，和最大的子段为：11,-4,13。和为20
3.6 动态规划_矩阵取值问题
一个N*N矩阵中有不同的正整数，经过这个格子，就能获得相应价值的奖励，从左上走到右下，只能向下向右走，求能够获得的最大价值
3.7 动态规划_最大和子矩阵
有一个正整数和负整数组成的NxN矩阵，请编写代码找出元素总和最大的子矩阵。请尝试使用一个高效算法。
思路: 将从第i行到第j行的每一行中相同列的加起来，可以得到一个一维数组如下： (ai1+……+aj1, ai2+……+aj2, ……,ain+……+ajn)
由此我们可以看出最后所求的就是此一维数组的最大子段和问题
3.8 动态规划_最长公共子序列
我们有两个字符串m和n，如果它们的子串a和b内容相同，则称a和b是m和n的公共子序列。子串中的字符不一定在原字符串中连续。
例如字符串“abcfbc”和“abfcab”，其中“abc”同时出现在两个字符串中，因此“abc”是它们的公共子序列。此外，“ab”、“af”等都是它们的字串。。
3.9 动态规划_最长递增子序列
对于一个数字序列，请设计一个复杂度为O(nlogn)的算法，返回该序列的最长上升子序列的长度，这里的子序列定义为这样一个序列U1，U2...，其中Ui < Ui+1，且A[Ui] < A[Ui+1]。
4.0 动态规划_最小编辑代价
对于两个字符串A和B，我们需要进行插入、删除和修改操作将A串变为B串，定义c0，c1，c2分别为三种操作的代价，请设计一个高效算法，求出将A串变为B串所需要的最少代价
4.1 字符串_全排列
4.2 字符串_移位
对于一个字符串，请设计一个算法，将字符串的长度为len的前缀平移到字符串的最后。
4.3 栈_下一个较大元素
现在我们有一个int数组，请你找出数组中每个元素的下一个比它大的元素。
给定一个int数组A及数组的大小n，请返回一个int数组，代表每个元素比他大的下一个元素,若不存在则为-1。保证数组中元素均为正整数。
思路: 从后往前维护一个栈,如果当前栈为空则直接入栈,不为空则弹出top，如果top元素大于当前元素则为较大元素;如果top元素小于当前元素，则继续弹出直到-1或者大于当前元素
4.4 动态规划和递归_魔术索引
在数组A[0..n-1]中，有所谓的魔术索引，满足条件A[i]=i。给定一个不下降序列，元素值可能相同，编写一个方法，判断在数组A中是否存在魔术索引。请思考一种复杂度优于o(n)的方法。
**思路:**事实上，看到A[5]=3时按照二分查找的做法，我们需要递归搜索右半部分。不过，如搜索左半部分， 我们可以跳过一些元素，值递归搜索A[0]到A[3]的元素。A[3]是第一个可能成为魔术索引的元素。
综上：我们得到一种搜索模式，先比较midIndex和midValue是否相同。然后，若两者不同，则按如下方式递归搜索左半部分和右半部分。
左半部分：搜索索引从start到min(midIndex-1,midValue)的元素。
右半部分：搜索索引从max(midIndex+1,minValue)到end的元素。
4.5 数组_循环有序数组最小值
对于一个有序循环数组arr，返回arr中的最小值。有序循环数组是指，有序数组左边任意长度的部分放到右边去，右边的部分拿到左边来
思路::如果子数组是普通升序数组，则A[left]<A[right]。对于循环升序数组，A[left]>A[right]
4.6 数组_第一个缺失的整数
给定一个数组，找到从1开始，第一个不在数组中的正整数，如3，5，1，2，-3，7，14，8输出4
思路::将找到的元素放到正确的位置上，如果最终发现某个元素一直没有找到，则该元素即为所求
若A[i]=i,i加1，继续比较后面的元素;
若A[i]<i或A[i]>N或A[i]=A[A[i]]则丢弃A[i];
若A[i]>i,则将A[A[i]]和A[i]交换
4.7 数组_荷兰国旗问题
设有一个仅由红白蓝三种颜色的条块组成的条块序列。求一种时间复杂度O(n)的算法，使得这些条块按红、白、蓝的顺序排好，即排成荷兰国旗的图案。
思路::快速排序的partition的过程
4.8 数组_最大子数组和
给定一个数组A[0,...,N-1],求A的连续子数组，使得该子数组的和的最大，如数组1,-2,3,10,-4,7,2,-5,最大子数组:3,10,-4,7,2
思路::动态规划 最优子问题
4.9 数组_最大间隔
给定整数数组A，求这N个数排序后的最大间隔，如1，7，14，9，4，13的最大间隔为4
思路::桶排序/hash映射
将N个数用间距(max-min)/(N-1)分成N-1个区间，则落在同一区间内的数不可能有最大间距，统计后一区间的最小值与前一个区间的最大值的差即可
5.0 二叉树_遍历打印
递归和非递归实现
5.1 二叉树_根据前序和中序求中后序
思路::根据前序中序，构造二叉树，后序遍历二叉树;后序遍历最后一个结点即为根结点
5.2 二叉树_层次遍历
给定二叉树的根结点root，请返回打印结果，结果按照每一层一个数组进行储存，所有数组的顺序按照层数从上往下，且每一层的数组内元素按照从左往右排列
思路::借助队列，何时换行?
定义两个指针last表示当前行的最右，nLast表示下一行的最右，当nLast==last时准备换行
5.3 二叉树_二叉查找树判断
给定整数数组，判断该数组有无可能是一颗二叉查找树后序遍历的结果.假定数组中没有重复元素
思路::由于后序遍历的最后一个元素为根结点，
根据该结点将数组分成前后两段,使得前半段都小于根结点，后半段反之
5.4 二叉树_平衡二叉树判断
5.5 二叉树_完全二叉树判断
**思路: **如果当前节点没有左孩子但是有右孩子，则return false; 如果当前节点并不是左右孩子都有，则孩子必须为子叶节点，否则return false
5.6 二叉树_树上最远距离
从二叉树的节点A出发，可以向上或者向下走，但沿途的节点只能经过一次，当到达节点B时，路径上的节点数叫作A到B的距离。对于给定的一棵二叉树，求整棵树上节点间的最大距离。
给定一个二叉树的头结点root，请返回最大距离。保证点数大于等于2小于等于500.
思路：
情况A: 路径经过左子树的最深节点，通过根节点，再到右子树的最深节点。
情况B: 路径不穿过根节点，而是左子树或右子树的最大距离路径，取其大者。
5.7 二叉树_寻找错误结点
一棵二叉树原本是搜索二叉树，但是其中有两个节点调换了位置，使得这棵二叉树不再是搜索二叉树，请找到这两个错误节点并返回他们的值。保证二叉树中结点的值各不相同。
给定一棵树的根结点，请返回两个调换了位置的值，其中小的值在前。
**思路：**第一次降序的较大值 第二次降序的较小值
5.8 二叉树_折纸问题
请把纸条竖着放在桌⼦上，然后从纸条的下边向上⽅对折，压出折痕后再展 开。此时有1条折痕，突起的⽅向指向纸条的背⾯，这条折痕叫做“下”折痕 ；突起的⽅向指向纸条正⾯的折痕叫做“上”折痕。如果每次都从下边向上⽅ 对折，对折N次。请从上到下计算出所有折痕的⽅向。
给定折的次数n,请返回从上到下的折痕的数组，若为下折痕则对应元素为"down",若为上折痕则为"up"
5.9 二叉树_二叉树的镜像
操作给定的二叉树，将其变换为源二叉树的镜像。
**思路：**改写中序遍历
6.0 二叉树_树的子结构
输入两颗二叉树A，B，判断B是不是A的子结构。
**思路：**第一步 在树A中找到与B的根结点的值一样的结点R
第二步再判断树A中以R为根结点的子树是不是包含树B一样的结构
6.1 二叉树_二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
思路：
1.核心是中序遍历的非递归算法。
2.修改当前遍历节点与前一遍历节点的指针指向
6.2 二叉树_二叉搜索树的第k个结点
二叉搜索树的第k个结点
**思路：**给定一颗二叉搜索树，请找出其中的第k大的结点。例如， 5 / \ 3 7 /\ /\ 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。
6.3 查找和排序_数组中的逆序对
有一组数，对于其中任意两个数组，若前面一个大于后面一个数字，则这两个数字组成一个逆序对。请设计一个高效的算法，计算给定数组中的逆序对个数。
**思路：**归并排序的**
6.4 查找和排序_查找和为定值的两个数
**思路：**两头扫
6.5 查找和排序_最短子数组
对于一个数组，请设计一个高效算法计算需要排序的最短子数组的长度。
6.7 查找和排序_堆排序
6.8 查找和排序_计数排序
6.9 图_单词变换问题word-ladder
Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end,
原题连接:https://leetcode.com/problems/word-ladder/
思路::隐式图 广度优先搜索 不需要事先建立图本身
7.0 栈的逆序
7.1 数组_求最长可整合子数组的长度
先给出可整合数组的定义： 如果一个数组arr在排序之后，从最小值到最大值的顺序中，每相邻两个数之间差的绝对值都为1，则arr为可整合数组。 例如： arr = {5，3，4，6，2}，再排序之后为：{2，3，4，5，6}，排序后符合每相邻两个数之间差的绝对值都为1，所以arr是可整合数组。 给定一个整形数组arr，请返回其中长度最大的可整合子数组的长度。
[5,0,1,2,4,3,9]，最长可整合子数组为
[5,0,1,2,4,3]，所以返回6
[6,7,3,0,1,2,4,7]，最长可整合子数组为
3,0,1,2,4]，所以返回5
要求：如果数组长度为N，时间复杂度请达到O(N^2)
思路：
可整合子数组没有重复(一旦出现就没有必要往右继续找了)
最大值-最小值+1 = 长度
不应该陷入题目中可整合子数组的定义中
7.2 数组_未排序数组中累加和为给定值的最长子数组
**思路：**sum[i]+k = sum[j],则j-(i+1)的长度即为所求，我们利用一个哈希表记录累加和sum[i]最早出现的位置
7.3 数组_最大子方阵
有一个方阵，其中每个单元(像素)非黑即白(非0即1)，请设计一个高效算法，找到四条边颜色相同的最大子方阵。
给定一个01方阵mat，同时给定方阵的边长n，请返回最大子方阵的边长。保证方阵边长小于等于100。
测试样例：
[[1,1,1],[1,0,1],[1,1,1]],3
返回：3
思路：
任何一个点的下方(包括自己)1的个数存于数组bottom[i][j]
任何一个点的右边(包括自己)1的个数存于数组right[i][j]
数组分别往上和往左填充
检验四条边颜色是否相同为时,往右或往下跳k个判断1个数是否为k或为0个
7.4 数组_奇数位上都是奇数或者偶数位上都是偶数
给定一个长度不小于2的数组arr。 写一个函数调整arr，使arr中要么所有的偶数位上都是偶数，要么所有的奇数位上都是奇数上。 要求：如果数组长度为N，时间复杂度请达到O(N)，额外空间复杂度请达到O(1),下标0,2,4,6...算作偶数位,下标1,3,5,7...算作奇数位，例如[1,2,3,4]调整为[2,1,4,3]即可
思路：
每次与最后一个元素比较，如果为奇数，则与奇数位上交换，下标+2,如果为偶数，同理
奇偶位上的数依次填入
7.5 字符串_正则表达式匹配
请实现一个函数用来匹配包括'.'和''的正则表达式。模式中的字符'.'表示任意一个字符，而''表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配
思路：
1.有效性检查:str不能有(.); pattern模式中前面必须有一个字符
2.情况分析:定义变量s[i]和p[i]表示从i位置到结尾的字符串
-
- s[i],p[i]不相等时，而且P[i+1]！=*或者,则return false;
如果P[i+1]=*则s[i]与p[i+2]继续比较
-2) s[i],p[i]相等时,如果p[i+1]=,比如s=xxxxzzzz,p=xyyyy
如果p[i+1]不等于*时，则i++
7.6 字符串_最短摘要生成算法
请设计并实现一个高效的最短摘要生成算法，该算法能找出S中包含所有T中的字符的最短子字符串，即最短摘要，如：
S="ADOBECODEBANC"
T="ABC"
最短摘要结果为"BANC"
7.7 数组_数组中出现次数超过一半的数字
思路： 同时删掉两个不同的数，众数不变。
于是我们随便记录一个数x，
来一个数 y， 和x不同的话就把x ,y都扔了，=
相当于扔掉两个不同的数，和x相同的话，就把计数器加1
7.8 数组_天平不平衡找假币问题
Sally Jones has a dozen Voyageur silver dollars. However, only eleven of the coins are true silver dollars; one coin is counterfeit even though its color and size make it indistinguishable from the real silver dollars. The counterfeit coin has a different weight from the other coins but Sally does not know if it is heavier or lighter than the real coins.
Happily, Sally has a friend who loans her a very accurate balance scale. The friend will permit Sally three weighings to find the counterfeit coin. For instance, if Sally weighs two coins against each other and the scales balance then she knows these two coins are true. Now if Sally weighs
one of the true coins against a third coin and the scales do not balance then Sally knows the third coin is counterfeit and she can tell whether it is light or heavy depending on whether the balance on which it is placed goes up or down, respectively.
By choosing her weighings carefully, Sally is able to ensure that she will find the counterfeit coin with exactly three weighings.
思路： 设置两个数组: real[12]-标志为真 lh[12]--标志被怀疑
每次称球的时候，如果是"even"则把对应的设置为"真东西",即置为1，
如果是"up"或"donw" 则把表示轻重的数组lh对应的 ++ 或者 --，直到最后。
然后把所有对应real中为1（即就是真东西啦)的lh置为0；那么操作之后， lh中存在没有辨认出真的，就是一系列的例如： -1,-2,1,2,3等数值，那么 假东西就是其中绝对值最大的那个！！------被怀疑次数最多，所以它为假
7.9 字符串_把一个数字看成字符串,判断是否为回文数
大家对回文串不陌生吧？一个字符串从前看和从后看如果一样的话，就是回文串。比如“上海自来水来自海上”就是一个回文串。现在我们的问题来了,把一个数字看成字符串,问它是不是一个回文数？这么简单的题目对想要成为小米工程师的你来说肯定不是问题。不过提醒一下哦：时间复杂度和空间复杂度越低的算法，得分越高。
示例：
12321 -> true
3 -> true
133434-> false
**思路：**通过计算得到数字前后对应位的数字
8.0 Trapping Rain Wate
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
思路：
一般做法：
water[i] = (min(max(arr[0....i]),max(i+1,......n))-arr[i]);
更好的做法： 见代码