二維數(shù)組中的查找

題目

在二維數(shù)組中醇份，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序，判斷二維數(shù)組中是否有該整數(shù)丢氢。

思路

查找整數(shù)時(shí)會(huì)出現(xiàn)重復(fù)查找問題，列從最右開始往左邊檢索先改，行從上往下邊開始檢索疚察，當(dāng)列中的值比目標(biāo)整數(shù)大，則該列中就不存在比目標(biāo)整數(shù)相等的值仇奶，列往左移動(dòng)貌嫡，當(dāng)行中的值比目標(biāo)整數(shù)小，行往下移動(dòng)

java中判斷數(shù)組為空该溯，要檢查三個(gè)部分:

一是數(shù)組首地址是否為空

二是是否為{}岛抄，也就是array.length==0的情況

三是{{}}，這時(shí)array.length == 1狈茉，但是array[0].length == 0夫椭。滿足任意一個(gè)條件就可以返回false了。

if(array == null || array.length == 0 || (array.length <= 1 && array[0].length == 0)) return false;

//時(shí)間復(fù)雜度 O(n^2)
public static boolean find(int[][] arr, int target) {
        if (arr == null || arr.length < 1 && arr[0].length < 1) {
            return false;
        }
        int row = 0;
        int col = arr.length - 1;
        while (row >= 0 && row < arr.length - 1 && col >= 0) {
            if (arr[row][col] == target) {
                return true;
            } else if (arr[row][col] > target) {//如果當(dāng)前的數(shù)字比target大氯庆，則表示不在該列蹭秋，則表示在該列的左邊
                col--;//列數(shù)遞減，表示往左移
            } else {//如果當(dāng)前的數(shù)字比target小堤撵，則表示不在該行仁讨，則表示在該行的下邊
                row++;//行數(shù)遞增，表示往下移
            }
        }
        return false;
}
//二分 時(shí)間復(fù)雜度 O(nlogn)
public static boolean find2(int[][] arr, int target) {
        if (arr == null || arr.length < 1 && arr[0].length < 1) {
            return false;
        }
        int i = 0;
        while (i < arr.length) {
            if (arr[i][arr[i].length - 1] < target) {
                i++;
            } else {
                int b = 0;
                int t = arr[i].length - 1;
                while (b <= t) {
                    int mid = (b + t) / 2;
                    if (arr[i][mid] < target) {
                        b = mid + 1;
                    } else if (arr[i][mid] > target) {
                        t = mid - 1;
                    } else {
                        return true;
                    }
                }
                i++;
            }
        }
        return false;
}

public static void main(String[] args) {
        int[][] matrix = { { 1, 2, 8, 9 }, 
                           { 2, 4, 9, 12 }, 
                           { 4, 7, 10, 13 }, 
                           { 6, 8, 11, 15 } };
        System.out.println(find(matrix, 7)); // 要查找的數(shù)在數(shù)組中
        System.out.println(find(matrix, 5)); // 要查找的數(shù)不在數(shù)組中
        System.out.println(find(matrix, 1)); // 要查找的數(shù)是數(shù)組中最小的數(shù)字
        System.out.println(find(matrix, 15)); // 要查找的數(shù)是數(shù)組中最大的數(shù)字
        System.out.println(find(matrix, 0)); // 要查找的數(shù)比數(shù)組中最小的數(shù)字還小
        System.out.println(find(matrix, 16)); // 要查找的數(shù)比數(shù)組中最大的數(shù)字還大
        System.out.println(find(null, 16)); // 健壯性測試实昨，輸入空指針
    }

替換空格

題目

請實(shí)現(xiàn)一個(gè)函數(shù)陪竿，把字符串中的空格替換成"%20"，輸入”we are happy.“，輸出”we%20are%20happy.“

思路

