分治算法的題型以及與動态規劃的差別

動态規劃屬于是分治算法的一種，而不同的是分治算法在大部分情況下是自頂向下進行求解，将問題分解為各個小問題再合并，而動态規劃大部分是定義dp數組，求解小問題後進一步自底向上進行求解大問題。

分治算法步驟：

1>分解：将原問題分解為各個小問題。

2>求解：如果可以簡單的進行求解則解出來，否則再次進行1>分解。

3>合并：将各個子問題合并為原問題最終解。

動态規劃步驟：

1>狀态定義2>狀态轉移方程3>初始狀态4>傳回值

動态規劃的三個特征：1最優子結構（利用子問題最優解推導出原問題最優解）2無後效性（定義狀态轉移方程之後，隻關心它前面的狀态是什麼，不考慮它是怎麼推導出來的，并且後續的決策對目前狀态不會有任何的影響）3重複子問題（不同的決策階段，可能有重複的狀态）

劍指 Offer 33. 二叉搜尋樹的後序周遊序列

題目會輸入一個二叉搜尋樹的後序周遊數組。

根據二叉搜尋樹的性質，知道左結點一定小于根結點，右結點一定大于根結點。

根據後續周遊的性質，知道數組的最後一個結點必為根結點。

問題分解：

先取出數組最後一個值，得到根結點的值

循環周遊數組，指派一個變量i，來尋找數組當中第一個大于根結點的值

根據上面得到的下标i，數組分割為兩部分：0,i與i,len-1。由于二叉搜尋樹的性質，前部分必全部小于根結點的值，後部分必大于根結點的值，利用數組的every方法來判斷，如果不滿足則return false

遞歸求解各個小問題：

在遞歸時永遠先寫回溯條件，在函數第一行寫上判斷如果數組元素小于等于一則return true進行回溯。

在判斷完左右清單滿足後，用&&對左右清單進行一個遞歸，如果全部滿足則最終會return true；

/**
 * @param {number[]} postorder
 * @return {boolean}
 */
var verifyPostorder = function(postorder) {
    var len = postorder.length;
    if (len<=1){
        return true;
    }
    var root = postorder[len-1];
    var i = 0;
    while(i<len-1){
        if(postorder[i]<root)i++;
        else break;
    }
    var left = postorder.slice(0,i);
    var right = postorder.slice(i,len-1);
    if (left.every(function(x){return x<root})&&right.every(function(x){return x>root}))return verifyPostorder(left)&&verifyPostorder(right);
    else return false;
};
           

劍指 Offer 16. 數值的整數次方

該題最簡單的辦法是利用循環來一下一下的減少n的值并且一直執行x*x。

進階一點可以利用遞歸來進行求解，并且加上對n奇數偶數的判斷（此處運用位運算來判斷，如果n為奇數其與1做和運算則必不為0），如果為偶數則将x*x并且n/2（利用x^4 == (x^2)^2 ）

其終止條件是n==0 return1；

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function(x, n) {
    if (n<0)return 1/myPow(x,-n);
    if (n==0) return 1;

    if(n&1)return myPow(x,n-1)*x;//位運算與，末尾為0則不是偶數，為1則是偶數
    else return myPow(x*x,n/2)
};
           

後來才知道這其實是一種思想：快速幂

其時間複雜度可以實作對數複雜度（logn）相當于二分查找  1/2 ^ k *n = 1

寫成循環的方式将空間複雜度降到1：

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function(x, n) {
    if(x==1)return 1;
    var res = 1;
    if(n<0){
        x=1/x;
        n=-n;
    }
    while(n){
        if(n&1)res*=x;
        x*=x;
        n>>>=1;
    }
    return res;
};
           

劍指 Offer 07. 重建二叉樹

分解問題：

利用二叉樹前序周遊和中序周遊的規律（根左右，左根右），可以得出該圖：

 分解問題：

先擷取根結點記錄為root

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    if(!preorder.length||!inorder.length)return null;
    var root = preorder[0];
    var i=0;
    for(i;i<inorder.length;i++){
        if(inorder[i] == root) break;
    }
    var left_in_list = inorder.slice(0,i);
    var right_in_list = inorder.slice(i+1,inorder.length);
    var left_pre_list = preorder.slice(1,i+1);
    var right_pre_list = preorder.slice(i+1,preorder.length);
    var node = new TreeNode(root);
    node.left = buildTree(left_pre_list,left_in_list);
    node.right = buildTree(right_pre_list,right_in_list);
    return node;
};
           

尋找在中序周遊當中的root值，将兩個數組劃分為左右兩塊。

定義var node = new treenode(root);

對node.left 與right進行定義

合并問題：

在函數開始寫上遞歸回溯條件，當數組為空時return null；

在定義node.left 與 right的時候直接傳遞數組的左右兩塊

code：