分治政策-LeetCode解題java實作

2.1 基本概念

在計算機科學中，分治法是一種很重要的算法。字面上的解釋是“分而治之”，就是把一個複雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題…直到最後子問題可以簡單地直接求解，原問題的解即子問題的解的合并。這個技巧是很多高校算法的基礎，如排序算法（快速排序，歸并排序），傅裡葉變換（快速傅裡葉變換）…

最優子結構是依賴特定問題和子問題的分割方式而成立的條件。各個子問題具有最優解，就能求出整個問題的最優解，此時條件成立。

比如求廣州到北京的最短距離，建設這個路徑必經過中間的南京，那麼先把路徑分割為（廣州，南京）和（南京，北京）。分别求出子路徑的最短距離然後再連接配接，就可以得到廣州到北京的最短路徑。是以，尋找最短路徑的問題可以利用子路徑的最優解獲得整個問題的最優解。這樣就可以證明，最短路徑具有最優子結構。反之，如果不能利用子問題的最優解獲得整個問題的最優解，那麼這種問題就不具有最優子結構。

任何一個可以用計算機求解的問題所需要的計算時間都與其規模有關。問題的規模越小，越容易直接求解，解題所需要的計算時間也越少。例如，對于n個元素的排序問題，當n=1時，不需要任何計算。n=2時，隻要做一次比較即可排好序。n=3時隻要做3次比較即可，…。而當n較大時，問題就不那麼容易處理了。要想直接解決一個規模較大的問題，有時是相當困難的。

第一：數學歸納是使用分治思想

第二：分治思想不一定使用遞歸結構

遞歸結構是循環結構的一種，也是分治思想應用最多的一種程式結構，但是不一定要使用它。

第三：分治思想的核心是“如何分”

能夠把問題很棒的進行分解，也是一種能力和本事！也就是說把問題用分治法來進行解決，是算法的難點，也是重點！一方面需要經驗，另一方面也需要想象力！

2.2 思想政策

分治法的設計思想是：将一個難以直接解決的大問題，分割成一些規模較小的相同問題，以便各個擊破，分而治之。

分治政策是：對于一個規模為n的問題，若該問題可以容易地解決（比如說規模n較小）則直接解決，否則将其分解為k個規模較小的子問題，這些子問題互相獨立且與原問題形式相同，遞歸地解這些子問題，然後将各子問題的解合并得到原問題的解。這種算法設計政策叫做分治法。

如果原問題可以分割成k個子問題，1<k≤n，且這些子問題都可解并可利用這些子問題的解求出原問題的解，那麼這種分治法就是可行的。由分治法産生的子問題往往是原問題的較小模式，這就為使用遞歸技術提供了友善。在這種情況下，反複應用分支手段，可以是子問題與原問題類型一緻而其規模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導緻遞歸過程的産生。分治與遞歸像一對孿生兄弟，經常同時應用在算法設計之中，并由此産生許多高效算法。

2.3 适用場景

分治法所能解決的問題一般具有以下幾個特征：

1) 該問題的規模縮小到一定的程度就可以容易地解決

2) 該問題可以分解為若幹個規模較小的相同問題，即該問題具有最優子結構性質。

3) 利用該問題分解出的子問題的解可以合并為該問題的解；

4) 該問題所分解出的各個子問題是互相獨立的，即子問題之間不包含公共的子子問題。

第一條特征是絕大多數問題都可以滿足的，因為問題的計算複雜性一般是随着問題規模的增加而增加；

第二條特征是應用分治法的前提它也是大多數問題可以滿足的，此特征反映了遞歸思想的應用；

第三條特征是關鍵，能否利用分治法完全取決于問題是否具有第三條特征，如果具備了第一條和第二條特征，而不具備第三條特征，則可以考慮用貪心法或動态規劃法。

第四條特征涉及到分治法的效率，如果各子問題是不獨立的則分治法要做許多不必要的工作，重複地解公共的子問題，此時雖然可用分治法，但一般用動态規劃法較好。

2.4 基本步驟

分治法在每一層遞歸上都有三個步驟：

step1 分解：将原問題分解為若幹個規模較小，互相獨立，與原問題形式相同的子問題；

step2 解決：若子問題規模較小而容易被解決則直接解，否則遞歸地解各個子問題

step3 合并：将各個子問題的解合并為原問題的解。

它的一般的算法設計模式如下：

Divide-and-Conquer(P)

if |P|≤n0
then return(ADHOC§)
将P分解為較小的子問題 P1 ,P2 ,…,Pk
for i←1 to k
do yi ← Divide-and-Conquer(Pi) △ 遞歸解決Pi
T ← MERGE(y1,y2,…,yk) △ 合并子問題
return(T)

2.5 經典示例

二分搜尋

大整數乘法

Strassen矩陣乘法

棋盤覆寫

合并排序

快速排序

線性時間選擇

最接近點對問題

循環賽日程表

2.6 應用執行個體

很多算法的思維本質上都是分治思維方式，如二分搜尋、大整數乘法、合并排序、快速排序等。

執行個體：求x的n次幂