遍歷一次字符串族跛，計(jì)算出其空格的個(gè)數(shù)闰挡，可以計(jì)算出替換之后的字符串總長度，每替換一個(gè)空格礁哄，長度就增加2长酗，因此替換后的長度等于原來的長度加上字符串空格的個(gè)數(shù)乘以2。替換的時(shí)候從后往前開始復(fù)制和替換桐绒，準(zhǔn)備兩個(gè)指針夺脾，p1和p2，p1指向原始字符串的末尾茉继，p2指向替換后的字符串末尾咧叭。接下來移動(dòng)p1，逐個(gè)把字符復(fù)制到p2烁竭，直到碰到第一個(gè)空為止菲茬，此時(shí)p1往前移動(dòng)一格，p2往前插入 "%20"派撕，由于 %20長度是3婉弹，因此p2也要往前移動(dòng)3格。重復(fù)以上步驟就可以把空格完全替換终吼。

時(shí)間復(fù)雜度 O(n)

public static int replaceBlank(char[] chars, int usedLength) {
        if (chars == null || chars.length < usedLength) {
            return -1;
        }
        int blankCount = 0;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == ' ') {
                blankCount++;
            }
        }
        if (blankCount == 0) {
            return usedLength;
        }
        int targetLength = blankCount * 2 + usedLength;//計(jì)算出替換后的長度
        //如果轉(zhuǎn)換后的長度大于數(shù)組最大長度镀赌，返回-1
        if (targetLength > chars.length) {
            return -1;
        }
        int temp = targetLength;
        usedLength--;//從后往前，第一個(gè)開始處理的字符
        targetLength--;//替換后的字符放置的位置
        //字符中有空白字符际跪，一直處理到所有空白字符處理完
        while (targetLength >= 0 && usedLength < targetLength) {
            if (chars[usedLength] == ' ') {
                chars[targetLength--] = '0';
                chars[targetLength--] = '2';
                chars[targetLength--] = '%';
            } else {
                chars[targetLength--] = chars[usedLength];
            }
            usedLength--;
        }
        return temp;
    }

public static void main(String[] args) {
        char[] string = new char[20];
        string[0] = 'w';
        string[1] = 'e';
        string[2] = ' ';
        string[3] = 'a';
        string[4] = 'r';
        string[5] = 'e';
        string[6] = ' ';
        string[7] = 'h';
        string[8] = 'a';
        string[9] = 'p';
        string[10] = 'p';
        string[11] = 'y';
        string[12] = '.';
        int length = replaceBlank(string, 13);//傳遞的長度是已經(jīng)使用的長度商佛，而數(shù)組的長度要比已使用的長度長，并且超過替換后的長度
        System.out.println(new String(string, 0, length));
    }

單鏈表

插入：將要插入的節(jié)點(diǎn)指向頭節(jié)點(diǎn)姆打，并將指針往后移動(dòng)良姆，直到后續(xù)節(jié)點(diǎn)為null，將新節(jié)點(diǎn)插入

刪除：只需要將節(jié)點(diǎn)往后移即可

public static void main(String[] args) {
        ListNode node = new ListNode(2);
        addNode(node,4);
        addNode(node,5);
        addNode(node,6);
        removeNode(node, 2);
        removeNode(node, 5);
        printNode2(node);
    }
    
    public static Stack<Integer> stack = new Stack<>();
    public static LinkedList<Integer> list = new LinkedList<>();
    //從頭到尾打印鏈表
    public static void printNode2(ListNode head) {
        ListNode cur = head;
        while (cur != null) {
            list.add(cur.val);
            cur = cur.node_next;
        }
        while (!list.isEmpty()) {
            System.out.print(list.pop()+"-->");
        }
    }
    //打印鏈表(利用棧從尾到頭打印鏈表)
    public static void printNode(ListNode head) {
        ListNode cur = head;
        while (cur != null) {
            stack.push(cur.val);
            cur = cur.node_next;
        }
        while (!stack.isEmpty()) {
            System.out.print(stack.pop()+"-->");
        }
    }
    //刪除節(jié)點(diǎn)
    public static void removeNode(ListNode head,int val) {
        if (head==null) {
            return;
        }
        if (head.val == val) {
            head = head.node_next;
        }else {
            ListNode curNode = head;
            while (curNode.node_next!=null && curNode.node_next.val != val) {
                curNode = curNode.node_next;
            }
            if (curNode.node_next !=null && curNode.node_next.val==val) {
                curNode.node_next = curNode.node_next.node_next;
            }
        }
    }
    //插入節(jié)點(diǎn)
    public static void addNode(ListNode head,int val) {
        ListNode newNode = new ListNode(val);
        if (head==null) {
            head = newNode;
        }else {
            ListNode CurNode = head;
            while (CurNode.node_next != null) {
                CurNode = CurNode.node_next;
            }
            CurNode.node_next = newNode;
        }
    }
    //結(jié)構(gòu)體
    static class ListNode{
        int val;
        ListNode node_next;
        public ListNode(int val) {
            super();
            this.val = val;
        }
    }

