26.二叉搜索樹與雙向鏈表

輸入一棵二叉搜索樹，將該二叉搜索樹轉(zhuǎn)換成一個排序的雙向鏈表。
要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只能調(diào)整樹中結(jié)點(diǎn)指針的指向。

由于二叉搜索樹已經(jīng)是排序好的了，因此我們可以采用中序遍歷的方式，對每個結(jié)點(diǎn)改變指針的方向

二叉搜索樹

我們需要用兩個輔助指針，一個pre來記錄中序遍歷情況下的上一個結(jié)點(diǎn)的位置，例如4->6->8->10->11->12->13，然后一個固定好的指針head來標(biāo)記頭結(jié)點(diǎn)的位置，例如4.
代碼如下

public class Solution {
    private TreeNode pre = null;
    private TreeNode head = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        mid_order(pRootOfTree);
        return head;
    }
    //原函數(shù)有返回值，我們在這里遞歸最好構(gòu)造一個無返回值類型的函數(shù)
    public void mid_order(TreeNode node){
        if(node==null){
            return ;
        }
        /*
        對于此處中序遍歷遞歸看不太清的可以一個一個代入進(jìn)行分析
        從下面的mid_order(node.left)一句中，其實就是不斷往左子節(jié)點(diǎn)遞歸
        遞歸到什么時候結(jié)束呢，10->6->4->null
        ok，到4.left的時候直接返回，那么此時node為4，開始執(zhí)行下面的語句
        */
        mid_order(node.left);
        //先將node的左節(jié)點(diǎn)指向pre，例如此時為4，那么4指向null
        node.left = pre;
        //下面這句話全局只有一次不生效，那就是最原始的時候pre==null
        if(pre!=null){
            pre.right = node;
        }
        //然后將pre移動到node的位置，例如從null移動到4，從4移動到6....
        //亦可以看做鏈表結(jié)點(diǎn)往后移動一個
        pre = node;
        //下面這句話全局只有一次生效，那就是不斷的遞歸到4這個初始結(jié)點(diǎn)的時候
        //相當(dāng)于找到了頭結(jié)點(diǎn)了，以后再也不會進(jìn)入這個if語句了
        if(head==null){
            head = node;
        }
        //然后進(jìn)入node.right
        //為什么這樣的順序是中序遍歷呢？
        //可以想象，在上面node等于6的時候，我們先執(zhí)行了mid_order(6.left)相關(guān)的操作
        //此時pre在4，我們執(zhí)行4,6連接的操作，然后將pre移動到6
        //等于一系列跑完了，再執(zhí)行mid_order(6.right),即此時要進(jìn)入8這個結(jié)點(diǎn)的操作了
        //后面等8跑完了，就返回到10了，10的10.right執(zhí)行的時候也會先遞歸到11
        //所以這樣一步步分析，都是順利成章到的利用遞歸實現(xiàn)中序遍歷了。
        mid_order(node.right);
    }
}

27.字符串的排列

輸入一個字符串,按字典序打印出該字符串中字符的所有排列。
例如輸入字符串a(chǎn)bc,則打印出由字符a,b,c所能排列出來的所有字符串a(chǎn)bc,acb,bac,bca,cab和cba。

這個題是個典型的回溯法，說白了就相當(dāng)于一個個試，例如“abc”的所有組合，怎么試呢，就是先把a(bǔ)放在第一個，然后再考慮后面的bc，后面的b、c有bc和cb兩種，拼接在a后面，就是abc和acb兩種了。
代碼如下

