做网站设计抬头,网站改版不换域名怎么做,网页设计公司员工,wordpress照片展示76. 所有奇数长度子数组的和#xff08;简单#xff09;
题目要求#xff1a;
给定一个正整数数组 arr #xff0c;计算所有奇数长度子数组的和。
子数组定义为原数组中的一个连续子序列。
返回 arr 中 所有奇数长度子数组的和 。
题目分析#xff1a;
先得到所有子…76. 所有奇数长度子数组的和简单
题目要求
给定一个正整数数组 arr 计算所有奇数长度子数组的和。
子数组定义为原数组中的一个连续子序列。
返回 arr 中 所有奇数长度子数组的和 。
题目分析
先得到所有子数组和构成的数组从中取出长度为奇数的子数组的和即可。
题目解答
#include iostream
using namespace std;
#include string
#include vector
#include algorithmclass Solution
{
public:int sumOddLengthSubarrays(vectorint arr){int n arr.size();vectorint 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()
{vectorint 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 algorithmclass Solution
{
public:int specialArray(vectorint nums){sort(nums.begin(), nums.end(), greaterint()); // 将数组降序排序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()
{vectorint 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 algorithmclass Solution
{
public:vectorint decrypt(vectorint code, int k){int n code.size(); // 获取数组尺寸vectorint 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; // 若k0l指向code[1]否则指向code[n k]int r k 0 ? k : n - 1; // 若k0r指向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()
{vectorint 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;vectorint res s.decrypt(code, k);cout 解码后为;for (int num : res){cout num , ;}cout endl;system(pause);return 0;
}