二叉樹的構(gòu)造

利用中序和后序構(gòu)造二叉樹

public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(postorder.length == 0 || inorder.length == 0) return null;
        Index index = new Index();
        index.index = postorder.length - 1;
        return helper(0,inorder.length - 1,inorder,postorder,index);
    }
    class Index 
    {
        int index;
    }
    public TreeNode helper(int inStart,int inEnd,int[] inorder, int[] postorder,Index index){
        if(inStart > inEnd) {
            return null;
        }else{
            TreeNode root = new TreeNode(postorder[index.index]);
            index.index--;
            int mid = 0;
            for(int i=inStart;i<=inEnd;i++){
                if(inorder[i] == root.val){
                    mid = i;
                }
            }
            root.right = helper(mid+1,inEnd,inorder, postorder,index);
            root.left = helper(inStart,mid-1,inorder, postorder,index);
            return root;
        }
    }

前序和中序構(gòu)造二叉樹

public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length == 0 || inorder.length == 0) return null;
        return helper(0,inorder.length - 1,preorder,inorder);
    }
    int preStart = 0;
    public TreeNode helper(int inStart,int inEnd,int[] preorder, int[] inorder){
        if(preStart>preorder.length || inStart>inEnd){
            return null;
        }else{
            TreeNode root = new TreeNode(preorder[preStart]);
            int mid = 0;
            for(int i=inStart;i<=inEnd;i++){
                if(inorder[i] == preorder[preStart]){
                    mid = i;
                }
            }
            preStart++;
            root.left = helper(inStart,mid-1,preorder,inorder);
            root.right = helper(mid+1,inEnd,preorder,inorder);
            return root;
        }
}

兩個(gè)棧實(shí)現(xiàn)隊(duì)列

public class StackToQueue {

    Stack<Integer> stack1 = new Stack<>();
    Stack<Integer> stack2 = new Stack<>();

    public void addLast(int x) {
        stack1.push(x);
    }
    
    public int removeFirst() {
        if (size()!=0) {//彈出條件：當(dāng)隊(duì)列不為空的時(shí)候
            if (stack2.isEmpty()) {//當(dāng)s2為空的時(shí)候穴肘，將s1中的數(shù)字壓入s2
                while (!stack1.isEmpty()) {
                    stack2.push(stack1.pop());
                }
            }
            return stack2.pop();//只要s2不為空歇盼，就彈出
        }else {
            System.out.println("隊(duì)列已空");
            return -1;
        }
    }

    public int size() {
        return stack1.size() + stack2.size();
    }

    public static void main(String[] args) {
        StackToQueue queue = new StackToQueue();
         queue.addLast(1);
         queue.addLast(2);
         queue.addLast(3);
         queue.addLast(4);
         System.out.println(queue.removeFirst());
         System.out.println(queue.removeFirst());
         System.out.println(queue.removeFirst());
         queue.addLast(5);
         queue.addLast(6);
         System.out.println(queue.removeFirst());
         System.out.println(queue.removeFirst());
         System.out.println(queue.removeFirst());
    }
}

