柠檬微趣笔试 - 0819

服务器开发--随机抽题0819（Java）

求和方式

题面

给定一个正整数 $s$ 和 $n$ 个正整数，求有多少种组合的和为 $s$ ？
数值相同的两个数视为不同的两个数。

输入描述:
第一行两个整数 $n, s$，含义如题所述；
第二行 $n$ 个整数，$1 ≤ n ≤ 30$，$1 ≤ s ≤ 900$，$1 ≤ w ≤ s$。

输出描述:
输出一个整数表示答案。特别地，如果没有合法方案，输出 $0$。

组合数问题，使用动态规划（DP）解决。

我们需要计算从给定的 $n$ 个数中选择若干个数，使它们的和等于 $s$ 的方案数。由于数值相同的两个数被视为不同的数，这实际上是一个带重复元素的组合问题。

1. 创建一个 DP 数组 dp[i][j]，其中 $i$ 表示考虑前 $i$ 个数，$j$ 表示当前和。dp[i][j] 的值表示使用前 $i$ 个数得到和为 $j$ 的方案数。

2. 初始化：dp[0][0] = 1，表示一个数都不选，和为 $0$ 的方案数为 $1$。

3. 对于每个数 nums[i-1]（$i$ 从 $1$ 到 $n$）：

   • 对于每个可能的和 $j$（从 $0$ 到 $s$）：
     • 如果不选择当前数：dp[i][j] = dp[i-1][j]
     • 如果选择当前数（前提是 j >= nums[i-1]）：dp[i][j] += dp[i-1][j - nums[i-1]]

4. 最终结果为 dp[n][s]。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        int n = scanner.nextInt(); // 数字的个数
        int s = scanner.nextInt(); // 目标和
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        
        // 创建DP数组
        long[][] dp = new long[n + 1][s + 1];
        
        // 初始化：不选任何数，和为0的方案数为1
        dp[0][0] = 1;
        
        // 填充DP表
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= s; j++) {
                // 不选当前数
                dp[i][j] = dp[i-1][j];
                
                // 选择当前数（如果可以）
                if (j >= nums[i-1]) {
                    dp[i][j] += dp[i-1][j - nums[i-1]];
                }
            }
        }
        
        // 输出结果
        System.out.println(dp[n][s]);
    }
}

实现简单的正则表达式匹配

题面

本题中模式字符串包含的字符的范围为字母，".", "*", "?"

"." 匹配任何单个字符
"*" 与括式字符串前一个字符组成一组，匹配零个或多个前面的字符
"?" 与括式字符串前一个字符组成一组，匹配一个或多个前面的字符

匹配应该覆盖到整个输入的字符串（而不是局部的），测试用例中不会出现超出匹配字符范围之外的字符，也不会出现非法的模式字符串。

输入描述：
输入的第一行为需要检测匹配的用例数。
接下来的每一行包括两个字符串，前一个字符串为待匹配的字符串，后一个字符串为模式字符串。待匹配字符串的长度不超过 $10$。

输出描述：
对于每一个测试用例，如果匹配则输出一行 true，如果不匹配则输出一行 false。

创建一个二维布尔数组 dp，其中 dp[i][j] 表示字符串 $s$ 的前 $i$ 个字符是否能匹配模式串 $p$ 的前 $j$ 个字符。通过填充这个数组，我们可以得到最终的匹配结果。

1. 创建一个二维布尔数组 dp[m+1][n+1]，其中 $m$ 和 $n$ 分别是字符串 $s$ 和模式串 $p$ 的长度。

2. 初始化 dp[0][0] = true，表示空字符串匹配空模式。

3. 处理模式串 $p$ 以 '*' 或 '?' 开头的特殊情况。

4. 遍历填充 dp 数组：

   • 如果 p[j-1] 是普通字符，则 dp[i][j] = dp[i-1][j-1] && (s[i-1] == p[j-1])
   • 如果 p[j-1] 是 '.'，则 dp[i][j] = dp[i-1][j-1]
   • 如果 p[j-1] 是 '*'，则 dp[i][j] = dp[i][j-2] || (dp[i-1][j] && (s[i-1] == p[j-2] || p[j-2] == '.'))
   • 如果 p[j-1] 是 '?'，则 dp[i][j] = dp[i-1][j-1] && (s[i-1] == p[j-2] || p[j-2] == '.')

5. 返回 dp[m][n] 作为最终结果。

import java.util.Scanner;

public class RegexMatcher {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = Integer.parseInt(scanner.nextLine());  // 读取测试用例数量

