先說一下全排列：

對于R={r1,r2,…,rn}，進行n個元素的全排列，設Ri=R – {ri}。結合X元素的全排列記為Perm(X)，(ri)Perm(X)表示在全排列Perm(X)的每個排列前面加上前綴ri的得到的序列。R的全排列可歸納定義如下：

n=1時，Perm(R)=(r)，其中r是R中的唯一元素；

n>1時，Perm(R)由(r1)Perm(R1), (r2)Perm(R2),…, (rn)Perm(Rn)構成。

顯然，部分排列，只要控制遞歸結束條件即可。

 

再說組合：

組合與排列相比，忽略了元素的次序，因此我們只需將元素按編號升序排列（或則其他的規則）即可。
代碼如下：

public class Main {
    
    static int count;
    public static void main(String[] args) {
        int a[] = {1, 2, 3, 4};
        count = 0;
        permutation(a, 0, 4);
        System.out.println("count=" + count);
        
        count = 0;
        combination(a, 0, 3, 0);
        System.out.println("count=" + count);
    }
    static void combination(int a[], int nowp, int m, int left){//zuhe
        /**//*
         * 求a[]中m個元素的組合
         * nowp表示當前已經組合好的元素的個數
         * left，只能選擇編號為left和它之后的元素 進行交換
         */
        if(nowp == m){
            count++;
            for(int i = 0; i < m; i++){
                System.out.print(a[i] + " ");
            }
            System.out.println();
        }
        else{
            for(int i = left; i < a.length; i++){
                swap(a, nowp, i);
                combination(a, nowp + 1, m, i + 1);
                swap(a, nowp, i);
            }
        }
    }
    static void permutation(int a[], int nowp, int m){// pailie
        /**//*
         * 求a[]m個元素的排列
         * nowp，當前已經排列好的元素的個數
         */
        
        if(nowp == m){
            count++;
            for(int i = 0; i < m; i++){
                System.out.print(a[i] + " ");
            }
            System.out.println();
        }
        else{
            for(int i = nowp; i < a.length; i++){
                swap(a, i, nowp);
                permutation(a, nowp + 1, m);
                swap(a, i, nowp);
            }
        }
    }
    static void swap(int a[], int n, int m){
        int t = a[n];
        a[n] = a[m];
        a[m] = t;
    }

}

題意：

給定兩個非負數，可以用較小那個數的任意正整數倍數去減較大那個數，但要保證結果非負。兩個人輪流操作，結果中先出現0的那個人獲勝。

 

第一次做博弈題，不知如何下手。這里認真分析一下。

 

假設兩個數a b，他們的大小關系無非是a>b,a<b,a==b中的一種，對本題二樣前兩種其實是同一種情況，第三種情況時結果已經出來了（此時輪到誰誰獲勝）。

 

我們再來討論a>b（a<b）的情況，又可細分為：

b<a<2 * b (1)

a == 2 * b (2)

a >2*b (3)

對情況（1），選手沒得選，只能用較小的樹去減較大的數，下一個狀態一定是b，a%b。也就是說這種狀態的出現不會影響最終結果。

情況（2），顯然，也可以結束游戲了，當前選手贏了。

情況（3），此時選手可以決定下一個狀態是下面狀態中的一種：

a-b, b

a-2*b, b

a-3*b, b

.

.

.

a%b+b, b （k-1）

b, a%b （k）

由于兩個選手必須輪流操作，因此，兩相鄰的狀態的輸贏結果一定相反。而此時，選手恰恰可以決定是到狀態（k-1）還是到狀態（k）（狀態（k-1）的下一個狀態一定是狀態（k），因為情況（1）），也就是說此時選手能決定自己的輸贏。

 

綜上我們可以得到如下結論

出現下述情況之一的就可斷定當前選手獲勝：

1.a==b

2.a>=2*b

 

細節：如果一開始輸入數據為a，0，本題認為Ollie wins

 

     摘要: 最大值 TimeLimit: 1000MS  MemoryLimit: 65536 Kb Totalsubmit: 161   Accepted: 4   Description Little Ming很喜歡訓練自己的快速讀能力，他最近找到一種新的考驗并訓練快速讀能力的方法，在一行具...  閱讀全文 括號的兩種不同表示間的轉換。
解題思路比較偷懶：先將括號恢復成我們喜歡看的形式，然后再轉換成w型的表示方式。
題意：
求給定矩陣的最大子矩陣和。
先來回顧一下一維的最大子段和問題：
給定一個序列a[n]，求a[n]的最大子段和。
DP的遞推公式為b[j] = max{b[j - 1] + a[j], a[j]}. 其中b[j]表示a[n]中包含b[j]的最大子段和。時間復雜度為O(n)
對于二維矩陣而言，我們可以通過把多行壓縮（按列求和）成一行的方式將問題轉換為一維。
行壓縮時枚舉復雜度為O(N^2)。因此整個求解過程的時間復雜度為O(N^3)。


題意：找出矩陣中的最長下降序列的長度。
解題思路：
1.回溯，時間復雜度，指數級別。這是一種很容易想到的做法，不過會超時。
2.動態規劃，時間復雜度O(N^2)。相信我們都學過一維的最長上升子序列問題，這一題是一維的變形，我們只需稍加轉換就可以轉換為一維的。
先來回想一下一維的最長上升子序列的做法：對一個給定的節點p，我們只需枚舉p前面的所有節點的最長上升子序列的長度，用p前面的節點的長度去試圖更新p的長度即可。
我們如何將本題轉化為一維的問題呢？我們只需將矩陣中的所有點按照他的high排序，然后按照一維的處理即可。只不過p前面的節點在更新p時還要考慮他們在矩陣中的相對位置，因為只有跟p相鄰的四個點才有可能去更新p點的長度。
     摘要: 題意：按照指定格式輸出目錄樹。要求同一層下的file要按文件名排序。解題步驟：1.用deep記錄當前目錄深度，遇到dir，deep++，遇到] deep--2.用strlist記錄所有未輸出的file，用棧stack記錄當前目錄下的file表的開始下標。遇到]或者*則輸出當前目錄下的所有file，并從strlist中刪除，相應的下標出棧(stack). 代碼Code highlighting p...  閱讀全文      摘要: 題意：對比連個圖是否相同。相同的條件是A圖中每個連通的區域都在B圖中有一塊相同的區域與之對應。經過旋轉后對應也可以。解題思路：思路一：暴力式。遍歷并存儲A圖中所有聯通的區域，然后在B中逐個尋找與之對應的圖形。思路二：等價轉化式。比較兩個圖中對應點的“連通度”是否相同。相同輸出YES。空白點的連通度為0，空白點的連通度為它所在行和列與之相連的非空白點的個數。方式二非常巧妙，將...  閱讀全文      摘要: 題意：字處理程序檢查輸入的單詞是否正確。若不正確，則按照規則在字典中找與該單詞相近的單詞。解題思路：按照題目給出的規則模擬。要點：要注意查找效率，遍歷會超時。此處用的是TreeMap，查找效率log2(N)。 代碼Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.c...  閱讀全文