兩個(gè)隊(duì)列實(shí)現(xiàn)棧

public class QueueToStack {

    LinkedList<Integer> queue1 = new LinkedList<>();
    LinkedList<Integer> queue2 = new LinkedList<>();

    public void push(int x) {
        queue1.addLast(x);
    }

    public int pop() {
        if (size() != 0) {
            if (queue1.size() > 1) {
                putN_1ToAnthor();
                return queue1.removeFirst();
            } else {
                putN_1ToAnthor();
                return queue2.removeFirst();
            }
        } else {
            System.out.println("棧已空");
            return -1;
        }
    }

    // 移動(dòng)n-1個(gè)到另一個(gè)隊(duì)列
    public void putN_1ToAnthor() {
        if (!queue1.isEmpty()) {
            while (queue1.size() > 1) {
                queue2.addLast(queue1.removeFirst());
            }
        } else if (!queue2.isEmpty()) {
            while (queue2.size() > 1) {
                queue1.addLast(queue2.removeFirst());
            }
        }
    }

    public int size() {
        return queue1.size() + queue2.size();
    }

    public static void main(String[] args) {
        QueueToStack stack = new QueueToStack();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        stack.push(5);
        stack.push(6);
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
    }
}

旋轉(zhuǎn)數(shù)組中最小數(shù)

public static int min(int[] nums) {
        int p1 = 0;
        int p2 = nums.length - 1;
        int mid = p1;
        while (nums[p1] >= nums[p2]) {
            if (p2 - p1 == 1) {
                mid = p2;
                break;
            }
            mid = (p1 + p2) / 2;
            if (nums[p1] == nums[p2] && nums[p1] == nums[mid]) {
                int temp = nums[p1];
                for (int i = 0; i < nums.length; i++) {
                    if (temp > nums[i]) {
                        temp = nums[i];
                    }
                }
                return temp;
            }
            if (nums[mid] >= nums[p1]) {
                p1 = mid;
            } else if (nums[mid] <= nums[p2]) {
                p2 = mid;
            }
        }
        return nums[mid];
    }

二進(jìn)制中1的個(gè)數(shù)

public static int numberOf2(int n) {
        int count = 0;
        while (n>0) {
            count += n&1;
            n = n>>1;
        }
        return count;
}
    
public static int numberOf1(int n) {
        int count = 0;
        while (n>0) {
            ++count;
            n = (n-1)&n;
        }
        return count;
}

數(shù)值的整數(shù)次方

1. 當(dāng)exponent為負(fù)數(shù)時(shí)，轉(zhuǎn)成正數(shù)求解后评抚，求解其倒數(shù)
2. 當(dāng)exponent為0時(shí)豹缀，直接返回0，當(dāng)exponent為1時(shí)慨代，返回base本身
3. 當(dāng)base小數(shù)為0時(shí)邢笙，不能直接和0比較，需要重寫equals方法侍匙，并且base為0考慮其為非法輸入氮惯。
4. 使用exponent>>1 代替除法叮雳，使用位與運(yùn)算代替 %，位運(yùn)算效率比乘除法高妇汗。

public static double power(double base, int exponent) {
        // 判斷底數(shù)為0并且指數(shù)小于0
        if (equals(base, 0.0) && exponent < 0) {
            invalideInput = true;
            return 0.0;
        }
        int absExponent = exponent;
        if (exponent > 0) {
            absExponent = exponent;
        }
        if (exponent < 0) {
            absExponent = -exponent;
        }
        double result = powerWithUnsignExponent(base, absExponent);
        if (exponent < 0) {
            result = 1.0 / result;
        }
        return result;
    }

    public static double powerWithUnsignExponent(double base, int exponent) {
        if (exponent == 0) {
            return 1;
        }
        if (exponent == 1) {
            return base;
        }
        double result = powerWithUnsignExponent(base, exponent >> 1);
        result *= result;
        //a^n = a^(n/2) * a^(n/2) (n為偶數(shù))
        //a^n = a^(n/2) * a^(n/2) * a (n為奇數(shù))
        //這個(gè)公式可以將時(shí)間復(fù)雜度提高到O(logn)帘不，否則直接求指數(shù)到時(shí)間復(fù)雜度為O(n)
        if ((exponent & 0x1) == 1) {//判斷exponent是奇數(shù)還是偶數(shù)
            result *= base;
        }
        return result;
    }

    public static boolean equals(double m, double n) {
        if ((m - n > -0.000001) && (m-n) < 0.000001) {
            return true;
        } else {
            return false;
        }
    }

