《算法集训传送门》

?引言

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

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

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