前言

题目难度中规中矩，字符串处理题还是比较烦人的，尽量熟悉字符串的api就好了。动态规划的题目比较简单，大部分同学应该都可以完成。第三题倒是容易想到单调栈，但是实际题意却不是如此，需要慎重考虑。

春招和暑期实习的笔试也陆陆续续开始啦，有参加笔试的同学欢迎投稿哦，投稿一场完整笔试的（题面＋代码），请你喝一周的奶茶的现金奖励哦！（投稿加文末微信，备注投稿）

文末也有我们的活动介绍，有兴趣参加活动也可以添加微信了解滴！

1.求和方式

给定一个正整数 s 和 n 个正整数 , 求有多少种组合的和为 s ?

数值相同的两个数视为不同的两个数。

输入描述

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

第二行 n 个整数。

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

输出描述

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

示例 1

输入

10 5 1 1 1 1 1 1 1 1 1 1

输出

252

说明

C(10, 5) = 252

思路与代码

动态规划。

核心是一个背包问题，每个元素2种选择：选和不选。

状态定义：f[i] [j] 考虑前i个元素，凑出和为j的元素有多少种组合。

状态转移：f[i] [j] = f[i-1] [j] + f[i-1] [j-a[i]]

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

int n, s;
vector<int> A;
map<pair<int, int>, int> memo;

int dfs(int i, int j) {
    // Check if the result is already in the memo
    auto it = memo.find({i, j});
    if (it != memo.end()) {
        return it->second;
    }
    
    if (i >= n || j > s) {
        return (j == s) ? 1 : 0; // Return 1 if j equals to s, otherwise 0
    }
    
    // Recursive calls: exclude the current element or include it
    int result = dfs(i + 1, j) + dfs(i + 1, j + A[i]);
    memo[{i, j}] = result; // Save the result in the memo before returning
    return result;
}

int main() {
    cin >> n >> s;
    A.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> A[i];
    }
    
    cout << dfs(0, 0) << endl;
    return 0;
}

2.Regular Expresssion

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

“.” 匹配任何单个字符

“*” 与模式字符串前一个字符组成一组，匹配零个或多个前面的字符

“?” 与模式字符串前一个字符组成一组，匹配一个或多个前面的字符

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

使用语言提供的正则表达式库将算作无效答案。

输入描述

输入的第一行为需要检测匹配的用例数。

接下来的每一行包括两个字符串，前一个字符串为待匹配的字符串，后一个字符串为模式字符串。

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

输出描述

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

示例 1

输入

3
aa a
aa aa
aaa aa

输出

false
true
false

示例 2

输入

5
a a.
a a.*
ab .*
ab .?
b a?

输出

false
true
true
true
false

思路与代码

这个问题可以通过递归来解决，逐个字符地比较输入字符串和模式字符串，同时处理特殊字符“.”、“*”和“?”。

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

bool matchCore(string& str, int sIndex, string& pattern, int pIndex) {
    if (sIndex == str.size() && pIndex == pattern.size()) return true; // 完全匹配
    if (sIndex != str.size() && pIndex == pattern.size()) return false; // 模式串用完但字符串没有用完，不匹配

    // 检查下一个字符是不是'*'或'?'
    bool nextIsStar = pIndex + 1 < pattern.size() && pattern[pIndex + 1] == '*';
    bool nextIsQuestion = pIndex + 1 < pattern.size() && pattern[pIndex + 1] == '?';

    if (nextIsStar) {
        if ((sIndex != str.size() && (pattern[pIndex] == str[sIndex] || pattern[pIndex] == '.')) ||
            (sIndex == str.size() && pIndex + 2 == pattern.size())) {
            // 移动字符串或模式串，或者两者都移动
            return matchCore(str, sIndex + 1, pattern, pIndex) ||
                   matchCore(str, sIndex, pattern, pIndex + 2) ||
                   matchCore(str, sIndex + 1, pattern, pIndex + 2);
        } else {
            return matchCore(str, sIndex, pattern, pIndex + 2);
        }
    } else if (nextIsQuestion) {
        if (sIndex != str.size() && (pattern[pIndex] == str[sIndex] || pattern[pIndex] == '.')) {
            // 匹配一个字符，然后移动模式串和字符串
            return matchCore(str, sIndex + 1, pattern, pIndex + 2);
        } else {
            return false; // '?''前的字符必须存在且匹配
        }
    } else if (sIndex != str.size() && (pattern[pIndex] == str[sIndex] || pattern[pIndex] == '.')) {
        return matchCore(str, sIndex + 1, pattern, pIndex + 1);
    }

    return false;
}

bool match(string& str, string& pattern) {
    return matchCore(str, 0, pattern, 0);
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        string s, p;
        cin >> s >> p;
        cout << (match(s, p) ? "true" : "false") << endl;
    }
    return 0;
}

3.野猪骑士

野猪骑士最近在一条路上锻炼，整条路可以被分作n块地块，每个地块有自己的高度i。野猪骑士在地块i时，会跳向 下标比i大 且 高度比hi严格大的地块的集合中，高度最小的地块。

野猪骑士希望知道自己在每个地块上的下一跳的目的地的高度，如果下一跳不存在的话，则记为-1。但这对野猪骑士来说太难了，他希望你来帮助他。

更形式化地说，给定一个数列h, 求一个数列d，其中如果

输入描述

第一行包括一个正整数n，第二行包含n个正整数h1,h2,...,hn。

输出描述

一行，包括n个正整数d1,d2,...,dn

补充说明

