剑指Offer题解

发表于 | 分类于 |

剑指Offer题解。

数组中重复的数字

1
2
3
4
5
6
7
找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution{
    public int findRepeatNumber(int[] nums){
        int n = nums.length();
        for(int i = 0; i < n; i++){
            //当前索引不等于当前索引的值，且以值为索引的值不等于当前值，则需要交换
            while(i != nums[i] && nums[nums[i]] != nums[i]){
                //swap i, nums[i]
                int temp = nums[i];
                nums[i] = nums[nums[i]];
                nums[nums[i]] = temp;
            }
            if(nums[i] != i && nums[nums[i]] == nums[i]){
                return nums[i];
            }
        }
        
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution{
    public int findRepeatNumber(int[] nums){
        //使用HashSet
        set<Integer> set = new HashSet<>();
        for(int num : nums){
            if(!set.add(num)){
                return num;
            }
        }
        
        return -1;
    }
}

不修改数组找出重复的数字

1
2
3
4
给定一个长度为 n+1 的数组nums，数组中所有的数均在 1∼n 的范围内，其中 n≥1。
请找出数组中任意一个重复的数，但不能修改输入的数组。
给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。
返回 2 或 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution{
    public int duplicateInArray(int[] nums){
        //二分1~n
        int lo = 1, hi = nums.length-1;
        while(lo < hi){
            int mid = ((hi - lo) >> 1) + lo;//[lo, mid] [mid+1, hi]
            int count = 0;
            for(int num : nums){
                if(num >= lo && num <= mid){
                    count++;
                }
            }
            if(count > (mid-lo+1)){
                hi = mid;
            }else{
                lo = mid+1;
            }
        }
        
        return hi;
    }
}

二维数组中的查找

1
2
3
4
5
6
7
8
9
10
11
12
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

现有矩阵 matrix 如下：
[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution{
    public boolean findNumberIn2DArray(int[][] matrix, int target){
        //corner case
        if(matrix == null || matrix.length == 0){
            return false;
        }
        
        int i = matrix.length-1, j = 0;
        
        while(i >= 0 && j < matrix[0].length){
            if(matrix[i][j] == target){
                return true;
            }else if(matrix[i][j] > target){
                i--;
            }else{
                j++;
            }
        }
        
        return false;
    }
}

替换空格

1
2
3
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
输入：s = "We are happy."
输出："We%20are%20happy."
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution{
    public String replaceSpace(String s){
        //corner case
        if(s == null || s.length() == 0){
            return s;
        }
        
        StringBuilder res = new StringBuilder();
        for(char ch : s.toCharArray()){
            if(ch == ' '){
                res.append("%20");
            }else{
                res.append(ch);
            }
        }
        
        return res.toString();
    }
}

从头到尾打印链表

1
2
3
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
输入：head = [1,3,2]
输出：[2,3,1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution{
    public int[] reversePrint(ListNode head){
        //corner case
        if(head == null){
            return new int[0];
        }
        
        Deque<Integer> stack = new ArrayDeque<>();
        while(head != null){
            stack.push(head.val);
            head = head.next;
        }
        
        int[] res = new int[stack.size()];
        for(int i = 0; i < res.length; i++){
            res[i] = stack.pop();
        }
        
        return res;
    }
}

重建二叉树

1
2
3
4
5
6
7
输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

Input: preorder = [-1], inorder = [-1]
Output: [-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution{
    public TreeNode buildTree(int[] preorder, int[] inorder){
        //corner case
        if(preorder == null || preorder.length == 0){
            return null;
        }
        
        TreeNode root = new TreeNode(preorder[0]);
        
        int index = findIndex(preorder, inorder);
        
        root.left = buildTree(Arrays.copyOfRange(preorder, 1, index+1), Arrays.copyOfRange(inorder, 0, index));
        root.right = buildTree(Arrays.copyOfRange(preorder, index+1, preorder.length), Arrays.copyOfRange(inorder, index+1, inorder.length));
        
        return root;
    }
    
    private int findIndex(int[] preorder, int[] inorder){
        for(int i = 0; i < inorder.length; i++){
            if(preorder[0] == inorder[i]){
                return i;
            }
        }
        
        return -1;
    }
}

二叉树的下一个节点

1
2
3
4
5
6
7
8
9
10
11
给定一棵二叉树的其中一个节点，请找出中序遍历序列的下一个节点。

如果给定的节点是中序遍历序列的最后一个，则返回空节点;
二叉树一定不为空，且给定的节点一定不是空节点；

假定二叉树是：[2, 1, 3, null, null, null, null]， 给出的是值等于2的节点。
则应返回值等于3的节点。
解释：该二叉树的结构如下，2的后继节点是3。
  2
 / \
1   3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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;
    }
}

用两个栈实现队列

1
2
3
4
5
6
7
8
9
10
11
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]

输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class CQueue {

    private Deque<Integer> stack1;
    private Deque<Integer> stack2;

    public CQueue() {
        //init
        this.stack1 = new ArrayDeque<>();
        this.stack2 = new ArrayDeque<>();
    }
    
    public void appendTail(int value) {
        stack2.push(value);
    }
    
    public int deleteHead() {
        if(stack1.isEmpty()){
            while(!stack2.isEmpty()){
                stack1.push(stack2.pop());
            }
        }

        if(stack1.isEmpty()){
            return -1;
        }else{
            return stack1.pop();
        }
    }
}

斐波那契数列

1
2
3
4
5
输入一个整数 n ，求斐波那契数列的第 n 项。
假定从 0 开始，第 0 项为 0。(n≤39)

输入整数 n=5 
返回 5
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution{
    //滚动数组的方法
    public int Fibonacci(int n){
        int p = 0, q = 1, r = 0;
        for(int i = 0; i < n; i++){
            r = (p+q);
            p = q;
            q = r;
        }
        
        return p;
    }
}

旋转数组的最小数字

1
2
3
4
5
6
7
8
9
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个升序的数组的一个旋转，输出旋转数组的最小元素。
例如数组 {3,4,5,1,2} 为 {1,2,3,4,5} 的一个旋转，该数组的最小值为 1。

数组可能包含重复项。
注意：数组内所含元素非负，若数组大小为 0，请返回 −1。

输入：nums = [2, 2, 2, 0, 1]
输出：0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution{
    public int findMin(int[] nums){
        //corner case
        if(nums == null || nums.length == 0){
            return -1;
        }
        
        int lo = 0, hi = nums.length-1;
        while(hi > 0 && nums[0] == nums[hi]){
            hi--;
        }
        
        if(nums[hi] >= nums[0]){
            return nums[0];
        }
        
        while(lo < hi){
            int mid = ((hi - lo) >> 1) + lo;
            if(nums[mid] < nums[0]){
                hi = mid;
            }else{
                lo = mid+1;
            }
        }
        
        return nums[hi];
    }
}

矩阵中的路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。
如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。

输入的路径不为空；
所有出现的字符均为大写英文字母；

matrix=
[
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
]
str="BCCE" , return "true" 
str="ASAE" , return "false"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution{
    public boolean hasPath(char[][] matrix, String str){
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[0].length; j++){
                if(dfs(matrix, str, i, j, 0)){
                    return true;
                }
            }
        }
    }
    
    private boolean dfs(char[][] matrix, String str, int i, int j, int k){
        //corner case
        if(i < 0 || j < 0 || i >= matrix.length || j >= matrix[0].length || matrix[i][j] != str.charAt(k)){
            return false;
        }
        
        if(k == str.length() - 1){
            return true;
        }
        
        char[] ch = matrix[i][j];
        matrix[i][j] = '.';
        
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};
        
        for(int q = 0; q < 4; q++){
            int nx = i+dx[q];
            int ny = j+dy[q];
            if(dfs(matrix, str, nx, ny, k+1)){
                return true;
            }
        }
        
        matrix[i][j] = ch;
        return false;
    }
}

