飞鱼科技笔试 - 1013

BraumAce2024年10月13日约 2179 字大约 7 分钟

飞鱼科技笔试 - 1013

第一题

题面

给定一个长度为 $n$ 的仅包含正整数的数组，另外有一些操作，每次操作你可以选择数组中的任意一个元素 $a_i$ ，同时数组中所有等于 $a_i - 1$ 和 $a_i + 1$ 的元素会被全部移除，同时你可以得到 $a_i$ 分，直到所有的元素都被选择或者删除。

请你计算最多能得到多少分。

数据范围：数组长度满足 $1 \leq n \leq 10^5$ ，数组中的元素大小都满足 $1 \leq a_i \leq 10^4$

输入描述：
第一行输入一个正整数 $n$ 表示数组的长度；
第二行输入 $n$ 个数字表示数组的各个元素值。

输出描述：
输出所得到的最大分数。

示例：

输入：3
      1 2 3
输出：4

思路与代码：

动态规划。

将问题转化为一个选择问题，即在数组中选择一些元素，使得得分最大化。每次选择一个元素 $a_i$ 时，所有等于 $a_i − 1$ 和 $a_i + 1$ 的元素会被移除，因此可以将问题转化为在一个数组中选择不相邻的元素，使得得分最大化。

步骤：

预处理：统计数组中每个元素出现的频率。由于数组中的元素大小都满足 $1 \leq a_i \leq 10^4$ ，我们可以使用一个大小为 $10^4 + 1$ 的数组 cnt 来存储每个元素的频率。
定义 DP 数组：dp[i] 表示选择元素 $i$ 时的最大得分。
状态转移：对于每个元素 $i$ $i$ ，有两种选择：
- 不选择元素 $i$ ，则 dp[i] = dp[i - 1]
- 选择元素 $i$ ，则 dp[i] = dp[i - 2] + i * cnt[i]
初始化：dp[0] = 0，dp[1] = cnt[1]
最终结果为 dp[10000]，即选择元素 $10000$ 时的最大得分。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        int mx = 10000;
        int[] cnt = new int[mx + 1];
        for (int x : arr) {
            cnt[x]++;
        }
        
        int[] dp = new int[mx + 1];
        dp[1] = cnt[1];
        
        for (int i = 2; i <= mx; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + i * cnt[i]);
        }
        
        System.out.println(dp[mx]);
    }
}

第二题

题面

有一个长度为 $n$ 的数组，请你找到出现次数大于等于数组长度一半的数。

输入描述:
第一行一个正整数 $n$ ，表示数组的长度，长度不超过 $100$ 。
第二行 $n$ 个正整数，表示数组的元素。保证仅有一个数满足要求。

输出描述:
输出出现次数大于等于数组长度一半的数。

示例：

输入：12
      3 9 3 2 5 6 7 3 2 3 3 3
输出：3

思路与代码：

遍历数组，使用一个 HashMap 统计每个元素出现的次数。

再次遍历哈希表，找到出现次数大于等于 $\frac{n + 1}{2}$ 的元素。因为题目保证有解。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        Map<Integer, Integer> map = new HashMap<>();
        for (int x : arr) {
            map.put(x, map.getOrDefault(x, 0) + 1);
        }
        
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() >= (n + 1) / 2) {
                System.out.println(entry.getKey());
                return;
            }
        }
    }
}

第三题

题面

小红正在玩一个游戏。游戏的地图是一个 n × m 的迷宫，迷宫有墙和道路，道路上可能会有一些怪物。
小红初始的血量是 $h$ ，每当小红经过一个有怪物的道路时，小红就会和怪物战斗，击杀怪物并且消耗自己的血量。小红消耗的血量等同于该怪物的战斗力。
请注意，如果小红血量为 $0$ 则死亡。因此只有当小红当前血量大于怪物的战斗力时才可经过该点。

地图其有以下几种标识:
'.' 代表道路，小红可以经过。
'#' 代表墙体，小红不能经过。
'1'-'9' 数字，代表该位置是个道路，且上面有一个战斗力为该数字的怪物。
小红只可以上下左右四个方向移动。

小红想知道，自己从左上角到右下角的最短行走路径的距离是多少？

输入描述：
第一行三个正整数 $n$ ， $m$ 和 $h$ ，用空格隔开。
接下来的 $n$ 行，每行一个长度为 $m$ 的字符串，用来表示地图，保证输入是合法的。
数据范围：
$2≤n,m,h≤50$ ，且怪物的数量不超过 $10$ 个。保证左上角和右下角都是道路且没有怪物。

输出描述：
如果小红无法到达右下角，则输出 $-1$ ，否则输出一个正整数，代表小红走的路径长度最小值。

示例：

输入：3 3 3
      . 1 1
      . * .
      2 2 .
