劍指offer21到30題總覽：

棧的壓入、彈出序列
從上往下打印二叉樹(shù)
二叉搜索樹(shù)的后序遍歷序列
二叉樹(shù)中和為某一值的路徑
復(fù)雜鏈表的復(fù)制
二叉搜索樹(shù)與雙向鏈表
字符串的排列
數(shù)組中出現(xiàn)次數(shù)超過(guò)一半的數(shù)字
最小的K個(gè)數(shù)
連續(xù)子數(shù)組的最大和

21、棧的壓入、彈出序列

題目描述

輸入兩個(gè)整數(shù)序列，第一個(gè)序列表示棧的壓入順序，請(qǐng)判斷第二個(gè)序列是否可能為該棧的彈出順序。假設(shè)壓入棧的所有數(shù)字均不相等。例如序列1,2,3,4,5是某棧的壓入順序，序列4,5,3,2,1是該壓棧序列對(duì)應(yīng)的一個(gè)彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。（注意：這兩個(gè)序列的長(zhǎng)度是相等的）

解題思路

使用一個(gè)輔助棧，先找到第一個(gè)pop出的元素popA[0]在pushA中的位置，將該位置記為pushIndex(pushIndex表示曾經(jīng)入棧過(guò)的元素的最遠(yuǎn)距離)，并將pushA中該元素之前的所有元素入棧。如果下一個(gè)popA元素不等于棧頂元素，則看能不能繼續(xù)入棧：如果可以繼續(xù)入棧且下一個(gè)要入棧的元素就是要pop出的元素，則pushIndex++；如果可以繼續(xù)入棧但下一個(gè)要入棧的元素并不是要pop出的元素，則元素入輔助棧，pushIndex++。如果不能繼續(xù)入棧，則返回false。

注意事項(xiàng)

在找第一個(gè)popA[0]時(shí)，有可能在pushA中根本沒(méi)有popA[0]這個(gè)元素。

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        if(pushA.length == 0){return true;}
        boolean flag = true;//flag默認(rèn)true，如果方法運(yùn)行完沒(méi)有發(fā)現(xiàn)序列不符合的情況，則返回flag。
        Stack<Integer> stack = new Stack<>();
        int pushIndex = -1;
        for(int i=0; i<pushA.length; i++){//找到第一個(gè)pop的數(shù)在push序列中的位置，并將其前面的數(shù)全部入棧
            if(pushA[i] != popA[0]){
                stack.push(pushA[i]);
            }else{
                pushIndex = i;//在pushA中找到了popA[0]，記錄下標(biāo)，表示當(dāng)前push的最遠(yuǎn)距離。
                break;
            }
        }
        if(pushIndex==-1){return false;}//如果在pushA中沒(méi)有找到popA[0]，則返回false。
        for(int i=1; i<popA.length; i++){
            if(popA[i]!=stack.peek()){//當(dāng)前棧頂元素不是當(dāng)前要pop的數(shù)
                if(pushIndex+1 < pushA.length){//pushA還有下一個(gè)
                    if(popA[i]!=pushA[pushIndex+1]){//下一個(gè)不是要pop的數(shù)，則繼續(xù)入棧
                        stack.push(pushA[pushIndex+1]);
                        pushIndex++;
                    }else{//下一個(gè)就是要pop的數(shù)
                        pushIndex++;
                    }
                }else{//已經(jīng)全部入棧
                    return false;
                }
            }else{//當(dāng)前棧頂元素就是要pop的數(shù)
                stack.pop();
            }
        }
        return flag;
    }
}

22、從上往下打印二叉樹(shù)

題目描述

從上往下打印出二叉樹(shù)的每個(gè)節(jié)點(diǎn)，同層節(jié)點(diǎn)從左至右打印。

解題思路

中序遍歷

import java.util.ArrayList;
import java.util.LinkedList;

public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        if(root == null){return list;}//如果root為空，則返回空l(shuí)ist
        
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);//先將根節(jié)點(diǎn)入隊(duì)列
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();//取隊(duì)頭元素，將val加入list
            list.add(node.val);
            if(node.left!=null){queue.offer(node.left);}//將其左右子結(jié)點(diǎn)如隊(duì)列
            if(node.right!=null){queue.offer(node.right);}
        }
        return list;
    }
}