机器人的运动范围

1
2
3
4
5
6
7
8
9
10
11
12
地上有一个 m 行和 n 列的方格，横纵坐标范围分别是 0∼m−1 和 0∼n−1。
一个机器人从坐标 (0,0) 的格子开始移动，每一次只能向左，右，上，下四个方向移动一格。
但是不能进入行坐标和列坐标的数位之和大于 k 的格子。
请问该机器人能够达到多少个格子？

输入：k=7, m=4, n=5
输出：20

输入：k=18, m=40, n=40
输出：1484
解释：当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。
但是，它不能进入方格（35,38），因为3+5+3+8 = 19。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution{
    public int movingCount(int threshold, int rows, int cols){
        boolean[][] used = new boolean[rows][cols];
        
        return dfs(threshold, rows, cols, 0, 0, used);
    }
    
    private int dfs(int threshold, int rows, int cols, int i, int j, boolean[][] used){
        //corner case
        if(i < 0 || j < 0 || i >= rows || j >= cols || used[i][j] || (i%10+i/10+j%10+j/10) > threshold){
            return 0;
        }
        
        used[i][j] = true;
        
        return dfs(threshold, rows, cols, i+1, j, used) + dfs(threshold, rows, cols, i, j+1, used) + 1;
    }
}

剪绳子

