牛客-剑指offer

发表于 更新于 分类于 阅读次数：

二维数组中的查找

https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?tpId=13&tqId=11154&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目描述：

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

方法：

从左下找

https://www.nowcoder.com/questionTerminal/abc3fe2ce8e146608e868a70efebf62e?answerType=1&f=discussion

对于左下角的值 m，m 是该行最小的数，是该列最大的数 每次将 m 和目标值 target 比较：

  1. 当 m < target，由于 m 已经是该行最大的元素，想要更大只有从列考虑，取值右移一位
  2. 当 m > target，由于 m 已经是该列最小的元素，想要更小只有从行考虑，取值上移一位
  3. 当 m = target，找到该值，返回 true

用某行最小或某列最大与 target 比较，每次可剔除一整行或一整列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public boolean Find(int target, int [][] array) {
        int r = array.length;
        int c = array[0].length;
        
        // 左下角
        int cur_r = r - 1;
        int cur_c = 0;
        
        while(cur_r >= 0 && cur_c <= c-1){
            int cur = array[cur_r][cur_c];
            if(target == cur)
                return true;
            else if(target < cur)
                cur_r--;
            else if(target > cur)
                cur_c++;
        }
        return false;
    }
}

复杂度：

时间复杂度：O(行高 + 列宽) 空间复杂度：O(1)

从尾到头打印链表

https://www.nowcoder.com/practice/d0267f7f55b3412ba93bd35cfa8e8035?tpId=13&tqId=11156&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目描述：

输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

法一：将链表翻转，再依次加入ArrayList

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
/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ListNode cur = listNode;
        ListNode prev = null;
        
        while(cur != null){
            ListNode tmp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = tmp;
        }
        
        ArrayList<Integer> arr = new ArrayList<>();
        while(prev != null){
            arr.add(prev.val);
            prev = prev.next;
        }
        return arr;
    }
}

法二：利用ArrayList的方法add(int index, E element),每次将链表中的元素添加至索引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
/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ListNode cur = listNode;
        ArrayList<Integer> arr = new ArrayList<>();
        
        while(cur != null){
            arr.add(0,cur.val);
            cur = cur.next;
        }

        return arr;
    }
}

复杂度：

时间复杂度：O(n) 空间复杂度：O(n)

重建二叉树

https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=13&tqId=11157&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目描述：

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

方法：

递归

根据中序遍历和前序遍历可以确定二叉树，具体过程为：

  1. 根据前序序列第一个结点确定根结点
  2. 根据根结点在中序序列中的位置分割出左右两个子序列
  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
26
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.Arrays;
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre.length==0 || in.length==0)
            return null;
        TreeNode root = new TreeNode(pre[0]);
        for(int i = 0; i < in.length;i++){
            if(in[i]==pre[0]){
                //copyOfRange 函数，左闭右开
                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i));
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(in,i+1,in.length));
                break;
            }
        }
        return root;
    }
}

复杂度：

时间复杂度：O(n) 空间复杂度：O(n)

用两个栈实现队列

https://www.nowcoder.com/practice/54275ddae22f475981afa2244dd448c6?tpId=13&tqId=11158&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目描述：

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {
        stack1.push(node);
    }
    
    public int pop() {
        if(stack2.empty()){ 
        // 注意这里有个stack2要是empty的条件，若stack2不是empty却往里push stack1中的元素，会出错
            while(!stack1.empty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

旋转数组的最小数字

https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba?tpId=13&tqId=11159&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目描述：

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回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
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if(array.length==0)
            return 0;
        int start = 0;
        int end = array.length-1;
        if(array[start]<array[end])
            return array[start];
        while(start < end){
            int mid = (start+end)/2;
            if(mid>1 && array[mid-1]>array[mid])
                return array[mid];
            if(array[mid]>array[0])
                // 往右
                start = mid+1;
            else if(array[mid]<array[0])
                // 往左
                end = mid-1;
            else
                start++;
        }
        return array[start];
    }
}

斐波那契数列

https://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3?tpId=13&tqId=11160&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目描述：

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。

n<=39

方法：

优化动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public int Fibonacci(int n) {
        if(n==0)
            return 0;
        
        int F1 = 0;
        int F2 = 1;
        int i = 2;
        while(i<=n){
            int F3 = F1 + F2;
            F1 = F2;
            F2 = F3;
            i++;
        }
        return F2;
    }
}

