LeetCode程序中值得反思的細節

以下題號均指LeetCode劍指offer題庫中的題號

本文章將每周定期更新，當內容達到10題左右時將會開下一節，

二維陣列越界問題04

public static void main(String[] args) {
    int[][]x = {{}};
    System.out.println(x.length+" "+x[0].length);
    int[][]y = {{1}};
    System.out.println(y.length+" "+y[0].length);
    int[][]z = {};
    System.out.println(z.length);
}

在遇到二維陣列時，要注意為空的不同情況

String和char[]的相互轉換05

char[] s = {'a','b','c'};
String s1 = new String(s); //這里為String的建構式
String s2 = "abc";
System.out.println(s1.equals(s2));
System.out.println(s1.equals(s));
System.out.println(s2.equals(s));

char[] s3 = new char[8];
s3[0]='a';s3[1]='b';s3[2]='c';
String s4 = new String(s3);
System.out.println(s4.equals(s2));
System.out.println(s2.equals(s4.trim()));//或者括號內為new String(s3,0,3)   String(char[],off,length)

注意，char[]強制轉換為String，相互比較結果不經處理恒為false，

原因：由equals原始碼決定

public boolean equals(Object anObject) {
    if (this == anObject) {
        return true;
    }
    if (anObject instanceof String) {
        String aString = (String)anObject;
        if (!COMPACT_STRINGS || this.coder == aString.coder) {
            return StringLatin1.equals(value, aString.value);
        }
    }
    return false;
}

String物件的內部也是一個char陣列，通過char陣列創建String時，如果不指定start和count，會將使用整個陣列，即連同后面的空字符，輸出結果不會受到影響，另外，String.trim()就是洗掉String 的char陣列前后的空白字符和空字符，使用trim()后再比較就得到值完全一樣的String了，

集合陣列互轉06

    // int[] 轉 List<Integer>
    List<Integer> list1 = Arrays.stream(data).boxed().collect(Collectors.toList());
    // Arrays.stream(arr) 可以替換成IntStream.of(arr)，
    // 1.使用Arrays.stream將int[]轉換成IntStream，
    // 2.使用IntStream中的boxed()裝箱，將IntStream轉換成Stream<Integer>，
    // 3.使用Stream的collect()，將Stream<T>轉換成List<T>，因此正是List<Integer>，
 
    // int[] 轉 Integer[]
    Integer[] integers1 = Arrays.stream(data).boxed().toArray(Integer[]::new);
    // 前兩步同上，此時是Stream<Integer>，
    // 然后使用Stream的toArray，傳入IntFunction<A[]> generator，
    // 這樣就可以回傳Integer陣列，
    // 不然默認是Object[]，
 
    // List<Integer> 轉 Integer[]
    Integer[] integers2 = list1.toArray(new Integer[0]);
    //  呼叫toArray，傳入引數T[] a，這種用法是目前推薦的，
    // List<String>轉String[]也同理，
 
    // List<Integer> 轉 int[]
    int[] arr1 = list1.stream().mapToInt(Integer::valueOf).toArray();
    // 想要轉換成int[]型別，就得先轉成IntStream，
    // 這里就通過mapToInt()把Stream<Integer>呼叫Integer::valueOf來轉成IntStream
    // 而IntStream中默認toArray()轉成int[]，
 
    // Integer[] 轉 int[]
    int[] arr2 = Arrays.stream(integers1).mapToInt(Integer::valueOf).toArray();
    // 思路同上，先將Integer[]轉成Stream<Integer>，再轉成IntStream，
 
    // Integer[] 轉 List<Integer>
    List<Integer> list2 = Arrays.asList(integers1);
    // 最簡單的方式，String[]轉List<String>也同理，
 
    // 同理
    String[] strings1 = {"a", "b", "c"};
    // String[] 轉 List<String>
    List<String> list3 = Arrays.asList(strings1);
    // List<String> 轉 String[]
    String[] strings2 = list3.toArray(new String[0]);