打印1到最大的n位數(shù)

public static boolean isCrement(int[] number) {
        boolean isOverFlow = false;
        int takeOver = 0;
        for (int i = number.length-1; i >=0; i--) {
            int sum = number[i] + takeOver;
            if (i == number.length-1) {
                sum++;
            }
            if (sum>=10) {
                if (i==0) {
                    isOverFlow = true; 
                }else {
                    takeOver = 1;
                    sum -= 10;
                    number[i] = sum;
                }
            }else {
                number[i] = sum;
                break;
            }
        }
        return isOverFlow;
    }
    
    public static void printNumber(int[] number) {
        boolean isBeginning = true;
        for (int i = 0; i < number.length; i++) {
            if (isBeginning && number[i] != 0) {
                isBeginning = false;
            }
            if (!isBeginning) {
                System.out.print(number[i]);
            }
        }
        System.out.println();
    }
    
    public static void printMaxOfNDigits(int n) {
        if (n<0) {
            System.out.println("輸入出錯(cuò)");
        }
        int[] number = new int[n];
        while (!isCrement(number)) {
            printNumber(number);
        }
    }

在O(1)時(shí)間內(nèi)刪除節(jié)點(diǎn)

時(shí)間復(fù)雜度

((n-1)*O(1) + O(n))/n = O(1)

只有在尾節(jié)點(diǎn)時(shí)需要從頭節(jié)點(diǎn)遍歷，時(shí)間復(fù)雜度為O(n)杨箭，其他時(shí)候復(fù)雜度為O(1)寞焙，綜合起來時(shí)間復(fù)雜度還是O(1)

1. 當(dāng)只有一個(gè)節(jié)點(diǎn)的時(shí)候（頭節(jié)點(diǎn)也是尾街店），直接刪除即可
2. 當(dāng)有多個(gè)節(jié)點(diǎn)并是中間節(jié)點(diǎn)時(shí)互婿，將要?jiǎng)h除的節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)的值復(fù)制到要?jiǎng)h除的節(jié)點(diǎn)并覆蓋它的值捣郊，然后把它后面的節(jié)點(diǎn)刪掉
3. 當(dāng)是尾節(jié)點(diǎn)的時(shí)候，需要從頭節(jié)點(diǎn)開始遍歷慈参，并刪除該節(jié)點(diǎn)

public static ListNode deleteNode(ListNode head, ListNode toDeleteNode) {
        if (head == null || toDeleteNode == null) {
            return head;
        }
        if (head == toDeleteNode) {
            return head.node_next;
        }
        // 要?jiǎng)h除的不是尾節(jié)點(diǎn)
        //將要?jiǎng)h除的下一個(gè)節(jié)點(diǎn)的值復(fù)制到要?jiǎng)h除的節(jié)點(diǎn)上呛牲，然后刪除它的下一個(gè)節(jié)點(diǎn)
        if (toDeleteNode.node_next != null) {
            toDeleteNode.val = toDeleteNode.node_next.val;
            toDeleteNode.node_next = toDeleteNode.node_next.node_next;
        } else if (toDeleteNode.node_next == head) {// 鏈表中只有一個(gè)節(jié)點(diǎn)，刪除頭節(jié)點(diǎn)（也是尾節(jié)點(diǎn)）
            toDeleteNode = null;
            head = null;
        } else {// 鏈表中有多個(gè)節(jié)點(diǎn)驮配，刪除尾節(jié)點(diǎn)
            ListNode curNode = head;
            while (curNode.node_next != null) {
                curNode = curNode.node_next;
            }
            curNode = null;
            toDeleteNode = null;
        }
        return head;
    }