複雜度為O(lgn)的解法

int power(int x, int n)
{
    int result;
    if(n == 1)
        return x;
    if( n % 2 == 0)
        result = power(x, n/2) * power(x, n / 2);
    else
        result = power(x, (n+1) / 2) * power(x, (n-1) / 2);
 
    return result;
}

2.7 練習題目

2.7.1 搜尋二維矩陣II（#240）

public boolean searchMatrix(int[][] matrix, int target) {
            if (matrix == null || matrix.length == 0) {
                return false;
            }
            int shorterDim = Math.min(matrix.length, matrix[0].length);
            for (int i = 0; i < shorterDim; i++) {
                boolean verticalFound = binarySearch(matrix, target, i, true);
                boolean horizontalFound = binarySearch(matrix, target, i, false);
                if (verticalFound || horizontalFound) {
                    return true;
                }
            }

            return false;
        }

        public boolean binarySearch(int[][] matrix, int target, int start, boolean vertical) {
            int lo = start;
            int hi = vertical ? matrix[0].length - 1 : matrix.length - 1;
            while (hi >= lo) {
                int middle = (lo + hi) / 2;
                if (vertical) {
                    if (matrix[start][middle] == target) {
                        return true;
                    } else if (matrix[start][middle] < target) {
                        lo = middle + 1;
                    } else {
                        hi = middle - 1;
                    }
                } else {
                    if (matrix[middle][start] == target) {
                        return true;
                    } else if (matrix[middle][start] < target) {
                        lo = middle + 1;
                    } else {
                        hi = middle - 1;
                    }
                }
            }
            return false;
        }

簡單實作，時間複雜度（log(N+M)）

public boolean searchMatrix(int[][] matrix, int target) {
   // start our "pointer" in the bottom-left
    int row = matrix.length - 1;
    int col = 0;

    while (row >= 0 && col < matrix[0].length) {
        if (matrix[row][col] > target) {
            row--;
        } else if (matrix[row][col] < target) {
            col++;
        } else { // found it
            return true;
        }
    }

    return false;
}

2.7.2 求衆數(#169)

使用哈希表存儲元素出現的次數進行求解

public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                map.put(nums[i], map.get(nums[i])+1);
            } else {
                map.put(nums[i], 1);
            }
        }

        int half = nums.length>>1;
        for (Integer integer : map.keySet()) {
            if (map.get(integer) > half) {
                return integer;
            }
        }

        return 0;
    }

使用分治算法求解,摘自leetcode

class Solution {
    private int countInRange(int[] nums, int num, int lo, int hi) {
        int count = 0;
        for (int i = lo; i <= hi; i++) {
            if (nums[i] == num) {
                count++;
            }
        }
        return count;
    }

    private int majorityElementRec(int[] nums, int lo, int hi) {
        // base case; the only element in an array of size 1 is the majority
        // element.
        if (lo == hi) {
            return nums[lo];
        }

        // recurse on left and right halves of this slice.
        int mid = (hi-lo)/2 + lo;
        int left = majorityElementRec(nums, lo, mid);
        int right = majorityElementRec(nums, mid+1, hi);

        // if the two halves agree on the majority element, return it.
        if (left == right) {
            return left;
        }

        // otherwise, count each element and return the "winner".
        int leftCount = countInRange(nums, left, lo, hi);
        int rightCount = countInRange(nums, right, lo, hi);

        return leftCount > rightCount ? left : right;
    }

    public int majorityElement(int[] nums) {
        return majorityElementRec(nums, 0, nums.length-1);
    }
}

作者：LeetCode-Solution
連結：https://leetcode-cn.com/problems/majority-element/solution/duo-shu-yuan-su-by-leetcode-solution/
來源：力扣（LeetCode）
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

2.7.3 合并k個排序連結清單（#23）：

class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            if (null == lists || lists.length == 0) return null;
            return merge(lists, 0, lists.length - 1);
        }

        private ListNode merge(ListNode[] lists, int left, int right) {
            if (left == right) return lists[left];
            int middle = left + (right - left) / 2;
            ListNode leftSide = merge(lists, left, middle);
            ListNode rightSide = merge(lists, middle + 1, right);
            return mergeList(leftSide, rightSide);
        }

        private ListNode mergeList(ListNode leftSide, ListNode rightSide) {
            if (leftSide == null) return rightSide;
            if (rightSide == null) return leftSide;
            if (leftSide.val < rightSide.val) {
                leftSide.next = mergeList(leftSide.next, rightSide);
                return leftSide;
            } else {
                rightSide.next = mergeList(leftSide, rightSide.next);
                return rightSide;
            }
        }

    }

分治政策-LeetCode解題java實作

2.1 基本概念

2.2 思想政策

2.3 适用場景

2.4 基本步驟

2.5 經典示例

2.6 應用執行個體

2.7 練習題目

繼續閱讀

Java String.format方法的簡單使用

neo4j之cypher使用文檔

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

LeetCode OJ Binary Tree Right Side View

Effective Java 8:通用程式設計

leetcode809

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method

hdu7108哈希