1. 遞歸
2. 分治法/二分法

1. 遞歸

1.1 遞歸思路的主要小思想

主要分成三步

1. 定義一個與題意相關(guān)的函數(shù)，要知道這個函數(shù)作用，函數(shù)的參數(shù)以及函數(shù)的返回值
2. 要知道遞歸的最基礎(chǔ)的結(jié)束條件
3. 要讓函數(shù)往遞歸的結(jié)束條件靠近，一點點縮小參數(shù)的范圍，縮小之后，我們可以通過一些輔助的變量或者操作，使原函數(shù)的結(jié)果不變。我們要找到父遞歸函數(shù)和子遞歸函數(shù)的關(guān)系，找到對應(yīng)的等價關(guān)系式。

1.2 Leetcode實例

q21 合并兩個有序鏈表

    /**
     * 使用遞歸的思路:
     * 1. 首先思考這個函數(shù)的作用: 輸入兩個鏈表的首節(jié)點，返回回來兩個鏈表合并之后的首節(jié)點
     * 2. 函數(shù)基本返回條件是其中一個node為空時返回另一個node
     *
     * 流程是:
     * 1. 先將基礎(chǔ)的終止條件寫出來
     * 2. 然后比較兩個node的值，需要遞歸更新狀態(tài)調(diào)用子函數(shù)，
     *    例如如果l1.val < l2. val, 遞歸調(diào)用l1.next = mergeTwoListsTwo(l1.next, l2) （其實也相當(dāng)于更新狀態(tài)）
     * @param l1
     * @param l2
     * @return
     */
    public ListNode mergeTwoListsTwo(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        if (l1.val < l2.val){
            l1.next = mergeTwoListsTwo(l1.next,l2);
            return l1;
        }else {
            l2.next = mergeTwoListsTwo(l1,l2.next);
            return l2;
        }
    }

q101 對稱二叉樹

    /**
     * 關(guān)于二叉樹注意根節(jié)點是個特殊點
     *
     * 使用遞歸的思路
     * 1. 當(dāng)前樹是否對稱取決于其左右子節(jié)點是否和其相對稱的節(jié)點是否對稱
     * 2. 增加一層null的葉子節(jié)點
     * 3. 對稱的思想主要在體現(xiàn)在對比對應(yīng)的節(jié)點, 可以聯(lián)想有兩棵樹找對應(yīng)節(jié)點就比較簡單
     *
     * 所以要借助函數(shù)isMirror(TreeNode t1, TreeNode t2)
     * 函數(shù)的意義是輸入需要進(jìn)行比對的兩個對稱節(jié)點， 判斷該節(jié)點以及子節(jié)點是否滿足對稱的要求
     * @param root
     * @return
     */
    public boolean isSymmetricTwo(TreeNode root) {
        return isMirrorTwo(root, root);
    }

    /**
     * 使用遞歸的思路:
     * 1. 因為都為樹增加了一層null的葉子節(jié)點，所以基本條件是兩個節(jié)點都為空返回true，若只有一個節(jié)點為空返回false
     * 2. 然后比對當(dāng)前節(jié)點的value，對比對應(yīng)節(jié)點的子節(jié)點是否是對稱的(遞歸，更新狀態(tài))
     * @param t1
     * @param t2
     * @return
     */
    public boolean isMirrorTwo(TreeNode t1, TreeNode t2){
        if (t1==null && t2==null) return true;
        if (t1==null || t2==null) return false;

        return (t1.val == t2.val) &&
                (isMirrorTwo(t1.right, t2.left))&&
                (isMirrorTwo(t1.left, t2.right));
    }

q104 二叉樹的最大深度

    /**
     * 使用遞歸的思路:
     * 1. 當(dāng)前樹的高度是否左右子樹高度的最大值+1得到的，這里使用了遞歸
     * 2. 基本結(jié)束條件是如果節(jié)點為null返回0
     * @param root
     * @return
     */
    public int maxDepthTwo(TreeNode root){
        if (root == null) return 0;
        return Math.max(maxDepthTwo(root.left),maxDepthTwo(root.right))+1;
    }

q226 翻轉(zhuǎn)二叉樹

    /**
     * 使用遞歸的思想
     * 1. 當(dāng)前樹進(jìn)行反轉(zhuǎn)的條件是交換已經(jīng)反轉(zhuǎn)好的左右子節(jié)點的位置
     *
     * 這里的注意事項是:
     * 需要把遞歸完之后返回的根節(jié)點進(jìn)行交換
     */
    public TreeNode invertTreeTwo(TreeNode root){
        if (root==null) return root;
        /**
         * 這樣寫是不ok的，因為第一行的遞歸把root.left更新了，所以結(jié)果是錯的 = =
        root.left = invertTreeTwo(root.right);
        root.right = invertTreeTwo(root.left);*/
        TreeNode t1 = invertTreeTwo(root.right);
        TreeNode t2 = invertTreeTwo(root.left);
        root.left = t1;
        root.right = t2;
        return root;
    }