复杂度：

时间复杂度：O(n) 空间复杂度：O(1)

跳台阶

https://www.nowcoder.com/practice/8c82a5b80378478f9484d87d1c5f12a4?tpId=13&tqId=11161&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目描述：

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

方法：

优化动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public int JumpFloor(int target) {
        if(target==0)
            return 0;
        int F1 = 1;
        int F2 = 1;
        int F3 = 0;
        for(int i = 2; i <= target; i++){
            F3 = F1 + F2;
            F1 = F2;
            F2 = F3;
        }
        return F2;
    }
}

复杂度：

时间复杂度：O(n) 空间复杂度：O(1)

变态跳台阶

https://www.nowcoder.com/practice/22243d016f6b47f2a6928b4313c85387?tpId=13&tqId=11162&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目描述：

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

方法：

易知 f(n)=f(n-1)+f(n-2)+……f(1) f(n-1)=f(n-2)+……f(1) 两式相减得f(n)=2f(n-1)

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public int JumpFloorII(int target) {
        if(target==0)
            return 0;
        int f1 = 1;
        int f2 = 0;
        for(int i = 2; i <= target; i++){
            f2 = 2*f1;
            f1 = f2;
        }
        return f1;
    }
}

矩形覆盖

https://www.nowcoder.com/practice/72a5a919508a4251859fb2cfb987a0e6?tpId=13&tqId=11163&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目描述:

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

比如n=3时，2*3的矩形块有3种覆盖方法：

1583470479650

方法：迭代

类似斐波那契数列

f(n) = f(n-1) + f(n-2)

20200306-162012 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public int RectCover(int target) {
        if(target==0)
            return 0;
        int f0=1;
        int f1=1;
        int f2=0;
        for(int i = 2; i <= target; i++){
            f2 = f0 + f1;
            f0 = f1;
            f1 = f2;
        }
        return f1;
    }
}

二进制中1的个数

https://www.nowcoder.com/practice/8ee967e43c2c4ec193b040ea7fbb10b8?tpId=13&tqId=11164&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目描述：

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

（注：输入的是二进制表示形式）

方法：

一个二进制数减去1，再和原二进制数做与运算，会把该数最右边的1变为0，那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。

https://www.nowcoder.com/questionTerminal/8ee967e43c2c4ec193b040ea7fbb10b8?answerType=1&f=discussion

举个例子：一个二进制数1100，减去1后，结果为1011。我们发现减1的结果是把最右边的一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。如1100&1011=1000.

1
2
3
4
5
6
7
8
9
10
public class Solution {
    public int NumberOf1(int n) {
        int count = 0;
        while(n!=0){
            n = n & (n-1);
            count++;
        }
        return count;
    }
}

数值的整数次方

https://www.nowcoder.com/practice/1a834e5e3e1a4b7ba251417554e07c00?tpId=13&tqId=11165&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目描述：

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

保证base和exponent不同时为0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public double Power(double base, int exponent) {
        boolean flag = false;
        if(exponent<0){
            flag = true;
            exponent = - exponent;
        }
        
        double ans = 1;
        while(exponent != 0){
            ans *= base;
            exponent--;
            
        }
        return flag? 1/ans : ans;
  }
}

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

题目描述：

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

思路：