1
2
3
4
5
6
7
给你一根长度为 n 绳子，请把绳子剪成 m 段（m、n 都是整数，2≤n≤58 并且 m≥2）。
每段的绳子的长度记为 k[1]、k[2]、……、k[m]。
k[1]k[2]…k[m] 可能的最大乘积是多少？
例如当绳子的长度是 8 时，我们把它剪成长度分别为 2、3、3 的三段，此时得到最大的乘积 18。

输入：8
输出：18
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution{
    public int maxProductAfterCutting(int length){
        //若绳子长度小于等于3，则需要分两段
        if(length <= 3){
            return 1*(length-1);
        }
        
        //绳子长度mod3==1，则拆出两个2，相当于拆出4
        //绳子长度mod3==2，则拆出一个2
        int res = 1;
        if(length % 3 == 1){
            res *= 4;
            length -= 4;
        }else if(length % 3 == 2){
            res *= 2;
            length -= 2;
        }
        
        while(length > 3){
            res *= 3;
            length -= 3;
        }
        
        return res;
    }
}

二进制中1的个数

1
2
3
4
5
6
7
8
9
10
11
输入一个 32 位整数，输出该数二进制表示中 1 的个数。
负数在计算机中用其绝对值的补码来表示。

输入：9
输出：2
解释：9的二进制表示是1001，一共有2个1。

输入：-2
输出：31
解释：-2在计算机里会被表示成11111111111111111111111111111110，
 一共有31个1。
1
2
3
4
5
6
7
8
9
public int NumberOf1(int n){
    int res = 0;
    while(n != 0){
        // n & (n-1) 结果为将a的二进制表示的最后一个1变为0
        // n & (-n) 结果为保留a的二进制的最后一个1，其余的1都变成0
        n -= (n & (-n));
        res++;
    }
}

数值的整数次方

1
2
3
4
5
6
7
8
9
10
11
12
实现函数double Power(double base, int exponent)，求base的 exponent次方。
不得使用库函数，同时不需要考虑大数问题。
只要输出结果与答案的绝对误差不超过 10−2 即视为正确。

不会出现底数和指数同为0的情况
当底数为0时，指数一定为正

输入：10 ，2
输出：100

输入：10 ，-2  
输出：0.01
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution{
    public double Power(double base, int exponent){
        //corner case
        if(exponent == 0){
            return 1.0;
        }
        
        long N = exponent;
        
        return N > 0 ? pow(base, N) : 1/pow(base, -N);
    }
    
    private double pow(double base, long exponent){
        //corner case
        if(exponent == 0){
            return 1.0;
        }
        
        double y = pow(base, exponent >> 1);
        
        return exponent >> 1 == 0 ? y*y : y*y*base;
    }
}

在O(1)时间删除链表结点

1
2
3
4
5
6
给定单向链表的一个节点指针，定义一个函数在O(1)时间删除该结点。
假设链表一定存在，并且该节点一定不是尾节点。