q236 二叉樹的最近公共祖先

    private TreeNode ans;

    public LowestCommonAncestorOfBinaryTree(){
        this.ans = null;
    }


    /**
     * 借助一個函數(shù)遍歷整顆樹的節(jié)點判斷該節(jié)點的子節(jié)點或者本身是不是包含目標(biāo)節(jié)點
     * @param root
     * @param p
     * @param q
     * @return 返回公共的父節(jié)點
     */
    public TreeNode lowestCommonAncestorTwo(TreeNode root, TreeNode p, TreeNode q) {
        recurseTreeTwo(root,p,q);
        return ans;
    }

    /**
     * 使用遞歸的思想
     * 判斷當(dāng)前節(jié)點的子節(jié)點們或者本身是不是包含目標(biāo)節(jié)點的前提是自己的左右子樹是不是也同樣符合此條件
     *
     * 并且在遍歷的過程中如果發(fā)現(xiàn)有一個節(jié)點left + right + mid >= 2， 該節(jié)點就是我們目標(biāo)要找的公共祖先節(jié)點
     * @param currentNode
     * @param p
     * @param q
     * @return 當(dāng)前節(jié)點的子節(jié)點或者本身節(jié)點是不是就包含著目標(biāo)節(jié)點
     */
    public boolean recurseTreeTwo(TreeNode currentNode, TreeNode p, TreeNode q){
        if (currentNode == null) return false;

        int left = recurseTreeTwo(currentNode.left,p,q)?1:0;
        int right = recurseTreeTwo(currentNode.right,p,q)?1:0;

        int mid = (currentNode == p || currentNode == q)?1:0;

        if (left+right+mid >=2) this.ans =currentNode;

        return (left+right+mid)>0;
    }

這道題除了遞歸還有一種比較簡單的思路:
首先使用深度優(yōu)先遍歷遍歷整棵樹，在遍歷的過程中使用map記錄每個節(jié)點的父子關(guān)系，map的key是子節(jié)點，value是對應(yīng)的父節(jié)點。
之后使用hashset記錄其中一個節(jié)點的所有祖先節(jié)點，然后遍歷另一個節(jié)點的祖先節(jié)點直到找到兩個祖先節(jié)點集合的交集就是找到了目標(biāo)結(jié)果。

2. 分治法/二分法

2.1 分治法與二分法的適用場景和基本思想

1. 分治法

分治法的基本思想是：把一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個擊破。

每一層遞歸上有三個步驟：

• 分解：將原問題分解為若干個規(guī)模較小，相互獨立并且與原問題形式相同的子問題
• 解決：若子問題規(guī)模較小且容易被解決則直接解決，否則遞歸地解決各個子問題
• 合并：合并子問題的解為原問題的解

2. 二分法

使用二分法的場景通常是數(shù)組中元素是有序的，然后根據(jù)中間元素的值和目標(biāo)值進(jìn)行比對，判斷下一步應(yīng)該在哪一半（舍棄另一半）查找，從而使得時間復(fù)雜度在O(log(n)).

二分法重點在于：

• 決定查找的邊界，左閉右開或者左閉右閉，根據(jù)查找的區(qū)間來決定邊界的更新以及循環(huán)結(jié)束的條件（區(qū)間中至少有一個元素或者已經(jīng)找到了臨界值）
• 要確定自己二分查找的結(jié)果的臨界條件

2.2 Leetcode實例

q23 合并K個排序鏈表

    /**
     * 按分治的思路進(jìn)行求解
     * 1. 這個已經(jīng)細(xì)分成非常小的list了，可以將合并k個list轉(zhuǎn)換成先進(jìn)行小范圍的兩兩合并
     * 2. 兩兩合并之后，擴(kuò)大list之間間隙，繼續(xù)進(jìn)行兩兩合并，這時候兩兩一組的數(shù)量縮小了一半
     * 3. 重復(fù)上述步驟，直到間隙超過了兩個數(shù)組之間的長度
     */
    public ListNode mergeKListsTwo(ListNode[] lists) {
        int interval = 1;
        while (interval < lists.length){
            for (int i=0;i<lists.length-interval;i+=2*interval){
                lists[i] = merge2List(lists[i], lists[i+interval]);
            }
            interval *=2;
        }

        return lists.length>0?lists[0]:null;
    }

    public ListNode merge2List(ListNode l1, ListNode l2){
        ListNode head = new ListNode(0);
        ListNode point = head;

        while (l1 != null && l2 != null){
            if (l1.val <= l2.val){
                point.next = l1;
                l1 = l1.next;
            }else {
                point.next = l2;
                l2 = l2.next;
            }
            point = point.next;
        }

        if (l1 == null){
            point.next = l2;
        } else {
            point.next = l1;
        }

        return head.next;
    }

