《算法集训传送门》

  👉引言

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

   众所周知，作为一名合格的程序员，算法 能力 是不可获缺的，并且在算法学习的过程中我们总是能感受到算法的✨魅力✨。
              ☀️🌟短短几行代码，凝聚无数前人智慧；一个普通循环，即是解题之眼🌟☀️
   💝二分，💝贪心，💝并查集，💝二叉树，💝图论，💝深度优先搜索(dfs)，💝宽度优先搜索（bfs），💝数论，💝动态规划等等， 路漫漫其修远兮，吾将上下而求索！ 希望在此集训中与大家共同进步，有所收获！！！🎉🎉🎉

今日主题：数论

 👉⭐️第一题💎

   ✨题目

       66. 加一

   ✨思路：

加一得十进一位个位数为 00 加法运算如不出现进位就运算结束了且进位只会是一
所以只需要判断有没有进位并模拟出它的进位方式，如十位数加 11 个位数置为 00，如此循环直到判断没有再进位就退出循环返回结果。
然后还有一些特殊情况当出现 9999、999999 之类的数字时，循环到最后也需要进位，出现这种情况时需要手动将它进一位。

   ✨代码：

class Solution {
public:
    void deal(int n, vector<int> &digits)
{
    if(n<0){
        digits.insert(digits.begin(),1);
        return;
    }
    if (digits[n] + 1 == 10)
    {
        digits[n] = 0;
        deal(n - 1, digits);
    }
    else
    {
        digits[n] += 1;
    }
}
vector<int> plusOne(vector<int> &digits)
{
    int n = digits.size();
    deal(n - 1, digits);
    return digits;
}
};

 👉⭐️第二题💎

   ✨题目

       172. 阶乘后的零

   ✨思路：

由 10=2*5易得，0只能由2和5相乘得到，而在5的个数又小于2的个数，所以按照木桶原理,只需要求出阶乘中有多少5,就可以的到有多少0,可直接用递归求得

   ✨代码：

class Solution
{
public:
    int ans1;
    void deal(int n)
    {
        if (n <= 1) return;
        deal(n-1);  
        while (!(n % 5))
        {   n /= 5; ans1++;}   
       };
    int trailingZeroes(int n)
    {
        deal(n);
        return ans1;
    }
};

 👉⭐️第三题💎

   ✨题目

      3.连续整数求和

   ✨思路：

其实就是一个数学推导的过程，首先如果 组数i为奇数，那么n必须能够整除i，并且平均数avg=n/i,avg>i/2，那么i<sqrt(2n)这样才有足够的i满足条件；当组数i为偶数时，则还要满足(2 * (n / i ) + 1) * (i / 2),随后一个for循环解决问题，时间复杂度为 O(√n)，，嗯，这是纯用数学归纳法得到，看了题解才知，原来直接用等差数列求和推出即可。。

   ✨代码：

class Solution {
public:

int consecutiveNumbersSum(int n)
{
    int ans = 0;
    for (int i = 1; i < sqrt(2 * n); i++)
    {
        if (!(n % i) && i & 1)
        {
            ans++;
        }
        else if (!(i & 1))
        {
            int t=n/i;
            ans += (2 * t + 1) * (i / 2) == n ? 1 : 0;
        }
    }
    return ans;
}
};

 👉⭐️第四题💎

   ✨题目

       4. OKEA

   ✨代码：

q = int(input())

for _ in range(q):
    n, k = map(int, input().split())
    s = input()
    if s == s[::-1] or k == 0:
        print(1)
    else:
        print(2)

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