本文包含三道 C++ 算法题解析。第一题通过字符串遍历将奇数位变为 1、偶数位变为 0；第二题利用行列前缀和避免重复计算优化二维数组得分问题；第三题使用滑动窗口或前缀和解决区间快乐值最大化及羞耻值最小化问题。
题目给定一个数，需将其修改：若某一位为奇数则变为 1，若为偶数则变为 0，最后输出结果。
本题较为简单，采用模拟过程即可。
直接按字符串处理，遍历判断奇偶性进行操作。无需逐位数值转换。
通过 ASCII 码可知，字符'0'到'9'的奇偶性与数值一致，判断时可直接使用字符本身。
最后使用 stoi 函数去除前导零并输出。
#include <iostream>
#include <string>
using namespace std;
int main() {
string str;
cin >> str;
for (int i = 0; i < str.size(); i++) {
if (str[i] % 2 == 0) str[i] = '0';
else str[i] = '1';
}
cout << stoi(str) << endl;
return 0;
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
输入 n*m 二维数组，求每个位置方格的得分情况。 得分规则：arr[i][j] 位置的得分等于第 i 行和第 j 列所有数的和。
暴力解法会超时。
优化思路：预先计算每行/每列的和。
思路：先求出行列和，(i,j) 位置得分为行和加列和减去 arr[i][j]（因为行列和中该位置被重复计算了一次）。
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int n, m;
long long row[N];
long long col[N];
int main() {
scanf("%lld %lld", &n, &m);
long long arr[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%lld", &arr[i][j]);
row[i] += arr[i][j];
col[j] += arr[i][j];
}
}
// 记录完成以后输出
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
printf("%lld ", row[i] + col[j] - arr[i][j]);
}
printf("\n");
}
return 0;
}
题目描述：小红想要吃桃子，吃完桃子以后每天可以获得 ai 的快乐值，获得 bi 个羞耻值，桃子效果可以持续 k 天。 现在我们要求，小红在哪一天吃桃子可以获得尽可能多的快乐值；（如果快乐值相等，就让羞耻值尽可能小）。
可使用暴力解法，但需优化。
方法一：滑动窗口
相邻区间差值为左出右入元素。 维护区间和 hSum、sSum，以及最大值 hMax、最小值 sMin。 入窗口：让 hSum 加上 right 位置的快乐值，sSum 加上 right 位置的羞耻值。 判断：当区间的长度大于 k 时，进行出窗口操作。 出窗口：让 hSum 减去 left 位置的快乐值，sSum 减去 left 位置的羞耻值；left++ 即可。 更新结果：当区间长度等于 k 时，进行更新结果操作，这里我们更新不止是 hSum > hMax 时进行更新，当 hSum == hMax && sSum < sMin 时，我们也要更新结果。
方法二：前缀和
也可使用前缀和优化。 对于 h 和 s 数组，分别创建对应的 hSum 和 sSum 数组，存放每一个位置之前所有数的和。 hSum[i]：i 位置之前 h 中所有数的和。 sSum[i]：i 位置之前 s 中所有数的和。 遍历 i 位置时，直接拿到从 i 位置开始 k 个数据的和 numh 和 nums。 这样遍历时候，取到 numh 和 nums 然后判断更新结果就好了。 注意边界条件，有效起始位置为 1 到 n-k+1。
滑动窗口：
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
long long n, k;
long long h[N + 1], s[N + 1];
int main() {
// 滑动窗口
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> h[i];
for (int i = 1; i <= n; i++) cin >> s[i];
int left = 1, right = 1;
long long hSum = 0, sSum = 0, hMax = 0, sMin = 0;
int ret = 0;
while (right <= n) {
hSum += h[right];
sSum += s[right];
while (right - left + 1 > k) {
hSum -= h[left];
sSum -= s[left];
left++;
}
if (right - left + 1 == k) {
// 更新结果
if ((hSum > hMax) || (hSum == hMax && sSum < sMin)) {
ret = left;
hMax = hSum;
sMin = sSum;
}
}
right++;
}
cout << ret << endl;
return 0;
}
前缀和：
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
long long n, k;
long long h[N + 1], s[N + 1];
long long hSum[N + 1], sSum[N + 1];
int main() {
// 前缀和
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> h[i];
hSum[i] = hSum[i - 1] + h[i];
}
for (int i = 1; i <= n; i++) {
cin >> s[i];
sSum[i] = sSum[i - 1] + s[i];
}
int ret = 0;
long long hMax = 0, sMin = 0;
for (int i = 1; i <= n - k + 1; i++) {
long long numh = hSum[i + k - 1] - hSum[i - 1];
long long nums = sSum[i + k - 1] - sSum[i - 1];
if ((numh > hMax) || (numh == hMax && nums < sMin)) {
ret = i;
hMax = numh;
sMin = nums;
}
}
cout << ret << endl;
return 0;
}