import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
    //定義一個存儲String的ArrayList
    private ArrayList<String> ret = new ArrayList<>();
    public ArrayList<String> Permutation(String str) {
        if(str.length()==0){
            return ret;
        }
        //將str轉(zhuǎn)化為字符數(shù)組
        char[] chars = str.toCharArray();
        //按chars中的字符的ASCII碼的進(jìn)行字典排序
        Arrays.sort(chars);
        //使用回溯函數(shù)，創(chuàng)建兩個新的變量
        //一個是布爾數(shù)組，用以表示chars中對應(yīng)位置的字符是否已經(jīng)被使用過
        //一個是StringBuilder類，用來實時的存儲字符串
        backtracking(chars,new boolean[chars.length],new StringBuilder());
        return ret;
        
    }
    //定義一個無返回值類型的回溯函數(shù)
    public void backtracking(char[] chars,boolean[] hasUsed,StringBuilder s){
        //當(dāng)臨時變量s的長度等于字符數(shù)組的長度的時候，證明已經(jīng)組裝完成了一個字符串
        //則，此時把這個字符串加入到最后的結(jié)果中，然后返回退出本次遞歸
        if(s.length()==chars.length){
            ret.add(s.toString());
            return;
        }
        //對字符數(shù)組chars中的所有字符進(jìn)行遍歷
        for(int i=0;i<chars.length;i++){
            //如果這個字符被用過了，那么循環(huán)繼續(xù)，這一步是很關(guān)鍵的
            if(hasUsed[i]){
                continue;
            }
            //這句if語句是確保不會重復(fù)
            //1.i!=0是為了chars[i-1]不為空
            //當(dāng)chars[i]==chars[i-1]時，有可能會發(fā)生重復(fù)
            /*!hasUsed[i-1]即hasUsed[i-1]為false時，可以嘗試去理解
              當(dāng)前元素等于上一個元素，而且上一個元素沒有被用過，證明上一個元素是經(jīng)歷過回溯的
              例如有兩個a,即a1,a2
              我們先組合過一次a1a2了，然后通過回溯，使得a1變成了未使用過的狀態(tài)
              假設(shè)我們此時再組合a2a1，在外在看來，實際上還是aa，這就會造成重復(fù)，
              所以當(dāng)當(dāng)前元素等于上一個元素，且上一個元素是沒有被使用的狀態(tài)時，我們就跳過本次循環(huán)
              
            */
            if(i!=0&&chars[i]==chars[i-1]&&!hasUsed[i-1]){
                continue;
            }
            //然后將當(dāng)前元素加入到s中，且將當(dāng)前元素標(biāo)記為已經(jīng)使用過的狀態(tài)
            s.append(chars[i]);
            hasUsed[i]=true;
            //然后使用回溯函數(shù)進(jìn)行遞歸
            backtracking(chars,hasUsed,s);
            //然后將s的最后一個元素進(jìn)行移除，且將當(dāng)前的元素標(biāo)記為未使用
            s.deleteCharAt(s.length()-1);
            hasUsed[i]=false;
            
        }
        
    }
}

這里用到了一個hasUsed數(shù)組來標(biāo)記字符是否被使用過，而且在回溯函數(shù)中每次的參數(shù)都是chars，其實關(guān)鍵就是這個hasUsed，與之前用python寫的例如使用了b之后，將ac拼接作為新的數(shù)組來輸入到回溯函數(shù)中不同，這里的做法是，用hasUsed來標(biāo)記某個元素是否被使用過，即每次進(jìn)入遞歸的時候都需要完整的對一個長度為chars.length的chars字符數(shù)組進(jìn)行遍歷；
這么解釋起來可能有點(diǎn)抽象，用一個簡單的實例來證明，我用0代表沒被使用過，1代表被使用過，從最開始的[a0,b0,c0]來跑遞歸函數(shù)；
在for循環(huán)中，當(dāng)i=0時，a被使用過了，立馬進(jìn)入了遞歸，即此時chars變成了[a1,b0,c0]，可以觀察到在進(jìn)入了這一層遞歸的時候for循環(huán)依然要從下標(biāo)為0的位置開始跑，只是此時a的狀態(tài)為1了，則跳過本次循環(huán)，進(jìn)入到b，b未被使用，則chars被改為了[a1,b1,c0]，然后順利成章的進(jìn)入到了第二層循環(huán)的循環(huán)，此時abc出爐，然后一個回溯，將c標(biāo)記為0，然后返回后b也被標(biāo)記為0，則進(jìn)入了a1狀態(tài)下的，第三個字符，起手先將第三個字符加入，變成ac，然后將c標(biāo)記為1，此時b為0，則最后為acb；
同理當(dāng)最最最外層循環(huán)的第一個字符跑完后，將a標(biāo)記為0，開始對第二個字符進(jìn)行操作，即b；
最后按遞歸的順序，所有的字符都是按照字典序添加的，如下所示
a b c
a c b
b a c
b c a
c a b
c b a

28.數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字

數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半，請找出這個數(shù)字。
例如輸入一個長度為9的數(shù)組{1,2,3,2,2,2,5,4,2}。
由于數(shù)字2在數(shù)組中出現(xiàn)了5次，超過數(shù)組長度的一半，因此輸出2。如果不存在則輸出0。