調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面

二分讓時(shí)間復(fù)雜度降低娘扩，提高擴(kuò)展性，使用一個(gè)函數(shù)來規(guī)定函數(shù)條件成立的標(biāo)準(zhǔn)

public static void order(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            while (left < right && !isEven(nums[left])) {
                left++;
            }
            while (left<right && isEven(nums[right])) {
                right--;
            }
            if(isEven(nums[left]) && !isEven(nums[right])) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
            }
        }
    }
    //判斷一個(gè)數(shù)是否是偶數(shù)
    public static boolean isEven(int n) {
        return (n & 1) == 0;
    }

鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)

public static ListNode kthNodeFromEnd(ListNode head,int k) {
        //當(dāng)頭指針為空或者k=0時(shí)僧凤，不在考慮范圍內(nèi)
        if (head==null || k==0) {
            return null;
        }
        ListNode pNode = head;
        ListNode pBehind = null;
        for (int i = 0; i < k-1; i++) {
            if (pNode.node_next!=null) {
                pNode = pNode.node_next;//先走到k-1到位置上
            }else {
                return null;//當(dāng)鏈表長度小于k當(dāng)時(shí)候畜侦，會(huì)拋空指針
            }
        }
        pBehind = head;
        while (pNode.node_next!=null) {
            pNode = pNode.node_next;//繼續(xù)走直到走到鏈表尾部
            pBehind = pBehind.node_next;//后一個(gè)指針從頭節(jié)點(diǎn)開始元扔，當(dāng)前面一個(gè)指針走到尾部躯保，循環(huán)結(jié)束，該指針剛好走到第k個(gè)位置上
        }
        return pBehind;
    }

反轉(zhuǎn)鏈表

三個(gè)指針分別記錄當(dāng)前節(jié)點(diǎn)澎语，當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)和上一個(gè)節(jié)點(diǎn)途事，記錄上一個(gè)和下一個(gè)節(jié)點(diǎn)未來防止反轉(zhuǎn)之后鏈表斷裂，反轉(zhuǎn)之后的頭節(jié)點(diǎn)就是為節(jié)點(diǎn)擅羞。

public static ListNode reverseNode(ListNode head) {
        if (head==null) {
            return null;
        }
        ListNode pReverseHead = null;//轉(zhuǎn)換后的頭節(jié)點(diǎn)
        ListNode pNode = head;//當(dāng)前節(jié)點(diǎn)
        ListNode pPrev = null;//當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
        while (pNode!=null) {
            ListNode pNext = pNode.node_next;
            if (pNext==null) {
                pReverseHead = pNode;
            }
            pNode.node_next = pPrev;
            pPrev = pNode;
            pNode = pNext;
        }
        return pReverseHead;
    }

合并兩個(gè)排序的鏈表

public static ListNode mergeNode(ListNode head1,ListNode head2) {
        if (head1==null) {
            return head2;
        }else if (head2==null) {
            return head1;
        }
        ListNode pMergedHead = null;
        if (head1.val < head2.val) {
            pMergedHead = head1;
            pMergedHead.node_next = mergeNode(head1.node_next, head2);
        }else {
            pMergedHead = head2;
            pMergedHead.node_next = mergeNode(head1, head2.node_next);
        }
        return pMergedHead;
    }

樹的子結(jié)構(gòu)

