首页 > 代码库 > 数据结构总结
数据结构总结
剑指OfferJAVA版
1. 排序算法
稳定性的概念：
假定待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，称这种排序算法是稳定的，否则称为不稳定的。
|
package com.ljl.sort;
import org.junit.Test;
/** * 七大排序算法 * @author acer * */ public class Sort { private int[] unsorted={1,3,2,8,9,7,6,6,5,3,4};
@Test public void test(){ //bubble(this.unsorted); //pick(this.unsorted); //insert(this.unsorted); //mergeSort(this.unsorted); //fastSort(this.unsorted); //heapSort(this.unsorted); print(this.unsorted);
}
public void print(int[] array){ if(array.length==0) System.out.println("数组为空"); if(array.length>0){ System.out.print("("); for(int i=0;i<array.length;i++){ System.out.print(array[i]+" "); } System.out.print(")"); } } /*冒泡排序算法，时间复杂度o(n^2)，空间复杂度o(1)*/ public void bubble(int[] unsorted){ /*两两相邻比较*/ for(int i=0;i<unsorted.length-1;i++){//大循环次数 for(int j=0;j<unsorted.length-i-1;j++){//两两比较的次数 if(unsorted[j]>unsorted[j+1]){ int tmp=unsorted[j]; unsorted[j]=unsorted[j+1]; unsorted[j+1]=tmp; } } } }
/*选择排序，时间复杂度o(n^2),空间复杂度o(1)*/ public void pick(int[] unsorted){ for(int i=0;i<unsorted.length;i++){ int min=i; for(int j=i+1;j<unsorted.length;j++){//寻找出这个子数组中的最小值，并将其填入unsorted[i]中 if(unsorted[min]>unsorted[j]){ min=j; } } int tmp= unsorted[i]; unsorted[i]=unsorted[min]; unsorted[min]=tmp; } }
/*插入排序，时间复杂度o(n^2)，空间复杂度o(1)*/ public void insert(int[] unsorted){ for(int i=0;i<unsorted.length;i++){ int tmp=unsorted[i];//选择要插入的值 int in=i;//开始要插入的位置 while(in>0&&unsorted[in-1]>tmp){ unsorted[in]=unsorted[in-1];//右移 in--; } unsorted[in]=tmp; } }
/*归并排序，时间复杂度为o(N*lgN),空间复杂度为*/ public void mergeSort(int[] unsorted){ int left=0; int right=unsorted.length-1; sort(unsorted,left,right); }
//归并排序实质上先是分组，然后排序合并 private void sort(int[] array,int left,int right){ if(left>=right) return; int cen=(right+left)/2; sort(array,left,cen); sort(array,cen+1,right); merge(array,left,cen,right); } private void merge(int[] unsorted,int first,int cen,int last){//合并相邻子数组 int[] tempArray=new int[unsorted.length]; int third=first; int temp=first; int mid=cen+1; while(first<=cen&&mid<=last){ if(unsorted[first]<=unsorted[mid]){ tempArray[third++]=unsorted[first++]; }else{ tempArray[third++]=unsorted[mid++]; } } //当mid==last时，但是first<=cen while(first<=cen){ tempArray[third++]=unsorted[first++]; } //当first==cen时，但是mid<=right while(mid<=last){ tempArray[third++]=unsorted[mid++]; } //将归并排序后的值重新写入unsorted while(temp<=last){ unsorted[temp]=tempArray[temp++]; }
}
//快速排序 public void fastSort(int[] unsorted){ int begin=0; int end=unsorted.length-1; FastSort(unsorted,begin,end); }
private void FastSort(int[] A,int begin,int end){ if(begin<end){ int q=partition(A,begin,end); FastSort(A,begin,q-1); FastSort(A,q+1,end); } }
private int partition(int[] A,int begin,int end){ int mid=(begin+end)/2; int tmp=A[mid]; //一次完整的过程，将划分值移至最右端 Swap(A,mid,end); int index=begin; for(int i=begin;i<=end-1;i++){ if(A[i]<=tmp){ //index上的值和i上的值进行互换 Swap(A,index,i); index++; } } //完成最右端的划分值和第一个比划分值互换 Swap(A,index,end); return index; }
/*堆排序算法*/ public void heapSort(int[] unsorted){ buildHeap(unsorted);//先构建二叉树 for(int i=unsorted.length-1;i>=0;i--){ Swap(unsorted,0,i); if(i==0) break; heapify(unsorted,i-1,0); } }
private void buildHeap(int [] array){ if(array==null ||array.length<=1) return ; int half=array.length/2-1;//其实这个值取得有问题 for(int i=half;i>=0;i--) heapify(array,array.length-1,i); }
private void heapify(int[] array,int heapSize,int index){//给定一个index，数组大小 int left=index*2+1;//左值 int right=index*2+2;//右值 int largest=index; if(left<=heapSize&&array[left]>array[largest]){ largest=left; } if(right<=heapSize&&array[right]>array[largest]){ largest=right; } if(index!=largest){//如果发生了调整 Swap(array,index,largest);//调整两者 heapify(array,heapSize,largest);//继续调整 } }
private void Swap(int[] array,int i,int j){ int tmp=array[i]; array[i]=array[j]; array[j]=tmp; }
//希尔排序 变步长插入排序 public void shellSort(int[] unsorted,int n){ int j,gap; for(gap=n;gap>0;gap/=2){ for(j=gap;j<n;j++){ if(unsorted[j]<unsorted[j-gap]){//一组 int temp=unsorted[j]; int k=j-gap; while(k>=0&&unsorted[k]>temp){//插入排序，不过是将步长变成了gap unsorted[k+gap]=unsorted[k]; k-=gap; } unsorted[k+gap]=temp; } } } }
}
|
1.1 题目
已知一个几乎有序的数组，几乎有序是指，如果数组排好顺序的话，每个元素移动的距离不超过k,并且k相对数组长度来说很小，请问选择什么方法对其排序比较好。
改进型的堆排序。时间复杂度O(N*lgK)
1.2 题目
数组中是否含有重复，空间复杂度为O(1)
非递归版本的堆排序
1.3 题目
有序数组合并
1.4 荷兰国旗问题
数组中只包含0,1,2进行排序，要求使用交换、原地排序，而不是利用计数排序。
思路：
|
package com.ljl.sort;
import org.junit.Test;
public class Problem { private int[] unsorted={1,2,0,0,1,1,2,1,2,1,0};
@Test public void test(){ change(this.unsorted); print(this.unsorted); }
public void print(int[] array){ if(array.length==0) System.out.println("数组为空"); if(array.length>0){ System.out.print("("); for(int i=0;i<array.length;i++){ System.out.print(array[i]+" "); } System.out.print(")"); } } /*荷兰国旗问题,数组中只包含0,1,2*/ public void change(int[] unsorted){ int headIndex=0; int railIndex=unsorted.length-1; for(int i=0;i<unsorted.length;i++){ if(i>=railIndex) break; if(unsorted[i]==0){ while(unsorted[headIndex]==0)headIndex++; Swap(unsorted,i,headIndex++); }else if(unsorted[i]==2){ while(unsorted[railIndex]==2) railIndex--; Swap(unsorted,i,railIndex--); } } }
private void Swap(int[] array,int i,int j){ int tmp=array[i]; array[i]=array[j]; array[j]=tmp; }
}
|
1.5 子数组问题
需要排序的最短子数组长度{1,5,4,3,2,6,7}返回4，因为只有{5,4,3,2}需要排序
|
/*最短需要排序子数组长度*/ public int shortestLength(int [] unsorted){ /*从左到右，找到遍历过最大值Max，找到满足M>current的最右值*/ /*从右到左，找到遍历过最小值Min, 找到满足Min<current的最左位置*/ int max=0; int min=unsorted.length-1; int right=0; int left=0; for(int i=1;i<unsorted.length;i++){ if(unsorted[max]<=unsorted[i]){ max=i; }else{ right=i; } } for(int j=unsorted.length-1;j>=0;j--){ if(unsorted[min]>unsorted[j]){ min=j; }else{ left=j; } } return right-left+1; } |
1.6 相邻两数的最大差值
给定一个整数数组arr,返回如果排序之后，相邻两数的最大差值。
桶排序，最优解时间复杂度O(N),额外空间复杂度O(N)
2. 在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
思路：
选取数组中右上角的数字。情况：
如果该数字等于要查找的数字，查找结束；
如果该数字大于要查找的数字，那么剔除所在的列；
如果该数字小于要查找的数字，那么剔除所在的行；
public boolean Find(int target, int [][] array) {
boolean flag=false;
if(array.length<=0) return false;
int rows=array.length;
int columns=array[0].length;
if(rows>0&&columns>0){
int row=0;
int column=columns-1;
while(row<rows&&column>=0){
if(array[row][column]==target){
flag=true;
break;
}else if(array[row][column]>target){
column--;
}else{
row++;
}
}
}
return flag;
}
3. 请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
public String replaceSpace(StringBuffer str) {
StringBuffer sb=new StringBuffer();
char[] rp={‘%‘,‘2‘,‘0‘};
for(int i=0;i<str.length();i++){
char ch=str.charAt(i);
if(ch==‘ ‘){
sb.append(rp);
}else{
sb.append(ch);
}
}
return sb.toString();
}
有两个排序的数组A1和A2,内存在A1的末尾有足够空余空间容纳A2。请事先一个函数，把A2中的所有数字插入到A1中，并且所有的数字都是排序的
public static int[] merge(int[] array1,int[] array2){
int length1=array1.length;
int length2=array2.length;
int[] array3=new int[array1.length+array2.length];
int count=array3.length-1;
int i=length1-1;
int j=length2-1;
while(count>=0){
while(i>=0&&j>=0){
if(array1[i]>array2[j]){
array3[count]=array1[i];
count--;
i--;
}else{
array3[count]=array2[j];
count--;
j--;
}
}
if(i==-1){
while(j>=0){
array3[count]=array2[j];
count--;
j--;
}
}
if(j==-1){
while(i>=0){
array3[count]=array1[i];
count--;
i--;
}
}
}
return array3;
}
4. 输入一个链表，从尾到头打印链表每个节点的值。
推广：
思路：
遍历的顺序时从头到尾，但是输出顺序时从尾到头打印。这就是典型的先进后出的数据结构。既然想到了用栈来实现这个函数，当然我们也可以使用递归策略。
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
Stack<ListNode> stack=new Stack<>();
ArrayList<Integer> array=new ArrayList<Integer>();
while(listNode!=null){
stack.push(listNode);
listNode=listNode.next;
}
while(!stack.isEmpty()){
array.add(stack.pop().val);
}
return array;
}
延伸题目：
非递归实现链表的反转
思路：
为了避免后序链表断开，需要在调整结点m的next之前要把结点m的next指针保存。
面试题13：
给定单向链表的头指针和一个结点指针，定义一个函数在O(1)时间内删除该结点
思路：
首先，判断结点是否存在单向链表中的耗费时间是O(n)，但是这里仅仅关注的是删除耗费时间。
删除一个结点是不是我们必须要知道前一个结点呢？答案是否定的，我们把下一个结点的内容复制到需要删除结点上覆盖原有内容即可，再把下一个结点删除就行；
如果我们删除的是尾结点，没有后续结点，那么我们就需要得到尾结点的前序结点即可；
如果链表仅仅只有一个结点，那么我们就将头结点设置为NULL。
分为三种情况：
1.中间结点(包括头结点)，结点个数大于1
2.结点个数等于1，头结点
3.尾结点
public static void DeleteNode(ListNode pHead,ListNode pNode){
if(pHead==null||pNode==null) return;
if(pNode.next!=null){
ListNode Next=pNode.next;//对于java来说，没法取得pNode的位置
pNode.val=Next.val;
pNode.next=Next.next;
Next=null;
}else if(pHead.val==pNode.val&&pNode.next==null){//只有一个头结点
pHead=null;
pNode=null;
}else{//尾结点
//找到该点
ListNode temp=pHead;
while(temp.next.val!=pNode.val){
temp=temp.next;
}
temp.next=null;
pNode=null;
}
}
延伸题目：
如何在不知道头指针的前提下删除指定结点？
public boolean deleteNode(Node pNode){
if(pNode==null || pNode.next==null) return false;
/*如果pNode!=null*/
int Value= http://www.mamicode.com/pNode.val;
Node Next=pNode.next;
pNode.next.val=Value;
pNode.next=Next.next;
}
延伸题目：
如何从链表中删除重复数据 //删除重复元素，但是链表并没有维护
面试题15：
链表中的倒数第k个结点
例如：一个链表有6个结点，从头结点开始它们的值依次是1,2,3,4,5,6这个链表的倒数第3个结点是值为4的结点
思路：
既然不能从尾结点开始遍历这个链表，假设整个链表有n个结点，那么倒数第k个结点就是从头结点开始的第n-k+1个结点。这种想法意味着我们要遍历链表两次。
为了实现只有一种算法，使得只需要一次遍历链表即可。
我们可以定义两个指针，第一个指针从链表的头指针开始遍历向前走k-1，第二个指针保持不动；从第k步起，第二个指针也开始从链表的头指针开始遍历。由于两者始终保持k-1,当第一个指针达到尾结点时，第二个指针也就正好达到了倒数第k个结点
|
public static ListNode FindKthToTail(ListNode pHead, int k){ if(pHead==null||k<=0) return null; ListNode temp=pHead; ListNode pNode=pHead; for(int i=0;i<k-1;i++){ if(temp.next!=null){ temp=temp.next; }else{ return null; } } while(temp.next!=null){ temp=temp.next; pNode=pNode.next; } return pNode; } |
延伸题目：
找到环的入口
推广题目
求链表的中间结点。如果链表中结点为奇数，返回中间结点；如果是偶数，返回中间结点中的任意结点。
思路：
我们同样可以定义两个两个指针，第一个指针的速度是第二指针移动速度的两倍。当走的快的指针达到了末尾时，当然走的慢的肯定也就走到了链表的中间结点。
|
if(pHead==null) return null; ListNode pNodeA=pHead; ListNode pNodeB=pHead; while(pNodeA.next!=null&&pNodeA.next.next!=null){ pNodeA=pNodeA.next.next; pNodeB=pNodeB.next; } return pNodeB; |
|
|
推广题目二
判断一个单向链表是否形成了环形结构。
思路：
和前面一样，定义两个指针，同时从链表的头结点出发，一个指针走两步，一个指针走两步。如果走的快到的指针追上了走的慢的指针，那么就是环形链表。
面试题37：
两个链表的第一个公共结点
注意：从第一个公共结点开始，不可能出现分叉。所以两个具有公共结点而部分重合的链表，拓扑结构更像是一个Y，而不是一个X。
|
public static ListNode FindFirstCommonNode(ListNode pHeadA,ListNode pHeadB){ //遍历出长度 if(pHeadA==null||pHeadB==null) return null; int alength=getListLength(pHeadA); int blength=getListLength(pHeadB); while(alength>blength){ pHeadA=pHeadA.next; alength--; } while(alength<blength){ pHeadB=pHeadB.next; blength--; } while(pHeadA!=null&&pHeadB!=null&&pHeadA.val!=pHeadB.val){ pHeadA=pHeadA.next; pHeadB=pHeadB.next; } return pHeadA; } public static int getListLength(ListNode node){ int i=1; while(node.next!=null){ node=node.next; i++; } return i; } |
面试题45：
把链表的末尾结点的指针指向头结点，从而形成一个环形链表。约瑟夫环问题
题目：0,1,…..n-1这n个数字排成一个圆圈，从数字0开始每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
思路：
每次在链表中第m个数字的位置
解法：环形链表
public static int LastRemaining(int n,int m){
if(n<1||m<1) return -1;
ArrayList<Integer> array=new ArrayList<>();
for(int i=0;i<n;i++) array.add(i);
int index=0;
while(array.size()>1){
index=(index+m-1)%(array.size());
array.remove(index);
}
return array.get(0);
}
面试题27：
链表中的结点中除了有指向下一个结点的指针，还有指向前一个结点的指针，双向链表。
题目：
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
思路：
按照中序遍历的顺序，当我们遍历到根结点时，它的左子树已经转换成一个排序的链表，并且处在链表中的最后一个结点是当前最大的结点。链表中最大值和根结点相连，此时链表的最后一个结点是根结点。接着我们遍历右子树。递归方法
public TreeNode Convert(TreeNode root) {
if(root==null)return null;
if(root.left==null&&root.right==null)return root;
TreeNode left=Convert(root.left);
TreeNode p=left;
while(p!=null&&p.right!=null)
{
p=p.right;
}
if(left!=null)
{
p.right=root;
root.left=p;
}
TreeNode right=Convert(root.right);
if(right!=null)
{
root.right=right;
right.left=root;
}
return left!=null?left:root;
}
面试题26：
链表中的结点中除了有指向下一个结点的指针，还有指向任意结点的指针，复杂链表
5. 二分查找
5.1 题目1
给定一个有序数组arr，其中不含有重复元素，请找到满足arr[i]==i条件的最左的位置.如果所有位置上的数不满足条件，返回-1.
5.2 题目2
给定一棵完全二叉树的头结点head，返回这课树的节点个数。如果完全二叉树的节点数为N，请事先时间复杂度低于O(N)的解法。
5.3 题目3
如何更快地求一个整数k的N次方。如果两个整数相乘得到的结果的时间复杂度为O(1),得到整数K的N次方的过程请实现复杂度为O(logN)的方法
6. 字符串问题
1.回文
2.子串
3.子序列
4.前缀树
5.后缀树和后缀数组
6.匹配
7.字典序
操作：
增删改查、替换、旋转
类型:
1.规则判断 回文字符串
2.数字运算
3.数组相关的调整、排序
4.字符计数
滑动窗口问题，最长无重复子串问题、变位词问题
5.动态规划
最长公共子串问题
最长公共公共子序列问题
最长回文子串
最长回文子序列问题
6.搜索类型
7.高级算法与数据结构解决的问题
Manacher算法解决最长回文子串问题
KMP算法解决字符串匹配问题
前缀树结构
后缀树和后缀数组
6.1 题目
给定两棵树头结点为t1和t2，判断t1是否含有t2树拓扑结构。
普通解法：二叉树遍历+匹配问题
最优解：二叉树序列化+KMP算法
public boolean DoesTree1HaveTree2(TreeNode pRoot1,TreeNode pRoot2){
if(pRoot1==NULL) return false;
if(pRoot2==NULL) return true;
if(pRoot1.value!=pRoot2.value) return false;
return DoesTree1HaveTree2(pRoot1.left,pRoot2.left)&&
DoesTree1HaveTree2(pRoot1.right,pRoot2.right);
}
6.2 变形词
给定两个字符串str1和str2，如果str1和str2出现字符种类一样且每种字符出现的次数也一样，那么str1和str2互为变形词，请实现两个字符串是否为互为变形词
使用哈希表做字符计数
6.3 旋转词
如果一个字符串str,把字符串str前面任意部分挪到后面形成的字符串叫做旋转词。给定两个字符串a和b,请判断a和b是否为旋转词
思路：
判断两者字符串长度是否相同
将str1+str1生成新的str1,利用KMP算法判断是否跟str2匹配
思路：
朴素模式匹配和KMP算法
|
/*KMP算法*/ public int search(String orginal,String find){ int i=0,j=0; char[] ors=orginal.toCharArray(); char[] finds=find.toCharArray(); int[] next=makeNext(finds); while(i<ors.length&&j<finds.length){ if(ors[i]==finds[j]){ ++i; ++j; }else{ //朴素模式匹配 i=i-j+1; j=0; //KMP匹配 /* if(j==0){ i++; }else{ j=next[j-1]; }*/ } } return (j==finds.length) ?(i-j):-1; }
/*KMP算法Next数组*/ /** * 匹配值 * 以“ABCDAB”为例， * @param patterns * @return */ public int[] makeNext(char[] patterns){ int q,k=0;//模板字符串下标；k:最大前后缀长度 int m=patterns.length; int []next=new int[m]; for(q=1;q<m;q++){ while(k>0&&patterns[q]!=patterns[k])//这句话很难理解 k=next[k-1]; if(patterns[q]==patterns[k])k++; next[q]=k; } return next; } |
6.4 字符串逆序
6.5 字典顺序
给定一个字符串类型的数组strs，请找到一种拼接顺序，使得将所有字符串拼接起来组成的大字符串所有可能性中字典顺序最小的，并返回这个大字符串。
6.6 最长无重复字符子串
哈希表map-à其中统计每种字符之前出现的位置
整型变量pre-à代表s[i-1]结尾的情况下，最长无重复子串的长度
6.7 最长回文子串LPS
暴力搜索
动态规划
|
/*最长回文子串 动态规划 * 状态方程和转移方程 * P[i,j]=0表示子串[i,j]不是回文串，P[i,j]=1表示子串[i,j]是回文串 * P[i+1,j-1]，if s[i]=s[j] * P[i,j]= * 0,if s[i]!=s[j] * */ public String findLongestPailndrom02(String s){ int length=s.length(); int maxlength=0; int start=0; boolean[][] P=new boolean[length][length];//初始化 for(int i=0;i<length;i++){ P[i][i]=true; if(i<length-1&&s.charAt(i)==s.charAt(i+1)){//相邻 P[i][i+1]=true; start=i; maxlength=2; } } //如果存在回文，我们总能找到这么两种情况，1-2-1,1-1这两种情况，我们初始化时，已经将所有这种情况标记为true for(int len=3;len<length;len++){//回文长度 for(int i=0;i<length-len;i++){ int j=i+len-1;//子串结束地址 if(P[i+1][j-1]&&s.charAt(i)==s.charAt(j)){//说明最大长度得到更新 maxlength=len; start=i; P[i][j]=true; } } } if(maxlength>=2) return s.substring(start,start+maxlength); return null; } |
6.8 最长重复字符子串
时间复杂度:O(N*2logN),后缀数组方法实现
后缀数组就是保留字符串所有位置到字符串末尾的字符串，a[i]就是第i个位置到末尾的子串。有了后缀数组，对后缀数组进行排序，然后进行求后缀数组相邻元素的最大前缀就是最大重复子串
|
/*最长重复子串 利用后缀数组实现*/ public String sublongest2(String input){ if (input == null || input.length() == 0||input.length()==1) { return null; }
int length=input.length(); String[] sts=new String[length]; for(int i=0;i<length;i++){ sts[i]=input.substring(i);//拿到后缀数组 } Arrays.sort(sts);//sts 默认自然排序 //两两从头比较后缀数组相邻的两个字符串的公共子串 int maxlength=0;//重复最长距离 String common=null; for(int i=0;i<length-1;i++){ //sts[i],sts[i+1],对这两个字符进行比较 int index=0; int comlength=0; String comStr=""; while(index<sts[i].length()&&index<sts[i+1].length()){ index++; if(sts[i].substring(0, index).equals(sts[i+1].substring(0, index))){ comlength++; comStr=sts[i].substring(0, index); } } if(maxlength<comlength){ maxlength=comlength; common=comStr; } }
return (common==null)?null:common; } |
|
/*暴力搜索求最长重复子串*/ public String sublongest(String input){ if (input == null || input.length() == 0) { return null; } // 重复子串的最长长度 int max = 0; // 最长重复子串的起始位置 int first = 0; int k = 0; for (int i = 1; i < input.length(); i++) { //间隔的字符串长度 k=0;//清除上一次遍历的结果信息 for (int j = 0; j < input.length() - i; j++) { if (input.charAt(j) == input.charAt(i + j)) { k++; } else { k = 0; } if (k > max) { max = k; //求出最长重复子串的长度 first = j - k + 1; // } } } if (max > 0) { System.out.println(max); return input.substring(first, first + max); } return null; } |
6.9 俄罗斯套娃问题----最长上升子序列LIS
dp[i]表示以i为结尾的最长递增子序列的长度，则状态转移方程：
dp[i]=max{dp[j]+1},1<=j<i,a[j]<a[i],时间复杂度为O(N^2)
7. 动态规划问题
1.实现暴力递归方法
2.在暴力搜索方法的函数中看着哪些参数可以代表递归过程。
3.找到代表递归过程的参数之后，记忆化搜索的方法非常容易实现
4.通过分析记忆化搜索的依赖路径，进而实现动态规划。
5.根据记忆化搜索方法改出动态规划方法，进而看看是否能够简化，如果能简化，还能实现时间复杂度更低的动态规划方法。
7.1 台阶问题
最简单的递归问题，也是动态规划问题，找到状态转移方程
7.2 矩阵最短路径和
给定一个n*m矩阵，矩阵中元素非负，从上角到右下角找到一条零，使得路径上元素之和最小，每次只能走一个方格。
7.3 数组中最长自增子序列
给定数组arr，返回arr的最长递增子序列长度。俄罗斯套娃问题
7.4 最长公共字符序列
字符序列的子序列是从给定字符序列中随意地(不一定连续)去掉若干个字符(可能一个也不去掉)后所形成的字符序列。
|
public String longestCommonSubsequence(String str1,String str2){ int [][] matrix=new int[str1.length()+1][str2.length()+1];//建立二维矩阵 /*初始化边界条件*/ for(int i=0;i<=str1.length();i++){ matrix[i][0]=0;//每行第一列置0 } for(int j=0;j<=str2.length();j++){ matrix[0][j]=0;//每列第一行置零 } //填充矩阵 for(int i=1;i<=str1.length();i++){ for(int j=1;j<=str2.length();j++){ if(str1.charAt(i-1)==str2.charAt(j-1)){ matrix[i][j]=matrix[i-1][j-1]+1; }else { matrix[i][j] = (matrix[i - 1][j] >= matrix[i][j - 1] ? matrix[i - 1][j] : matrix[i][j - 1]); } } } //遍历整个矩阵，找到最长公共子序列 Stack<Character> stack=new Stack<>(); char[] s1=str1.toCharArray(); char[] s2=str2.toCharArray(); int i=s1.length-1; int j=s2.length-1; while(i>=0&&j>=0){ if(s1[i]==s2[j]){ stack.push(s1[i]); i--; j--; }else{ if(matrix[i+1][j]>matrix[i][j+1]){ j--; }else{ i--; }
}
} StringBuilder sb=new StringBuilder(); while(stack.isEmpty()){ sb.append(stack.pop()); } return sb.toString(); } |
7.5 0-1背包问题
假设前n个物品，总承重为j，物品的重量为w，其最大价值为v[n,j]
当背包承重为0，或者不将物品放入背包时，背包中的最大总价值均为0，即v[n,0]=v[0,n]=0
放入当前物品n超过背包的最大承重时，则无法将该物品放入背包中，即v[n,j]=v[n-1,j]
放入当前物品n不超过背包的最大承重时，则当前物品放入背包时的最大价值为
Vn+V[n-1,j-Wn]，不放入背包时的最大价值为v[n-1,j]，因此对于当前物品是否放入背包中所能获得最大价值为v[n,j]=max{v[n-1,j],vn+v[n-1,j-Wn]}
|
/*0-1背包问题 * 物品的数量 * -----物品重量w * -----物品价值v * 背包总承重totalWeight * 最终背包的最大总价值maxValue * */ public int bigPackage(int[] weights,int [] values,int total){
int count=weights.length;//weights和values的维数相同 int[][] bestValues=new int[count+1][total+1]; for(int j=0;j<=total;j++){ for(int i=0;i<=count;i++){ if(i==0||j==0) { bestValues[i][j]=0;//当物品没有放入或者承重为0时，其最大价值为0 }else{ if(j<weights[i-1]){//如果第i个物品大于总承重，则最优解存在于前i-1个背包中 bestValues[i][j]=bestValues[i-1][j]; }else{//如果第i个物品小于总承重，那么最优解要么是包含第i个背包的最优解，要么是不包含第i个背包的最优解，取两者最大值 int weight=weights[i-1]; int value=http://www.mamicode.com/values[i-1]; bestValues[i][j]=Math.max(bestValues[i-1][j], bestValues[i-1][j-weight]+value); } } } } return bestValues[count][total]; } |
7.6 换零钱问题
给定数组arr,arr中所有的值都是正数且不重复，每个值都代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个整数aim代表要找的钱数，求还钱有多少种方法？并且要求打印出所有的找钱方案，那么就可以使用递归。
打印出还钱方案：
7.7 整数分解问题
|
/*要求出所有的整数和形式*/ public void sum(int aim){ for(int i=1;i<=aim;i++){ int[] pData=http://www.mamicode.com/new int[i]; sum(aim,i,pData,0); } } //待拆分的参数 //当前递归层要拆分的个数 num //pData，存放每一个拆分单元 //nDepth，拆分的深度 //num+nDepth之和为最终要拆分的总个数 public void sum(int aim,int num,int[] pData,int nDepth){ if(1==num){ pData[nDepth]=aim; for(int i=0;i<num+nDepth;i++){ System.out.print(pData[i]+" "); } System.out.println(); }else{ int i=(nDepth==0?1:pData[nDepth-1]); for(;i<=aim/num;i++){ pData[nDepth++]=i; sum(aim-i,num-1,pData,nDepth); nDepth--; } } } |
8. 二叉树
递归函数
图的遍历方式，比如说BFS和DFS
结合队列、栈、链表、字符串等很多数据结构
8.1 构建二叉树
8.2 遍历
先序遍历：中、左、右
中序遍历：左、中、右
后序遍历：左、右、中
递归遍历的时间复杂度是O(N),空间复杂度是O(L),L是层数
8.3 用递归和非递归实现二叉树先序、中序和后序遍历及层次遍历
先序遍历：
具体过程：
1.申请新栈，stack
2.然后将头结点head压入stack中
3.每次从stack中弹出栈顶元素cur,如果cur右孩子不为空，那么就将cur的右孩子压入堆栈。最后，如果cur的左孩子不为空，那么就将cur左孩子压入栈中。
4.不断重复步骤3，直到stack为空，全部过程结束。
中序遍历：
1.申请栈stack,申请一个变量cur
2.先把cur结点压入栈中，对以cur结点为头的整棵子树来说，依次把整棵树的左结点压入栈中，即不断令cur=cur.left,然后重复步骤2
3.不断重复步骤2，直到发现cur为空，此时stack中弹出一个节点，记为node.打印node的值，并cur=node.right,然后继续重复步骤2.
4.当cur为null并且stack为空时，遍历结束
后序遍历
方法一：使用两个栈实现
具体过程：
1.申请一个栈，记为s1,然后将头结点压入s1中
2.从s1中弹出的结点记为cur,然后先把cur的左孩子压入s1中，然后把cur的右孩子压入s1中
3.在整个过程，每一个s1弹出的结点都放进第二栈s2中
4.不断重复步骤2和步骤3，直到s1为空为止
5.从s2中弹出所有的结点，即为后序遍历
方法二:一个栈实现
1.申请一个栈，将头结点压入栈中，同时设置两个变量h和c。在整个过程中，h代表最近一次弹出并打印的结点，c代表当前stack的栈顶结点，初始化时令h为头结点，c为null
2.每次令c等于当前stack的栈顶结点，但是不从stack中弹出结点，此时分成三种情况：
1）如果c的左孩子不为空，且h不等于c的左孩子，也不等于c的右孩子，那么将c左孩子压入栈中
2）如果情况1不成立，并且c的右孩子不为空，并且h不等于c的右孩子，则把c的右孩子压入stack中。
3）如果情况1和情况2都不成立，那么从stack中弹出c并打印，然后令h等于c.
4)一直重复2，直到stack为空为止。
|
package com.ljl.tree;
import java.util.LinkedList; import java.util.Queue; import java.util.Stack;
public class TreeTraversal { /*分别先序、中序、后序，层次用递归和非递归实现遍历树*/ public static class TreeNode{ public int val; public TreeNode left=null; public TreeNode right=null; }
/*递归实现前序遍历*/ public void preOrder(TreeNode root){ if(root==null) return ; System.out.println(root.val); if(root.left!=null) preOrder(root.left); if(root.right!=null) preOrder(root.right); } /*利用非递归方式实现前序遍历*/ public void preOrder02(TreeNode root){ Stack<TreeNode> stack=new Stack<>(); stack.push(root); while(!stack.isEmpty()){ TreeNode cur=stack.pop(); if(cur.right!=null) stack.push(cur.right); if(cur.left!=null) stack.push(cur.left); System.out.println(cur.val); } } /*中序二叉树遍历*/ public void inOrder(TreeNode root){ if(root==null) return ; if(root.left!=null) inOrder(root.left); System.out.println(root.val); inOrder(root.right); }
/*非递归实现中序遍历*/ public void inOrder02(TreeNode root){ Stack<TreeNode> stack=new Stack<>(); TreeNode cur=root; while(!stack.isEmpty()||cur!=null){ if(cur!=null){ stack.push(cur); cur=cur.left; }else{ TreeNode node=stack.pop(); cur=node.right; System.out.println(node.val); } } }
/*后序遍历*/ public void postOrder(TreeNode root){ if(root==null) return ; if(root.left!=null) postOrder(root.left); if(root.right!=null)postOrder(root.right); System.out.println(root.val); }
/*非递归实现后序遍历*/ public void postOrder02(TreeNode root){ /*双栈实现后序遍历*/ Stack<TreeNode> stack1=new Stack<>(); Stack<TreeNode> stack2=new Stack<>(); stack1.push(root); while(!stack1.isEmpty()){ TreeNode cur=stack1.pop(); if(cur.left!=null) stack1.push(cur.left); if(cur.right!=null) stack1.push(cur.right); stack2.push(cur); } while(!stack2.isEmpty()){ System.out.println(stack2.pop().val); } }
public void postOrder03(TreeNode root){ /*一个栈实现后序遍历*/ Stack<TreeNode> stack=new Stack<>(); stack.push(root); TreeNode h=null;//表示最近一次打印的结点 TreeNode cur=null;//栈顶结点 while(!stack.isEmpty()){ cur=stack.peek(); if(cur.left!=null&&h!=cur.left&&h!=cur.right){ stack.push(cur.left); }else if(cur.left==null&&cur.right!=null&&h!=cur.right){ stack.push(cur.right); }else{ cur=stack.pop(); h=cur; System.out.println(h.val); } }
} /*按照层次打印*/ public void layerTraversal(TreeNode root){ Queue<TreeNode> queue=new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()){ TreeNode bn=queue.poll(); System.out.println(bn.val); if(bn.left!=null) queue.offer(bn.left); if(bn.right!=null) queue.offer(bn.right); } } /*输出带行号信息的按层次遍历*/ public void layerTraversal03(TreeNode root){ Queue<TreeNode> queue=new LinkedList<>(); queue.offer(root); if(root==null) return ; int last=1,nlast=0;//last是当前层的结点总数，nlast是下一层的结点总数 while(!queue.isEmpty()){ TreeNode bn=queue.poll(); System.out.print(bn.val+" "); last--; if(bn.left!=null){ nlast++; queue.offer(bn.left); } if(bn.right!=null){ nlast++; queue.offer(bn.right); } if(0==last){ last=nlast; nlast=0; System.out.println(); } } } /*递归按层次遍历，带有信息*/ public void layerTraversal02(TreeNode root){ /*求树的深度*/ if(root==null) return; int depth=Depth(root); for(int i=1;i<=depth;i++){ PrintNodeAtLevel(root,i); System.out.println(); } }
public void PrintNodeAtLevel(TreeNode root,int level){ if(root==null||level<1)return; if(level==1){ System.out.print(root.val+" "); return ; } PrintNodeAtLevel(root.left,level-1); PrintNodeAtLevel(root.right,level-1); }
public int Depth(TreeNode root){//求树的深度 int depth=0; if(root==null) depth=0; else{ int m=Depth(root.left); int n=Depth(root.right); depth=(m>n)?(m+1):(n+1); } return depth; }
}
|
8.4 二叉树的子树
8.5 平衡二叉树AVL树
判断一棵树是否是平衡二叉树
8.6 搜索二叉树
判断是否为搜索二叉树
1.中序遍历 非递归实现
8.7 满二叉树和完全二叉树
完全二叉树
判断是否为完全二叉树
1.判断按层次遍历二叉树，从每层到的左边向右边依次遍历所有的结点
2.如果当前节点有右孩子，但没有左孩子，直接返回false.
3.如果当前节点并不是左右孩子全有，那么之后的结点必须为叶子结点，否则返回false
4.遍历过程如果不返回false,遍历结束后返回true即可。
8.8 题目
1.重建二叉树
已知前序遍历和中序遍历的结果，重建出该二叉树。
已知中序遍历和后续遍历的结果，重建出该二叉树。
已知后续遍历
9. 栈和队列
DFS 深度优先搜索---stack
BFS 宽度优先搜素---queue
9.1 用两个栈来实现队列操作
9.2 实现一个栈的逆序操作，但是只能用递归函数和这个栈本身的操作来实现，而不能自己申请另外的数据结构
移除栈底元素并返回
9.3 利用双栈实现排序
9.4 滑动窗口
10. 位操作
10.1 布隆过滤器
数据结构总结