数组(难度：easy)
- 数组(难度：easy)
- 2011. 执行操作后的变量值
- 解法：
- 1929. 数组串联
- 解法：
- 1720. 解码异或后的数组
- 解法：
- 2574. 左右元素和的差值
- 解法：
- LCP 01. 猜数字
- 解法：
- LCP 06. 拿硬币
- 解法：
- 1365. 有多少小于当前数字的数字
- 1732. 找到最高海拔
- 解法：
- 1464. 数组中两元素的最大乘积
- 解法：
- 2496. 数组中字符串的最大值
- 解法：
- 1979. 找出数组的最大公约数
- 解法：辗转相除法
- 485. 最大连续 1 的个数
- 解法：
- 495. 提莫攻击
- 解法：
- 414. 第三大的数
- 解法：
- 628. 三个数的最大乘积
- 解法：
- 645. 错误的集合
- 解法：
- 697. 数组的度
- 解法：
- 448. 找到所有数组中消失的数字
- 解法：
2011. 执行操作后的变量值
存在一种仅支持 4 种操作和 1 个变量 X 的编程语言：
- ++X 和 X++ 使变量 X 的值 加 1
- --X 和 X-- 使变量 X 的值 减 1
最初，X 的值是 0
给你一个字符串数组 operations ，这是由操作组成的一个列表，返回执行所有操作后， X 的 最终值 。
示例：
输入：operations = ["--X","X++","X++"]
输出：1
解释：操作按下述步骤执行：
最初，X = 0
--X：X 减 1 ，X = 0 - 1 = -1
X++：X 加 1 ，X = -1 + 1 = 0
X++：X 加 1 ，X = 0 + 1 = 1
解法：
class Solution {
public:int finalValueAfterOperations(vector<string>& operations) {int x = 0;for(vector<string>::iterator it = operations.begin(); it != operations.end(); it++){if(*it == "--X" || *it == "X--"){x -= 1;}else{x += 1;}}return x;}
};//增强for循环 C++11
class Solution {
public:int finalValueAfterOperations(vector<string>& operations) {int x = 0;for(string &op : operations){if(op == "--X" || op == "X--"){x -= 1;}else{x += 1;}}return x;}
};
1929. 数组串联
给你一个长度为 n 的整数数组 nums 。请你构建一个长度为 2n 的答案数组 ans ，数组下标 从 0 开始计数 ，对于所有 0 <= i < n 的 i ，满足下述所有要求：
ans[i] == nums[i]
ans[i + n] == nums[i]
具体而言，ans 由两个 nums 数组 串联 形成。
返回数组 ans 。
示例：
输入：nums = [1,2,1]
输出：[1,2,1,1,2,1]
解释：数组 ans 按下述方式形成：
- ans = [nums[0],nums[1],nums[2],nums[0],nums[1],nums[2]]
- ans = [1,2,1,1,2,1]
解法：
class Solution {
public:vector<int> getConcatenation(vector<int>& nums) {int n = nums.size();//vector<int>v(2*n);for(int i = 0; i < n; i++){//v[i] = nums[i % n];nums.push_back(nums[i]);}//return v;return nums;}
};// push_back函数 展开
void Push_Back(const T& val)
{//先判断数组容量是否足够if(this->m_capacity == this.m_Size){cout << "数组已满" << endl;return;}this->pAddress[this->m_Size] = val;//在数组末尾插入数据this->m_Size++;//更新大小}1720. 解码异或后的数组
未知 整数数组 arr 由 n 个非负整数组成。
经编码后变为长度为 n - 1 的另一个整数数组 encoded ，其中 encoded[i] = arr[i] XOR arr[i + 1] 。例如，arr = [1,0,2,1] 经编码后得到 encoded = [1,2,3] 。
给你编码后的数组 encoded 和原数组 arr 的第一个元素 first（arr[0]）。
请解码返回原数组 arr 。可以证明答案存在并且是唯一的。
示例：
输入：encoded = [1,2,3], first = 1
输出：[1,0,2,1]
解释：若 arr = [1,0,2,1] ，那么 first = 1 且 encoded = [1 XOR 0, 0 XOR 2, 2 XOR 1] = [1,2,3]
解法：
class Solution {
public:vector<int> decode(vector<int>& encoded, int first) {int size = encoded.size();vector<int> arr;arr.push_back(first);for(int i = 0; i < size; i++){int x = first ^ encoded[i];first = x;arr.push_back(x);}return arr;}
};
2574. 左右元素和的差值
给你一个下标从 0 开始的长度为 n 的整数数组 nums。
定义两个数组 leftSum 和 rightSum，其中：
leftSum[i] 是数组 nums 中下标 i 左侧元素之和。如果不存在对应的元素，leftSum[i] = 0 。
rightSum[i] 是数组 nums 中下标 i 右侧元素之和。如果不存在对应的元素，rightSum[i] = 0 。
返回长度为 n 数组 answer，其中 answer[i] = |leftSum[i] - rightSum[i]|。
示例：
输入：nums = [10,4,8,3]
输出：[15,1,11,22]
解释：数组 leftSum 为 [0,10,14,22] 且数组 rightSum 为 [15,11,3,0] 。
数组 answer 为 [|0 - 15|,|10 - 11|,|14 - 3|,|22 - 0|] = [15,1,11,22] 。
解法：
class Solution {
public:vector<int> leftRightDifference(vector<int>& nums) {int n = nums.size();vector<int>v(n,0);for(int i = 1; i < n; i++){v[i] = v[i-1] + nums[i-1]; //左侧和}int temp = 0;for(int i = n - 2; i >= 0; i--){temp += nums[i+1];//右侧和v[i] = abs(v[i] - temp);//直接得出差值的绝对值}return v;}
};LCP 01. 猜数字
小A 和 小B 在玩猜数字。小B 每次从 1, 2, 3 中随机选择一个，小A 每次也从 1, 2, 3 中选择一个猜。他们一共进行三次这个游戏，请返回 小A 猜对了几次？
输入的guess数组为 小A 每次的猜测，answer数组为 小B 每次的选择。guess和answer的长度都等于3。
示例：
输入：guess = [1,2,3], answer = [1,2,3]
输出：3
解释：小A 每次都猜对了。
解法：
class Solution {
public:int game(vector<int>& guess, vector<int>& answer) {int count = 0;for(int i = 0; i < 3; i++){if(guess[i] == answer[i]){count++;}}return count;}
};
LCP 06. 拿硬币
桌上有 n 堆力扣币，每堆的数量保存在数组 coins 中。我们每次可以选择任意一堆，拿走其中的一枚或者两枚，求拿完所有力扣币的最少次数。
示例：
输入：[4,2,1]
输出：4
解释：第一堆力扣币最少需要拿 2 次，第二堆最少需要拿 1 次，第三堆最少需要拿 1 次，总共 4 次即可拿完。
解法：
class Solution {
public:int minCount(vector<int>& coins) {int sum = 0;for(int& i: coins){sum += (i + 1)/2;}return sum;}/*
向上取整（Ceiling）通常是指将一个数字 向上舍入 到最接近的整数。如果数字已经是整数，则返回该数字本身。
啥意思？也就是当一个数字超过它自身多出来的小数，我们 向更大值 方向取一个最接近的整数。可以看一下 向上取整 常用于以下场景：分页： 在分页中，向上取整用于计算需要的页数。例如，如果有 10 条数据，每页 3 条数据，实际需要 4 页来显示所有数据。
计算容器大小： 在一些算法中，当我们需要将元素分配到容器中时，可能需要向上取整来确保所有元素都能放进容器。
代码逻辑如下：// 对于两个整数 a 和 b，我们可以通过以下方法实现 a / b 的向上取整：int ceilDiv(int a, int b) {return (a + b - 1) / b;
}
// 如果 a 能被 b 整除，那么 (a + b - 1) / b 仍然等于 a / b。
// 如果 a 不能被 b 整除，(a + b - 1) / b 会将 a 向上舍入，得到正确的向上取整。而针对这个题：
一次“动作”，有2个结果 一枚或者两枚；而从 贪心 的角度来看，除非 conis[i] 本身就 1 ，要不也不会 只取一枚；而前面说了 一枚/两枚 的动作都是一次，也就是说行动上是一样的。
那么就统一成“一次取两枚，如果还有剩余，再取一次”；那这个题转化成了 “conis[i] 是 2 的多倍，是否有余数”这不就我上面说的 向上取整 么。直接套公式： (conis[i] + 2 - 1) / 2*/
1365. 有多少小于当前数字的数字
给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。
换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。
以数组形式返回答案。
示例：
输入：nums = [8,1,2,2,3]
输出：[4,0,1,1,3]
解释：
对于 nums[0]=8 存在四个比它小的数字：（1，2，2 和 3）。
对于 nums[1]=1 不存在比它小的数字。
对于 nums[2]=2 存在一个比它小的数字：（1）。
对于 nums[3]=2 存在一个比它小的数字：（1）。
对于 nums[4]=3 存在三个比它小的数字：（1，2 和 2）。
//暴力破解
class Solution {
public:vector<int> smallerNumbersThanCurrent(vector<int>& nums) {vector<int>count(nums.size(),0);for(int i = 0; i < nums.size(); i++){for(int j = 0; j < nums.size(); j++){if(nums[i] > nums[j]){count[i]++;}}}return count;}
};//排序
/*
我们也可以将数组排序，并记录每一个数在原数组中的位
置。对于排序后的数组中的每一个数，我们找出其左侧第一
个小于它的数，这样就能够知道数组中小于该数的数量。
*/
class Solution {
public:vector<int> smallerNumbersThanCurrent(vector<int>& nums) {vector<pair<int,int>> data;int n = nums.size();for(int i = 0; i < n; i++){data.emplace_back(nums[i],i);}sort(data.begin(),data.end());vector<int> ret(n,0);int prev = -1;for(int i = 0; i < n; i++){if(prev == -1 || data[i].first > data[i - 1].first){prev = i;}ret[data[i].second] = prev;}return ret;}
};
1732. 找到最高海拔
有一个自行车手打算进行一场公路骑行，这条路线总共由 n + 1 个不同海拔的点组成。自行车手从海拔为 0 的点 0 开始骑行。
给你一个长度为 n 的整数数组 gain ，其中 gain[i] 是点 i 和点 i + 1 的 净海拔高度差（0 <= i < n）。请你返回 最高点的海拔 。
示例：
输入：gain = [-5,1,5,0,-7]
输出：1
解释：海拔高度依次为 [0,-5,-4,1,1,-6] 。最高海拔为 1 。
解法：
class Solution {
public:int largestAltitude(vector<int>& gain) {int ans = 0;int sum = 0;for(int x : gain){sum += x;ans = max(ans,sum);}return ans;}
};
//或
class Solution {
public:int largestAltitude(vector<int>& gain) {int ans = 0;int sum = 0;for (int x : gain) {sum += x;if (sum > ans)ans = sum;}return ans;}
};
1464. 数组中两元素的最大乘积
给你一个整数数组 nums，请你选择数组的两个不同下标 i 和 j，使 (nums[i]-1)*(nums[j]-1) 取得最大值。
请你计算并返回该式的最大值。
示例：
输入：nums = [3,4,5,2]
输出：12
解释：如果选择下标 i=1 和 j=2（下标从 0 开始），则可以获得最大值，(nums[1]-1)(nums[2]-1) = (4-1)(5-1) = 3*4 = 12 。
解法：
class Solution {
public:int maxProduct(vector<int>& nums) {int max = 0;for(int i = 0; i < nums.size(); i++){for(int j = 0; j < nums.size(); j++){int ans = (nums[i] - 1) * (nums[j] - 1);if(ans > max) max = ans;}}return max;}
};
//或 下面的方法 只遍历一次即可
class Solution {
public:int maxProduct(vector<int>& nums) {int max1 = 0, max2 =0;for(int x : nums){if(x > max1){max2 = max1;max1 = x;}else if(x > max2){max2 = x;}}return (max1 - 1) * (max2 - 1);}
};
//或调用API sort()从小到大排序;nums.back()末尾元素;nums[nums.size() - 2]倒数第二个元素
class Solution {
public:int maxProduct(vector<int>& nums) {sort(nums.begin(),nums.end());return (nums.back() - 1) * (nums[nums.size() - 2] - 1);}
};
2496. 数组中字符串的最大值
一个由字母和数字组成的字符串的 值 定义如下：
如果字符串 只 包含数字，那么值为该字符串在 10 进制下的所表示的数字。
否则，值为字符串的 长度 。
给你一个字符串数组 strs ，每个字符串都只由字母和数字组成，请你返回 strs 中字符串的 最大值 。
示例：
输入：strs = ["alic3","bob","3","4","00000"]
输出：5
解释：
- "alic3" 包含字母和数字，所以值为长度 5 。
- "bob" 只包含字母，所以值为长度 3 。
- "3" 只包含数字，所以值为 3 。
- "4" 只包含数字，所以值为 4 。
- "00000" 只包含数字，所以值为 0 。
所以最大的值为 5 ，是字符串 "alic3" 的值。
解法：
class Solution {
public:int maximumValue(vector<string>& strs) {int max_val = 0;for (string& str : strs) {bool all_digit = all_of(str.begin(),str.end(),::isdigit);int current_val = 0;if (all_digit){ current_val = atoi(str.c_str());} else {current_val = str.size();}if(current_val > max_val){max_val = current_val;}}return max_val;}
};
//或
class Solution {
public:int all_digit(string& str) { //判断字符串是否全为数字int temp = 0;for (int i = 0; i < str.size(); i++) {temp = int(str[i]);if (temp >= 48 && temp <= 57) {continue;}else{return 0;}}return 1;}int maximumValue(vector<string>& strs) {int max_val = 0;for (string& str : strs) {int current_val = 0;if (all_digit(str)) {//是返回1 并将字符串变为数字current_val = atoi(str.c_str());} else {//不是求去字符串长度current_val = str.size();}if (current_val > max_val) {//找到最大值max_val = current_val;}}return max_val;}
};
1979. 找出数组的最大公约数
给你一个整数数组 nums ，返回数组中最大数和最小数的 最大公约数 。
两个数的 最大公约数 是能够被两个数整除的最大正整数。
示例：
输入：nums = [2,5,6,9,10]
输出：2
解释：
nums 中最小的数是 2
nums 中最大的数是 10
2 和 10 的最大公约数是 2
解法：辗转相除法
class Solution {
public:int findGCD(vector<int>& nums) {sort(nums.begin(), nums.end());int n = nums.size();int x = nums[0];//最小值int y = nums[n - 1];//最大值int temp;while(x)//最小值为循环条件{temp = y % x;y = x;x = temp;}return y;}
};
485. 最大连续 1 的个数
给定一个二进制数组 nums ， 计算其中最大连续 1 的个数。
示例：
输入：nums = [1,1,0,1,1,1]
输出：3
解释：开头的两位和最后的三位都是连续 1 ，所以最大连续 1 的个数是 3.
解法：
class Solution {
public:int findMaxConsecutiveOnes(vector<int>& nums) {int max = 0, count = 0;for (int x : nums) {if (x == 1) {count++;} else {if (count > max)max = count;count = 0;}}if (count > max)max = count;return max;}
};
495. 提莫攻击
在《英雄联盟》的世界中，有一个叫 “提莫” 的英雄。他的攻击可以让敌方英雄艾希（编者注：寒冰射手）进入中毒状态。
当提莫攻击艾希，艾希的中毒状态正好持续 duration 秒。
正式地讲，提莫在 t 发起攻击意味着艾希在时间区间 [t, t + duration - 1]（含 t 和 t + duration - 1）处于中毒状态。如果提莫在中毒影响结束 前 再次攻击，中毒状态计时器将会 重置 ，在新的攻击之后，中毒影响将会在 duration 秒后结束。
给你一个 非递减 的整数数组 timeSeries ，其中 timeSeries[i] 表示提莫在 timeSeries[i] 秒时对艾希发起攻击，以及一个表示中毒持续时间的整数 duration 。
返回艾希处于中毒状态的 总 秒数。
示例：
输入：timeSeries = [1,4], duration = 2
输出：4
解释：提莫攻击对艾希的影响如下：
- 第 1 秒，提莫攻击艾希并使其立即中毒。中毒状态会维持 2 秒，即第 1 秒和第 2 秒。
- 第 4 秒，提莫再次攻击艾希，艾希中毒状态又持续 2 秒，即第 4 秒和第 5 秒。
艾希在第 1、2、4、5 秒处于中毒状态，所以总中毒秒数是 4 。
解法：
class Solution {
public:int findPoisonedDuration(vector<int>& timeSeries, int duration) {int ans = 0;for(int i = 1; i < timeSeries.size(); i++){int diff = timeSeries[i] - timeSeries[i - 1];//计算差值，如果差值大于等于中毒时间，先直接加一整个//中毒时间；如果差值小于中毒时间，先只加当前攻击与前//一次攻击的差值if(diff >= duration){ans += duration;}else{ans += diff;}}//最后无论哪种情况都需要加一整个中毒时间ans += duration;return ans;}
};
414. 第三大的数
给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。
示例：
输入：[3, 2, 1]
输出：1
解释：第三大的数是 1 。
解法：
class Solution {
public:int thirdMax(vector<int>& nums) {sort(nums.begin(),nums.end(),greater<int>());//从大到小排序int n = nums.size();if(n < 3){return nums[0];}int count = 1;//记录最大值现在为1for(int i = 1; i < n; i++){if(nums[i] != nums[i - 1]){count++;if(count == 3){return nums[i];}}}return nums[0];}
};
628. 三个数的最大乘积
给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
示例：
输入：nums = [1,2,3]
输出：6
解法：
class Solution {
public:int maximumProduct(vector<int>& nums) {//思路：先排序从大到小方式，如果全为正数或全为负数，则取number2算法，如果又有正数又有负数，则取number1算法int number1 = 0;int number2 = 0;int count = 0;sort(nums.begin(), nums.end(), greater<int>());int n = nums.size();number1 = nums[0] * nums[n-1] * nums[n - 2];number2 = nums[0] * nums[1] * nums[2];if(number1 > number2){return number1;}return number2;}
};
645. 错误的集合
集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。
给定一个数组 nums 代表了集合 S 发生错误后的结果。
请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。
示例：
输入：nums = [1,2,2,4]
输出：[2,3]
解法：
class Solution {
public:vector<int> findErrorNums(vector<int>& nums) {//哈希表法：先在map统计各个数字的个数，如果遇到数量为2的，则代表是重复数字，将下标赋给x;如果count为0，则代表缺失数字的下标赋给y。int n = nums.size(), x = 0, y = 0, count = 0;map<int,int>map;for(int num : nums){map[num]++;}for(int i = 1; i <= n; i++){count = map[i];if(count == 2){x = i;}else if(count == 0){y = i;}}return {x, y};}
};
697. 数组的度
给定一个非空且只包含非负数的整数数组 nums，数组的 度 的定义是指数组里任一元素出现频数的最大值。
你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。
示例：
输入：nums = [1,2,2,3,1]
输出：2
解释：
输入数组的度是 2 ，因为元素 1 和 2 的出现频数最大，均为 2 。
连续子数组里面拥有相同度的有如下所示：
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
最短连续子数组 [2, 2] 的长度为 2 ，所以返回 2 。
解法：
class Solution {
public:int findShortestSubArray(vector<int>& nums) {unordered_map<int, vector<int>> map;int n = nums.size();for (int i = 0; i < n; i++) {if (map.count(nums[i])) {map[nums[i]][0]++;map[nums[i]][2] = i;} else {map[nums[i]] = {1, i, i};}}int maxNum = 0, minLen = 0;for (auto& [_, vec] : map) {//auto& [, vec] 的意思是：对于 mp 中的每一个键值对// 元素（它是一个 pair），我声明一个对它的引用。然后// ，我将这个 pair 的第二个成员（值）解包到一个名为 // vec 的引用中，同时忽略它的第一个成员（键）。if (maxNum < vec[0]) {maxNum = vec[0];minLen = vec[2] - vec[1] + 1;} else if (maxNum == vec[0]) {if (minLen > vec[2] - vec[1] + 1) {minLen = vec[2] - vec[1] + 1;}}}return minLen;}
};
448. 找到所有数组中消失的数字
给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。
示例：
输入：nums = [4,3,2,7,8,2,3,1]
输出：[5,6]
解法：
class Solution {
public:vector<int> findDisappearedNumbers(vector<int>& nums) {int n = nums.size();int count = 0;map<int,int>mp;//利用哈希表记录数组内的在数字个数vector<int> res;for(int num : nums){mp[num]++;}for(int i = 1; i <= n; i++){count = mp[i];if(count == 0)//如果个数为0 则代表数组内没有这个数，并将此数插入到res数组中{res.push_back(i); }}return res;}
};