👉引言
| 铭记于心 ||唯一知道的，便是我一无所知||
我们的算法之路
众所周知，作为一名合格的程序员，算法 能力 是不可获缺的，并且在算法学习的过程中我们总是能感受到算法的✨魅力✨
☀️🌟短短几行代码，凝聚无数前人智慧；一个普通循环，即是解题之眼🌟☀️
💝 二分，💝 贪心，💝 并查集，💝 二叉树，💝 图论，💝 深度优先搜索(dfs)，💝 宽度优先搜索（bfs），💝 数论，💝 动态规划等等， 路漫漫其修远兮，吾将上下而求索！ 希望在此集训中与大家共同进步，有所收获！！！🎉🎉🎉
今日主题：数组
👉⭐️第一题 💎
✨题目
✨思路：
首先进行排序，这里比较容易出错的就是 数组中会有负数，而这种情况就是取最小的两个负数，以及一个正数，与正常情况（最大的三个数）相比，返回较大值
✨代码：
class Solution { public: int maximumProduct(vector<int>& nums) { sort(nums.begin(),nums.end()); int n=nums.size(); int num1= nums[n-1]*nums[n-2]*nums[n-3]; int num2=nums[0]*nums[1]*nums[n-1]; return max(num1,num2); } };
👉⭐️第二题 💎
✨题目
就是对原数组进行排序，然后对每个数，统计小于该数的个数，这里使用STL中的map实现
✨:代码：
class Solution { public: vector<int> smallerNumbersThanCurrent(vector<int>& nums) { map<int, int>ans; for (int i : nums) { ans[i]++; } for (int i = 0; i < nums.size(); i++) { int num = nums[i]; int sum = 0; for (map<int, int>::iterator it = ans.begin(); it != ans.end(); it++) { if (it->first != num) { sum += it->second; continue; }break; }nums[i] = sum; } return nums; } };
👉⭐️第三题 💎
✨题目
✨思路：
当我们找到一个没有出现过的数的时候，将之前某个重复出现的数增加成这个没有出现过的数。注意，这里 「之前某个重复出现的数」 是可以任意选择的，它并不会影响最终的答案，这里先参考官方题解，等小编有能力了自己写一个
✨代码：
class Solution { public: int minIncrementForUnique(vector<int>& nums) { int C[800000]={0}; for (int x : nums) { C[x]++; } int ans = 0, taken = 0; for (int x = 0; x < 800000; ++x) { if (C[x] >= 2) { taken += C[x] - 1; ans -= x * (C[x] - 1); } else if (taken > 0 && C[x] == 0) { taken--; ans += x; } } return ans; } };
👉⭐️第四题 💎:
✨题目
✨思路：
有n堆沙子,其中第i堆沙子有a块沙子。如果1<i<n 且 ai>ai-1+ai+1,则第i个桩被称为太高。也就是说,如果一堆沙子比它的两个邻居加起来还多,那么它就太高了。(请注意,数组末端的堆不能太高。)给定一个整数k。一个操作包括连续拾取k堆沙子,然后向它们全部添加一个单位的沙子。形式上,选择1sl,rsn 使得r-l+1=k。然后对于所有Isisr,更新ai-ai+1。在一些(可能为零)操作之后,同时太高的桩的最大数量是多少?
✨代码：
#include <bits/stdc++.h> using namespace std; const int MAX = 200007; const int MOD = 1000000007; void solve() { int n, k; cin >> n >> k; int a[n]; for (int i = 0; i < n; i++) { cin >> a[i]; } if (k > 1) { int res = 0; for (int i = 1; i < n - 1; i++) { res += (a[i] > a[i - 1] + a[i + 1]); } cout << res << '\n'; } else { cout << (n - 1) / 2 << '\n'; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();} // solve(); }
写在最后： 相信大家对今天的集训内容的理解与以往已经有很大不同了吧，或许也感受到了算法的魅力,当然这是一定的，路漫漫其修远兮，吾将上下而求索！伙伴们，明天见！
