力扣刷题总结 -- 数组26

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个元素大于等于iif (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;
}