https://www.nowcoder.com/questionTerminal/beb5aa231adc45b2a5dcc5b62c93f593?answerType=1&f=discussion

  • i++往前走，碰到偶数停下来，j=i+1
  • 若 a[j]为偶数，j++前进，直到碰到奇数
    • a[j]对应的奇数插到a[i]位置，j经过的j-1个偶数依次后移
  • 如果j==len-1时还没碰到奇数，证明i和j之间都为偶数了，完成整个移动
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
public class Solution {
    public void reOrderArray(int [] array) {
        if(array.length<=1)
            return ;
        int i = 0;
        while(i < array.length){
            // i遇到偶数停下
            if(array[i]%2 == 0){
                int j = i + 1;
                int count = 0;
                // j遇到奇数停下
                while(array[j]%2==0){
                    if(j==array.length-1)
                        return ;
                    j++;
                    count++;
                }

                int temp = array[i];
                array[i] = array[j];
                for(int k=0; k < count; k++){
                    array[j-k] = array[j-k-1];
                }
                array[j-count] = temp;
            }
            i++;
        }
    }
}

链表中第k个结点

https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&tqId=11167&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目描述：

输入一个链表，输出该链表中倒数第k个结点。

方法：快慢指针

快指针先往前走k步，注意判断边界，然后快慢一起走，当快指针为null的时候，慢指针走到了倒数第k个节点

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
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        ListNode slow = head;
        ListNode fast = head;
        for(int i = 0; i < k; i++){
            if(fast==null)
                return null;
            fast = fast.next;
        }
        while(fast!=null){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

反转链表

https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca?tpId=13&tqId=11168&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目描述：

输入一个链表，反转链表后，输出新链表的表头。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head==null)
            return null;
        ListNode cur = head;
        ListNode prev = null;
        while(cur!=null){
            ListNode tmp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = tmp;
        }
        return prev;
    }
}

合并两个排序的链表

https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337?tpId=13&tqId=11169&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目描述：

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

方法：递归

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
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1==null)
            return list2;
        if(list2==null)
            return list1;
        if(list1.val < list2.val){
            list1.next = Merge(list1.next,list2);
            //不要忘记这个return
            return list1;
        }
        else{
            list2.next = Merge(list1, list2.next);
            //不要忘记这个return
            return list2;
        }
    }
}

树的子结构

https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88?tpId=13&tqId=11170&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目描述：

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

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
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root1==null || root2==null)
            return false;
        return judge(root1, root2) || judge(root1.left, root2) ||judge(root2.right, root2);
    }
    
    public boolean judge(TreeNode root1, TreeNode root2){
        if(root2==null)
            return true;
        if(root1==null)
            return false;
        if(root1.val==root2.val)
            return judge(root1.left, root2.left) && judge(root1.right, root2.right);
        return judge(root1.left, root2) || judge(root1.right, root2);
    }
}

注意与子树的区别：

https://www.nowcoder.com/questionTerminal/6e196c44c7004d15b1610b9afca8bd88?answerType=1&f=discussion

二叉树的镜像

https://www.nowcoder.com/practice/564f4c26aa584921bc75623e48ca3011?tpId=13&tqId=11171&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目描述：

操作给定的二叉树，将其变换为源二叉树的镜像。

输入描述:

二叉树的镜像定义：

​ 源二叉树 ​ 8 ​ /
​6 10 ​ /   /
​5 7 9 11 ​ 镜像二叉树 ​ 8 ​ /
​10 6 ​ /   /
​11 9 7 5

思路：

交换左右子树的节点，然后递归调用该方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public void Mirror(TreeNode root) {
        if(root==null)
            return ;
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        Mirror(root.left);
        Mirror(root.right);
    }
}

顺时针打印矩阵

https://www.nowcoder.com/practice/9b4c81a02cd34f76be2659fa0d54342a?tpId=13&tqId=11172&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目描述:

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

思路：

