一、算法分析基礎
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..動態規劃發
將待求解的問題分若干個相互練習的子問題，先求解子問題，然后從這些子問題的解得到原問題的解；對于重復出現的子問題，只在第一次遇見時對它進行求解，并把答案保存起來，讓以后再次遇到時直接引用答案，不必重新求解。
例：多段圖問題
例：連續子數組的最大和
分析：
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
int res = array[0]; //記錄當前所有子數組的和的最大值
int max=array[0]; //包含array[i]的連續數組最大值
for (int i = 1; i < array.length; i++) {
max=Math.max(max+array[i], array[i]);
res=Math.max(max, res);
}
return res;
}
}4.回溯法
基本思想：
1）針對所給的問題，定義問題的解空間；
2）確定易于搜索的解空間結構；
3）以深度優先方式搜索解空間，并在搜索的過程中用剪枝函數避免無效的搜索。
例：批處理作業問題、0/1背包問題
5.分支限界法
常見的兩種分支限界法框架：
1）隊列式（FIFO）分支限界法：按照隊列先進先出的原則選取下一個結點為擴展節點；
2）優先隊列式分支限界法：按照優先隊列中規定的優先級選取優先級最高的節點成為當前的擴展節點。
分支限界法的算法步驟：
1）針對所給的問題，定義問題的解空間
6、遞歸和循環
遞歸有簡潔的優點，但是它同時也有顯著的缺點。遞歸由于是函數調用自身，而函數調用是有時間和空間消耗的：每一次函數調用，都需要在內存棧中分配空間以保存參數、返回地址和環境變量，而且往棧里面壓入數據和彈出數據都需要時間。
除了效率之外，遞歸還有可能引起更為嚴重的問題：調用棧溢出。每一次函數調用在內存棧中分配空間，而每個進程的棧的容量是有限的。當遞歸調用的層級太多，就會超出棧的容量，從而導致調用棧溢出。
例1:1+2+...+n
int AddFromToN_recursive(int n){//遞歸方法實現
return n<=0 ? 0 : n + AddFromToN_recursive(n-1);
}
int AddFromToN_Interative( int n){
int result=0;
for(int i=1;i<n;++i)
result+=i;
return result;
}要求不能使用乘除法、for、while、if、else、switch、case等關鍵字及條件判斷語句（A?B:C）。
class Solution {
public:
int Sum_Solution(int n) {
bool a[n][n+1];
return sizeof(a)>>1;
}
}; 1）斐波那契數列
公式：f(n)=｛ 0 n=0; 1 n=1; f(n-1)+f(n-2) n>1｝
實用解法：
long long Fibonacci(unsigned n)
{
int result[2]={0,1};
if(n<2)
{
return result[n];
}
long long fibNMinusOne=1;
long long fibNMinusTwo=0;
long long fibN=0;
for(unsigned int i=2;i<=n;++i)
{
fibN=fibNMinusOne+fibNMinusTwo;
fibNMinusTwo=fibNMinusOne;
fibNMinusOne=fibN;
}
return fibN;
}題目描述：
一只青蛙一次可以跳上1級臺階，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的臺階總共有多少種跳法。
class Solution {
public:
/**
說明：
1）這里的f(n) 代表的是n個臺階有一次1,2,...n階的 跳法數。
2）n = 1時，只有1種跳法，f(1) = 1
3) 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)
*/
int jumpFloorII(int number) {
int target = number;
if (target <= 0) {
return -1;
} else if (target == 1) {
return 1;
} else {
return 2 * 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)
√ | √ | ||||||
× | × |
代碼：
public class Solution {
public int RectCover(int target) {
if(target <= 1){
return 1;
}
if(target*2 == 2){
return 1;
}else if(target*2 == 4){
return 2;
}else{
return RectCover((target-1))+RectCover(target-2);
}
}
}
public class Solution {
public int RectCover(int target) {
if(target==0)
return 0;
if(target==1)
return 1;
if(target==2)
return 2;
int a=1,b=2,c=0;
for(int i=2;i<target;i++){
c=a+b;
a=b;
b=c;
}
return c;
}
}2）漢諾塔問題
int i; //記錄步數
//i表示進行到的步數,將編號為n的盤子由from柱移動到to柱(目標柱)
void move(int n,char from,char to){
printf("第%d步:將%d號盤子%c---->%c\n",i++,n,from,to);
}
//漢諾塔遞歸函數
//n表示要將多少個"圓盤"從起始柱子移動至目標柱子
//start_pos表示起始柱子,tran_pos表示過渡柱子,end_pos表示目標柱子
void Hanio(int n,char start_pos,char tran_pos,char end_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個盤子
//此時借助原來的起始柱作為過渡柱(因為起始柱已經空了)
}
}題目描述
統計一個數字在排序數組中出現的次數。
思路：
可以遍歷
public class Solution {
public int GetNumberOfK(int [] array , int key){
/**
* 數組長度魯棒性檢查
*/
if(array.length == 0){
return 0;
}
int firstK = getFirstK(array, key, 0, array.length-1);
int lastK = getLastK(array, key, 0, array.length-1);
if(firstK != -1 && lastK != -1){
return lastK - firstK + 1;
}
return 0;
}
//遞歸寫法
private int getFirstK(int [] array , int k, int start, int end){
/**
* 魯棒性檢查
*/
if(start > end){
return -1;
}
int mid = (start + end) >> 1;
if(array[mid] > k){
return getFirstK(array, k, start, mid-1);
}else if (array[mid] < k){
return getFirstK(array, k, mid+1, end);
}else if(mid-1 >=0 && array[mid-1] == k){
return getFirstK(array, k, start, mid-1);
}else{
return mid;
}
}
//循環寫法
private int getLastK(int [] array , int k, int start, int end){
/**
* 魯棒性檢查
*/
int length = array.length;
int mid = (start + end) >> 1;
while(start <= end){
if(array[mid] > k){
end = mid-1;
}else if(array[mid] < k){
start = mid+1;
}else if(mid+1 < length && array[mid+1] == k){
start = mid+1;
}else{
return mid;
}
mid = (start + end) >> 1;
}
return -1;
}
}/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) :
* val(x), next(NULL) {
* }
* };
*/
import java.util.Stack;
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
Stack<Integer> stack = new Stack<>();
while (listNode != null) {
stack.push(listNode.val);
listNode = listNode.next;
}
ArrayList<Integer> list = new ArrayList<>();
while (!stack.isEmpty()) {
list.add(stack.pop());
}
return list;
}
}題目描述
輸入一棵二叉樹，求該樹的深度。從根結點到葉結點依次經過的結點（含根、葉結點）形成樹的一條路徑，最長路徑的長度為樹的深度。
思路
第一種方法是使用遞歸方法執行，第二種方法是使用循環（里面使用了隊列）
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
/**
* 遞歸寫法
* @return
*/
public int TreeDepth(TreeNode root) {
if(root==null){
return 0;
}
int nLeft=TreeDepth(root.left);
int nRight=TreeDepth(root.right);
return nLeft>nRight?(nLeft+1):(nRight+1);
}
/**
* 非遞歸寫法：層次遍歷
* @return
*/
public int TreeDepth3(TreeNode pRoot)
{
if(pRoot == null){
return 0;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(pRoot);
int depth = 0, count = 0, nextCount = 1;
while(queue.size()!=0){
TreeNode top = 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++;
}
}
return depth;
}
}輸入一棵二叉搜索樹，將該二叉搜索樹轉換成一個排序的雙向鏈表。要求不能創建任何新的結點，只能調整樹中結點指針的指向。
遞歸版
解題思路：
1.將左子樹構造成雙鏈表，并返回鏈表頭節點。
2.定位至左子樹雙鏈表最后一個節點。
3.如果左子樹鏈表不為空的話，將當前root追加到左子樹鏈表。
4.將右子樹構造成雙鏈表，并返回鏈表頭節點。
5.如果右子樹鏈表不為空的話，將該鏈表追加到root節點之后。
6.根據左子樹鏈表是否為空確定返回的節點。
public TreeNode Convert(TreeNode root) {
if(root==null)
return null;
if(root.left==null&&root.right==null)
return root;
// 1.將左子樹構造成雙鏈表，并返回鏈表頭節點
TreeNode left = Convert(root.left);
TreeNode p = left;
// 2.定位至左子樹雙鏈表最后一個節點
while(p!=null&&p.right!=null){
p = p.right;
}
// 3.如果左子樹鏈表不為空的話，將當前root追加到左子樹鏈表
if(left!=null){
p.right = root;
root.left = p;
}
// 4.將右子樹構造成雙鏈表，并返回鏈表頭節點
TreeNode right = Convert(root.right);
// 5.如果右子樹鏈表不為空的話，將該鏈表追加到root節點之后
if(right!=null){
right.left = root;
root.right = right;
}
return left!=null?left:root;
}
改進遞歸版
解題思路：
思路與方法二中的遞歸版一致，僅對第2點中的定位作了修改，新增一個全局變量記錄左子樹的最后一個節點。
// 記錄子樹鏈表的最后一個節點，終結點只可能為只含左子樹的非葉節點與葉節點
protected TreeNode leftLast = null;
public TreeNode Convert(TreeNode root) {
if(root==null)
return null;
if(root.left==null&&root.right==null){
leftLast = root;// 最后的一個節點可能為最右側的葉節點
return root;
}
// 1.將左子樹構造成雙鏈表，并返回鏈表頭節點
TreeNode left = Convert(root.left);
// 3.如果左子樹鏈表不為空的話，將當前root追加到左子樹鏈表
if(left!=null){
leftLast.right = root;
root.left = leftLast;
}
leftLast = root;// 當根節點只含左子樹時，則該根節點為最后一個節點
// 4.將右子樹構造成雙鏈表，并返回鏈表頭節點
TreeNode right = Convert(root.right);
// 5.如果右子樹鏈表不為空的話，將該鏈表追加到root節點之后
if(right!=null){
right.left = root;
root.right = right;
}
return left!=null?left:root;
}輸入一個字符串,按字典序打印出該字符串中字符的所有排列。例如輸入字符串abc,則打印出由字符a,b,c所能排列出來的所有字符串abc,acb,bac,bca,cab和cba。
輸入一個字符串,長度不超過9(可能有字符重復),字符只包括大小寫字母。
import java.util.*;
public class Solution {
public ArrayList<String> Permutation(String str) {
ArrayList<String> result = new ArrayList<String>() ;
if(str==null || str.length()==0) { return result ; }
char[] chars = str.toCharArray() ;
TreeSet<String> temp = new TreeSet<>() ;
Permutation(chars, 0, temp);
result.addAll(temp) ;
return result ;
}
public void Permutation(char[] chars, int begin, 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(int i=begin ; i<=chars.length-1 ; i++) {
swap(chars, begin, i) ;
Permutation(chars, begin+1, result);
swap(chars, begin, i) ;
}
}
}
public void swap(char[] x, int a, int b) {
char t = x[a];
x[a] = x[b];
x[b] = t;
}
}免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