输入：链表 1->4->6->8
删掉节点：第2个节点即6（头节点为第0个节点）
输出：新链表 1->4->8
1
2
3
4
5
6
class Solution{
    public void deleteNode(ListNode node){
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

删除链表中的重复节点

1
2
3
4
5
6
7
在一个排序的链表中，存在重复的节点，请删除该链表中重复的节点，重复的节点不保留。

输入：1->2->3->3->4->4->5
输出：1->2->5

输入：1->1->1->2->3
输出：2->3    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution{
    public ListNode deleteDuplication(ListNode head){
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode temp = dummy, cur = head;
        
        while(cur != null && cur.next != null){
            while(cur.next != null && cur.val == cur.next.val){
                cur = cur.next;
            }
            if(temp.next != cur){
                temp.next = cur.next;
            }else{
                temp = cur;
            }
            
            cur = cur.next;
        }
        
        return dummy.next;
    }
}

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

1
2
3
4
5
输入一个整数数组，实现一个函数来调整该数组中数字的顺序。
使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分。

输入：[1,2,3,4,5]
输出: [1,3,5,2,4]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution{
    public void reOrderArray(int[] array){
        //快排交换思想
        int lo = 0, hi = array.length-1;
        while(lo < hi){
            while(lo < hi && (array[lo] & 1) != 0){
                lo++;
            }
            while(lo < hi && (array[hi] & 1) != 1){
                hi--;
            }
            int temp = array[lo];
            array[lo] = array[hi];
            array[hi] = temp;
            
            lo++;
            hi--;
        }
    }
}

链表中倒数第K个节点

1
2
3
4
5
6
7
8
输入一个链表，输出该链表中倒数第 k 个结点。

注意：
k >= 1;
如果 k 大于链表长度，则返回 NULL;

输入：链表：1->2->3->4->5 ，k=2
输出：4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution{
    public ListNode findKthToTail(ListNode pListHead, int k){
        int count = 0;
        ListNode temp = pListHead;
        while(temp != null){
            temp = temp.next;
            count++;
        }
        
        if(count < k){
            return null;
        }
        
        for(int i = 0; i < (count - k); i++){
            pListHead = pListHead.next;
        }
        
        return pListHead;
    }
}

链表中环的入口结点

1
2
3
4
5
6
7
给定一个链表，若其中包含环，则输出环的入口节点。
若其中不包含环，则输出null。

[1, 2, 3, 4, 5, 6]
2
注意，这里的2表示编号是2的节点，节点编号从0开始。所以编号是2的节点就是val等于3的节点。
则输出环的入口节点3.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution{
    public ListNode entryNodeOfLoop(ListNode head){
        //corner case
        if(head == null || head.next == null){
            return head;
        }
        
        ListNode fast = head, slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                ListNode temp = head;
                while(temp != slow){
                    temp = temp.next;
                    slow = slow.next;
                }
                
                return slow;
            }
        }
        
        return null;
    }
}

反转链表

1
2
3
4
定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。