ArrayList.get(); ArrayList.set(index,value);

重建二叉樹的兩種方法07

根據先序和中序遞回還原二叉樹

先序：根節點，{左子樹}，{右子樹}

中序：{左子樹}，根節點，{右子樹}

兩種思路：遞回和迭代

遞回：

class Solution {
    private HashMap<Integer,Integer> indexmap = new HashMap<>();

    public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorderleft,int preorderright,int inorderleft,int inorderright){
        if(preorderleft>preorderright)
            return null;
        TreeNode root = new TreeNode(preorder[preorderleft]);
        int inorderroot = indexmap.get(preorder[preorderleft]);
        int prelen = inorderroot - inorderleft;
        root.left = myBuildTree(preorder,inorder,preorderleft+1,preorderleft+prelen,inorderleft,inorderroot-1);
        root.right = myBuildTree(preorder,inorder,preorderleft+prelen+1,preorderright,inorderroot+1,inorderright);
        return root;
    }


    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int len = preorder.length;
        for(int i = 0 ; i < len ; i++){
            indexmap.put(inorder[i],i);
        }
        return myBuildTree(preorder,inorder,0,len-1,0,len-1);
    }
}

將以上演算法后四個引數 (int preorderleft,int preorderright,int inorderleft,int inorderright) 分別稱為A,B,C,D，則A和B相當于建立的樹的先序遍歷的左邊指標和右邊指標，C和D相當于中序遍歷的左指標和右指標，用來標記多次遍歷程序的左子樹邊界和右子樹邊界，

迭代思路中，則需要用到堆疊stack

可利用deque介面實作stack

deque支持兩端元素插入和移除的線性集合，名稱deque是“雙端佇列”的縮寫，通常發音為“deck”，大多數Deque實作對它們可能包含的元素的數量沒有固定的限制，但是該介面支持容量限制的deques以及沒有固定大小限制的deques，

Deque<TreeNode> stack = new LinkedList<TreeNode>();

stack.peek()取堆疊頂元素，不彈出

stack.push()壓入元素

stack.pop()取堆疊頂元素，并彈出

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || preorder.length == 0)
            return null;
        int len = preorder.length;
        int index = 0;   //中序遍歷的指標
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode root = new TreeNode(preorder[0]);
        stack.push(root);
        TreeNode node;
        for(int i = 1 ; i < len ; i++){
            if((node = stack.peek()).val != inorder[index]){
                node.left = new TreeNode(preorder[i]);
                stack.push(node.left);
            }
            else{
                while(!stack.isEmpty() && stack.peek().val==inorder[index]){ //stack存當前構造樹的左節點，可能會有多個構造的樹
                    node = stack.pop();
                    index++;
                }
                node.right = new TreeNode(preorder[i]);
                stack.push(node.right);
            }
        }
        return root;
    }
}

在這個思路中，主要應用中序遍歷的第一個元素將是樹的左邊界，以先序遍歷的順序與該元素進行比較，若根節點與其相同，則無左子樹；不同的話即為壓入堆疊的堆疊頂元素的左節點，這個思路主要在于先序遍歷和中序遍歷的程序特點，遞回主要利用的是先序和中序的結構特點，

重要在于理解：每次遍歷程序中，操作的是堆疊頂元素，而遍歷的當前i在堆疊頂元素的后面，

利用兩個堆疊實作佇列 09

佇列要實作的是先進先出，而堆疊實作的是先進后出，所以可以建立兩個stack

堆疊1負責壓入元素，而當需要洗掉的時候，只需將堆疊1中的元素轉入堆疊2

stack2.push(stack1.pop());

這樣的話，堆疊2中，堆疊頂元素為最開始添加進去的元素，為佇列頭，直至堆疊2洗掉完后，若堆疊1還有元素，繼續轉移，若沒有，則回傳0，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/274694.html

標籤：其他

上一篇：解決“用PicGo-2.3.0-beta5 + GitHub做博客圖床，github倉庫圖片檔案不顯示”的問題記錄（備忘）