23、二叉搜索樹(shù)的后序遍歷序列

題目描述

輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹(shù)的后序遍歷的結(jié)果。如果是則輸出Yes,否則輸出No。假設(shè)輸入的數(shù)組的任意兩個(gè)數(shù)字都互不相同。

解題思路

序列的最后一個(gè)數(shù)即為數(shù)的根節(jié)點(diǎn)，其左子樹(shù)上的結(jié)點(diǎn)比根節(jié)點(diǎn)小，其右子樹(shù)上的結(jié)點(diǎn)比根節(jié)點(diǎn)大。遍歷序列找到第一個(gè)比根節(jié)點(diǎn)大的數(shù)，將序列分為左右根三部分。遍歷第二部分(對(duì)應(yīng)右子樹(shù)的部分)，如果發(fā)現(xiàn)有比根節(jié)點(diǎn)小的，則返回false，如果沒(méi)有發(fā)現(xiàn)比根節(jié)點(diǎn)小的，則遞歸左右子樹(shù)。

注意事項(xiàng)

找到第一個(gè)比根節(jié)點(diǎn)小的數(shù)后，要判斷對(duì)應(yīng)右子樹(shù)的部分是否都比根節(jié)點(diǎn)大。

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length==0){return false;}//用例規(guī)定seq為空時(shí)返回false
        return verify(sequence, 0, sequence.length);
    }
    public boolean verify(int[] sequence, int start, int end){
        if(end-start<=0){return true;}//如果該段序列長(zhǎng)度為0，則返回true
        int root = sequence[end-1];
        int index = end-1;
        for(int i=start; i<end-1; i++){//保存第一個(gè)比根節(jié)點(diǎn)小的數(shù)的下標(biāo)
            if(sequence[i] > root){
                index = i;
                break;
            }
        }
        for(int i=index; i<end-1; i++){//遍歷對(duì)應(yīng)右子樹(shù)的數(shù)是否都比根節(jié)點(diǎn)大
            if(sequence[i] < root){
                return false;
            }
        }
        return verify(sequence, start, index) && verify(sequence, index, end-1);//遞歸左右子樹(shù)
    }
}

24、二叉樹(shù)中和為某一值的路徑

題目描述

輸入一顆二叉樹(shù)的跟節(jié)點(diǎn)和一個(gè)整數(shù)，打印出二叉樹(shù)中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑。路徑定義為從樹(shù)的根結(jié)點(diǎn)開(kāi)始往下一直到葉結(jié)點(diǎn)所經(jīng)過(guò)的結(jié)點(diǎn)形成一條路徑。(注意: 在返回值的list中，數(shù)組長(zhǎng)度大的數(shù)組靠前)

解題思路

深度遍歷，并設(shè)置回退機(jī)制。每訪問(wèn)一個(gè)節(jié)點(diǎn)，target減少val，當(dāng)遇到葉子節(jié)點(diǎn)的時(shí)候(左右子樹(shù)均為空)，判斷target與葉子節(jié)點(diǎn)的值是否相等。如果相等，則將該葉子節(jié)點(diǎn)加入list，將path加入最終結(jié)果，并將list該葉子節(jié)點(diǎn)再取出，回退；如果不相等，則該path并不符合，list中不加入該葉子節(jié)點(diǎn)。當(dāng)遇到非葉子節(jié)點(diǎn)的時(shí)候，將root.val加入list，target減去root.val，遞歸。遍歷完左子樹(shù)之后，在遍歷右子樹(shù)之前，要回退一步。

注意事項(xiàng)

回退機(jī)制。
list要復(fù)制之后再加入最終path中，否則傳入的是同一個(gè)list的引用。
數(shù)字均為整數(shù)但不一定一定為正數(shù)，所以一定需要遍歷到最深處。

