《算法集训传送门》
??👉引言
| 铭记于心 | ||
|---|---|---|
| 🎉?🎉我唯一知道的，便是我一无所知🎉?🎉 |
💖
??我们的算法之路??💖
? ?众所周知，作为一名合格的程序员，算法 能力 是不可获缺的，并且在算法学习的过程中我们总是能感受到算法的?魅力?。
? ???? ???? ????🌟短短几行代码，凝聚无数前人智慧；一个普通循环，即是解题之眼🌟??
? ?💝二分，💝贪心，💝并查集，💝二叉树，💝图论，💝深度优先搜索(dfs)，💝宽度优先搜索（bfs），💝数论，💝动态规划等等， 路漫漫其修远兮，吾将上下而求索！ 希望在此集训中与大家共同进步，有所收获！！！🎉🎉🎉
今日主题：贪心
?👉??第一题💎
????题目
??????397. 整数替换
????思路：
递归来写，后面可以改成动态规划（也可以用贪心，找出固定的最优解方式：将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);
}
};
?👉??第二题💎
????题目
??????670. 最大交换
????思路：
可以用递归，每次找出最大的一个字符以及字符在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());
}
};
?👉??第三题💎
????题目
??????910. 最小差值 II
????思路：
这题就比较有意思了，一开始就想到了将数组分为两段，前上移后下移动，问题是从哪里分，一开始认为是从最接近平均值的位置，但显然并不对，于是受到题解的启发，直接暴力扫描，将每个可能的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;
}
};
?👉??第四题💎
????题目
??????A. Sum of Odd Integers
您将获得两个整数 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;
}
写在最后：
相信大家对今天的集训内容的理解与以往已经有很大不同了吧，或许也感受到了算法的魅力,当然这是一定的，路漫漫其修远兮，吾将上下而求索！伙伴们，明天见！
