剑指Offer

3.数组中重复的数字

排序遍历

可以直接将数组排序，然后进行循环遍历，就可以找到数组中重复的数字了。

class Solution {
    public int findRepeatNumber(int[] nums) {
        Arrays.sort(nums);
        for (int i = 1;i < nums.length; i++) {
            if (nums[i] == nums[i - 1]) {
                return nums[i];
            }
        }
        return 0;
    }
}

Set去重

可以将该数组丢到Set集合里去重，若是添加失败就代表该数字重复，直接返回就好了。

class Solution {
    public int findRepeatNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i : nums) {
            if (!set.add(i)) {
                return i;
            }
        }
        return 0;
    }
}

哈希表

跟Set差不多，添加到哈希表之前，先判断一下是否有该键，然后要是有就直接返回。

class Solution {
    public int findRepeatNumber(int[] nums) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i : nums) {
            if (map.containsKey(i)) {
                return i;
            }
            map.put(i,i);
        }
        return 0;
    }
}

原地置换（类似桶排序）

遍历数组，将每一个数放在与它等值的下标下，因为题目说了数字都在1~n - 1，所以当该下标出现了与它一样的数字，代表这个数字是重复的。

class Solution {
    public int findRepeatNumber(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
           while(nums[i] != i) {
                if(nums[i] == nums[nums[i]]) return nums[i];
                int temp = nums[i];
                nums[i] = nums[temp];
                nums[temp] = temp;
           }
        }
        return 0;
    }
}

衍生题

题目详情可以参考https://www.acwing.com/problem/content/description/15/。

这里可以使用上述的哈希和Set集合来进行查找，或者在创建一个数组，然后使用桶排序找出重复的元素。

因为必定会有一个重复的，可以理解为数组中间会出现一个环，所以可以当成寻找链表的环。

class Solution {
    public int duplicateInArray(int[] nums) {
        // 快慢指针寻找相遇点
        int fast = 0；
        int slow = 0;
        while (fast == 0 || fast != slow) {
            fast = nums[nums[fast]];
            slow = nums[slow];
        }
        // 寻找入环点
        fast = 0;
        while (fast != slow) {
            fast = nums[fast];
            slow = nums[slow];
        }
        return slow;
    }
}

还有就是利用分治的思想来解。类似二分查找的思想。

利用数值将数组分成两半，如果一边坑的个数小于数的个数，代表重复的数字就在那半边，所以缩小区间，直到找到。

class Solution {
    public int duplicateInArray(int[] nums) {
        int l = 1;
        int r = nums.length - 1;
        while (l < r) {
            int mid = l + r >> 1;     // 分成两个区间[l, mid]和[mid + 1, r]
            int count = 0;  
            // 统计[l, mid]的个数
            for(int i : nums)
            {
                if(l <= i && i <= mid)
                    count++;
            }
			// 个数若是大于坑位，代表该区间有重复的数字，然后调整区间
            if(count > mid - l + 1)
                r = mid;
            else 
                l = mid + 1;
        }
        return l;
    }
}

4.二维数组中的查找

数组遍历

直接将这个二维数组遍历，暴力破解。

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        for (int[] i : matrix) {
            for (int j : i) {
                if (j == target) return true;
            }
        }
        return false;
    }
}

二维查找

根据递增的单调性，可以从最右上角一个个进行排除，寻找对应的值。可以从右下角向左下角进行遍历（反过来也可以）。

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) return false;
        int i = 0;
        // 从最后一列开始，排除最后一列小于给定值的行
        int j = matrix[0].length - 1;
        while(i < matrix.length && j >= 0) {
            if (matrix[i][j] == target) return true;
            // 如果值大于给定值，代表当前行不存在给定值，所以遍历下一行
            if (matrix[i][j] > target) j--;
            else i++;
        }
        return false;
    }
}

5.替换空格

replaceAll

String类里就自带一个替换的方法了，所以可以直接进行替换。

class Solution {
    public String replaceSpace(String s) {
        return s.replaceAll(" ","%20");
    }
}

遍历字符串

直接遍历字符串，出现了空格就替换，不然就不替换。

class Solution {
    public String replaceSpace(String s) {
        StringBuilder res = new StringBuilder();
        char[] str = s.toCharArray();
        for (char c : str) {
            if (c == ' ') res.append("%20");
            else res.append(c);
        }
        return res.toString();
    }
}