public class Solution {
    ArrayList<ArrayList<Integer>> result = new ArrayList<>();//存儲(chǔ)符合要求的path
    ArrayList<Integer> list = new ArrayList<>();//list保存當(dāng)前路徑，如果需要回退則remove
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        if(root != null){
            if(root.left==null && root.right==null){//如果當(dāng)前根結(jié)點(diǎn)為葉子結(jié)點(diǎn)
                if(target == root.val){//如果相等，則為符合要求的path
                    list.add(root.val);//將當(dāng)前根結(jié)點(diǎn)加入list
                    result.add(new ArrayList<Integer>(list));//初始化一個(gè)新list，加入result中
                    list.remove(list.size()-1);//移除當(dāng)前根結(jié)點(diǎn)，回退
                }
            }else{//如果當(dāng)前根結(jié)點(diǎn)不是葉子節(jié)點(diǎn)，則需要遞歸左右子樹(shù)
                if(root.left!=null){//左子樹(shù)不為空
                    list.add(root.val);//將當(dāng)前根結(jié)點(diǎn)加入list
                    FindPath(root.left, target - root.val);//遞歸，target減少
                    list.remove(list.size()-1);//回退
                }
                if(root.right!=null){
                    list.add(root.val);
                    FindPath(root.right, target-root.val);
                    list.remove(list.size()-1);
                }//寫(xiě)的比較重復(fù)，可更簡(jiǎn)潔
            }
        }
        return result;
    }
}

25、復(fù)雜鏈表的復(fù)制

題目描述

輸入一個(gè)復(fù)雜鏈表（每個(gè)節(jié)點(diǎn)中有節(jié)點(diǎn)值，以及兩個(gè)指針，一個(gè)指向下一個(gè)節(jié)點(diǎn)，另一個(gè)特殊指針指向任意一個(gè)節(jié)點(diǎn)），返回結(jié)果為復(fù)制后復(fù)雜鏈表的head。（注意，輸出結(jié)果中請(qǐng)不要返回參數(shù)中的節(jié)點(diǎn)引用，否則判題程序會(huì)直接返回空）

解題思路

對(duì)原鏈表中的每個(gè)結(jié)點(diǎn)，都新建一個(gè)新結(jié)點(diǎn)，插入到原結(jié)點(diǎn)的后面。所有結(jié)點(diǎn)插入完畢后，復(fù)制random指針，要注意有的random為空。random指針復(fù)制完后，拆分鏈表。

注意事項(xiàng)

有的random指針為空，則不需要復(fù)制。

public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        if(pHead == null){return null;}//如果鏈表為空，則返回空
        RandomListNode p = pHead;
        while(p != null){//新建結(jié)點(diǎn)插入到每個(gè)結(jié)點(diǎn)的后面
            RandomListNode node = new RandomListNode(p.label);
            node.next = p.next;
            p.next = node;
            p = node.next;
        }
        RandomListNode head = pHead.next;//head為拷貝的新鏈表的head
        p = pHead;
        while(p != null){//拷貝random指針，注意有的random結(jié)點(diǎn)為空
            if(p.random!=null){
                p.next.random = p.random.next;
                p = p.next.next;
            }else{
                p = p.next;
            }
        }
        p = pHead;
        RandomListNode q = p.next;
        while(p.next.next != null){//拆分鏈表
            p.next = q.next;
            p = p.next;
            q.next = p.next;
            q = q.next;
        }
        p.next = null;
        return head;
    }
}

26、二叉搜索樹(shù)與雙向鏈表

題目描述

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

解題思路

中序遍歷，前一個(gè)pop出的結(jié)點(diǎn)為pre，當(dāng)前結(jié)點(diǎn)為curr。

import java.util.Stack;