输入:1->2->3->4->5->NULL
输出:5->4->3->2->1->NULL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution{
    
    //迭代
    public ListNode reverseList(ListNode head){
        //corner case
        if(head == null || head.next == null){
            return head;
        }
        
        ListNode pre = null, cur = head;
        while(cur != null){
            ListNode after = cur.next;
            cur.next = pre;
            pre = cur;
            cur = after;
        }
        
        return pre;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution{
    //递归
    public ListNode reverseList(ListNode head){
        //corner case
        if(head == null || head.next == null){
            return head;
        }
        
        ListNode temp = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        
        return temp;
    }
}

合并两个排序的链表

1
2
3
4
输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。

输入：1->3->5 , 2->4->5
输出：1->2->3->4->5->5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution{
    public ListNode merge(ListNode l1, ListNode l2){
        //corner case
        if(l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }
        
        if(l1.val < l2.val){
            l1.next = merge(l1.next, l2);
            return l1;
        }else{
            l2.next = merge(l1, l2.next);
            return l2;
        }
    }
}

树的子结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
输入两棵二叉树 A，B，判断 B 是不是 A 的子结构。
我们规定空树不是任何树的子结构。

树 A：
     8
    / \
   8   7
  / \
 9   2
    / \
   4   7
树 B：
   8
  / \
 9   2
 返回 true，因为 B 是 A 的子结构。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution{
    public boolean hasSubtree(TreeNode pRoot1, TreeNode pRoot2){
        if(pRoot1 == null || pRoot2 == null){
            return false;
        }
        
        return helper(pRoot1, pRoot2) || hasSubtree(pRoot1.left, pRoot2) || hasSubtree(pRoot1.right, pRoot2);
    }
    
    private boolean helper(TreeNode A, TreeNode B){
        if(B == null){
            return true;
        }
        
        if(A == null){
            return false;
        }
        
        return A.val == B.val && helper(A.left, B.left) && helper(A.right, B.right);
    }
}

二叉树的镜像

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
输入一个二叉树，将它变换为它的镜像。
输入树：
      8
     / \
    6  10
   / \ / \
  5  7 9 11

 [8,6,10,5,7,9,11,null,null,null,null,null,null,null,null] 
输出树：
      8
     / \
    10  6
   / \ / \
  11 9 7  5

 [8,10,6,11,9,7,5,null,null,null,null,null,null,null,null]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution{
    public void mirror(TreeNode root){
        //corner case
        if(root == null){
            return;
        }
        
        if(root.left == null && root.right == null){
            return;
        }
        
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        
        mirror(root.left);
        mirror(root.right);
    }
}

对称的二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
请实现一个函数，用来判断一棵二叉树是不是对称的。
如果一棵二叉树和它的镜像一样，那么它是对称的。
如下图所示二叉树[1,2,2,3,4,4,3,null,null,null,null,null,null,null,null]为对称二叉树：
    1
   / \
  2   2
 / \ / \
3  4 4  3

如下图所示二叉树[1,2,2,null,4,4,3,null,null,null,null,null,null]不是对称二叉树：
    1
   / \
  2   2
   \ / \
   4 4  3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution{
    public boolean isSymmetric(TreeNode root){
        //corner case
        if(root == null){
            return true;
        }
        
        return helper(root.left, root.right);
    }
    
    private boolean helper(TreeNode A, TreeNode B){
        //corner case
        if(A == null || B == null){
            return A == null && B == null;
        }
        
        return A.val == B.val && helper(A.left, B.right) && helper(A.right, B.left);
    }
}

顺时针打印矩阵

1
2
3
4
5
6
7
8
9
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
输入：
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]

输出：[1,2,3,4,8,12,11,10,9,5,6,7]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution{
    public int[] printMatrix(int[][] matrix){
        //corner case
        if(matrix == null || matrix.length == 0){
            return new int[0];
        }
        
        int n = matrix.length, m = matrix[0].length;
        
        //定义方向数组
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};
        
        //定义一个二维数组，表示已经访问过的元素
        boolean[][] used = new boolean[n][m];
        
        //res Array
        int[] res = new int[n*m];
        
        //起点
        int x = 0, y = 0, d = 1;
        //遍历
        for(int i = 0; i < n*m; i++){
            //放入res中，并标记该位置为以访问
            res[i] = matrix[x][y];
            used[x][y] = true;
            //下一个位置
            int nx = x+dx[d], ny = y+dy[d];
            //判断下一个位置的合法性，不满足则需要改变方向
            if(nx < 0 || ny < 0 || nx >= n || ny >= m || used[nx][ny]){
                d = (d+1)%4;
                nx = x+dx[d];
                ny = y+dy[d];
            }
            x = nx;
            y = ny;
        }
        
        return res;
    }
}

包含Min函数的栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
设计一个支持push，pop，top等操作并且可以在O(1)时间内检索出最小元素的堆栈。
push(x)–将元素x插入栈中
pop()–移除栈顶元素
top()–得到栈顶元素
getMin()–得到栈中最小元素

MinStack minStack = new MinStack();
minStack.push(-1);
minStack.push(3);
minStack.push(-4);
minStack.getMin();   --> Returns -4.
minStack.pop();
minStack.top();      --> Returns 3.
minStack.getMin();   --> Returns -1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class MinStack{
    private Deque<Integer> stack, minStack;
    
    public MinStack(){
        this.stack = new ArrayDeque<>();
        this.minStack = new ArrayDeque<>();
    }
    
    public void push(int x){
        //stack直接加入，minStack中若为空则加入，否则只有栈顶大于等于x时才加入
        stack.push(x);
        if(minStack.isEmpty() || minStack.peek() >= x){
            minStack.push(x);
        }
    }
    
    public void pop(){
        //若stack栈顶和minStack栈顶相同则都需要弹栈
        if(stack.peek().equals(minStack.peek())){
            minStack.pop();
        }
        stack.pop();
    }
    
    public int top(){
        return stack.peek();
    }
    
    public int getMin(){
        return minStack.peek();
    }
}

