笔试时间：2024年03月03日 春招

历史笔试传送门：2023秋招笔试合集

第一题

题目：求和方式

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

输入描述

第一行两个整数 n，s，含义如题所述；

第二行 n 个整数。

1<=n<=30, 1<=s<=900, 1<=wi<=s

输出描述

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

样例输入

10 5

1 1 1 1 1 1 1 1 1 1

样例输出

252

说明

C(10, 5) = 252

参考题解

采用动态规划的方式，对于n个整数，每一个可能被选上，也可能不被选上，状态定义：f[i] [j] 考虑前i个元素，凑出和为j的元素有多少种组合。状态转移方程：f[i] [j] = f[i-1] [j] + f[i-1] [j-a[i]]。

Python：[此代码未进行大量数据的测试，仅供参考]

memo = {}

def count_subsets(index, current_sum):
    key = (index, current_sum)
    if key in memo:
        return memo[key]

    if index >= num_elements or current_sum > target_sum:
        return 1 if current_sum == target_sum else 0

    result = count_subsets(index + 1, current_sum) + count_subsets(index + 1, current_sum + elements[index])
    memo[key] = result
    return result

num_elements, target_sum = map(int, input().split())
elements = list(map(int, input().split()))

print(count_subsets(0, 0))

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int num_elements, target_sum;
vector<int> elements;
map<pair<int, int>, int> memo;

int countSubsets(int index, int current_sum) {
    // 检查结果是否已经存在于备忘录中
    map<pair<int, int>, int>::iterator it = memo.find(make_pair(index, current_sum));
    if (it != memo.end()) {
        return it->second;
    }
    
    if (index >= num_elements || current_sum > target_sum) {
        return (current_sum == target_sum) ? 1 : 0; // 如果 current_sum 等于 target_sum，则返回 1，否则返回 0
    }
    
    // 递归调用：排除当前元素或包含它
    int result = countSubsets(index + 1, current_sum) + countSubsets(index + 1, current_sum + elements[index]);
    memo[make_pair(index, current_sum)] = result; // 在返回前将结果保存到备忘录中
    return result;
}

int main() {
    cin >> num_elements >> target_sum;
    elements.resize(num_elements);
    for (int i = 0; i < num_elements; ++i) {
        cin >> elements[i];
    }
    
    cout << countSubsets(0, 0) << endl;
    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    static int numElements, targetSum;
    static int[] elements;
    static Map<String, Integer> memo;

    static int countSubsets(int index, int currentSum) {
        String key = index + "," + currentSum;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        if (index >= numElements || currentSum > targetSum) {
            return (currentSum == targetSum) ? 1 : 0;
        }

        int result = countSubsets(index + 1, currentSum) + countSubsets(index + 1, currentSum + elements[index]);
        memo.put(key, result);
        return result;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        numElements = scanner.nextInt();
        targetSum = scanner.nextInt();
        elements = new int[numElements];
        memo = new HashMap<>();

        for (int i = 0; i < numElements; ++i) {
            elements[i] = scanner.nextInt();
        }

        System.out.println(countSubsets(0, 0));
    }
}

第二题

题目：Regular Expresssion

实现简单的正则表达式匹配，本题中模式字符串所包含的字符的范围为字母、“.”、“*”、“?"、其中：

• “.” 匹配任何单个字符；
• “*” 与模式字符串前一个字符组成一组，匹配零个或多个前面的字符；
• “?” 与模式字符串前一个字符组成一组，匹配一个或多个前面的字符；

匹配应该覆盖到整个输入的字符串（而不是局部的），测试用例中不会出现超出匹配字符范围之外的字符，也不会出现非法的模式字符串。使用语言提供的正则表达式库将算作无效答案。

输入描述

输入的第一行为需要检测匹配的用例数，接下来的每一行包括两个字符串，前一个字符串为待匹配的字符串，后一个字符串为模式字符串，

待匹配字符串的长度不超过10。

输出描述

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

样例输入一

3

aa a

aa aa

aaa aa

样例输出一

false

true

false

样例输入二

5

a a.

a a.*

ab .*

ab .?

b a?

样例输出二

false

true

true

true

false

参考题解

需要注意不同符号的功能，然后逐个比较字符串就行。

Python：[此代码未进行大量数据的测试，仅供参考]

def match_core(text, text_index, pattern, pattern_index):
    if text_index == len(text) and pattern_index == len(pattern):
        return True  # 完全匹配
    if text_index != len(text) and pattern_index == len(pattern):
        return False  # 模式串用完但字符串没有用完，不匹配

    # 检查下一个字符是不是'*'或'?'
    next_is_star = pattern_index + 1 < len(pattern) and pattern[pattern_index + 1] == '*'
    next_is_question = pattern_index + 1 < len(pattern) and pattern[pattern_index + 1] == '?'

    if next_is_star:
        if (text_index != len(text) and (pattern[pattern_index] == text[text_index] or pattern[pattern_index] == '.')) or \
                (text_index == len(text) and pattern_index + 2 == len(pattern)):
            # 移动字符串或模式串，或者两者都移动
            return match_core(text, text_index + 1, pattern, pattern_index) or \
                   match_core(text, text_index, pattern, pattern_index + 2) or \
                   match_core(text, text_index + 1, pattern, pattern_index + 2)
        else:
            return match_core(text, text_index, pattern, pattern_index + 2)
    elif next_is_question:
        if text_index != len(text) and (pattern[pattern_index] == text[text_index] or pattern[pattern_index] == '.'):
            # 匹配一个字符，然后移动模式串和字符串
            return match_core(text, text_index + 1,