        for (int i = 0; i < n; i++) {
            String line = scanner.nextLine();
            String[] parts = line.split(" ");
            String s = parts[0];  // 待匹配的字符串
            String p = parts[1];  // 模式字符串
            System.out.println(isMatch(s, p));
        }
    }

    public static boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];

        // 初始化
        dp[0][0] = true;  // 空字符串匹配空模式

        // 处理模式 p 以 '*' 或 '?' 开头的特殊情况
        for (int j = 1; j <= n; j++) {
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 2];
            }
        }

        // 填充 dp 数组
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1)) {
                    // 当前字符匹配
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p.charAt(j - 1) == '*') {
                    // '*' 可以匹配零个或多个前面的字符
                    dp[i][j] = dp[i][j - 2];  // 匹配零个
                    if (p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1)) {
                        dp[i][j] |= dp[i - 1][j];  // 匹配一个或多个
                    }
                } else if (p.charAt(j - 1) == '?') {
                    // '?' 必须匹配一个或多个前面的字符
                    if (j > 1 && (p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1))) {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                }
            }
        }

        return dp[m][n];
    }
}

野猪骑士

题面

野猪骑士要在在一条路上狩猎，整条路可以被分作 $n$ 块地块，每个地块有自己的高度 $h_i$，$i \in \{1,2,3,\ldots,n\}$。野猪骑士在地块 $i$ 时，会看见下一块高大且离得远的集合中，高度是小于等于 $h_i$ 的地块，且高度最小的地块。

野猪骑士要想知道自己在每个地块上的下一块的目标的高度。如果下一块不存在的话，则记为 -1。但这次野猪骑士并没有上路，他希望你来帮他狩猎。

更形式化地说，给定一个数列 $a$，求一个数列 $d_i$，其中如果 $\{h_j | j > i \& h_j > h_i\}$ 不为空，则 $d_i := \min\{h_j | j > i \& h_j > h_i\}$，否则 $d_i := -1$ (其中 $:=$ 表示赋值)。

输入描述：
第一行包含一个正整数 $n$，第二行包含 $n$ 个正整数 $h_1,h_2,\ldots,h_n$。

输出描述：
一行，包括 $n$ 个正整数 $d_1,d_2,\ldots,d_n$。

补充说明：
$3 ≤ n ≤ 1e5, 1 < h_i < 1e9$

PS:

• 由于本题输出较多，使用 java 的同学尽量使用 StringBuilder，一次性输出答案，否则容易超时；
• 由于本题输出较多，使用 C++ 的同学尽量使用 printf，或者关闭同步流，否则容易超时；

本质上是求每个元素右侧第一个比它大的元素。

我们可以使用单调栈来解决。从右往左遍历数组，维护一个单调递减的栈，栈中存储元素的下标。对于每个元素，我们弹出栈中所有比它小的元素，然后将当前元素的下标入栈。这样，栈顶元素就是当前元素右侧第一个比它大的元素。

1. 初始化一个结果数组 result，长度为 $n$，所有元素初始化为 $-1$。

2. 创建一个栈 stack，用于存储元素的下标。

3. 从右往左遍历数组（从 $n-1$ 到 $0$）：

   • 当栈不为空且栈顶元素对应的高度小于等于当前元素高度时，弹出栈顶元素。
   • 如果栈不为空，栈顶元素就是右侧第一个比当前元素高的地块，将其高度赋值给 result[i]。
   • 将当前元素的下标入栈。

4. 返回结果数组。

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] heights = new int[n];
        String[] input = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            heights[i] = Integer.parseInt(input[i]);
        }
        
        int[] result = findNextHigherGround(heights);
        
        // 使用 StringBuilder 一次性输出结果
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(result[i]).append(" ");
        }
        System.out.println(sb.toString().trim());
    }
    
    public static int[] findNextHigherGround(int[] heights) {
        int n = heights.length;
        int[] result = new int[n];
        Arrays.fill(result, -1); // 初始化结果数组为-1
        
        Stack<Integer> stack = new Stack<>();
        
        // 从右向左遍历
        for (int i = n - 1; i >= 0; i--) {
            // 弹出栈中所有高度小于等于当前高度的元素
            while (!stack.isEmpty() && heights[stack.peek()] <= heights[i]) {
                stack.pop();
            }
            
            // 如果栈不为空，栈顶元素就是右侧第一个比当前元素高的地块
            if (!stack.isEmpty()) {
                result[i] = heights[stack.peek()];
            }
            
            // 将当前元素入栈
            stack.push(i);
        }
        
        return result;
    }
}

过生日

题面

今天是 Lemon 的生日，生日会上有游戏活动，为此需要一个游戏的排行榜。
Lemon 不想手动修改排行榜，所以想请你实现排行榜主要业务逻辑：包括加人、踢人、更新积分、查询排名
要求如下：

1. 加人、踢人、更新至少 $O(n)$ 的最差时间复杂度
2. 查询排名至少 $O(logn)$ 的最差时间复杂度

其中输入输出部分已经实现，你只需考虑业务逻辑如何实现即可（不允许直接使用 sort, upper_bound, lower_bound）。

特别说明：

• 当玩家存在相分相同时，他们排名也相同，例如分数和排名情况为
  姓名 积分 排名
  Alice 100 1
  Bob 80 2
  Carol 80 2
  Dave 70 4

