劍指offer21到30題總覽：
- 棧的壓入油额、彈出序列
- 從上往下打印二叉樹
- 二叉搜索樹的后序遍歷序列
- 二叉樹中和為某一值的路徑
- 復雜鏈表的復制
- 二叉搜索樹與雙向鏈表
- 字符串的排列
- 數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字
- 最小的K個數(shù)
- 連續(xù)子數(shù)組的最大和
21莉御、棧的壓入实幕、彈出序列
題目描述
輸入兩個整數(shù)序列洞慎，第一個序列表示棧的壓入順序告抄，請判斷第二個序列是否可能為該棧的彈出順序赴背。假設壓入棧的所有數(shù)字均不相等铣焊。例如序列1,2,3,4,5是某棧的壓入順序逊朽，序列4,5,3,2,1是該壓棧序列對應的一個彈出序列罕伯，但4,3,5,1,2就不可能是該壓棧序列的彈出序列曲伊。（注意：這兩個序列的長度是相等的）
解題思路
使用一個輔助棧，先找到第一個pop出的元素popA[0]在pushA中的位置追他，將該位置記為pushIndex(pushIndex表示曾經(jīng)入棧過的元素的最遠距離)坟募，并將pushA中該元素之前的所有元素入棧。如果下一個popA元素不等于棧頂元素邑狸，則看能不能繼續(xù)入棧：如果可以繼續(xù)入棧且下一個要入棧的元素就是要pop出的元素懈糯，則pushIndex++；如果可以繼續(xù)入棧但下一個要入棧的元素并不是要pop出的元素单雾，則元素入輔助棧赚哗，pushIndex++。如果不能繼續(xù)入棧硅堆，則返回false屿储。
注意事項
- 在找第一個popA[0]時，有可能在pushA中根本沒有popA[0]這個元素渐逃。
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
if(pushA.length == 0){return true;}
boolean flag = true;//flag默認true够掠，如果方法運行完沒有發(fā)現(xiàn)序列不符合的情況，則返回flag茄菊。
Stack<Integer> stack = new Stack<>();
int pushIndex = -1;
for(int i=0; i<pushA.length; i++){//找到第一個pop的數(shù)在push序列中的位置疯潭，并將其前面的數(shù)全部入棧
if(pushA[i] != popA[0]){
stack.push(pushA[i]);
}else{
pushIndex = i;//在pushA中找到了popA[0]，記錄下標面殖，表示當前push的最遠距離竖哩。
break;
}
}
if(pushIndex==-1){return false;}//如果在pushA中沒有找到popA[0]，則返回false脊僚。
for(int i=1; i<popA.length; i++){
if(popA[i]!=stack.peek()){//當前棧頂元素不是當前要pop的數(shù)
if(pushIndex+1 < pushA.length){//pushA還有下一個
if(popA[i]!=pushA[pushIndex+1]){//下一個不是要pop的數(shù)相叁，則繼續(xù)入棧
stack.push(pushA[pushIndex+1]);
pushIndex++;
}else{//下一個就是要pop的數(shù)
pushIndex++;
}
}else{//已經(jīng)全部入棧
return false;
}
}else{//當前棧頂元素就是要pop的數(shù)
stack.pop();
}
}
return flag;
}
}
22、從上往下打印二叉樹
題目描述
從上往下打印出二叉樹的每個節(jié)點吃挑，同層節(jié)點從左至右打印钝荡。
解題思路
中序遍歷
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為空，則返回空list
LinkedList<TreeNode> queue = new LinkedList<>();
queue.offer(root);//先將根節(jié)點入隊列
while(!queue.isEmpty()){
TreeNode node = queue.poll();//取隊頭元素舶衬，將val加入list
list.add(node.val);
if(node.left!=null){queue.offer(node.left);}//將其左右子結點如隊列
if(node.right!=null){queue.offer(node.right);}
}
return list;
}
}
23埠通、二叉搜索樹的后序遍歷序列
題目描述
輸入一個整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷的結果逛犹。如果是則輸出Yes,否則輸出No端辱。假設輸入的數(shù)組的任意兩個數(shù)字都互不相同梁剔。
解題思路
序列的最后一個數(shù)即為數(shù)的根節(jié)點，其左子樹上的結點比根節(jié)點小舞蔽，其右子樹上的結點比根節(jié)點大荣病。遍歷序列找到第一個比根節(jié)點大的數(shù)，將序列分為左右根三部分渗柿。遍歷第二部分(對應右子樹的部分)个盆，如果發(fā)現(xiàn)有比根節(jié)點小的，則返回false朵栖，如果沒有發(fā)現(xiàn)比根節(jié)點小的颊亮，則遞歸左右子樹。
注意事項
- 找到第一個比根節(jié)點小的數(shù)后陨溅，要判斷對應右子樹的部分是否都比根節(jié)點大终惑。
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence.length==0){return false;}//用例規(guī)定seq為空時返回false
return verify(sequence, 0, sequence.length);
}
public boolean verify(int[] sequence, int start, int end){
if(end-start<=0){return true;}//如果該段序列長度為0，則返回true
int root = sequence[end-1];
int index = end-1;
for(int i=start; i<end-1; i++){//保存第一個比根節(jié)點小的數(shù)的下標
if(sequence[i] > root){
index = i;
break;
}
}
for(int i=index; i<end-1; i++){//遍歷對應右子樹的數(shù)是否都比根節(jié)點大
if(sequence[i] < root){
return false;
}
}
return verify(sequence, start, index) && verify(sequence, index, end-1);//遞歸左右子樹
}
}
24门扇、二叉樹中和為某一值的路徑
題目描述
輸入一顆二叉樹的跟節(jié)點和一個整數(shù)雹有，打印出二叉樹中結點值的和為輸入整數(shù)的所有路徑。路徑定義為從樹的根結點開始往下一直到葉結點所經(jīng)過的結點形成一條路徑臼寄。(注意: 在返回值的list中霸奕，數(shù)組長度大的數(shù)組靠前)
解題思路
深度遍歷，并設置回退機制脯厨。每訪問一個節(jié)點铅祸，target減少val，當遇到葉子節(jié)點的時候(左右子樹均為空)合武，判斷target與葉子節(jié)點的值是否相等临梗。如果相等，則將該葉子節(jié)點加入list稼跳，將path加入最終結果盟庞，并將list該葉子節(jié)點再取出，回退汤善；如果不相等什猖，則該path并不符合，list中不加入該葉子節(jié)點红淡。當遇到非葉子節(jié)點的時候不狮，將root.val加入list，target減去root.val在旱，遞歸摇零。遍歷完左子樹之后，在遍歷右子樹之前桶蝎，要回退一步驻仅。
注意事項
- 回退機制谅畅。
- list要復制之后再加入最終path中，否則傳入的是同一個list的引用噪服。
- 數(shù)字均為整數(shù)但不一定一定為正數(shù)毡泻，所以一定需要遍歷到最深處。
public class Solution {
ArrayList<ArrayList<Integer>> result = new ArrayList<>();//存儲符合要求的path
ArrayList<Integer> list = new ArrayList<>();//list保存當前路徑粘优，如果需要回退則remove
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
if(root != null){
if(root.left==null && root.right==null){//如果當前根結點為葉子結點
if(target == root.val){//如果相等仇味，則為符合要求的path
list.add(root.val);//將當前根結點加入list
result.add(new ArrayList<Integer>(list));//初始化一個新list，加入result中
list.remove(list.size()-1);//移除當前根結點敬飒，回退
}
}else{//如果當前根結點不是葉子節(jié)點邪铲，則需要遞歸左右子樹
if(root.left!=null){//左子樹不為空
list.add(root.val);//將當前根結點加入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);
}//寫的比較重復无拗，可更簡潔
}
}
return result;
}
}
25、復雜鏈表的復制
題目描述
輸入一個復雜鏈表（每個節(jié)點中有節(jié)點值昧碉，以及兩個指針英染，一個指向下一個節(jié)點，另一個特殊指針指向任意一個節(jié)點）被饿，返回結果為復制后復雜鏈表的head四康。（注意，輸出結果中請不要返回參數(shù)中的節(jié)點引用狭握，否則判題程序會直接返回空）
解題思路
對原鏈表中的每個結點闪金，都新建一個新結點，插入到原結點的后面论颅。所有結點插入完畢后哎垦，復制random指針，要注意有的random為空恃疯。random指針復制完后漏设，拆分鏈表。
注意事項
- 有的random指針為空今妄，則不需要復制郑口。
public class Solution {
public RandomListNode Clone(RandomListNode pHead) {
if(pHead == null){return null;}//如果鏈表為空，則返回空
RandomListNode p = pHead;
while(p != null){//新建結點插入到每個結點的后面
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結點為空
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犬性、二叉搜索樹與雙向鏈表
題目描述
輸入一棵二叉搜索樹，將該二叉搜索樹轉換成一個排序的雙向鏈表腾仅。要求不能創(chuàng)建任何新的結點乒裆，只能調(diào)整樹中結點指針的指向。
解題思路
中序遍歷攒砖，前一個pop出的結點為pre缸兔，當前結點為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);//根結點入棧
while(pRootOfTree.left!=null){//將從根節(jié)點到最左邊的節(jié)點全部入棧，返回的鏈表的頭節(jié)點惰蜜，就是最左邊的結點(最小的結點)
pRootOfTree = pRootOfTree.left;
stack.push(pRootOfTree);
}
TreeNode pre = null;//pre為上一個pop的結點昂拂，一開始為null
TreeNode curr = null;//當前節(jié)點
while(!stack.empty()){
curr = stack.pop();//pop出棧頂元素
curr.left = pre;//當前結點的上一個結點(left)為pre
if(pre!=null){//pre結點的下一個結點(right)為當前結點
pre.right = curr;
}
pre = curr;//pre變?yōu)楫斍敖Y點
if(curr.right!=null){//訪問當前結點的右結點，如果有右結點則入棧
curr = curr.right;
stack.push(curr);
while(curr.left!=null){//將該右結點往下的所有左結點入棧
curr = curr.left;
stack.push(curr);
}
}
}
return pRootOfTree;
}
}
27抛猖、字符串的排列
題目描述
輸入一個字符串,按字典序打印出該字符串中字符的所有排列格侯。例如輸入字符串a(chǎn)bc,則打印出由字符a,b,c所能排列出來的所有字符串a(chǎn)bc,acb,bac,bca,cab和cba。
輸入描述:
輸入一個字符串,長度不超過9(可能有字符重復),字符只包括大小寫字母财著。
解題思路
字符的全排列联四，主要是用交換兩個字符的方法進行。要注意如果要交換的兩個字符相等撑教，則不需要交換朝墩。
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用來交換字符
if(index==chars.length-1){//chars[index]為當前要確定的字符
list.add(String.valueOf(chars));//到了要確定最后一個字符伟姐，已經(jīng)沒有字符可以交換了收苏，可以直接加入list
}else{
for(int i=index; i<chars.length; i++){//從要確定的index位開始
if(i==index){//index位和index位不需要交換，已確定確定index位愤兵，遞歸確定下一位
permu(chars, index+1);//直接遞歸下一位
}else{//index位與后面的位進行字符交換
if(chars[i]!=chars[index]){//當字符不相同時交換
temp = chars[index];//交換index和i
chars[index] = chars[i];
chars[i] = temp;
permu(chars, index+1);//交換后遞歸
temp = chars[index];//交換回來
chars[index] = chars[i];
chars[i] = temp;
}
}
}
}
}
}
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。
解題思路
一種是hashmap双藕，另一種為陣地攻守思想淑趾。陣地攻守思想?yún)⒖寂？途W(wǎng)作者：cm問前程https://www.nowcoder.com/questionTerminal/e8a1b01a2df14cb2b228b30ee6a92163
陣地攻守的思想：
第一個數(shù)字作為第一個士兵忧陪，守陣地扣泊；count = 1；
遇到相同元素嘶摊，count++;
遇到不相同元素延蟹，即為敵人，同歸于盡,count--叶堆；當遇到count為0的情況阱飘，又以新的i值作為守陣地的士兵，繼續(xù)下去，到最后還留在陣地上的士兵沥匈，有可能是主元素蔗喂。
再加一次循環(huán)，記錄這個士兵的個數(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];//先將第一個元素記做result缰儿，count計1
int count = 1;
for(int i=1; i<array.length; i++){//遍歷數(shù)組，陣地攻守
if(count==0){//如果count被滅為0
result = array[i];//將當前數(shù)記為result散址，count計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個數(shù)
題目描述
輸入n個整數(shù)瞪浸，找出其中最小的K個數(shù)。例如輸入4,5,1,6,2,7,3,8這8個數(shù)字吏祸，則最小的4個數(shù)字是1,2,3,4,对蒲。
解題思路
堆排序，構造小頂堆犁罩，即可找到k個最小值齐蔽；或者用大數(shù)淘汰法，構建一個k個數(shù)的大頂堆床估，每次加入一個數(shù)，如果比頂大诱渤，則淘汰掉頂丐巫，重新調(diào)整。
注意事項
- 下面的代碼是用k個數(shù)的PriorityQueue實現(xiàn)的，
public PriorityQueue(int initialCapacity, Comparator<? super E> comparator)，在new一個PriorityQueue的時候可以設置initialCapacity為k荚藻，同時可以實現(xiàn)Comparator接口印蔗。
- Comparable是排序接口，若一個類實現(xiàn)了Comparable接口从绘，就意味著“該類支持排序”。實現(xiàn)了Comparable接口的類的對象的列表或數(shù)組可以通過Collections.sort或Arrays.sort進行自動排序。而Comparator是比較器遗菠，我們?nèi)粜枰刂颇硞€類的次序，可以建立一個“該類的比較器”來進行排序华蜒。
- Comparable相當于“內(nèi)部比較器”辙纬，而Comparator相當于“外部比較器”。
- 經(jīng)過實踐叭喜，該題返回結果的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;}
//建立一個大頂堆，如果不傳入實現(xià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個數(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){//實踐證明該題不需要將list中的數(shù)排序
list.add(i);
}
return list;
}
}
30譬涡、連續(xù)子數(shù)組的最大和
題目描述
HZ偶爾會拿些專業(yè)問題來忽悠那些非計算機專業(yè)的同學闪幽。今天測試組開完會后,他又發(fā)話了:在古老的一維模式識別中,常常需要計算連續(xù)子向量的最大和,當向量全為正數(shù)的時候,問題很好解決。但是,如果向量中包含負數(shù),是否應該包含某個負數(shù),并期望旁邊的正數(shù)會彌補它呢涡匀？例如:{6,-3,-2,7,-15,1,2,2},連續(xù)子向量的最大和為8(從第0個開始,到第3個為止)盯腌。給一個數(shù)組，返回它的最大連續(xù)子序列的和渊跋，你會不會被他忽悠桌拔恕？(子向量的長度至少是1)
解題思路
動態(tài)規(guī)劃思想：攀霸停客網(wǎng)鏈接：https://www.nowcoder.com/questionTerminal/459bd355da1549fa8a49e350bf3df484
：以
為末尾元素的子數(shù)組的和的最大值燕少，子數(shù)組的元素的相對位置不變。
：所有子數(shù)組的和的最大值
示例：數(shù)組
：
：
：
：
：
以此類推客们，最終的值為8。
從上面的例子可以看到材诽，我們計算以i=4為結尾的子數(shù)組最大值的時候底挫，得到
，為負數(shù)脸侥，那么當我們計算
的時候建邓，只要
為整數(shù)，那么前面的數(shù)加上
一定沒有甩開前面的數(shù)睁枕，直接從
開始的子串數(shù)組要大官边，所以這時我們會從
開始重新計算子數(shù)組和。
這個題不需要輸出到底是哪個子串外遇，所以只需要實時更新最大的子串就行注簿。
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
if(array.length==0){}//題目沒說數(shù)組長度為0時返回什么
int max = array[0];//先對數(shù)組下標為0的位置設置0，賦初值
int result = array[0];
for(int i=1; i<array.length; i++){//這里從i=1開始計算
max = Math.max(max+array[i], array[i]);//轉移公式跳仿，意義是計算是否要丟棄前面的數(shù)诡渴，從array[i]開始計算子數(shù)組
result = Math.max(max, result);//得到更大的result
}
return result;
}
}
結尾
如果您發(fā)現(xiàn)我的文章有任何錯誤，或對我的文章有什么好的建議菲语，請聯(lián)系我妄辩！如果您喜歡我的文章，請點喜歡~*我是藍白絳谨究，感謝你的閱讀恩袱！
