高強度學習訓練第九天總結：5道劍指offer的題目

實在不想看JVM了。刷幾道劍指Offer的題，今天就水一水吧，腦子迷糊。

1.二維數組中的查找

在一個二維數組中（每個一維數組的長度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數，輸入這樣的一個二維數組和一個整數，判斷數組中是否含有該整數。

解題思路：從右上角開始搜索，從上到下為遞增，從右到左為遞減。根據這個思路來進行搜索，演算法複雜度n+m

public class Solution {
    public boolean Find(int target, int [][] array) {
        int x=0,y=array[0].length-1;
        while(x<array.length&&y>-1){
            if(array[x][y]>target){
                y--;
            }else if(array[x][y]<target){
                x++;
            }else{
                return true;
            }
        }
        return false;
    }
}

2.替換空格

請實現一個函數，將一個字元串中的每個空格替換成“%20”。例如，當字元串為We Are Happy.則經過替換之後的字元串為We%20Are%20Happy。

解題思路：不能一個一個插入，複雜度太高，要用空間來換取時間。一個一個賦值比較好。

public class Solution {
    public String replaceSpace(StringBuffer str) {
        StringBuffer sb = new StringBuffer();
        for(int i=0;i<str.length();i++) {
            if(str.charAt(i)==' ') {
                sb.append("%20");
            }else {
                sb.append(str.charAt(i));
            }
        }
        return sb.toString();
    }
}

3.從尾到頭列印鏈表

輸入一個鏈表，按鏈表從尾到頭的順序返回一個ArrayList。

解題思路：這題用C++的話可以直接把指針反轉，不過Java傳進來的是一個集合類。就算了吧。用傻瓜式解法。

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> al = new ArrayList<Integer>();
        while(listNode!=null) {
            al.add(0,listNode.val);
            listNode = listNode.next;
        }
        return al;
    }
}

4.重建二叉樹

輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重覆的數字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹並返回。

解題思路：遞歸建樹。基礎題。

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre.length==0) return null;
        TreeNode trn = new TreeNode(pre[0]);
        if(pre.length==1) return trn;
        else for(int i=0;i<in.length;i++) {
            if(in[i]==pre[0]) {
                int [] preleft = new int[i];
                int [] preright = new int[in.length-i-1];
                int [] inleft = new int[i];
                int [] inright = new int[in.length-i-1];
                System.arraycopy(pre,1,preleft,0,i);
                System.arraycopy(pre,i+1,preright,0,in.length-i-1);
                System.arraycopy(in,0, inleft, 0, i);
                System.arraycopy(in,i+1, inright, 0, in.length-i-1);
                trn.left = reConstructBinaryTree(preleft, inleft);
                trn.right = reConstructBinaryTree(preright,inright);
                return trn;
            }
        }
        return trn;
    }
}

5.用兩個棧實現隊列

用兩個棧來實現一個隊列，完成隊列的Push和Pop操作。 隊列中的元素為int類型。

解題思路：對先進後出和先進先出的基礎理解即可想明白。

import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
     public void push(int node) {
        stack1.push(node);
    }
    
    public int pop() {
        if(!stack2.empty()) {
            return stack2.pop();
        }
        else{
            while(!stack1.empty()) {
                stack2.push(stack1.pop());
            }
            return stack2.pop();
        }
    }
}