要是不能用动态的增加字符串，就只能先遍历一遍字符串，然后判断答案的长度，然后在创建一个新的数组，然后依次放入新数组就好了。

6. 从尾到头打印链表

反转链表后输出

这里最简单的解法就是将链表反转，然后在打印链表了。

class Solution {
    public int[] reversePrint(ListNode head) {
        if (head == null) return new int[0];
        ListNode newhead = reverse(head);
        List<Integer> list = new ArrayList<>();
        while(newhead != null) {
            list.add(newhead.val);
            newhead = newhead.next;
        }
        int[] res = new int[list.size()];
        for (int i = 0; i< list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
    public ListNode reverse(ListNode head) {
        if (head.next == null) return head;
        ListNode newhead = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return newhead;
    }
}

递归遍历

这里可以使用类似后序遍历的操作，先递归进去然后添加值，这样就类似栈了，直接从后到前输出。或者这里定义一个栈也可以进行。

class Solution {
    List<Integer> list = new ArrayList<>();
    public int[] reversePrint(ListNode head) {
        if (head == null) return new int[0];
        reverse(head);
        int[] res = new int[list.size()];
        for (int i = 0; i< list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
    public void reverse(ListNode head) {
        if (head == null) return;
        reverse(head.next);
        list.add(head.val);
    }
}

反向输出

其实可以看到，其实从前遍历，然后反向输出就行了，其实并不用一定是正向的数据。

class Solution {
    
    public int[] reversePrint(ListNode head) {
        if (head == null) return new int[0];
        List<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        int[] res = new int[list.size()];
        for (int i = 0; i< list.size(); i++) {
            res[i] = list.get(list.size() - i - 1);
        }
        return res;
    }

}

两次遍历

第一次遍历链表，判断数组的个数，然后从后往前赋值就好了。之前的解法也可以改为先进行一次遍历后再赋值，这样就不用使用list集合了，效率太低。

class Solution {
    
    public int[] reversePrint(ListNode head) {
        if (head == null) return new int[0];
        ListNode node = head;
        int size = 0;
        while(node != null) {
            size++;
            node = node.next;
        }
        int[] res = new int[size];
        for (int i = size - 1; i > -1;i--) {
             res[i] = head.val;
             head = head.next;
        }
        return res;
    }
}

7.重建二叉树

这题主要是要划分区间，划分好左子树和右子树的区间。

前序遍历的区间可以分为三个。根的值，左子树的值，右子树的值。

中序遍历的区间可以分为三个。左子树的值，根的值，右子树的值。

所以可以用前序遍历的第一个值创建节点，然后遍历前序遍历的数组，用中序遍历的数组来判断是否达到根的值。

class Solution {

    private int ino = 0;
    private int pre = 0;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder, inorder, Integer.MIN_VALUE + 1);
    }

    private TreeNode build(int[] preorder, int[] inorder, long stop) {
        if (pre >= preorder.length) return null;
        // 判断该子树是否碰到根
        if (inorder[ino] == stop) {
            ino++;
            return null;
        }
        TreeNode node = new TreeNode(preorder[pre++]);
        // 左子树的范围，到当前节点值，即到子树的根值(按前序遍历的数组)
        node.left = build(preorder,inorder,node.val);
        // 右子树的范围，从当前节点到最后
        node.right = build(preorder,inorder,stop);

        return node;
    }

}

上面是通过前序遍历和中序遍历去创建一颗二叉树，接下来是通过中序遍历和后序遍历来创建一个二叉树，其实差不多。

class Solution { 
    
    private int ino = 0;
    private int pos = 0;
    
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        pos = postorder.length - 1;
        ino = inorder.length - 1;
        return build(inorder,postorder,Integer.MIN_VALUE - 1);
    }
    
    public TreeNode build(int[] inorder, int[] postorder,long stop) {
        if (pos == -1) return null;
        if (inorder[ino] == stop) {
            ino--;
            return null;
        }
        TreeNode node = new TreeNode(postorder[pos--]);
        node.right = build(inorder,postorder,node.val);
        node.left = build(inorder,postorder,stop);
        return node;
    }
    
}

8.二叉树的下一个节点

题目详情可以参考https://www.acwing.com/problem/content/31/

这里就是直接找下一个节点就好了。

于是会有两种情况。

1. 当前节点有右子树。那么该节点的下一个节点就是右子树里的最左子节点。
2. 当前节点没有右子树，那就要追溯回原来第一个是其father左儿子的节点。
   • 该节点是父节点的左孩子，这样下一个节点就是它的father
   • 该节点是父孩子的右孩子，这样下一个节点就是该左子树的父节点

class Solution {
    public TreeNode inorderSuccessor(TreeNode p) {
        // 存在右子树的情况
        if (p.right != null) {
            p = p.right;
            while(p.left != null) p = p.left;
            return p;
        }
        // 不存在右子树的情况
        while(p.father != null && p == p.father.right) p = p.father;
        
        return p.father;
    }
}

9.用两个栈实现队列

这里先来分析一下这两个栈的作用。栈是先进后出的数据结构，而队列是先进先出的，所以无法进行互通，引入第二个栈是用来存储第一个栈中出栈的元素，这样第二个栈的元素就是第一个栈元素的倒序了，直接出栈就是最先进来的元素了。

入队就直接压入第一个栈中就可以了。

主要是要探讨出队的情况。

1. 当第二个栈中还有元素的时候，代表这些元素是最先进入的元素，所以直接出栈就是之前最先入队的元素了。
2. 当第二个栈和第一个栈都没有元素了，那就证明队列为空。
3. 当第二个栈没有元素，第一个栈有元素，那就直接将第一个栈的元素全部出栈压入第二栈，实现倒序。

class MyQueue {
    