該題最好的解法當(dāng)然是O(n)時間復(fù)雜度的，用到兩個變量，一個變量key用來存儲所謂的“關(guān)鍵元素”，一個變量cnt用來存儲關(guān)鍵元素key的出現(xiàn)次數(shù)，將key初始化為array[0]，cnt初始化為1.具體算法流程為：1、先判斷cnt是否為0，如果為0，則將當(dāng)前元素賦給key，且cnt=0；否則的話判斷當(dāng)前元素與key是否相等，如果相等則cnt+1，不相等則cnt-1；2.找到了key元素之后還需要進(jìn)行檢查，因為例如12345這種情況最后的key就是5,所以還要檢查key元素在數(shù)組中出現(xiàn)的次數(shù)是否大于數(shù)組長度的一般，總結(jié)起來就是一句話，大于數(shù)組長度一半的元素一定會留下來成為key元素，但key元素并不一定是大于數(shù)組長度一般的元素，因此要進(jìn)行檢查。
代碼如下

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array.length==0){
            return 0;
        }
        int key = array[0];
        //從數(shù)組第一個元素開始進(jìn)行循環(huán)遍歷
        for(int i=1,cnt=1;i<array.length;i++){
            //如果cnt等于0，那么就重新計數(shù)和確定key元素
            //否則，就確定cnt數(shù)值如何變化
            if(cnt==0){
                key=array[i];
                cnt=1;
            }else{
                cnt=array[i]==key?cnt+1:cnt-1;
            }
            
        }
        //找到key元素之后，來對key元素進(jìn)行驗證
        int cnt=0;
        for(int j=0;j<array.length;j++){
            cnt=array[j]==key?cnt+1:cnt;
        }
        return cnt>array.length/2?key:0;
    }
}

29.最小的K個數(shù)

輸入n個整數(shù)，找出其中最小的K個數(shù)。例如輸入4,5,1,6,2,7,3,8這8個數(shù)字，則最小的4個數(shù)字是1,2,3,4,。

本題最簡單的思路就是用堆排來做，用一個容量為K的大根堆去維護(hù)數(shù)組，如果當(dāng)新元素加入堆之后容量超過了K，那么就拋棄堆頂元素，而java中實現(xiàn)堆的最簡單的方法就是封裝好的優(yōu)先隊列，但是注意由于隊列的性質(zhì)是先進(jìn)先出，只能彈出隊列首部的元素，因此我們需要對優(yōu)先隊列進(jìn)行降序即可。
代碼如下

import java.util.PriorityQueue;
import java.util.ArrayList;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        //如果k<0或者input為空或者k大于input的長度，那么返回一個空的ArrayList
        if(k<0||input.length==0||k>input.length){
            return new ArrayList<>();
        }
        //用優(yōu)先隊列創(chuàng)建一個大根堆，注意由于隊列先進(jìn)先出的性質(zhì)，所以我們要進(jìn)行降序
        //這里用o1,o2指代兩個元素，用o2-o1代表降序
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1,o2)->o2-o1);
        for(int i=0;i<input.length;i++){
            maxHeap.add(input[i]);
            //如果優(yōu)先隊列的容量大于K，則彈出隊列首部的元素
            if(maxHeap.size()>k){
                maxHeap.poll();
            }
        }
        return new ArrayList<>(maxHeap);
    }
}

30.連續(xù)子數(shù)組的最大和

HZ偶爾會拿些專業(yè)問題來忽悠那些非計算機(jī)專業(yè)的同學(xué)。
今天測試組開完會后,他又發(fā)話了:在古老的一維模式識別中,常常需要計算連續(xù)子向量的最大和,當(dāng)向量全為正數(shù)的時候,問題很好解決。
但是,如果向量中包含負(fù)數(shù),是否應(yīng)該包含某個負(fù)數(shù),并期望旁邊的正數(shù)會彌補(bǔ)它呢？
例如:{6,-3,-2,7,-15,1,2,2},連續(xù)子向量的最大和為8(從第0個開始,到第3個為止)。
給一個數(shù)組，返回它的最大連續(xù)子序列的和，你會不會被他忽悠??？(子向量的長度至少是1)

典型的入門DP問題，用一個dp數(shù)組來存儲以array中每個元素為結(jié)尾的可能的最大連續(xù)子數(shù)組和，試想，當(dāng)我處理第i項時，已經(jīng)存儲了前面i-1個元素的最大連續(xù)子數(shù)組和，如果前面這個和即dp[i-1]已經(jīng)小于0了，那我要前面的何用？以我array[i]結(jié)尾的如果把前面的加上豈不是越加越小？所以此時dp[i]就等于array[i]，如果前面的大于或者等于0，那么把前面的加起來，豈不是美滋滋？所以此時dp[i]=dp[i-1]+array[i];
dp方程如下：

從第1項開始
dp[i] = dp[i-1]>0?dp[i-1]+array[i]:array[i];

求出了以array中每個元素為結(jié)尾能夠得到的連續(xù)子數(shù)組的最大值的一個數(shù)組，然后求出這個數(shù)組的最大值，即可.
代碼如下

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        if(array.length==0){
            return 0;
        }
        //先復(fù)制一份原數(shù)組
        int[] dp = array.clone();
        //動態(tài)規(guī)劃過程
        for(int i = 1;i<array.length;i++){
            dp[i] = dp[i-1]>0?dp[i-1]+array[i]:array[i];
        }
        int max = dp[0];
        //求出dp數(shù)組的最大值
        for(int num:dp){
            max = Math.max(max,num);
        }
        return max;
    }
}