public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null){return null;}
        Stack<TreeNode> stack = new Stack<>();//新建棧
        stack.push(pRootOfTree);//根結(jié)點(diǎn)入棧
        while(pRootOfTree.left!=null){//將從根節(jié)點(diǎn)到最左邊的節(jié)點(diǎn)全部入棧，返回的鏈表的頭節(jié)點(diǎn)，就是最左邊的結(jié)點(diǎn)(最小的結(jié)點(diǎn))
            pRootOfTree = pRootOfTree.left;
            stack.push(pRootOfTree);
        }

        TreeNode pre = null;//pre為上一個(gè)pop的結(jié)點(diǎn)，一開(kāi)始為null
        TreeNode curr = null;//當(dāng)前節(jié)點(diǎn)

        while(!stack.empty()){
            curr = stack.pop();//pop出棧頂元素
            curr.left = pre;//當(dāng)前結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)(left)為pre
            if(pre!=null){//pre結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)(right)為當(dāng)前結(jié)點(diǎn)
                pre.right = curr;
            }
            pre = curr;//pre變?yōu)楫?dāng)前結(jié)點(diǎn)

            if(curr.right!=null){//訪問(wèn)當(dāng)前結(jié)點(diǎn)的右結(jié)點(diǎn)，如果有右結(jié)點(diǎn)則入棧
                curr = curr.right;
                stack.push(curr);
                while(curr.left!=null){//將該右結(jié)點(diǎn)往下的所有左結(jié)點(diǎn)入棧
                    curr = curr.left;
                    stack.push(curr);
                }
            }
        }
        return pRootOfTree;
    }
}

27、字符串的排列

題目描述

輸入一個(gè)字符串,按字典序打印出該字符串中字符的所有排列。例如輸入字符串a(chǎn)bc,則打印出由字符a,b,c所能排列出來(lái)的所有字符串a(chǎn)bc,acb,bac,bca,cab和cba。
輸入描述:
輸入一個(gè)字符串,長(zhǎng)度不超過(guò)9(可能有字符重復(fù)),字符只包括大小寫(xiě)字母。

解題思路

字符的全排列，主要是用交換兩個(gè)字符的方法進(jìn)行。要注意如果要交換的兩個(gè)字符相等，則不需要交換。

import java.util.ArrayList;
import java.util.Collections;

public class Solution {
    ArrayList<String> list = new ArrayList<>();
    public ArrayList<String> Permutation(String str) {
        if(str == null || str.length()==0){}
        permu(str.toCharArray(), 0);//全排列
        Collections.sort(list);//permu方法不管順序，需要sort
        return list;
    }
    public void permu(char[] chars, int index){
        char temp;//temp用來(lái)交換字符
        if(index==chars.length-1){//chars[index]為當(dāng)前要確定的字符
            list.add(String.valueOf(chars));//到了要確定最后一個(gè)字符，已經(jīng)沒(méi)有字符可以交換了，可以直接加入list
        }else{
            for(int i=index; i<chars.length; i++){//從要確定的index位開(kāi)始
                if(i==index){//index位和index位不需要交換，已確定確定index位，遞歸確定下一位
                    permu(chars, index+1);//直接遞歸下一位
                }else{//index位與后面的位進(jìn)行字符交換
                    if(chars[i]!=chars[index]){//當(dāng)字符不相同時(shí)交換
                        temp = chars[index];//交換index和i
                        chars[index] = chars[i];
                        chars[i] = temp;

                        permu(chars, index+1);//交換后遞歸

                        temp = chars[index];//交換回來(lái)
                        chars[index] = chars[i];
                        chars[i] = temp;
                    }
                }
            }
        }
    }
}

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

題目描述

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

解題思路