    Stack<Integer> stack1 = new Stack();
    Stack<Integer> stack2 = new Stack();
    
    /** Initialize your data structure here. */
    public MyQueue() {}
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        stack1.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if (!stack2.isEmpty()) return stack2.pop();
        if (!stack1.isEmpty()) {
            while(!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
            return stack2.pop();
        }
        return -1;
    }
    
    /** Get the front element. */
    public int peek() {
        if (!stack2.isEmpty()) return stack2.peek();
        if (!stack1.isEmpty()) {
            while(!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
            return stack2.peek();
        }
        return -1;
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        if (stack1.isEmpty() && stack2.isEmpty()) return true;
        else return false;
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

10.斐波那契数列

剑指Offer这题的斐波那契数列是结果取模的，因为返回的是int，除了这个需要注意的，其他的和经常的解法差不多了。

递归

可以考虑直接递归，但一般都会超时。

class Solution {
    public int fib(int n) {
        if (n < 0) return 0;
        if (n == 1 || n == 2) return 1;
        return (fib(n - 1) + fib(n - 2)) % 1000000007;
    }
}

dp数组的递归解法

class Solution {
    
    public int fib(int n) {
        int[] memo = new int[n + 1];
        Arrays.fill(memo,0);
        return dp(memo,n);
    }

    public int dp(int[] memo,int n) {
        if (n < 0) return 0;
        if (n == 1 || n == 2) return 1;
        if (memo[n] != 0) return memo[n];
        memo[n] = (dp(memo,n - 1) + dp(memo,n - 2)) % 1000000007;
        return memo[n];
    }

}

迭代解法

这里是可以考虑dp数组的迭代解法的，但是这里只是一次性达到答案，不会回头了，所以记录之前的状态并没有什么意思，所以可以创建临时变量保存需要的临时变量就可以了。

class Solution {
    public int fib(int n) {
        if (n <= 0) return 0;
        if (n == 1 || n == 2) return 1; 
        int a = 1;
        int b = 1;
        for (int i = 3;i <= n; i++) {
            int c = (a + b) % 1000000007;
            a = b;
            b = c;
        }
        return b;
    }
}

青蛙跳台阶

class Solution {
    public int numWays(int n) {
        if (n <= 1) return 1;
        if (n == 2) return 2;
        int a = 1;
        int b = 1;
        for (int i = 2;i <= n;i++) {
            int c = (a + b) % 1000000007;
            a = b;
            b = c;
        }
        return b;
    }
}

11.旋转数组的最小数字

排序

可以直接排序在取第一个。

class Solution {
    public int minArray(int[] numbers) {
        Arrays.sort(numbers);
        return numbers[0];
    }
}

不递增

找到第一个不递增的数字那就是最小的数字了。

class Solution {
    public int minArray(int[] numbers) {
        for (int i = 0;i < numbers.length - 1; i++) {
            if (numbers[i] > numbers[i + 1]) return numbers[i + 1];
        }
        return numbers[0];
    }
}

二分查找

二分查找最主要的就是划分区间，需要先分析一下怎样确定好区间。

1. 中间的数大于最右边的数，代表期间不会单调递增，直接进入右边的区间
2. 中间的数小于最右边的数，代表期间是单调递增的，直接进入左边的区间
3. 要是中间的数与最右边的数相等，那就缩进一下区间

class Solution {
    public int minArray(int[] numbers) {
        int l = 0;
        int r = numbers.length - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (numbers[mid] > numbers[r]) {
                l = mid + 1;
            } else if (numbers[mid] < numbers[r]) {
                r = mid;
            } else {
                r -= 1;
            }
        }
        return numbers[l];
    }
}

12.矩阵中的路径

经典的dfs和回溯。

class Solution {
    public boolean exist(char[][] board, String word) {
        if (board == null) return false;
        int row = board.length;
        int col = board[0].length;
        // 标记是否经过的数组
        boolean[][] isVisited = new boolean[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                // 遍历每个点，确定dfs的起点
                if (board[i][j] == word.charAt(0) && dfs(board,word,0,i,j,isVisited)) return true;
            }
        }
        return false;
    }

    public boolean dfs(char[][] board,String word,int n,int x,int y,boolean[][] isVisited){
        if (board[x][y] != word.charAt(n)) return false;
        if (n == word.length() - 1) return true;
        // 标记经过
        isVisited[x][y] = true;
        // 偏移数组，上下左右
        int[] dx = {0,0,-1,1};
        int[] dy = {-1,1,0,0};
        // 按上下左右开始偏移
        for (int i = 0; i < 4; i++) {
            int lx = x + dx[i];
            int ly = y + dy[i];
            // 保证下一步没有越界而且没有经过
            if (lx >= 0 && lx < board.length && ly >= 0 && ly < board[0].length && !isVisited[lx][ly]) {
                if (dfs(board,word,n + 1,lx,ly,isVisited)) return true;
            }
        }
        // 取消标记，回溯
        isVisited[x][y] = false;
        return false;
    }
}

13.机器人的运动范围

dfs

class Solution {
    public int movingCount(int m, int n, int k) {
        if (m == 0 || n == 0) return 0;
        boolean[][] isVisited = new boolean[m][n];
        return dfs(0,0,k,isVisited);
    }

