前面14个填空题
T1
已知 子数组 定义为原数组中的一个连续子序列。现给定一个正整数数组 arr，请计算该数组内所有可能的奇数长度子数组的数值之和。
输入描述
输入一个正整数数组arr
输出描述
所有可能的奇数长度子数组的和
示例 1
输入
1,4,2,5,3
输出
58
说明
解释:所有奇数长度子数组和它们的和为:
[1] = 1
[4] = 4
[2] = 2
[5] = 5
[3] = 3
[1,4,2] = 7
[4,2,5] = 11
[2,5,3] = 10
[1,4,2,5,3] = 15
我们将所有值求和得到1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58
C++实现代码
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <sstream>
using namespace std;
int main() {
string input;
vector<int> v;
getline(cin, input);
stringstream ss(input);
string item;
while (getline(ss, item, ',')) {
v.push_back(stoi(item));
}
long long ans = 0;
int n = v.size();
for (int i = 0; i < n; i++) {
long long cur = 0;
int cnt = 0;
for (int j = i; j < n; j++) {
cur += v[j];
cnt += 1;
if (cnt % 2) {
ans += cur;
}
}
}
cout << ans << endl;
return 0;
}
T2
平台运行过程中出现异常时一般会将信息记录在后台日志文件中，定位问题时通常使用关键字进行过滤。正则表达式具备很强大的文本匹配功能，能够快速高效地处理文本。常见元字符为:
^：匹配字符串开头。
$：匹配字符串结尾。
.：匹配任意字符。
*：匹配前面的字符零次或多次。
+：匹配前面的字符一次或多次。
?：匹配前面的字符零次或一次。
给定一个输入字符串s和一个字符模式p，s和p的长度均在100以内，要求实现一个支持’.‘和’*'的正则表达式匹配。字符模式必须能够完全匹配输入字符串。
如果匹配成功返回1，匹配失败返回0
请设计一个时间复杂度为 O(mn)或更优的算法来解决这个问题。如果使用内置正则库得0分。
输入描述
第一行输入为字符串s
第二行输入为字符模式p
输出描述
如果匹配成功返回1，匹配失败返回0
示例 1
输入
aaa
a*
输出
1
说明
通配符*可以匹配aa
示例 2
输入
abaa
ab*a
输出
0
说明
通配符*匹配前面的字符零次或多次,由于前面的字符是b,无法匹配a
示例 3
输入
abaa
ab.a
输出
1
说明
通配符.可以匹配任意字符,因此能够匹配a
C++实现代码
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
bool isMatch(string s, string p) {
int m = s.size(), n = p.size();
vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
dp[0][0] = true;
for (int j = 1; j <= n; j++) {
if (p[j - 1] == '*') {
// s为空字符串的时候, *匹配0个元素, 例如"a*" = ""
dp[0][j] = dp[0][j - 2];
}
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s[i - 1] == p[j - 1] || p[j - 1] == '.') {
dp[i][j] = dp[i - 1][j - 1];
}
else if (p[j - 1] == '*') {
// *匹配0次
if (s[i - 1] != p[j - 2] && p[j - 2] != '.') {
dp[i][j] = dp[i][j - 2];
// *匹配多次
}
else {
dp[i][j] = dp[i][j - 2] || dp[i - 1][j];
}
}
}
}
return dp[m][n];
}
int main() {
string s, p;
cin >> s >> p;
if (isMatch(s, p)) {
cout << 1 << endl;
}
else {
cout << 0 << endl;
}
return 0;
}
T3
给定存在 N个元组的集合，每个元组里面的值为(等级，价格)，等级和价格都是非负整数。在集合中选取数量大于0小于等于N的元组，要求这些元组的等级差不能超过x，并且它们的价格之和最大。最后输出最大的价格
输入描述
第一行包含两个整数 N 和 x (1 ≤ n ≤ 105,1 ≤ x ≤ 1010) —— 分别是给定的元组集合的数量和等级差。
接下来的 N 行是元组的具体数值，每一行为一个元组的两个值，等级和价格，数字之间用空格隔开
输出描述
输出选取的元组最大的价格之和
示例 1
输入
4 2
0 14
3 16
8 9
10 18
输出
27
说明
总共有4个元组，限制选取的元组等级差为2，那么只能选第三和第四个，或者只选一个。对比这几种选组，价格之和最高的是选第三和第四个元组，结果为27。
C++实现代码
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int main() {
int N;
long long x;
cin >> N >> x;
vector<vector<long long>> v(N, vector<long long>(2));
for (int i = 0; i < N; i++) {
cin >> v[i][0] >> v[i][1];
}
sort(v.begin(), v.end());
long long ans = 0;
int i = 0, j = 0;
long long cur = v[0][1];
while (j < N) {
if (v[j][0] - v[i][0] <= x) {
ans = max(ans, cur);
j++;
if (j < N) {
cur += v[j][1];
}
}
else {
cur -= v[i][1];
i++;
}
}
cout << ans << endl;
return 0;
}
T4
小明正在一个由m x n的单元格组成的游戏地图上寻找金币，地图由一个二维整数数组 grid 表示。每个 grid[i][j] 都表示地图上单元格 (i, j) 的金币数量。如果 grid[i][j]是 0，表示这个单元格没有金币。如果 grid[i][j]是正数，表示这个单元格有grid[i][j] 个金币。如果 grid[i][j]是-1，表示这个单元格是不可到达的区域。小明的起始位置是左上角，也就是点(0,0)，并且每次可以向上、下、左、右四个方向移动，但不能移出游戏地图。小明有一个特殊的技能: 他可以使用这个技能将一个不可到达的区域(-1的单元格)变为可达区域，但是他只能使用一次这个技能。使用技能后，不可到达的区域会变成0，也就是没有金币但是可以通过。
你的任务是帮助小明计算，他最多可以收集多少个金币。
输入描述
m,n范围为[0,100]
grid[i][j]值范围为[-1,5]，其中0≤i≤m，0≤j≤n
输出描述
输出收集金币数
示例 1
输入
[1,-1]
[1,1]
输出
2
说明
输入一个2*2的二维数组，小明将grid [0][1](或grid[1][0])的-1变成0则可收集到价值2金币，故输出2
示例2
输入
[-1]
输出
0
说明
输入一个1*1的二维数组,小明无论是否使用技能都无法获得金币，故输出0
C++实现代码
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <sstream>
#include <deque>
using namespace std;
int main() {
vector<vector<int>> v;
string line;
while (getline(cin, line) && !line.empty()) {
istringstream iss(line.substr(1, line.size() - 2));
string token;
vector<int> row;
while (getline(iss, token, ',')) {
if (!token.empty()) {
row.push_back(stoi(token));
}
}
v.push_back(row);
}
deque<pair<int, int>> dq;
vector<vector<int>> vis;
int m, n;
m = v.size();
n = v[0].size();
vis.assign(m, vector<int>(n, 0));
function<int(void)> func = [&](void){
if (v[0][0] == -1) {
return 0;
}
dq.clear();
vis.assign(m, vector<int>(n, 0));
dq.push_back({ 0, 0 });
vis[0][0] = 1;
// 下上右左
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
int ans = 0;
while (!dq.empty()) {
auto [x, y] = dq.front();
dq.pop_front();
ans += v[x][y];
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && v[nx][ny] >= 0 && !vis[nx][ny]) {
vis[nx][ny] = 1;
dq.push_back({ nx, ny });
}
}
}
return ans;
};
int ans = func();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (v[i][j] == -1) {
v[i][j] = 0;
ans = max(ans, func());
v[i][j] = -1;
}
}
}
cout << ans << endl;
return 0;
}
之后我会持续更新，如果喜欢我的文章，请记得一键三连哦，点赞关注收藏，你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 ！！！↖(▔▽▔)↗感谢支持！
