《算法集训传送门》

  👉引言

---

💖 ❄️我们的算法之路❄️💖

   众所周知，作为一名合格的程序员，算法 能力 是不可获缺的，并且在算法学习的过程中我们总是能感受到算法的✨魅力✨。
              ☀️🌟短短几行代码，凝聚无数前人智慧；一个普通循环，即是解题之眼🌟☀️
   💝二分，💝贪心，💝并查集，💝二叉树，💝图论，💝深度优先搜索(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);
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

 👉⭐️第二题💎

   ✨题目

      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());
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

 👉⭐️第三题💎

   ✨题目

      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;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

 👉⭐️第四题💎

   ✨题目

      A. Sum of Odd Integers

您将获得两个整数 n 和 k。你的任务是找出n是否可以表示为k个不同的正奇数（不能被2整除）整数之和。

您必须回答 t 个独立的测试用例。

   ✨思路：

数学推导题，推导搞明白了coding不超过一分钟。经过一系列假设和猜想后可以得到 若要题设成立（m为k个不同奇数值的和），则m与k必定奇偶性相同，m必定大于n平方

   ✨代码：

#include 
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

写在最后：
相信大家对今天的集训内加粗样式容的理解与以往已经有很大不同了吧，或许也感受到了算法的魅力,当然这是一定的，路漫漫其修远兮，吾将上下而求索！伙伴们，明天见！

、
加粗样式