一、算法分析基础

1.什么是好的算法

1）正确性；2）简明性；3）效率；4）最优解

2.时间复杂度：是指算法运行所需要的时间

设：对于算法A，I是某次运行时的输入数据，其规模为n，则运行时间是两者的函数，记作T（n,I）。又设在该次运算中抽象机的第i个基本运算的执行次数是b(i)，1<=i<=m,b(i)也是n和I的函数，记作bi(n,I)。那么，算法A在输入为I时的运行时间是：T(n,I)=a1*b1(n,I)+a2*b2(n,I)+......+am*bm(n,I).

3.算法的空间复杂度

1）固定空间复杂度；2)可变空间复杂度。

（1）O

大O，可以认为它的含义是“order of”（大约是）。

简单列举几个，当人们形容：

某个算法的时间复杂度是O(1)，就说明这是一个优秀的算法。

某个算法的时间复杂度是O(logn)，就说明这是一个良好的算法。

某个算法的时间复杂度是O(n)，就说明这个算法还不错。

某个算法的时间复杂度是O(n2)，就说明这个算法差一些了。

O(g(n))表示所有增长阶数不超过g(n)的函数的集合，它表达一个算法的运行上界。

二、常用算法

1.、分治法

将一个问题分解为若干个规模较小的子问题，且这些子问题的互相独立且与原问题类型相同。递归处理这些子问题，直到这些子问题的规模小到可以直接求解，然后将这些子问题合并到原问题的解。

例：归并排序，快速排序

2.贪心法

基本思想：把求解的问题分解成几若干个子问题，对每个子问题求解，得到子问题的局部最优解，把子问题的局部最优解合并成原来问题的一个解。

两个特性：贪心选择特性，最有子结构特性

例：最小生成树（prim、克鲁斯卡尔算法）

3..动态规划发

将待求解的问题分若干个相互练习的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇见时对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。

例：多段图问题

例：连续子数组的最大和

分析：