栈的压入、弹出序列

1
2
3
4
5
6
7
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。
假设压入栈的所有数字均不相等。
例如序列 1,2,3,4,5 是某栈的压入顺序，序列 4,5,3,2,1 是该压栈序列对应的一个弹出序列，但 4,3,5,1,2 就不可能是该压栈序列的弹出序列。
注意：若两个序列长度不等则视为并不是一个栈的压入、弹出序列。若两个序列都为空，则视为是一个栈的压入、弹出序列。
输入：[1,2,3,4,5]
      [4,5,3,2,1]
输出：true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution{
    public boolean isPopOrder(int[] pushV, int[] popV){
        if(pushV.length != popV.length){
            return false;
        }
        
        Deque<Integer> stack = new ArrayDeque<>();
      	int index = 0;
        //遍历数组
        for(int pushs : pushV){
            //遍历到的数组都先入栈
            stack.push(pushs);
            //若栈中不为空且栈顶元素等于当前popv数组中的值时，则弹出栈，且数值向后移
            while(!stack.isEmpty() && stack.peek() == popV[index]){
                stack.pop();
                index++;
            }
        }
        
        return stack.isEmpty();
    }
}

不分行从上往下打印二叉树

1
2
3
4
5
6
7
8
9
10
11
从上往下打印出二叉树的每个结点，同一层的结点按照从左到右的顺序打印。
输入如下图所示二叉树[8, 12, 2, null, null, 6, null, 4, null, null, null]
    8
   / \
  12  2
     /
    6
   /
  4

输出：[8, 12, 2, 6, 4]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution{
    public List<Integer> printFromTopToBottom(TreeNode root){
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            res.add(node.val);
            if(node.left != null){
                queue.offer(node.left);
            }
            if(node.right != null){
                queue.offer(node.right);
            }
        }
        
        return res;
    }
}

分行从上往下打印二叉树

1
2
3
4
5
6
7
8
9
10
11
从上到下按层打印二叉树，同一层的结点按从左到右的顺序打印，每一层打印到一行。
输入如下图所示二叉树[8, 12, 2, null, null, 6, null, 4, null, null, null]
    8
   / \
  12  2
     /
    6
   /
  4