    public int dfs(int i,int j,int k,boolean[][] isVisited) {
        if (i < 0 || i >= isVisited.length || j < 0 || j >= isVisited[0].length || isVisited[i][j] || !isAllowed(i,j,k)) return 0;
        isVisited[i][j] = true;
        // 上下左右
        return dfs(i-1,j,k,isVisited) + dfs(i+1,j,k,isVisited) + dfs(i,j-1,k,isVisited) + dfs(i,j+1,k,isVisited) + 1;
    }
	// 判断是否合法
    public boolean isAllowed(int m, int n, int k) {
        int sum = 0;
        while (m != 0) {
            sum += m % 10;
            m = m / 10;
        }
        while (n != 0) {
            sum += n % 10;
            n = n / 10;
        }
        if (sum <= k) return true;
        else return false;
    }
}

看看别人的发现判断是否合法不用这么麻烦，还可以优化一下，所以变成下面这样。

class Solution {
    public int movingCount(int m, int n, int k) {
        if (m == 0 || n == 0) return 0;
        boolean[][] isVisited = new boolean[m][n];
        return dfs(0,0,k,isVisited);
    }

    public int dfs(int i,int j,int k,boolean[][] isVisited) {
        if (i < 0 || i >= isVisited.length || j < 0 || j >= isVisited[0].length || isVisited[i][j] || (i/10+i%10+j/10+j%10)>k) return 0;
        isVisited[i][j] = true;
        return dfs(i-1,j,k,isVisited) + dfs(i+1,j,k,isVisited) + dfs(i,j-1,k,isVisited) + dfs(i,j+1,k,isVisited) + 1;
    }

}

从0,0开始，其实只用向右和向下就可以走完全部的格子了，所以可以去掉向左和向上的dfs。

class Solution {
    public int movingCount(int m, int n, int k) {
        if (m == 0 || n == 0) return 0;
        boolean[][] isVisited = new boolean[m][n];
        return dfs(0,0,k,isVisited);
    }

