数据结构 —— 剑指Offer算法题突破口总结
注意：本文适用于已刷过题目，想短短几分钟快速简单回顾的情况。没看过《剑指offer》的读者建议先阅读下。
斐波那契数列
1、1、2、3、5、8、13、21、34、……
在数学上，斐波纳契数列以如下被以递归的方法定义：F(0)=1，F(1)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）
解法比较：
- 递归
int F(int n)
{
if(n <= 0)
return 0;
else if(n == 1)
return 1;
else
return F(n-1) + F(n-2);
}
缺点：效率非常低，时间复杂度是指数级的。重复的计算量是无比巨大的。
2.迭代法。
long Fib(int n)
{
int i;
unsigned long a = 0, b = 1, c;
if (n <= 1) {
return n;
} else {
for (i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return c;
}
}
求Fibonacci数列第n项时虽然要用到前面两项的值，但它们仅作为临时计算的中间值，不作为结果输出，因此无保留的必要，完全可以转化成迭代法求解
青蛙跳台阶
一次可跳1阶或2阶，求n阶跳法，变相斐波那契数列。
青蛙跳台阶变态版本
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
f(n)=2f(n-1)*
图解：
效率更高的解法：
if(number<=0)
return 0;
if(number==1)
return 1;
int sum=1<<(number-1);//位运算代替*2 1<<n 意思为2的n次方
return sum;
矩形覆盖
同青蛙跳台阶理
二进制中1的个数
int count = 0;
while(n!= 0){
count++;
n = n & (n - 1);
}
return count;
例：一个二进制数1100，从右边数起第三位是处于最右边的一个1。减去1后，第三位变成0，它后面的两位0变成了1，而前面的1保持不变，因此得到的结果是1011.我们发现减1的结果是把最右边的一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。如1100&1011=1000.也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0.那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。
数值的整数次方
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
考虑：
- 指数为0的情况
- 指数为负数->对指数求绝对值，算出次方结果后取倒数，倒数还要判断底数为0的情况。
- 浮点数的比较是有误差的，因此不能用简单的a==0来比较。一般的比较方式是，相减的差在一个很小的区间内，我们就认为是相等的
(float1- float2 > -0.0000001) && (float1 -float2 < 0.0000001)
最佳解决：
可用>>1代替/2
if(exponent==0)
return 1;
if(exponent==1)
return base;
if(exponent==-1)
return 1.0/base;
if((exponent&1)==1){
//奇数
double result=Power(base,(exponent-1)/2);
result*=result;
result*=base;
return result;
}else{
//偶数
double result=Power(base,exponent/2);
result*=result;
return result;
}
从尾到头打印链表
采用栈临时存储遍历的节点值，遍历完后栈输出。
替换空格
将长度为1的空格替换为长度为3的“%20”，字符差的长度变长。如果允许我们开辟一个新的数组来存放替换空格后的字符串，那么这道题目就非常简单。但是如果面试官要求在原先的字符串上操作，并且保证原字符串有足够长的空间来存放替换后的字符串，那么我们就得另想方法。
如果从前往后替换字符串，那么保存在空格后面的字符串肯定会被覆盖，那么我们就考虑从后往前进行替换。
首先遍历原字符串，找出字符串的长度以及其中的空格数量，
根据原字符串的长度和空格的数量我们可以求出最后新字符串的长度。
设置两个指针point1和point2分别指向原字符串和新字符串的末尾位置。
如果point1指向内容不为空格，那么将内容赋值给point2指向的位置，如果point1指向为空格，那么从point2开始赋值“02%”
直到point1==point2时表明字符串中的所有空格都已经替换完毕。
二维数组中的查找
数组每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
一张图说明，查找7为例：
旋转数组的最小数字
例：{3，4，5，1，2}为{1，2，3，4，5}的旋转数组，求最小数字。
可用二分查找法。
注意：存在该情况{1，2，3，4，5}仍然是数组的选择。
特殊情况：{1，0，1，1}（a[start]==a[end]==a[mid]）此时只能采用顺序查找。
求链表中倒数第k个数
首先要先判断k和链表的长度比较，如果k<=链表长度，
则先指针1走k步，指针2和指针1一起走。指针1指向NULL的时候，指针2所指就是倒数第k个数。
从上往下打印二叉树
采用队列作为临时存储容器
二叉树深度
int TreeDepth(TreeNode* pRoot)
{
if(pRoot==NULL)
return 0;
return max(TreeDepth(pRoot->left),TreeDepth(pRoot->right))+1;
}
连续子数组的和
例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)子向量的长度至少是1。【动态规划思想】
public int FindGreatestSumOfSubArray(int[] array) {
int sum=array[0];
int max=array[0];
for(int i=1;i<array.length;i++){
if(sum<=0){
sum=array[i];
}else
sum+=array[i];
if(max<sum)
max=sum;
}
return max;
}
两个栈实现队列
stack1只管push
stack2为空时把stack1内容弹出，一一入stack2栈，stack2栈顶为要pop的元素，若stack2不为空，直接出栈。
包含min函数的栈
例存储为stack，采用栈minStack辅助存min，当push进stack更小值时，minStack存入当前push的值，若push的值比minStack栈顶值大，则minStack再次入栈栈顶的值。stack pop时，minStack比较大小，若小于pop的值，minStack跟着pop。
数字在排序数组中出现的次数
二分查找出头和尾，尾下标-头下标+1为出现次数。
思路简单，但是要注意越界的坑！
public int GetNumberOfK(int[] array, int k) {
int end = findEnd(array, 0, array.length-1, k);
int start = findStart(array, 0, array.length-1, k);
if (end == -1 || start == -1)
return 0;
return end-start+1;
}
public int findStart(int[] array, int start, int end, int k) {
if (start > end||end>=array.length||start<0)
return -1;
int mid = (start + end) / 2;
if (array[mid] == k) {
if (mid - 1 < 0)
return mid;
if (array[mid - 1] != k)
return mid;
else
return findStart(array, start, mid - 1, k);
} else if (array[mid] > k)
return findStart(array, start, mid - 1, k);
else
return findStart(array, mid + 1, end, k);
}
public int findEnd(int[] array, int start, int end, int k) {
if (start > end||end>=array.length||start<0)
return -1;
int mid = (start + end) / 2;
if (array[mid] == k) {
if (mid + 1 >= array.length)
return mid;
if (array[mid + 1] != k)
return mid;
else
return findEnd(array, mid + 1, end, k);
} else if (array[mid] > k)
return findEnd(array, start, mid - 1, k);
else
return findEnd(array, mid + 1, end, k);
}
数组中出现次数超一半的数字
没什么好说的，出现次数超过一半，那么排序后该数字必然会在数组中位线处。
另一种思路：符合条件的数字，则它出现的次数比其他所有数字出现的次数和还要多。在遍历数组时保存两个值：一是数组中一个数字，一是次数。遍历下一个数字时，若它与之前保存的数字相同，则次数加1，否则次数减1；若次数为0，则保存下一个数字，并将次数置为1。遍历结束后，记得统计下数组，所保存的数字在数组中出现的次数是否超过数组的一半长度，不超过直接return 0，否则返回保存的数字。
反转链表
三个指针pPrev、p、pNext、tmp，初始化时分别指向NULL、head、head->next、head->next->next。重复进行p->next=pPrev操作。再一一挪到下一个指向。
if(pHead==NULL)
return NULL;
ListNode* pPrev=NULL;
ListNode* p=pHead;
ListNode* pNext=p->next;
while(p!=NULL)
{
ListNode* tmp;
if(pNext!=NULL)
tmp=pNext->next;
p->next=pPrev;
pPrev=p;
p=pNext;
pNext=tmp;
}
return pPrev;
合并两个排序的链表
分别从link1和link2的头部开始比较，谁小谁就作为新链表的next点。
需要注意的情况：
- 两个链表都为NULL
- 有一个链表为NULL
- 两个链表长度不一致
- 第一次比较时newLink表头为NULL，赋值给头，下一次比较赋值给newLink的next，且要有临时变量存储newLink的头指针（最后返回临时变量），因为在循环中不断newLink=newLink->next后返回newLink，此时newLink指向链表的中部而不是头。
调整数组顺序使奇数位于偶数前面
- 不稳定算法（不强调相对顺序）：头尾两个指针，头遇到偶数停止，尾遇到奇数停止，交换，一直到头指针下标大于尾指针下标。
- 稳定算法（调整完保证奇数和奇数，偶数和偶数之间的相对位置不变）：
采用插入排序思想。找到奇数时，往前0~奇数位置范围新找偶数，交换位置。
丑数
只包含因子2、3和5的数称作丑数，习惯上把1当做是第一个丑数。
//1，2，3，4，5，6，8，9，10，12，15，16，18....
分析：
//用数组存储计算出来的丑数，返回a[index-1]即可(数组从0开始)
（1）index=1，num=a[index-1]=a[0]=1
（2）index=2，num=min（a[index-2]*2,a[index-2]*3,a[index-2]*5）;
//前一个数乘以3个因子的最小值 也就是1*2和1*3和1*5比较，min为2。
（3）index=3，num=min（a[index-3]*2,a[index-3]*3,a[index-3]*5,a[index-2]*2,a[index-2]*3,a[index-2]*5）;
//前2个数乘以3个因子的最小值。
也就是1*2和1*3和1*5和2*2和2*3和2*5比较，min为2。
但是此时的丑数要大于前一个丑数！！，所以取次小值3。
最好的办法是循环计算得到 第一个 *2大于下一个目标数的丑数的下标
第一个 *3大于下一个目标数的丑数的下标
第一个 *5大于下一个目标数的丑数的下标
分别保存下来，然后求这三个数的最小值。
if (index <= 0)
return 0;
if (index == 1)
return 1;
int a[index];
a[0] = 1;
int index1 = 0, index2 = 0, index3 = 0;
for (int i = 1; i < index; i++) {
int min = getMin(a[index1] * 2, a[index2] * 3, a[index3] * 5);
a[i] = min;
while (a[index1] * 2 <= a[i])
index1++;
while (a[index2] * 3 <= a[i])
index2++;
while (a[index3] * 5 <= a[i])
index3++;
}
return a[index - 1];
第一次只出现一次的字符
java用哈希表，先扫描一遍，统计各个字符出现的次数。
再扫描第二遍，去哈希表取对应的次数，一旦等于1，跳出循环，返回下标。
c用数组代替哈希表，总共只有256个字符，数组长度256即可。
二叉树的镜像
没什么好说，上关键代码。
void Mirror(TreeNode* root)
{
if(root==NULL)
return ;
if(root!=NULL)
{
TreeNode* tmp=root->left;
root->left=root->right;
root->right=tmp;
if(root->left)
Mirror(root->left);
if(root->right)
Mirror(root->right);
}
}
栈的压入弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
思路：
模拟堆栈操作：将原数列依次压栈，栈顶元素与所给出栈队列相比，如果相同则出栈，接着比较出栈队列下一位。如果不同则继续压栈，直到原数列中所有数字压栈完毕。
检测栈中是否为空，若空，说明出栈队列可由原数列进行栈操作得到。否则，说明出栈队列不能由原数列进行栈操作得到。
两个链表的第一个公共结点
两个单向链表存在公共点，类似“Y”
- 方法一：遍历两个链表，存入栈。一一出栈，最后一个相同的结点，即为第一个公共结点。
- 方法二：遍历两个链表，获取长度，长的链表先走len1-len2步，然后两个链表一起遍历，第一个相同的结点为第一个公共结点。
不用加减乘除做加法
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
int Add(int num1, int num2)
{
while(num2!=0)
{
int n=num1^num2;
num2=(num1&num2)<<1;
num1=n;
}
return num1;
}
根据先序和中序重建二叉树
递归思想
假定已知二叉树如下：
7
/ \
10 2
/ \ /
4 3 8
\ /
1 11
那么它的先序遍历和中序遍历的结果如下：
preorder = {7,10,4,3,1,2,8,11}
inorder = {4,10,3,1,7,11,8,2}
需要关注几个重要的点：
1）先序遍历的第一个结点总是根结点。先序遍历时父结点总是在子结点前遍历。
2）可以观察到在中序遍历中，7是第4个值（从0开始算起）。由于中序遍历顺序为：左子树，根结点，右子树。所以7左边的{4,10,3,1} 这四个结点属于左子树，而根结点7右边的{11,8,2}属于右子树。
3）可以从上面的结论得到递归式。在构建了根结点7后，我们可以根据中序遍历{4, 10, 3, 1} 和{11,8,2}分别构建它的左子树和右子树。我们同时需要相应的先序遍历结果用于发现规律。我们可以由先序遍历知道左右子树的先序遍历分别是{10，4, 3, 1}和{2， 8， 11}。左右子树也分别为二叉树，由此可以递归来解决问题。
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
return build(pre,0,pre.length-1,in,0,in.length-1);
}
public TreeNode build(int [] pre,int prestart,int preend,int [] in,int instart,int inend) {
if(prestart>preend||instart>inend)
return null;
TreeNode root=new TreeNode(pre[prestart]);
for(int i=instart;i<=inend;i++){
if(in[i]==pre[prestart]){
root.left=build(pre,prestart+1,prestart+i-instart,in,instart,i-1);
root.right=build(pre,prestart+i-instart+1,preend,in,i+1,inend);
break;
}
}
return root;
}
二叉搜索树的后序遍历序列
判断一个序列是否是二叉搜索树的后序遍历序列。二叉搜索树的后序遍历满足以下条件，例:{1,3,2,5,7,6,4}。最后一位4为根节点，{1,3,2}为左子树，{5,7,6}为右子树。再继续递归，2为根节点，1为左子树，3为右子树。6为根节点，5为左子树，7为右子树。
public boolean VerifySquenceOfBST(int[] sequence) {
if (sequence.length <= 0)
return false;
return build(sequence, 0, sequence.length - 1);
}
public boolean build(int[] sequence, int start, int end) {
if (start > end || end < 0 || start >= sequence.length) {
return true;
}
int root = sequence[end];
int j = end - 1;
while (j >= start && sequence[j] > root) {
j--;//找到第一个小于根节点的下标
}
for (int i = start; i <= j; i++) {
if (sequence[i] > root)
return false;
//判断左子树序列是否都小于根节点，不小于则不满足
}
//检查左子树和右子树
return build(sequence, start, j) && build(sequence, j + 1, end - 1);
}
树的子结构
递归比较
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
{
if(pRoot1==NULL||pRoot2==NULL)
return false;
return find(pRoot1,pRoot2)||HasSubtree(pRoot1->left,pRoot2)||HasSubtree(pRoot1->right,pRoot2);
//用短路或代替flag
}
bool find(TreeNode* pRoot1, TreeNode* pRoot2)
{
if(pRoot2==NULL)
return true;
if(pRoot1==NULL)
return false;
if(pRoot1->val==pRoot2->val)
return find(pRoot1->left, pRoot2->left)&&find(pRoot1->right, pRoot2->right);
return false;
}
顺时针打印矩阵
如果觉得注意边界情况太麻烦，可以采用魔方的逆时针旋转的方法，一直做取出第一行的操作
例如
1 2 3
4 5 6
7 8 9
输出并删除第一行后，再进行一次逆时针旋转，就变成：
6 9
5 8
4 7
继续重复上述操作即可。
最小的k个数
快排后输出前k个。
平衡二叉树
空树或它的左右两个子树的高度差的绝对值不超过1,且左右子树都是平衡二叉树。
bool IsBalanced_Solution(TreeNode* pRoot) {
if(pRoot==NULL)
return true;
int height=getHeight(pRoot->left)-getHeight(pRoot->right);
if(height>1||height<-1)
return false;
return IsBalanced_Solution(pRoot->left)&&IsBalanced_Solution(pRoot->right);
}
int getHeight(TreeNode* pRoot){
if(pRoot==NULL)
return 0;
return max(getHeight(pRoot->left),getHeight(pRoot->right))+1;
}
本文持续更新中。。。。