输入描述：
第 1 行为一个整数 $N$，表示总共有 $N$ 次操作。
第 2 到第 N+1 行，每行代表一次操作，一共有四种操作：

• ADD role score，表示将 role以 score 的积分插入到排行榜中。
• DELETE role，表示将 role 从排行榜中删除。
• UPDATE role delta，表示将 role 的积分更新为 score+delta。
• SEARCH role，查询 role 的排名。

输出描述：
对于每个 search，输出一个正整数表示所查的排名。

这道题要求实现一个游戏排行榜系统，需要支持添加玩家、删除玩家、更新积分和查询排名等操作，且对时间复杂度有严格要求。

考虑到查询排名需要 $O(log n)$ 的复杂度，我们可以使用平衡二叉搜索树来实现。

在 Java 中，我们可以使用 TreeMap 来维护玩家积分，同时使用另一个 TreeMap 来维护积分到玩家的映射，这样可以高效地处理相同积分的情况。

1. 创建两个 TreeMap：

   • scoreMap: 用于存储玩家名称到积分的映射
   • rankMap: 用于存储积分到玩家列表的映射

2. 实现 ADD 操作：

   • 将玩家和积分加入 scoreMap
   • 将玩家加入 rankMap 对应积分的列表中

3. 实现 DELETE 操作：

   • 从 scoreMap 中获取玩家积分并删除玩家
   • 从 rankMap 中对应积分的列表中删除该玩家

4. 实现 UPDATE 操作：

   • 从 scoreMap 中获取玩家原积分
   • 从 rankMap 中对应原积分的列表中删除该玩家
   • 更新 scoreMap 中玩家的积分
   • 将玩家加入 rankMap 中新积分对应的列表

5. 实现 SEARCH 操作：

   • 从 scoreMap 中获取玩家积分
   • 使用 rankMap 的 headMap 方法获取所有大于该积分的玩家数量

6. 计算并返回排名

import java.util.*;

public class LeaderBoard {
    // 存储玩家名称到积分的映射
    private TreeMap<String, Integer> scoreMap;
    // 存储积分到玩家列表的映射
    private TreeMap<Integer, Set<String>> rankMap;

    public LeaderBoard() {
        scoreMap = new TreeMap<>();
        rankMap = new TreeMap<>(Collections.reverseOrder()); // 使用降序排列
    }

    public void add(String role, int score) {
        // 将玩家和积分加入 scoreMap
        scoreMap.put(role, score);
        // 将玩家加入 rankMap 对应积分的列表中
        rankMap.computeIfAbsent(score, k -> new HashSet<>()).add(role);
    }

    public void delete(String role) {
        // 从 scoreMap 中获取玩家积分并删除玩家
        Integer score = scoreMap.remove(role);
        if (score != null) {
            // 从 rankMap 中对应积分的列表中删除该玩家
            Set<String> players = rankMap.get(score);
            players.remove(role);
            if (players.isEmpty()) {
                rankMap.remove(score);
            }
        }
    }

    public void update(String role, int delta) {
        // 从 scoreMap 中获取玩家原积分
        Integer oldScore = scoreMap.get(role);
        if (oldScore != null) {
            // 从 rankMap 中对应原积分的列表中删除该玩家
            Set<String> players = rankMap.get(oldScore);
            players.remove(role);
            if (players.isEmpty()) {
                rankMap.remove(oldScore);
            }
            
            // 更新 scoreMap 中玩家的积分
            int newScore = oldScore + delta;
            scoreMap.put(role, newScore);
            
            // 将玩家加入 rankMap 中新积分对应的列表
            rankMap.computeIfAbsent(newScore, k -> new HashSet<>()).add(role);
        }
    }

    public int search(String role) {
        // 从 scoreMap 中获取玩家积分
        Integer score = scoreMap.get(role);
        if (score == null) {
            return -1; // 玩家不存在
        }
        
        // 使用 rankMap 的 headMap 方法获取所有大于该积分的玩家数量
        int rank = 1;
        for (Map.Entry<Integer, Set<String>> entry : rankMap.headMap(score, false).entrySet()) {
            rank += entry.getValue().size();
        }
        
        return rank;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        scanner.nextLine(); // 消耗换行符

        LeaderBoard leaderBoard = new LeaderBoard();

        for (int i = 0; i < N; i++) {
            String[] operation = scanner.nextLine().split(" ");
            switch (operation[0]) {
                case "ADD":
                    leaderBoard.add(operation[1], Integer.parseInt(operation[2]));
                    break;
                case "DELETE":
                    leaderBoard.delete(operation[1]);
                    break;
                case "UPDATE":
                    leaderBoard.update(operation[1], Integer.parseInt(operation[2]));
                    break;
                case "SEARCH":
                    System.out.println(leaderBoard.search(operation[1]));
                    break;
            }
        }

        scanner.close();
    }
}