    public int dfs(int i,int j,int k,boolean[][] isVisited) {
        if (i >= isVisited.length || j >= isVisited[0].length || isVisited[i][j] || (i/10+i%10+j/10+j%10)>k) return 0;
        isVisited[i][j] = true;
        return dfs(i+1,j,k,isVisited) + dfs(i,j+1,k,isVisited) + 1;
    }

}

15.二进制中1的个数

用方法

有个方法是可以算出二进制中1的个数。

public class Solution {
    public int hammingWeight(int n) {
        return Integer.bitCount(n);
    }
}

位运算

通过数字与1的与运算，来判断最后一个二进制的数是不是1，是的话与运算会返回1，就这样逐个判断二进制1的个数。

public class Solution {
    public int hammingWeight(int n) {
        int res = 0;
        while(n != 0) {
            res += n & 1;
            n >>>= 1;
        }
        return res;
    }
}

还有一个就是用n & (n - 1)来判断，这样的与运算会消去二进制中最右边的1。

public class Solution {
    
    public int hammingWeight(int n) {
        int res = 0;
        while (n != 0) {
            n = n & (n - 1);
            res++;
        }
        return res;
    }
}

n & (n - 1)还能用来判断是不是2的幂。

16.数值的整数次方

这里直接使用相乘的算法会超时，所以用到了快速幂的写法。这里需要注意的点是n为负数的时候，int的负数会比正数多一个，力扣上正好用到了这个边界−2147483648，所以需要用long类型来存储。

快速幂的迭代写法

class Solution {
    public double myPow(double x, int n) {
        if (n == 0) return 1;
        long a = n;
        double res = 1.0;
        if (n < 0) {
            x = 1 / x;
            a = -a;
        }
        while (a > 0) {
            if ((a & 1) == 1) res *= x;
            x = x * x;
            a = a >> 1;
        }
        return res;
    }
}

快速幂的递归写法

class Solution {
    public double myPow(double x, int n) {
        if (n == 0) return 1;
        if (n == -1) return 1 /x;
        if ((n & 1) == 1) return myPow(x * x,n >> 1) * x;
        else return myPow(x * x,n >> 1);
    }
}

18.删除链表的节点

这里可以直接查到那个需要删除的节点，然后改变链表的指向就好了。

迭代写法

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if (head == null) return null;
        if (head.val == val) return head.next;
        ListNode node = head;
        while (head.next.val != val) {
            head = head.next;
        } 
        head.next = head.next.next;
        return node;
    }
}

递归写法

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if (head == null) return null;
        if (head.val == val) return head.next;
        head.next = deleteNode(head.next,val);
        return head;
    }
}

21.调整数组顺序使奇数位于偶数前面

这题一看题目就是有点像快排的思想，双指针遍历就好了。

class Solution {
    public int[] exchange(int[] nums) {
        if (nums.length == 0) return new int[0];
        int pre = 0;
        int cur = nums.length - 1;
        while (cur > pre) {
            while (nums[pre] % 2 != 0 && pre < cur) pre++;
            while (nums[cur] % 2 == 0 && pre < cur) cur--;
            int temp = nums[pre];
            nums[pre] = nums[cur];
            nums[cur] = temp;
        }
        return nums;
    }
}

22.链表中倒数第K个节点

快慢指针

这题用快慢指针还是很简单的，先让快指针走N步，然后快慢指针一起走，当快指针都到链表尾部，那么慢指针就是倒数第K个节点了。

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast = head;
        ListNode slow = head;
        while (k-- > 0) fast = fast.next;
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

24.反转链表

迭代

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode node = cur.next;
            cur.next = pre;
            pre = cur;
            cur = node;
        }
        return pre;
    }
}

递归

class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(head);
    }
    public ListNode reverse(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode last = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }
}

25.合并两个排序的链表

迭代

这个只要遍历就好了。

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l2 == null) return l1;
        if (l1 == null) return l2;
        ListNode res = new ListNode();
        ListNode node = res;
        while (l1 != null && l2 != null) {
            if (l1.val > l2.val) {
                node.next = new ListNode(l2.val);
                l2 = l2.next;
                node = node.next;
            } else {
                node.next = new ListNode(l1.val);
                l1 = l1.next;
                node = node.next;
            }
        }
        if (l1 == null) node.next = l2;
        if (l2 == null) node.next = l1;
        return res.next;
    }
}

递归