一種是hashmap，另一種為陣地攻守思想。陣地攻守思想?yún)⒖寂？途W(wǎng)作者：cm問(wèn)前程https://www.nowcoder.com/questionTerminal/e8a1b01a2df14cb2b228b30ee6a92163
陣地攻守的思想：
第一個(gè)數(shù)字作為第一個(gè)士兵，守陣地；count = 1；
遇到相同元素，count++;
遇到不相同元素，即為敵人，同歸于盡,count--；當(dāng)遇到count為0的情況，又以新的i值作為守陣地的士兵，繼續(xù)下去，到最后還留在陣地上的士兵，有可能是主元素。
再加一次循環(huán)，記錄這個(gè)士兵的個(gè)數(shù)看是否大于數(shù)組一般即可。

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array.length==0){return 0;}
        if(array.length==1){return array[0];}
        int result = array[0];//先將第一個(gè)元素記做result，count計(jì)1
        int count = 1;
        for(int i=1; i<array.length; i++){//遍歷數(shù)組，陣地攻守
            if(count==0){//如果count被滅為0
                result = array[i];//將當(dāng)前數(shù)記為result，count計(jì)1
                count++;
            }else{
                if(array[i]!=result){//遇到不同的數(shù)則count-1
                    count--;
                }else{//遇到相同的數(shù)則count+1
                    count++;
                }
            }
        }
        count = 0;
        for(int i=0; i<array.length; i++){//再遍歷一次，記錄上次遍歷找到的result出現(xiàn)的次數(shù)，用于檢查出現(xiàn)次數(shù)是否大于length的一半
            if(array[i] == result){
                count++;
            }
        }
        if(count <= array.length/2){return 0;}//檢查出現(xiàn)次數(shù)
        return result;
    }
}

29、最小的K個(gè)數(shù)

題目描述

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

解題思路

堆排序，構(gòu)造小頂堆，即可找到k個(gè)最小值；或者用大數(shù)淘汰法，構(gòu)建一個(gè)k個(gè)數(shù)的大頂堆，每次加入一個(gè)數(shù)，如果比頂大，則淘汰掉頂，重新調(diào)整。

注意事項(xiàng)

下面的代碼是用k個(gè)數(shù)的PriorityQueue實(shí)現(xiàn)的，
public PriorityQueue(int initialCapacity, Comparator<? super E> comparator)，在new一個(gè)PriorityQueue的時(shí)候可以設(shè)置initialCapacity為k，同時(shí)可以實(shí)現(xiàn)Comparator接口。

Comparable是排序接口，若一個(gè)類實(shí)現(xiàn)了Comparable接口，就意味著“該類支持排序”。實(shí)現(xiàn)了Comparable接口的類的對(duì)象的列表或數(shù)組可以通過(guò)Collections.sort或Arrays.sort進(jìn)行自動(dòng)排序。而Comparator是比較器，我們?nèi)粜枰刂颇硞€(gè)類的次序，可以建立一個(gè)“該類的比較器”來(lái)進(jìn)行排序。
Comparable相當(dāng)于“內(nèi)部比較器”，而Comparator相當(dāng)于“外部比較器”。

經(jīng)過(guò)實(shí)踐，該題返回結(jié)果的list不需要升序排列。

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

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        if(k==0){return list;}
        if(input.length < k){return list;}
        //建立一個(gè)大頂堆，如果不傳入實(shí)現(xiàn)的比較器則默認(rèn)小頂堆
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(k, new Comparator<Integer>(){
            @Override
            public int compare(Integer a, Integer b){
                return b - a;
            }
        });
        for(int i=0; i<input.length; i++){
            if(queue.size()<k){//堆不滿k個(gè)數(shù)時(shí)直接offer
                queue.offer(input[i]);
            }else{
                if(input[i]<queue.peek()){//遇到了更小的數(shù)則poll，offer入新數(shù)
                    queue.poll();
                    queue.offer(input[i]);
                }
            }
        }
        for(Integer i: queue){//實(shí)踐證明該題不需要將list中的數(shù)排序
            list.add(i);
        }
        return list;
    }
}

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

題目描述

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

解題思路

動(dòng)態(tài)規(guī)劃思想：?？途W(wǎng)鏈接：https://www.nowcoder.com/questionTerminal/459bd355da1549fa8a49e350bf3df484
$F(i)$ ：以 $array[i]$ 為末尾元素的子數(shù)組的和的最大值，子數(shù)組的元素的相對(duì)位置不變。
$F(i)=max(F(i-1)+array[i], array[i])$
$res$ ：所有子數(shù)組的和的最大值
$res=max(res，F(xiàn)(i))$