输出：4
解释：先向右走两步，再向下走两步，到达右下角时血量为1；
      如果先向下走两步，小红不可能击杀掉所有怪物。

思路与代码：

BFS。

我们需要找到从左上角到右下角的最短路径，同时要考虑路径上的怪物对小红血量的影响。由于地图规模较小，可以使用 BFS 来解决这个问题。BFS 能够保证在找到路径时是最短的，同时我们需要在 BFS 的过程中维护小红的血量状态。

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 h = sc.nextInt();
        sc.nextLine();
        char[][] g = new char[n][m];
        for (int i = 0; i < n; i++) {
            g[i] = sc.nextLine().toCharArray();
        }

        System.out.println(bfs(g, n, m, h));
    }

    private static int bfs(char[][] g, int n, int m, int h) {
        Queue<int[]> q = new LinkedList<>();
        boolean[][][] vis = new boolean[n][m][h + 1];
        int[][] dir = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
        
        q.offer(new int[]{0, 0, 0, h});
        vis[0][0][h] = true;
        
        while (!q.isEmpty()) {
            int[] cur = queue.poll();
            int x = cur[0], y = cur[1], dist = cur[2], health = cur[3];
            
            if (x == n - 1 && y == m - 1) return dist;
            
            for (int[] d : dir) {
                int xx = x + d[0], yy = y + d[1];
                if (xx >= 0 && xx < n && yy >= 0 && yy < m && g[xx][yy] != '#') {
                    int newHealth = health;
                    if (g[xx][yy] >= '1' && g[xx][yy] <= '9') {
                        int num = grid[xx][yy] - '0';
                        if (health <= num) continue;
                        newHealth -= num;
                    }

                    if (!vis[xx][yy][newHealth]) {
                        vis[xx][yy][newHealth] = true;
                        q.offer(new int[]{xx, yy, dist + 1, newHealth});
                    }
                }
            }
        }

        return -1;
    }
}

第四题

题面

编写 SQL 语句，组合 Products 表中的产品名称（prod_name）和 Customers 表中的顾客名称（cust_name）并返回，然后按产品名称对结果进行升序排序。

【示例】
Products 表含有字段 prod_name 代表产品名称

prod_name
flower
rice
ring
umbrella

Customers 表代表顾客信息，cust_name 代表顾客名称

cust_name
andy
ben
tony
tom
an
lee
hex

【示例结果】

prod_name
an
andy
ben
flower
hex
lee
rice
ring
tom
tony
umbrella

【示例解析】
拼接 cust_name 和 prod_name 并根据结果升序排序

思路与代码：

从 Products 表中选择 prod_name，从 Customers 表中选择 cust_name，将 prod_name 和 cust_name 合并到一个结果集中。

最后按 prod_name 对合并后的结果进行升序排序。

SELECT prod_name FROM Products
UNION
SELECT cust_name FROM Customers
ORDER BY prod_name ASC;

第五题

题面

假设农场中成熟的母牛每年只会生 $1$ 头小母牛，并且永远不会死。第一年农场中有一只成熟的母牛，从第二年开始，母牛开始生小母牛。每只小母牛 $3$ 年之后成熟，可以生小母牛。

给定整数 $n$ ，求出 $n$ 年后牛的数量。

输入描述：
输入一个整数 $n(1≤n≤10^{18})$

输出描述：
输出 $n$ 年后牛的数量对 $10^9 +7$ 取模的值。

示例：

输入：6
输出：9

思路与代码：

动态规划。

定义 DP 数组：设 dp[i] 表示第 $i$ 年牛的数量。
初始状态：dp[1] = 1，因为第一年只有一头成熟的母牛。
状态转移：
- 第 $i$ 年的牛的数量由以下几部分组成：
- 第 $i-1$ 年的所有牛（因为牛不会死）。
- 第 $i-3$ 年的所有牛（因为这些牛在第 $i$ 年已经成熟并且可以生小母牛）。
- 因此，状态转移方程为：dp[i] = dp[i - 1] + dp[i - 3]。
边界条件：由于 dp[i - 3] 在 $i < 4$ $i < 4$ 时会越界，所以我们需要特别处理 $i < 4$ $i < 4$ 的情况：
- dp[2] = 2
- dp[3] = 3
取模操作：由于结果可能非常大，我们需要对结果取模 $10^9 + 7$ 。

public class Main {
    public static void main(String[] args) {
        long n = Long.parseLong(System.console().readLine());
        if (n == 1) {
            System.out.println(1);
            return;
        }

        long mod = 1_000_000_007;
        long[] dp = new long[(int) (n + 1)];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        for (int i = 4; i <= n; i++) {
            dp[i] = (dp[i - 1] + dp[i - 3]) % mod;
        }

        System.out.println(dp[(int) n]);
    }
}

上述写法会报栈溢出错误，只能过 10%
写不出来了，待更新...

解析：矩阵快速幂技巧练习——母牛问题