這道題還有個思路我覺得很好：
就是首先通過把所有l(wèi)ist之中首元素加入到PriorityQueue之中，維護(hù)一個大小小于等于所有l(wèi)ists大小的隊列，然后循環(huán)把最小的元素pop出來，然后如果最小的那個元素的下一個不為空，就把他放入到隊列之中，重復(fù)整個流程直到Queue為空就得到了答案。

q33 搜索旋轉(zhuǎn)排序數(shù)組

    /**
     * 想要讓時間復(fù)雜度是O(logN)，要使用二分的方式進(jìn)行查找
     * 二分的特點在于根據(jù)區(qū)間特點和目標(biāo)值，可以確定目標(biāo)節(jié)點落在哪一半的區(qū)間上，
     * 每經(jīng)歷一次查找，要查找區(qū)間的長度就會縮短一半
     *
     * 二分查找的時候必須要注意尋找的區(qū)間和目標(biāo)值
     * 這道題用的區(qū)間是左閉合右閉合的區(qū)間，所以保證區(qū)間中有元素的條件是low<=high
     * 在遍歷的過程中判斷元素看target在哪個區(qū)間，然后縮小區(qū)間范圍
     *
     * 這道題的思路是:
     * 1. 在每次劃分的時候其實都是可能劃分成一個有拐點的區(qū)間和一個正常的區(qū)間
     * 2. 要判斷在這兩種區(qū)間中target出現(xiàn)時具備的條件
     * @param nums 輸入的原數(shù)組
     * @param target 在原數(shù)組中要查找的目標(biāo)值
     * @return 目標(biāo)值在數(shù)組中的index，沒找到返回-1
     */
    public static int searchTwo(int[] nums, int target){
        if (nums.length == 0) return -1;
        int i=0, j= nums.length-1;
        while (i<=j){
            int mid = (i+j)/2;
            if (nums[mid] == target){
                return mid;
            } else if (nums[mid] < nums[i]){ //說明區(qū)間的左半邊有拐點
                if (target<nums[i] && target>nums[mid]){ //target落到右邊連續(xù)區(qū)間的特點
                    i = mid+1;
                }else {
                    j = mid-1;
                }
            } else {//說明區(qū)間左邊是連續(xù)的
                if (target>=nums[i] && target<nums[mid]){
                    j=mid-1;
                }else {
                    i = mid+1;
                }
            }
        }

        return -1;
    }

q34 在排序數(shù)組中查找元素的第一個和最后一個位置

    public int[] searchRangeTwo(int[] nums, int target) {
        int[] res = {-1,-1};
        int leftIdx = findLeftestIndex(nums,target);
        if (leftIdx == nums.length || nums[leftIdx] != target){
            return res;
        }

        res[0] = leftIdx;
        res[1] = findRightestIndex(nums, target)-1;
        return res;
    }

    /**
     * 使用二分法查找到最左邊與目標(biāo)值一樣的元素
     *
     * 所選擇的區(qū)間是左閉右開的
     * 結(jié)束的條件是l=r, 也就是區(qū)間之中沒有元素, 看r最后停在哪里
     *
     * 1. 當(dāng)mid的值是>=目標(biāo)值的時候，右半邊的區(qū)域其實也不用查找了，但是r所在的位置可能是與目標(biāo)值相等的
     *    但是需要看看左半邊還有沒有和目標(biāo)值一樣的，如果沒有就會到l=r的結(jié)束條件，返回結(jié)果
     * 2. 當(dāng)mid值如果小于目標(biāo)值，肯定左半邊都舍棄掉了，從mid+1開始查找
     * @param nums
     * @param target
     * @return
     */
    public int findLeftestIndex(int[] nums, int target){
        int left =0, right = nums.length;
        while (left<right){
            int mid = (left+right)/2;
            if (nums[mid]>=target){
                right = mid;
            }else {
                left = mid+1;
            }
        }
        return left;
    }

    /**
     * 使用二分查找法找到第一個比目標(biāo)值大的元素
     *
     * 所選擇的區(qū)間是左閉右開
     * 結(jié)束的條件也是l=r, 也就是區(qū)間之中沒有元素, 看r最后停在哪里
     *
     * 1. 當(dāng)mid的值是>目標(biāo)值的時候，右半邊的區(qū)域其實也不用查找了，但是r所在的位置可能是第一個比目標(biāo)值大的
     * 但是需要看看左半邊還有沒有比目標(biāo)值大的元素，如果沒有就會到l=r的結(jié)束條件，返回結(jié)果
     * 2. 當(dāng)mid值如果小于目標(biāo)值，肯定左半邊都舍棄掉了，從mid+1開始查找
     * @param nums
     * @param target
     * @return
     */
    public int findRightestIndex(int[] nums, int target){
        int left =0, right = nums.length;
        while (left<right){
            int mid = (left+right)/2;
            if (nums[mid]>target){
                right = mid;
            }else {
                left = mid+1;
            }
        }
        return left;
    }