public static boolean sameSubTree(TreeNode node1,TreeNode node2) {
        if (node1==null && node2 == null) {
            return false;
        }
        boolean result = false;
        if (node1.val == node2.val) {
            result = doesTree1HasTree2(node1, node2);
        }
        if (!result) {
            result = doesTree1HasTree2(node1.left, node2);
        }
        
        if (!result) {
            result = doesTree1HasTree2(node1.right, node2);
        }
        return result;
    }
    
    public static boolean doesTree1HasTree2(TreeNode node1,TreeNode node2) {
        if (node2==null) {
            return true;
        }
        if (node1 == null) {
            return false;
        }
        if (node1.val != node2.val) {
            return false;
        }
        return doesTree1HasTree2(node1.left, node2.left) && doesTree1HasTree2(node1.right, node2.right);
    }

樹的鏡像

public static void mirrorTreeNode(TreeNode node) {
        if (node == null) {
            return;
        }
        if (node.left== null && node.right == null) {
            return;
        }
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
        if (node.left!=null) {
            mirrorTreeNode(node.left);
        }
        if (node.right!=null) {
            mirrorTreeNode(node.right);
        }
    }

順時(shí)針打印矩陣

public static void printMatrixInCircle(int[][] nums) {
        if (nums == null || nums.length == 0 || nums[0].length == 0) {
            return;
        }
        int start = 0;
        while (nums.length > start * 2 && nums[0].length > start * 2) {
            printMatrixInCircle(nums, nums.length, nums[0].length, start);
            start++;
        }
    }

    private static void printMatrixInCircle(int[][] nums, int rows, int cols, int start) {
        int endX = cols - 1 - start;
        int endY = rows - 1 - start;
        // 從左往右打印一行
        for (int i = start; i <= endX; ++i) {
            printNumber(nums[start][i]);
        }
        System.out.println();
        // 從上到下打印一列
        for (int i = start+1; i <= endY; i++) {
            printNumber(nums[i][endX]);
        }
        System.out.println();
        // 從右到左打印一行
        if (start < endX && start < endY) {
            for (int i = endX - 1; i >= start; --i) {
                printNumber(nums[endY][i]);
            }
            System.out.println();
        }
        // 從下到上打印一列
        if (start < endX && start < endY - 1) {
            for (int i = endY - 1; i >= start + 1; --i) {
                printNumber(nums[i][start]);
            }
            System.out.println();
        }
    }

    private static void printNumber(int number) {
        System.out.print(number + " ");
    }

包含min函數(shù)的棧

public class MinStack {

    Stack<Integer> date = new Stack<>();
    Stack<Integer> min = new Stack<>();

    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(3);
        minStack.push(4);
        minStack.push(2);
        minStack.push(1);
        minStack.push(0);
        System.out.println(minStack.pop());
        System.out.println(minStack.min());
        System.out.println(minStack.min());
    }

    public void push(int x) {
        date.push(x);
        if (min.size() == 0 || x < min.peek()) {
            min.push(x);
        }else {
            min.push(min.peek());
        }
    }
    
    public int pop() {
        if (date.size()>0 && min.size()>0) {
            min.pop();
            return date.pop();
        }
        return -1;
    }
    
    public int min() {
        if (date.size()>0 && min.size()>0) {
            return min.peek();
        }
        return -1;
    }
}

棧的壓入尸变、彈出序列

public static boolean isPopOrder(int[] pushList,int[] popList) {
        if (pushList==null || popList==null || pushList.length==0 || popList.length == 0) {
            return false;
        }
        Stack<Integer> pushStack = new Stack<>();
        int pushIndex = 0;
        int popIndex = 0;
        while (popIndex < popList.length) {
            //入棧元素還未全部入棧的條件下，如果棧為空减俏，或者棧頂元素不與當(dāng)前處理的相等召烂，則一直進(jìn)行入棧操作，直到入棧元素全部入椡蕹校或者找到出棧元素相等的元素
            while (pushIndex<pushList.length && (pushStack.isEmpty() || pushStack.peek() != popList[popIndex])) {
                //入棧數(shù)組中的元素入棧
                pushStack.push(pushList[pushIndex]);
                //指向下一個(gè)要處理的入棧元素
                pushIndex++;
            }
            //如果在上一步的入棧操作中找到了與出棧元素相等的元素
            if (pushStack.peek() == popList[popIndex]) {
                pushStack.pop();//將元素出棧
                popIndex++;//指向下一個(gè)要處理的元素
            }else {
                return false;//如果沒有找到與出棧元素相等的元素奏夫，說明出棧順序不合法
            }
        }
        return true;
    }