输出：[[8], [12, 2], [6], [4]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution{
    public List<List<Integer>> printFromTopToBottom(TreeNode root){
        List<List<Integer>> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        
        while(!queue.isEmpty()){
            List<Integer> list = new ArrayList<>();
            for(int i = queue.size(); i > 0; i--){
                TreeNode node = queue.poll();
                list.add(node.val);
                if(node.left != null){
                    queue.offer(node.left);
                }
                if(node.right != null){
                    queue.offer(node.right);
                }
            }
            
            res.add(list);
        }
        
        return res;
    }
}

之字形打印二叉树

1
2
请实现一个函数按照之字形顺序从上向下打印二叉树。
即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
1
2
3
4
5
6
7
输入如下图所示二叉树[8, 12, 2, null, null, 6, 4, null, null, null, null]
    8
   / \
  12  2
     / \
    6   4
输出：[[8], [2, 12], [6, 4]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution{
    public List<List<Integer>> printFromTopToBottom(TreeNode root){
        //res
        List<List<Integer>> res = new ArrayList<>();
        
        //corner case
        if(root == null){
            return res;
        }
        
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        
        while(!queue.isEmpty()){
            List<Integer> list = new LinkedList<>();
            for(int i = queue.size(); i > 0; i--){
                TreeNode node = queue.poll();
                if((res.size() & 1) == 0){
                    list.add(node.val);
                }else{
                    list.add(0, node.val);
                }
                
                if(node.left != null){
                    queue.offer(node.left);
                }
                if(node.right != null){
                    queue.offer(node.right);
                }
            }
            
            res.add(list);
        }
        
        return res;
    }
}

二叉搜索树的后序遍历序列

1
2
3
4
5
6
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
如果是则返回true，否则返回false。
假设输入的数组的任意两个数字都互不相同。

输入：[4, 8, 6, 12, 16, 14, 10]
输出：true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution{
    public boolean verifySequenceOfBST(int[] sequence){
        return dfs();
    }
    
    private boolean dfs(int lo, int hi, int[] sequence){
        //corner case
        if(lo >= hi){
            return true;
        }
        
        int root = sequence[hi];
        int temp = lo;
        while(lo < hi && sequence[temp] < root){
            temp++;
        }
        for(int i = temp; i < hi; i++){
            if(sequence[i] < root){
                return false;
            }
        }
        
        return dfs(lo, temp-1, sequence) && dfs(temp, hi-1, sequence);
    }
}

二叉树中和为某一值的路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入一棵二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。
从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
保证树中结点值均不小于 0。

给出二叉树如下所示，并给出num=22。
      5
     / \
    4   6
   /   / \
  12  13  6
 /  \    / \
9    1  5   1

输出：[[5,4,12,1],[5,6,6,5]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution{
    public List<List<Integer>> findPath(TreeNode root, int sum){
        List<List<Integer>> res = new ArrayList<>();
        //corner case
        if(root == null){
            return res;
        }
        
        helper(res, sum, root, new ArrayList<>());
        
        return res;
    }
    
    private void helper(List<List<Integer>> res, int sum, TreeNode root, List<Integer> list){
        //corner case
        if(root == null){
            return;
        }
        
        list.add(root.val);
        sum -= root.val;
        
        if(sum == 0 && root.left == null && root.right == null){
            res.add(new ArrayList<>(list));
        }
        
        helper(res, sum, root.left, list);
        helper(res, sum, root.right, list);
        list.remove(list.size()-1);
    }
}

复杂链表的复刻

1
2
请实现一个函数可以复制一个复杂链表。
在复杂链表中，每个结点除了有一个指针指向下一个结点外，还有一个额外的指针指向链表中的任意结点或者null。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution{
    public ListNode copyRandomList(ListNode head){
        //corner case
        if(head == null){
            return null;
        }
        
        ListNode temp = head;
        //复制下一个结点
        while(temp != null){
            ListNode newNode = new ListNoe(temp.val);
            newNode.next = temp.next;
            temp.next = newNode;
            temp = newNode.next;
        }
        
        temp = head;
        //复制Random结点
        while(temp != null){
            temp.next.random = temp.random == null ? null : temp.random.next;
        }
        
        ListNode res = head.next, pre = head;
        temp = res;
        //拆开两条链表
        while(temp.next != null){
            pre.next = pre.next.next;
            temp.next = temp.next.next;
            pre = pre.next;
            temp = temp.next;
        }
        pre.next = null;
        
        return res;
    }
}

二叉搜索树与双向链表

1
2
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
要求不能创建任何新的结点，只能调整树中结点指针的指向。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Sulotion{
    public TreeNode convert(TreeNode root){
        //corner case
        if(root == null){
            return root;
        }
        TreeNode head = null, tail = null;
        Deque<TreeNode> stack = new ArrayDeque<>();
        
        //中序遍历
        while(root != null || !stack.isEmpty()){
            //左
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            
            //根
            TreeNode node = stack.pop();
            if(head == null){
                head = node;
                tail = node;
            }else{
                tail.right = node;
                node.left = tail;
                tail = node;
            }
            
            //右
            root = node.right;
        }
        
        return head;
    }
}

序列化二叉树

1
2
3
4
5
6
7
8
9
10
请实现两个函数，分别用来序列化和反序列化二叉树。
您需要确保二叉树可以序列化为字符串，并且可以将此字符串反序列化为原始树结构。

你可以序列化如下的二叉树
    8
   / \
  12  2
     / \
    6   4
为："[8, 12, 2, null, null, 6, 4, null, null, null, null]"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution{
    String serialize(TreeNode root){
        return serialize(root, new StringBuilder()).toString();
    }
    
    private StringBuilder serialize(TreeNode root, StringBuilder sb){
        //corner case
        if(root == null){
            return sb.append("null,");
        }
        
        sb.append(root.val).append(',');
        sb = serialize(root.left, sb);
        sb = serialize(root.right, sb);
        
        return sb;
    }
    
    TreeNode deserialize(String data){
        String[] strArray = data.split(",");
        List<String> list = new ArrayList<>(Arrays.asList(strArray));
        return deserialize(list);
    }
    
    private TreeNode deserialize(List<String> list){
        if(list.get(0).equals("null")){
            list.remove(0);
            return null;
        }
        
        TreeNode root = new TreeNode(Integer.valueOf(list.get(0)));
        list.remove(0);
        root.left = deserialize(list);
        root.right = deserialize(list);
        
        return root;
    }
}

数字排列

1
2
3
4
5
6
7
8
9
10
11
输入一组数字（可能包含重复数字），输出其所有的排列方式。
输入：[1,2,3]
输出：
      [
        [1,2,3],
        [1,3,2],
        [2,1,3],
        [2,3,1],
        [3,1,2],
        [3,2,1]
      ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Slolution{
    public List<List<Integer>> permutation(int[] nums){
        List<List<Integer>> res = new ArrayList<>();
        //corner case
        if(nums == null || nums.length == 0){
            return res;
        }
        
        //sort
        Arrays.sort(nums);
        helper();
        
        return res;
    }
    
    private void helper(int[] nums, boolean[] used, List<Integer> list, List<List<Integer>> res){
        if(list.size() == nums.length){
            res.add(new ArrayList<>(list));
            return;
        }
        
        for(int i = 0; i < nums.length; i++){
            //去重
            if(i > 0 && nums[i-1] == nums[i] && !used[i-1]){
                continue;
            }
            
            if(!used[i]){
                used[i] = true;
                list.add(nums[i]);
                helper(nums, used, list, res);
                list.remove(list.size()-1);
                used[i] = false;
            }
        }
    }
}

数组中出现次数超过一半的数字

1
2
3
4
5
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
假设数组非空，并且一定存在满足条件的数字。

输入：[1,2,1,1,3]
输出：1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution{
    public int moreThanHalfNum_Solution(int[] nums){
        //摩尔投票法
        int count = 0;
        int val = -1;
        for(int num : nums){
            if(count == 0){
                val = num;
                count = 1;
            }else{
                if(num == val){
                    count++;
                }else{
                    count--;
                }
            }
        }
        
        return val;
    }
}

最小的K个数

1
2
3
4
输入 n 个整数，找出其中最小的 k 个数。

输入：[1,2,3,4,5,6,7,8] , k=4
输出：[1,2,3,4]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution{
    public List<Integer> getLeastNumber_Solution(int[] input, int k){
        List<Integer> res = new ArrayList<>(k);
        
        //大根堆
        PriorityQueue<Integer> heap = new PriorityQueue<>((a,b) -> b.compareTo(a));
        
        //遍历数组
        for(int in : input){
            heap.offer(in);
            if(heap.size() > k){
                heap.poll();
            }
        }
        
        while(heap.size() > 0){
            res.add(heap.poll());
        }
        
        Collections.reverse(res);
        
        return res;
    }
}

数据流中的中位数

1
2
3
4
5
6
7
如何得到一个数据流中的中位数？
如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。
如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

输入：1, 2, 3, 4
输出：1,1.5,2,2.5
解释：每当数据流读入一个数据，就进行一次判断并输出当前的中位数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution{
    //维护一个大根堆，一个小根堆
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a,b) -> b.compareTo(a));
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    
    public void insert(Integer num){
        //大根堆中插入数据
        maxHeap.offer(num);
        if(minHeap.size() > 0 && maxHeap.peek() > minHeap.peek()){
            int max = maxHeap.poll(), min = minHeap.poll();
            maxHeap.offer(min);
            minHeap.offer(max);
        }
        if(maxHeap.size() > minHeap.size()+1){
            minHeap.offer(maxHeap.poll());
        }
    }
    
    public Double getMedian(){
        if(((maxHeap.size() + minHeap.size()) & 1) == 1){
            return maxHeap.peek() / 1.0;
        }else{
            return (minHeap.peek() + maxHeap.peek()) / 2.0;
        }
    }
}
Donate comment here