👉引言
| 铭记于心 | ||
| 🎉✨🎉我唯一知道的，便是我一无所知🎉✨🎉 |
💖 ❄️我们的算法之路❄️💖
众所周知，作为一名合格的程序员，算法 能力 是不可获缺的，并且在算法学习的过程中我们总是能感受到算法的✨魅力✨。
☀️🌟短短几行代码，凝聚无数前人智慧；一个普通循环，即是解题之眼🌟☀️
💝二分，💝贪心，💝并查集，💝二叉树，💝图论，💝深度优先搜索(dfs) ，💝宽度优先搜索（bfs） ，💝数论，💝动态规划等等， 路漫漫其修远兮，吾将上下而求索！ 希望在此集训中与大家共同进步，有所收获！！！🎉🎉🎉
今日主题：贪心
👉⭐️第一题💎
✨题目
✨思路：
递归来写，后面可以改成动态规划（也可以用贪心，找出固定的最优解方式：将n变为n+1总是不比n-1差，除n-1=2的情况）
✨代码：
class Solution { public: int dp(int n) { if (n == 1) return 0; if (!(n & 1)) return dp(n >> 1)+1; else return min(dp(n - 1), dp(n + 1))+1; } int integerReplacement(int n) { if(n==INT32_MAX)n-=1; return dp(n); } };
👉⭐️第二题💎
✨题目
✨思路：
可以用递归，每次找出最大的一个字符以及字符在s中出现的最后位置，如果该最大字符无效（比如312，先找到3，但是3已经在最佳位置，所以继续往后找），则继续往下找，这里使用的比较简单的方法
✨代码：
class Solution { public: void swap(string &s, int a, int b) { char tem = s[a]; s[a] = s[b]; s[b] = tem; } int maximumSwap(int num) { char tem[1024]; sprintf(tem, "%d", num); string s(tem); string s1 = s; sort(s1.begin(), s1.end(), greater<char>()); int i = 0; while (i < s.size() && s[i] == s1[i]) i++; if (i == s.size()) return atoi(s.c_str()); int t = s.rfind(s1[i], s.size() - 1); swap(s, t, i); return atoi(s.c_str()); } };
👉⭐️第三题💎
✨题目
✨思路：
这题就比较有意思了，一开始就想到了将数组分为两段，前上移后下移动，问题是从哪里分，一开始认为是从最接近平均值的位置，但显然并不对，于是受到题解的启发，直接暴力扫描，将每个可能的i位置都走一遍不就得了。。。
✨代码：
class Solution { public: int smallestRangeII(vector<int> &nums, int k) { sort(nums.begin(), nums.end()); int n = nums.size(); int ans = nums[n - 1] - nums[0]; for (int i = 0; i < n - 1; i++) { int Max = max(nums[i] + k, nums[n - 1] - k); int Min = min(nums[0] + k, nums[i + 1] - k); ans = min(Max - Min,ans); } return ans; } };
👉⭐️第四题💎
✨题目
您将获得两个整数 n 和 k。你的任务是找出n是否可以表示为k个不同的正奇数（不能被2整除）整数之和。
您必须回答 t 个独立的测试用例。
✨思路：
数学推导题，推导搞明白了coding不超过一分钟。经过一系列假设和猜想后可以得到 若要题设成立（m为k个不同奇数值的和），则m与k必定奇偶性相同，m必定大于n平方
✨代码：
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; while(n--){ int m, k; cin >> m >> k; if(m%2==k%2&&m>=pow(k,2)){ cout<<"YES"<<endl; }else cout<<"NO"<<endl; } system("pause"); return 0; }
写在最后：
相信大家对今天的集训内容的理解与以往已经有很大不同了吧，或许也感受到了算法的魅力,当然这是一定的，路漫漫其修远兮，吾将上下而求索！伙伴们，明天见！