示例：數(shù)組 $[6, -3, -2, 7, -15, 1, 2, 2]$
$i=0$ ：
$F(0)=6$
$res=6$
$i=1$ ：
$F(1) = \max( F(0) - 3, -3 ) = \max( 6 - 3, 3 ) = 3$
$res = \max( F(1), res ) = \max( 3, 6 ) = 6$
$i=2$ ：
$F(2)=\max( F(1) - 2, -2 ) = \max( 3 - 2, -2）=1$
$res=\max( F(2), res ) = \max( 1, 6）=6$
$i=3$ ：
$F(3)=\max( F( 2 ) + 7, 7 ) = \max( 1 + 7, 7 ) =8$
$res=\max( F( 2 ) , res ) = \max( 8, 6 ) =8$
$i=4$ ：
$F(4)=\max( F( 3 ) - 15, -15 ) = \max( 8 - 15, -15 ) =-7$
$res=\max( F( 4 ) , res ) = \max( -7, 8 ) =8$
$i=5$
$F(5)=\max{(F( 4 ) + 1,1)}=\max{(-6,1)}=1$
$res=max{(F( 5 ), res)}=\max{(1,8)}=8$
以此類推，最終 $res$ 的值為8。
從上面的例子可以看到，我們計(jì)算以i=4為結(jié)尾的子數(shù)組最大值 $F(4)$ 的時(shí)候，得到 $F(4)=-7$ ，為負(fù)數(shù)，那么當(dāng)我們計(jì)算 $F(5)$ 的時(shí)候，只要 $array[5]$ 為整數(shù)，那么前面的數(shù)加上 $F(5)$ 一定沒(méi)有甩開(kāi)前面的數(shù)，直接從 $F(5)$ 開(kāi)始的子串?dāng)?shù)組要大，所以這時(shí)我們會(huì)從 $i=5$ 開(kāi)始重新計(jì)算子數(shù)組和。
這個(gè)題不需要輸出到底是哪個(gè)子串，所以只需要實(shí)時(shí)更新最大的子串就行。

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        if(array.length==0){}//題目沒(méi)說(shuō)數(shù)組長(zhǎng)度為0時(shí)返回什么
        int max = array[0];//先對(duì)數(shù)組下標(biāo)為0的位置設(shè)置0，賦初值
        int result = array[0];
        for(int i=1; i<array.length; i++){//這里從i=1開(kāi)始計(jì)算
            max = Math.max(max+array[i], array[i]);//轉(zhuǎn)移公式，意義是計(jì)算是否要丟棄前面的數(shù)，從array[i]開(kāi)始計(jì)算子數(shù)組
            result = Math.max(max, result);//得到更大的result
        }
        return result;
    }
}

結(jié)尾

如果您發(fā)現(xiàn)我的文章有任何錯(cuò)誤，或?qū)ξ业奈恼掠惺裁春玫慕ㄗh，請(qǐng)聯(lián)系我！如果您喜歡我的文章，請(qǐng)點(diǎn)喜歡~*我是藍(lán)白絳，感謝你的閱讀！

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

劍指offer｜21-30題解題思路及代碼(Java版)

劍指offer21到30題總覽：

21、棧的壓入、彈出序列

題目描述

解題思路

注意事項(xiàng)

22、從上往下打印二叉樹(shù)

題目描述

解題思路

23、二叉搜索樹(shù)的后序遍歷序列

題目描述

解題思路

注意事項(xiàng)

24、二叉樹(shù)中和為某一值的路徑

題目描述

解題思路

注意事項(xiàng)

25、復(fù)雜鏈表的復(fù)制

題目描述

解題思路

注意事項(xiàng)

26、二叉搜索樹(shù)與雙向鏈表

題目描述

解題思路

27、字符串的排列

題目描述

解題思路

28、數(shù)組中出現(xiàn)次數(shù)超過(guò)一半的數(shù)字

題目描述

解題思路

29、最小的K個(gè)數(shù)

題目描述

解題思路

注意事項(xiàng)

30、連續(xù)子數(shù)組的最大和

題目描述

解題思路

結(jié)尾

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

21、棧的壓入、彈出序列

22、從上往下打印二叉樹(shù)

23、二叉搜索樹(shù)的后序遍歷序列

24、二叉樹(shù)中和為某一值的路徑

25、復(fù)雜鏈表的復(fù)制

27、字符串的排列

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

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