递归的解法挺简洁的，但是可能会有点绕。

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l2 == null) return l1;
        if (l1 == null) return l2;
        if (l1.val <= l2.val) {
            l1.next = mergeTwoLists(l1.next,l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        }
    }
}

27.二叉树的镜像

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if (root == null) return null;
        TreeNode node = new TreeNode(root.val);
        node.left = mirrorTree(root.right);
        node.right = mirrorTree(root.left);
        return node;
    }
}

28.对称的二叉树

这题递归主要是要理清思路。将左子树和右子树传入，然后比较值，在将左子树的左子树和右子树的右子树，右子树的左子树和左子树的右子树放入递归判断就好了。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return issymmetric(root.left,root.right);
    }
    public boolean issymmetric(TreeNode left,TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;
        if (left.val != right.val) return false;
        return issymmetric(left.left,right.right) && issymmetric(left.right,right.left);
    }
}

29.顺时针打印矩阵

这题和那题螺旋矩阵差不多，最主要的就是遍历的边界的界定，这还是有点麻烦的。

class Solution {
    public int[] spiralOrder(int[][] matrix) {
        int rows = matrix.length;
        if (rows == 0) return new int[0];
        int cols = matrix[0].length;
        if (cols == 0) return new int[0];
        int[] res = new int[rows * cols];
        int count = 0;
        int up = 0,down = rows - 1,left = 0,right = cols - 1;
        while (count < rows * cols) {
            // 向右，遍历完，上边界下移
            for (int i = left; i <= right; i++) res[count++] = matrix[up][i];
            up++;
            // 向下，遍历完，右边界左移
            for (int i = up; i <= down; i++) res[count++] = matrix[i][right];
            right--;
            // 向左，遍历完，下边界上移
            for (int i = right; i >= left && up <= down; i--) res[count++] = matrix[down][i];
            down--;
            // 向上，遍历完，左边界右移
            for (int i = down; i >= up && left <= right; i--) res[count++] = matrix[i][left];
            left++;
        }
        return res;
    }
}

30. 栈的压入和弹出序列

这题要先理清思路，首先要将压入序列压入栈，直到和弹出序列的第一个元素一样后，就要弹出直到和弹出序列不一样了在压入栈。这样直到压入序列遍历完了之后，要是栈为空的话，那就代表这个弹出序列不对。

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int count = 0;
        for(int i : pushed) {
            stack.push(i); 
            while(!stack.isEmpty() && stack.peek() == popped[count]) {
                stack.pop();
                count++;
            }
        }
        return stack.isEmpty();
    }
}

32.1.从上到下打印二叉树

这题就是层序遍历就可以了，要注意的就是确定数组的长度。

class Solution {
    public int[] levelOrder(TreeNode root) {
        int count = pro(root);
        if (count == 0) return new int[0];
        int[] res = new int[count];
        count = 0;
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        while (!deque.isEmpty()) {
            TreeNode node = deque.poll();
            res[count++] = node.val;
            if (node.left != null) deque.offer(node.left);
            if (node.right != null) deque.offer(node.right);
        }
        return res;

    }

    public int pro(TreeNode root) {
        if (root == null) return 0;
        return pro(root.left) + pro(root.right) + 1;
    }
}

32.2.从上到下打印二叉树

这个也是层序遍历，与上一题不一样的是要确定每层的节点数。

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null) return res;
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        while(!deque.isEmpty()) {
            int size = deque.size();
            List<Integer> list = new ArrayList<>();
            while(size > 0) {
                TreeNode node = deque.poll();
                list.add(node.val);
                if(node.left != null) deque.offer(node.left);
                if(node.right != null) deque.offer(node.right);
                size--;
            }
            res.add(list);
        }
        return res;
    }
}

32.3从上到下打印二叉树

这个就是要记录一下层数，这里的倒序可以分为两种解法。

1. 倒着加入到数组
2. 加入到数组后再倒序

两种方法哪个都可以，我就使用了第二种方法。

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null) return res;
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        int deep = 1;
        while(!deque.isEmpty()) {
            int size = deque.size();
            List<Integer> list = new ArrayList<>();
            while(size > 0) {
                TreeNode node = deque.poll();
                list.add(node.val);
                if(node.left != null) deque.offer(node.left);
                if(node.right != null) deque.offer(node.right);
                size--;
            }
            if (deep++ % 2 == 0) Collections.reverse(list);
            res.add(list);
        }
        return res;
    }
}