二叉樹的后序遍歷序列

private static boolean verifySequenceOfBST(List<Integer> sequence, int start, int end) {
        if (start >= end) {
            return true;
        }
        int index = start;
        //從左往右找到第一個(gè)不大于根節(jié)點(diǎn)都元素的位置
        while (index<end-1 && sequence.get(index) < sequence.get(end)) {
            index++;
        }
        //到此，[start,index-1]的值都比根節(jié)點(diǎn)小历筝，[start,index-1]可以看作是根節(jié)點(diǎn)都左子樹
        //right記錄第一個(gè)不小于根節(jié)點(diǎn)都位置
        int right = index;
        //找到[index,end-1]都所有元素都大于根節(jié)點(diǎn)酗昼，[index,end-1]為根節(jié)點(diǎn)都右子樹
        while (index<end-1 && sequence.get(index) > sequence.get(end)) {
            index++;
        }
        //當(dāng)index=end-1，說明目前是合法的
        if (index!=end-1) {
            return false;
        }
        index = right;//right記錄的第一個(gè)不大于根節(jié)點(diǎn)的位置梳猪，遞歸判斷左子樹和右子樹是否合法
        return verifySequenceOfBST(sequence, start, index - 1) && verifySequenceOfBST(sequence, index, end - 1);
    }

二叉樹中和胃某一值的路徑

    public static void findPath(TreeNode node, int expectSum) {
        List<Integer> path = new ArrayList<>();
        if (node != null) {
            findPath(node, path, expectSum, 0);
        }
    }

    public static void findPath(TreeNode node, List<Integer> path, int expectSum, int curSum) {
        if (node == null) {
            return;
        }
        path.add(node.val);
        curSum += node.val;

        if (curSum < expectSum) {
            if (node.left != null) {
                findPath(node.left, path, expectSum, curSum);
            }
            if (node.right != null) {
                findPath(node.right, path, expectSum, curSum);
            }
        } else if (curSum == expectSum) {
            if (node.left == null && node.right == null) {
                for (Integer val : path) {
                    System.out.print(val + " ");
                }
            }
        }
        path.remove(path.size() - 1);
        curSum -= node.val;
    }

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

public static void cloneNode(ListNode head) {
        if (head == null) {
            return;
        }
        ListNode pNode = head;
        ListNode cloneNode = new ListNode();
        cloneNode.val = pNode.val;
        cloneNode.node_next = pNode.node_next;
        pNode.node_next = cloneNode;
        pNode = cloneNode.node_next;
        cloneNode.node_sibling = null;
    }

    public static void connectSiblingNode(ListNode head) {
        if (head == null) {
            return;
        }
        ListNode pNode = head;
        if (pNode != null) {
            ListNode cloneNode = pNode.node_next;
            while (pNode.node_sibling != null) {
                cloneNode.node_sibling = pNode.node_sibling.node_next;
                pNode = cloneNode.node_next;
            }
        }
    }

    public static ListNode reConnectNode(ListNode head) {
        ListNode cloneHead = null;
        ListNode cloneNode = null;
        ListNode pNode = head;
        if (pNode != null) {
            cloneHead = cloneNode = pNode.node_next;
            pNode.node_next = cloneNode.node_next;
            pNode = cloneNode.node_next;
            cloneNode.node_next = pNode.node_next;
            cloneNode = cloneNode.node_next;
        }
        return cloneHead;
    }

    public static ListNode clone(ListNode head) {
        cloneNode(head);
        connectSiblingNode(head);
        return reConnectNode(head);
    }

    static class ListNode {
        int val;
        ListNode node_next;
        ListNode node_sibling;
    }