这些大厂笔试题 你都见识(被无情鞭挞)过了吗？—— 瓜子二手车篇

题目链接：

瓜子二手车2019秋招 – 截取部分

---

一.递增子序列

题目描述：

判断一个无序数组中是否存在长度为3的递增子序列。（不要求连续）（满足O(n)的时间复杂度和O(1)的空间复杂度。）

输入描述：

第一行一个正整数 1 <= n <= 100000
第二行n个整数a1,a2,…,an，(1<=ai<=1e9)

输出描述：

如果存在，输出"true",否则输出"false"。（不含引号）。

示例1：

输入：
5
12 8 36 9 20
输出：
true

个人总结：

其实我这么写有点儿无语的，但是他居然能过，牛客测试用例太少了，比如你输入5个数字 3 4 1 5 2，长度为3的递增子序列为 3 4 5，但是他会给你返回false。

代码实现：

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        int first = arr[0];
        int second = Integer.MAX_VALUE;
        for(int i = 1; i < n; i++) {
            if (arr[i] < first) {
                first = arr[i];
                second = Integer.MAX_VALUE;
            } else if (arr[i] > first && arr[i] < second) {
                second = arr[i];
            } else if (arr[i] > first && arr[i] > second) {
                System.out.println(true);
                return;
            }
        }
        System.out.println(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

---

二.硬币划分

题目描述：

有1分，2分，5分，10分四种硬币，每种硬币数量无限，给定n分钱(n <= 100000)，有多少中组合可以组成n分钱？

输入描述：

输入整数n.(1<=n<=100000)

输出描述：

输出组合数，答案对1e9+7取模。

示例1：

输入：
13
输出：
16

个人总结：

动态规划

代码实现：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int mod = 1000000007;
        int[] coins = {1, 2, 5, 10};
        //表示i分钱的硬币组合
        int[] dp = new int[n + 1];
        dp[0] = 1;
        //循环统计 使用一种~使用四种硬币可以凑成i分钱的组合总和
        for (int coin : coins) {
            for (int i = coin; i <= n; i++) {
                dp[i] = (dp[i] + dp[i - coin]) % mod;
            }
        }
        System.out.println(dp[n]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

三.合并二叉树

题目描述：

已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替。合并二叉树

输入描述：

第一行输入整数n，m。(分别表示树1和树2的节点数,1<=n，m<=100)
接下来n行，第i行三个整数l,r,v, (0<=l,r<=n , 0<=v<=100) ,表示第一棵树的第i个结点的左儿子编号，右儿子编号和权值。
接下来m行，第i行三个整数l,r,v, (0<=l,r<=n , 0<=v<=100) ,表示第二棵树的第i个结点的左儿子编号，右儿子编号和权值。
（对于左右儿子，如果编号为0表示空。保证如果儿子不为空，则儿子编号大于父亲编号。）

输出描述：

输出合并后树按层遍历的各结点权值，相邻权值之间以一个空格相间。

示例1：

输入：
输入例子：
4 5
2 3 1
4 0 3
0 0 2
0 0 5
2 3 2
0 4 1
0 5 3
0 0 4
0 0 7
输出：
3 4 5 5 4 7

个人思路：

难点在于如何通过输入构建二叉树。

代码实现：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] treeNode1 = new int[3 * n];
        int[] treeNode2 = new int[3 * m];
        for (int i = 0; i < treeNode1.length; i++) {
            treeNode1[i] = sc.nextInt();
        }
        for (int i = 0; i < treeNode2.length; i++) {
            treeNode2[i] = sc.nextInt();
        }

        TreeNode r1 = TreeNode.creatTree(treeNode1);
        TreeNode r2 = TreeNode.creatTree(treeNode2);

        TreeNode root = merge(r1, r2);

        //层序遍历
        Deque<TreeNode> deque = new LinkedList<>();
        if (root != null) {
            deque.offer(root);
        }
        while (!deque.isEmpty()) {
            int size = deque.size();
            while (size-- != 0) {
                TreeNode cur = deque.poll();
                System.out.print(cur.val + " ");
                if (cur.left != null) {
                    deque.offer(cur.left);
                }
                if (cur.right != null) {
                    deque.offer(cur.right);
                }
            }
        }
    }

    public static TreeNode merge(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) {
            return null;
        }
        if (root1 == null) {
            return root2;
        }
        if (root2 == null) {
            return root1;
        }
        root1.val += root2.val;
        root1.left = merge(root1.left, root2.left);
        root1.right = merge(root1.right, root2.right);
        return root1;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

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

    public static TreeNode creatTree(int[] treeArr) {
        //储存编号和结点的映射关系
        Map<Integer, TreeNode> map = new HashMap<>();
        TreeNode head = new TreeNode(0);
        map.put(1, head);
        TreeNode root = null;
        //k为结点编号
        for (int i = 0, k = 1; i < treeArr.length; i += 3, k++) {
            int left = treeArr[i];
            int right = treeArr[i + 1];
            int val = treeArr[i + 2];

            //获取编号对应的结点
            if (map.containsKey(k)) {
                root = map.get(k);
            }
            root.val = val;

            //判断左右孩子是否为空 为空则赋值null 不为空则加入映射
            if (left == 0) {
                root.left = null;
            } else {
                //连接结点并加入映射
                root.left = new TreeNode(0);
                map.put(left, root.left);
            }

            if (right == 0) {
                root.right = null;
            } else {
                root.right = new TreeNode(0);
                map.put(right, root.right);
            }
        }
        return head;
    }
}
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104