publicclassSolution{publicintFindGreatestSumOfSubArray(int[]array){intres=array[0];//记录当前所有子数组的和的最大值intmax=array[0];//包含array[i]的连续数组最大值for(inti=1;i<array.length;i++){max=Math.max(max+array[i],array[i]);res=Math.max(max,res);}returnres;}}

4.回溯法

基本思想：

1）针对所给的问题，定义问题的解空间；

2）确定易于搜索的解空间结构；

3）以深度优先方式搜索解空间，并在搜索的过程中用剪枝函数避免无效的搜索。

例：批处理作业问题、0/1背包问题

5.分支限界法

常见的两种分支限界法框架：

1）队列式（FIFO）分支限界法：按照队列先进先出的原则选取下一个结点为扩展节点；

2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前的扩展节点。

分支限界法的算法步骤：

1）针对所给的问题，定义问题的解空间

6、递归和循环

递归有简洁的优点，但是它同时也有显著的缺点。递归由于是函数调用自身，而函数调用是有时间和空间消耗的：每一次函数调用，都需要在内存栈中分配空间以保存参数、返回地址和环境变量，而且往栈里面压入数据和弹出数据都需要时间。

除了效率之外，递归还有可能引起更为严重的问题：调用栈溢出。每一次函数调用在内存栈中分配空间，而每个进程的栈的容量是有限的。当递归调用的层级太多，就会超出栈的容量，从而导致调用栈溢出。

例1:1+2+...+n

intAddFromToN_recursive(intn){//递归方法实现returnn<=0?0:n+AddFromToN_recursive(n-1);}intAddFromToN_Interative(intn){intresult=0;for(inti=1;i<n;++i)result+=i;returnresult;}

要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。classSolution{public:intSum_Solution(intn){boola[n][n+1];returnsizeof(a)>>1;}};

1）斐波那契数列

公式：f(n)=｛ 0n=0;1n=1;f(n-1)+f(n-2)n>1｝

实用解法：

longlongFibonacci(unsignedn){intresult[2]={0,1};if(n<2){returnresult[n];}longlongfibNMinusOne=1;longlongfibNMinusTwo=0;longlongfibN=0;for(unsignedinti=2;i<=n;++i){fibN=fibNMinusOne+fibNMinusTwo;fibNMinusTwo=fibNMinusOne;fibNMinusOne=fibN;}returnfibN;}变态跳台阶

题目描述：

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

classSolution{public:/**说明：1）这里的f(n)代表的是n个台阶有一次1,2,...n阶的跳法数。2）n=1时，只有1种跳法，f(1)=13)n=2时，会有两个跳得方式，一次1阶或者2阶，这回归到了问题（1），f(2)=f(2-1)+f(2-2)4)n=3时，会有三种跳得方式，1阶、2阶、3阶，那么就是第一次跳出1阶后面剩下：f(3-1);第一次跳出2阶，剩下f(3-2)；第一次3阶，那么剩下f(3-3)因此结论是f(3)=f(3-1)+f(3-2)+f(3-3)5)n=n时，会有n中跳的方式，1阶、2阶...n阶，得出结论：f(n)=f(n-1)+f(n-2)+...+f(n-(n-1))+f(n-n)=>f(0)+f(1)+f(2)+f(3)+...+f(n-1)6)由以上已经是一种结论，但是为了简单，我们可以继续简化：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)=f(0)+f(1)+f(2)+f(3)+...+f(n-2)+f(n-1)=f(n-1)+f(n-1)可以得出：f(n)=2*f(n-1)7)得出最终结论,在n阶台阶，一次有1、2、...n阶的跳的方式时，总得跳法为：|1,(n=0)f(n)=|1,(n=1)|2*f(n-1),(n>=2)*/intjumpFloorII(intnumber){inttarget=number;if(target<=0){return-1;}elseif(target==1){return1;}else{return2*jumpFloorII(target-1);}}};矩形覆盖问题

问题描述

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

分析：

依旧是斐波那契数列

2*n的大矩形，和n个2*1的小矩形

其中target*2为大矩阵的大小

有以下几种情形：

1⃣️target <= 0 大矩形为<= 2*0,直接return 1；

2⃣️target = 1大矩形为2*1，只有一种摆放方法，return1；

3⃣️target = 2 大矩形为2*2，有两种摆放方法，return2；

4⃣️target = n 分为两步考虑：

第一次摆放一块 2*1 的小矩阵，则摆放方法总共为f(target - 1)

√

√

第一次摆放一块1*2的小矩阵，则摆放方法总共为f(target-2)

因为，摆放了一块1*2的小矩阵（用√√表示），对应下方的1*2（用××表示）摆放方法就确定了，所以为f(targte-2)

√

√

×

×

代码：

publicclassSolution{publicintRectCover(inttarget){if(target<=1){return1;}if(target*2==2){return1;}elseif(target*2==4){return2;}else{returnRectCover((target-1))+RectCover(target-2);}}}publicclassSolution{publicintRectCover(inttarget){if(target==0)return0;if(target==1)return1;if(target==2)return2;inta=1,b=2,c=0;for(inti=2;i<target;i++){c=a+b;a=b;b=c;}returnc;}}

2）汉诺塔问题

inti;//记录步数//i表示进行到的步数,将编号为n的盘子由from柱移动到to柱(目标柱)voidmove(intn,charfrom,charto){printf("第%d步:将%d号盘子%c---->%c\n",i++,n,from,to);}//汉诺塔递归函数//n表示要将多少个"圆盘"从起始柱子移动至目标柱子//start_pos表示起始柱子,tran_pos表示过渡柱子,end_pos表示目标柱子voidHanio(intn,charstart_pos,chartran_pos,charend_pos){if(n==1){//很明显,当n==1的时候,我们只需要直接将圆盘从起始柱子移至目标柱子即可.move(n,start_pos,end_pos);}else{Hanio(n-1,start_pos,end_pos,tran_pos);//递归处理,一开始的时候,先将n-1个盘子移至过渡柱上move(n,start_pos,end_pos);//然后再将底下的大盘子直接移至目标柱子即可Hanio(n-1,tran_pos,start_pos,end_pos);//然后重复以上步骤,递归处理放在过渡柱上的n-1个盘子//此时借助原来的起始柱作为过渡柱(因为起始柱已经空了)}}3.数字在排序数组中出现的次数

题目描述

统计一个数字在排序数组中出现的次数。

思路：

可以遍历

publicclassSolution{publicintGetNumberOfK(int[]array,intkey){/***数组长度鲁棒性检查*/if(array.length==0){return0;}intfirstK=getFirstK(array,key,0,array.length-1);intlastK=getLastK(array,key,0,array.length-1);if(firstK!=-1&&lastK!=-1){returnlastK-firstK+1;}return0;}//递归写法privateintgetFirstK(int[]array,intk,intstart,intend){/***鲁棒性检查*/if(start>end){return-1;}intmid=(start+end)>>1;if(array[mid]>k){returngetFirstK(array,k,start,mid-1);}elseif(array[mid]<k){returngetFirstK(array,k,mid+1,end);}elseif(mid-1>=0&&array[mid-1]==k){returngetFirstK(array,k,start,mid-1);}else{returnmid;}}//循环写法privateintgetLastK(int[]array,intk,intstart,intend){/***鲁棒性检查*/intlength=array.length;intmid=(start+end)>>1;while(start<=end){if(array[mid]>k){end=mid-1;}elseif(array[mid]<k){start=mid+1;}elseif(mid+1<length&&array[mid+1]==k){start=mid+1;}else{returnmid;}mid=(start+end)>>1;}return-1;}}4.链表递归

/***structListNode{*intval;*structListNode*next;*ListNode(intx):*val(x),next(NULL){*}*};*/importjava.util.Stack;importjava.util.ArrayList;publicclassSolution{publicArrayList<Integer>printListFromTailToHead(ListNodelistNode){Stack<Integer>stack=newStack<>();while(listNode!=null){stack.push(listNode.val);listNode=listNode.next;}ArrayList<Integer>list=newArrayList<>();while(!stack.isEmpty()){list.add(stack.pop());}returnlist;}}5..二叉树的深度

题目描述

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

思路

第一种方法是使用递归方法执行，第二种方法是使用循环（里面使用了队列）

/**publicclassTreeNode{intval=0;TreeNodeleft=null;TreeNoderight=null;publicTreeNode(intval){this.val=val;}}*/publicclassSolution{/***递归写法*@return*/publicintTreeDepth(TreeNoderoot){if(root==null){return0;}intnLeft=TreeDepth(root.left);intnRight=TreeDepth(root.right);returnnLeft>nRight?(nLeft+1):(nRight+1);}/***非递归写法：层次遍历*@return*/publicintTreeDepth3(TreeNodepRoot){if(pRoot==null){return0;}Queue<TreeNode>queue=newLinkedList<TreeNode>();queue.add(pRoot);intdepth=0,count=0,nextCount=1;while(queue.size()!=0){TreeNodetop=queue.poll();count++;if(top.left!=null){queue.add(top.left);}if(top.right!=null){queue.add(top.right);}if(count==nextCount){nextCount=queue.size();count=0;depth++;}}returndepth;}}6.二叉搜索树与双向链表题目描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

递归版解题思路：1.将左子树构造成双链表，并返回链表头节点。2.定位至左子树双链表最后一个节点。3.如果左子树链表不为空的话，将当前root追加到左子树链表。4.将右子树构造成双链表，并返回链表头节点。5.如果右子树链表不为空的话，将该链表追加到root节点之后。6.根据左子树链表是否为空确定返回的节点。publicTreeNodeConvert(TreeNoderoot){if(root==null)returnnull;if(root.left==null&&root.right==null)returnroot;//1.将左子树构造成双链表，并返回链表头节点TreeNodeleft=Convert(root.left);TreeNodep=left;//2.定位至左子树双链表最后一个节点while(p!=null&&p.right!=null){p=p.right;}//3.如果左子树链表不为空的话，将当前root追加到左子树链表if(left!=null){p.right=root;root.left=p;}//4.将右子树构造成双链表，并返回链表头节点TreeNoderight=Convert(root.right);//5.如果右子树链表不为空的话，将该链表追加到root节点之后if(right!=null){right.left=root;root.right=right;}returnleft!=null?left:root;}改进递归版解题思路：思路与方法二中的递归版一致，仅对第2点中的定位作了修改，新增一个全局变量记录左子树的最后一个节点。//记录子树链表的最后一个节点，终结点只可能为只含左子树的非叶节点与叶节点protectedTreeNodeleftLast=null;publicTreeNodeConvert(TreeNoderoot){if(root==null)returnnull;if(root.left==null&&root.right==null){leftLast=root;//最后的一个节点可能为最右侧的叶节点returnroot;}//1.将左子树构造成双链表，并返回链表头节点TreeNodeleft=Convert(root.left);//3.如果左子树链表不为空的话，将当前root追加到左子树链表if(left!=null){leftLast.right=root;root.left=leftLast;}leftLast=root;//当根节点只含左子树时，则该根节点为最后一个节点//4.将右子树构造成双链表，并返回链表头节点TreeNoderight=Convert(root.right);//5.如果右子树链表不为空的话，将该链表追加到root节点之后if(right!=null){right.left=root;root.right=right;}returnleft!=null?left:root;}7.字符串的排序题目描述

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

importjava.util.*;publicclassSolution{publicArrayList<String>Permutation(Stringstr){ArrayList<String>result=newArrayList<String>();if(str==null||str.length()==0){returnresult;}char[]chars=str.toCharArray();TreeSet<String>temp=newTreeSet<>();Permutation(chars,0,temp);result.addAll(temp);returnresult;}publicvoidPermutation(char[]chars,intbegin,TreeSet<String>result){if(chars==null||chars.length==0||begin<0||begin>chars.length-1){return;}if(begin==chars.length-1){result.add(String.valueOf(chars));}else{for(inti=begin;i<=chars.length-1;i++){swap(chars,begin,i);Permutation(chars,begin+1,result);swap(chars,begin,i);}}}publicvoidswap(char[]x,inta,intb){chart=x[a];x[a]=x[b];x[b]=t;}}