PS：

- 由于本题输出较多，使用java的同学尽量使用StringBuilder，一次性输出答案，否则容易超时。

- 由于本题输出较多，使用C++的同学尽量使用printf，或者关闭同步流，否则容易超时。

示例 1

输入

4
4 1 2 3

输出

-1 2 3 -1

示例 2

输入

7
11 13 10 5 12 21 3

输出

12 21 12 12 21 -1 -1

思路与代码

主要思路是红黑树 。部分语言没有红黑树的就要自己找一个有序、可删除元素的数据结构进行替代。

从前往后遍历，对于每一个元素，在红黑树上查找大于当前元素的最小值，遍历完这个元素记得删除这个元素。

#include <iostream>
#include<set>
#include<map>
using namespace std;
int n,arr[100010], ans[100010];
int main() {
    int n;
    cin.tie(0);
    cin >> n;
    set<int> s;
    map<int, int> mm;
    for (int i = 0 ; i < n ; i++) {
        cin >> arr[i];
        if (i != 0) mm[arr[i]] += 1;
    }

    auto it = mm.upper_bound(arr[0]);
    if (it != mm.end() ) ans[0] = mm.upper_bound(arr[0])->first;
    else ans[0] = -1;

    for (int i = 1 ; i < n ; i++) {

        auto it = mm.upper_bound(arr[i]);
        if (it != mm.end() ) ans[i] = it->first;
        else ans[i] = -1;

        mm[arr[i]] -=1;
        if (mm[arr[i]] == 0) mm.erase(arr[i]);
    }

    for (int i = 0 ; i < n ; i++) cout << ans[i] << " ";

}
// 64 位输出请用 printf("%lld")

4.Integer Encoding

Protocol Buffer 是 Google 的一种用于网络数据传输的序列化库，其对整数采用变长编码的方法。整数从低位向高位输出，每次输出一个字节，该输出字节中含有源整数的7bit 信息，输出字节的最高位用作标志位，1表示继续，0表示结束。

输入描述

第一行包含一个正整数 n

第二行包含一个正整数x编码后的字符串

输出描述

第一行包含正整数n编码后的结果

第二行包含解析出来的正整数x

补充说明

编码数据为16进制字符串

字母大写 整数n, x都是无符号64bit整数

示例 1

输入

100
0XE70X07

输出

0X64
999

说明

100 = 0x64 = 0b01100100; 低位7bit为0b1100100 = 0x64，高位没有剩余为1的bit，所以输出字节最高位为0，编码结束，结果为0x64

0xe7 = 0b11100111; 取低7bit，x = 0b1100111 0x07 = 0b00000111; 取低7bit放在x的高位，x = 0b00001111100111; 由于0x07最高bit为0，表示这是最后一个字节，所以x = 0b00001111100111 = 999

思路与代码

主要思路是位操作和字节处理。部分语言没有直接支持变长编码的库，就要自己通过位操作，进行编码和解码。

从整数n的编码开始，对于每一个7位的分段，在位操作上进行处理。编码过程如下：

1. 提取最低有效的7位：从整数的最低有效7位开始，每次处理7位。
2. 设置字节标志位：将这7位放入一个字节的低7位中，如果还有更多位待处理，就将这个字节的最高位设置为1，表示后续还有数据；如果没有，设置为0，表示这是最后一个字节。
3. 转换为16进制字符串：将每个处理过的字节转换成16进制字符串，以符合输出格式。
4. 重复直到完成：继续处理剩余的位，直到整数的所有位都被编码。

解码过程也同理：

1. 读取每个编码字节：将编码字符串的每个字节转换回二进制格式。
2. 处理字节标志位：检查每个字节的最高位，如果为1，表示还有后续字节；去除最高位后，将剩下的7位放置到结果整数的适当位置。
3. 完成解码：如果某个字节的最高位为0，表示这是编码的最后一个字节；同样去除最高位后，将剩下的7位添加到结果整数中，结束解码过程。

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <iomanip>

// 将整数编码为Protocol Buffer变长编码的16进制字符串
string encode(unsigned long long n) {
    vector<unsigned char> bytes;
    do {
        unsigned char byte = n % 128 + (n >= 128 ? 128 : 0); // 判断是否需要设置最高位为1
        bytes.push_back(byte);
        n /= 128;
    } while (n > 0);

    stringstream ss;
    for (auto it = bytes.rbegin(); it != bytes.rend(); ++it) {
        ss << "0X" <<    uppercase <<    setfill('0') <<    setw(2) <<    hex << static_cast<int>(*it);
    }
    return ss.str();
}

// 从Protocol Buffer变长编码的16进制字符串解码为原始整数
unsigned long long decode(string& encoded) {
    unsigned long long x = 0;
    int shift = 0;
    for (size_t i = 0; i < encoded.length(); i += 4) { // 每次处理一个编码字节
           string byteStr = encoded.substr(i + 2, 2); // 获取两个字符，表示一个字节
        unsigned char byte =    stoul(byteStr, nullptr, 16);
        x |= static_cast<unsigned long long>(byte & 0x7F) << shift; // 应用低7位
        if ((byte & 0x80) == 0) break; // 如果最高位为0，则终止
        shift += 7;
    }
    return x;
}

int main() {
    unsigned long long n;
       string encodedX;

       cin >> n;
       cin >> encodedX;

    // 输出n的编码结果
       cout << encode(n) <<    endl;
    // 解码并输出x的原始值
       cout << decode(encodedX) <<    endl;

    return 0;
}