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

小咪咪 2023-09-28 23:40 29阅读 0赞

**题目链接：**

> [瓜子二手车2019秋招][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分，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]);
        }
    }

--------------------

### 三.合并二叉树 ###

**题目描述：**

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

**输入描述：**

> **第一行输入整数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;
        }
    }

[2019]: https://www.nowcoder.com/test/18874168/summary
[Link 1]: https://www.nowcoder.com/questionTerminal/d7e10a7a25ed4ba59eadeab7b87914b6