76. 所有奇数长度子数组的和（简单）
题目要求：
给定一个正整数数组 arr ，计算所有奇数长度子数组的和。
子数组定义为原数组中的一个连续子序列。
返回 arr 中 所有奇数长度子数组的和 。
题目分析：
先得到所有子数组和构成的数组，从中取出长度为奇数的子数组的和即可。
题目解答：
#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <algorithm>
class Solution
{
public:
int sumOddLengthSubarrays(vector<int>& arr)
{
int n = arr.size();
vector<int> prefixSums(n + 1);
for (int i = 0; i < n; i++)
{
prefixSums[i + 1] = prefixSums[i] + arr[i]; // prefixSums[i] 表示数组 arr 从下标 0 到下标 i−1 的元素和。
}
int sum = 0;
for (int start = 0; start < n; start++) // 设置子数组的起点位置
{
for (int length = 1; start + length <= n; length += 2) // 设置子数组的长度，保持为奇数
{
int end = start + length - 1; // 在起点和长度已知的情况下计算终点
sum += prefixSums[end + 1] - prefixSums[start]; // 计算起点到终点之间所有长度为奇数的子数组的元素和
}
}
return sum;
}
};
int main()
{
vector<int> arr = { 1,4,2,5,3 };
Solution s;
cout << "原数组为：";
for (int num : arr)
{
cout << num << ", ";
}
cout << endl;
int res = s.sumOddLengthSubarrays(arr);
cout << "所有奇数长度子数组的和为：" << res << endl;
system("pause");
return 0;
}
77. 特殊数组的特征值（简单）
题目要求：
给定一个非负整数数组nums。如果存在一个数x，使得nums 中恰好有 x 个元素大于或者等于 x ，那么就称 nums 是一个 特殊数组 ，而 x 是该数组的特征值。
注意： x 不必 是 nums 的中的元素。
如果数组 nums 是一个 特殊数组 ，请返回它的特征值 x 。否则，返回 -1 。可以证明的是，如果 nums 是特殊数组，那么其特征值 x 是唯一的 。
题目分析：
假设数组长度为n，根据特征值的定义，其值一定在[1, n]之间。将数组降序排列，如果nums[i - 1] >= i且nums[i] < i，那么说明i是特征值。如果i = n，则nums[i]不存在，同样说明i是特征值。
题目解答：
#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <algorithm>
class Solution
{
public:
int specialArray(vector<int>& nums)
{
sort(nums.begin(), nums.end(), greater<int>()); // 将数组降序排序
int n = nums.size(); // 获取数组长度
for (int i = 1; i <= n; i++) // 特征值只会在[1, n]中出现
{
// 由于降序排序，如果数组中在索引i之前的元素都大于等于i，则数组有i个元素大于等于i
if (nums[i - 1] >= i && (i == n || nums[i] < i))
{
return i;
}
}
return -1;
}
};
int main()
{
vector<int> nums = { 3,6,7,7,0 };
Solution s;
cout << "原数组为：";
for (int num : nums)
{
cout << num << ", ";
}
cout << endl;
int res = s.specialArray(nums);
if (res > 0)
{
cout << "数组的特征值为：" << res << endl;
}
else
{
cout << "数组的特征值不存在！" << endl;
}
system("pause");
return 0;
}
78. 拆炸弹（巧妙）
题目要求：
你有一个炸弹需要拆除，时间紧迫！情报员会给你一个长度为n的循环数组code 以及一个密钥 k 。
为了获得正确的密码，你需要替换掉每一个数字。所有数字会同时被替换。
如果 k > 0 ，将第 i 个数字用 接下来 k 个数字之和替换。
如果 k < 0 ，将第 i 个数字用 之前 k 个数字之和替换。
如果 k == 0 ，将第 i 个数字用 0 替换。
由于 code 是循环的， code[n-1] 下一个元素是 code[0] ，且 code[0] 前一个元素是 code[n-1] 。
给你 循环 数组 code 和整数密钥 k ，请你返回解密后的结果来拆除炸弹！
题目分析：
可以将普通数组首尾复制一份作为循环数组，根据k的值设置解码需要的数组区间的左右端点，对于每个解码值，平移该区间即可。
题目解答：
#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <algorithm>
class Solution
{
public:
vector<int> decrypt(vector<int>& code, int k)
{
int n = code.size(); // 获取数组尺寸
vector<int> res(n); // 新建存储结果的数组
if (k == 0)
{
return res;
}
code.resize(n * 2); // 将原数组重构为两倍大小，相当于循环数组
copy(code.begin(), code.begin() + n, code.begin() + n); // 将code.begin()到code.begin()+n之间的元素复制一份放在code.begin()+n后面
// l和k分别代表解密需要的数组区间的起点和终点
int l = k > 0 ? 1 : n + k; // 若k>0，l指向code[1]；否则指向code[n + k]
int r = k > 0 ? k : n - 1; // 若k>0，r指向code[k]；否则指向code[n - 1]
int w = 0; // 初始化解密需要增加的元素和
for (int i = l; i <= r; i++)
{
w += code[i]; // 计算code[0]解密需要的元素和
}
for (int i = 0; i < n; i++) // 遍历整个数组，在code[0]对应的w的基础上得到code[i]对应的w
{
res[i] = w;
w -= code[l];
w += code[r + 1];
l++;
r++;
}
return res;
}
};
int main()
{
vector<int> code = { 5,7,1,4 };
int k;
Solution s;
cout << "原数组为：";
for (int num : code)
{
cout << num << ", ";
}
cout << endl;
cout << "请输入密钥：";
cin >> k;
cout << "=====================" << endl;
cout << "解码中......" << endl;
cout << "=====================" << endl;
vector<int> res = s.decrypt(code, k);
cout << "解码后为：";
for (int num : res)
{
cout << num << ", ";
}
cout << endl;
system("pause");
return 0;
}