https://www.nowcoder.com/questionTerminal/9b4c81a02cd34f76be2659fa0d54342a?answerType=1&f=discussion

  1. 向右走存入整行的值，当存入后，该行再也不会被遍历，代表上边界的 up 加一，同时判断是否和代表下边界的 down 交错
  2. 向下走存入整列的值，当存入后，该列再也不会被遍历，代表右边界的 right 减一，同时判断是否和代表左边界的 left 交错
  3. 向左走存入整行的值，当存入后，该行再也不会被遍历，代表下边界的 down 减一，同时判断是否和代表上边界的 up 交错
  4. 向上走存入整列的值，当存入后，该列再也不会被遍历，代表左边界的 left 加一，同时判断是否和代表右边界的 right 交错
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
42
43
44
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printMatrix(int [][] matrix) {
        ArrayList<Integer> res = new ArrayList<>();
        if(matrix.length==0 || matrix[0].length==0)
            return res;
        
        int up = 0;
        int right = matrix[0].length - 1;
        int down = matrix.length - 1;
        int left = 0;
        
        while(true){
            for(int i = left; i <= right; i++)
                res.add(matrix[up][i]);
            up++;
            // 判断是否出界
            if(up>down)
                break;
            
            for(int i = up; i <= down; i++)
                res.add(matrix[i][right]);
            right--;
            // 判断是否出界
            if(right<left)
                break;
            
            for(int i = right; i >= left; i--)
                res.add(matrix[down][i]);
            down--;
            // 判断是否出界
            if(down<up)
                break;
            
            for(int i = down; i>=up; i--)
                res.add(matrix[i][left]);
            left++;
            // 判断是否出界
            if(left>right)
                break;
        }
        return res;
    }
}

包含min函数的栈

https://www.nowcoder.com/practice/4c776177d2c04c2494f2555c9fcc1e49?tpId=13&tqId=11173&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目描述：

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O(1)）。

注意：保证测试中不会当栈为空的时候，对栈调用pop()或者min()或者top()方法。

思路：

关键在于若用一个int来保存最小值，被pop出去了后怎么办：

使用两个栈，一个保存所有的元素，另一个用来保存历史最小值。

当pop()时，检查stack与minStack的栈顶元素是否相同，若相同则都pop()，否则只需pop stack.

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
import java.util.Stack;

public class Solution {
    Stack<Integer> stack = new Stack<>();
    Stack<Integer> minStack = new Stack<>();

    public void push(int node) {
        if(stack.empty() || node <= stack.peek())
            minStack.push(node);
        stack.push(node);
    }
    
    public void pop() {
        if(stack.peek()==minStack.peek())
            minStack.pop();
        stack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int min() {
        return minStack.peek();
    }
}

栈的压入、弹出序列

https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&tqId=11174&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目描述：

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

思路：

新建一个栈，将数组A压入栈中，只要栈顶元素等于数组B时，就将其出栈，当循环结束时，判断栈是否为空，若为空则返回true.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.ArrayList;
import java.util.Stack;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        if(pushA.length==0 || popA.length==0 || pushA.length != popA.length)
            return false;
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for(int i = 0; i < pushA.length; i++){
            stack.push(pushA[i]);
            while(!stack.empty() && stack.peek()==popA[j]){
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }
}

从上往下打印二叉树

https://www.nowcoder.com/practice/7fe2212963db4790b57431d9ed259701?tpId=13&tqId=11175&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目描述：

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

思路：

https://www.nowcoder.com/questionTerminal/7fe2212963db4790b57431d9ed259701?answerType=1&f=discussion

每一次打印一个节点的时候，如果该节点有子节点，则把该节点的子节点放到一个队列的尾部。接下来到对队列的头部取出最早进入队列的节点放到ArrayList 中，重复前面的操作，直至队列为空。

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
import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        if(root==null)
            return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            res.add(cur.val);
            if(cur.left!=null)
                queue.offer(cur.left);
            if(cur.right!=null)
                queue.offer(cur.right);
        }    
        return res;
    }
}