C/C++每日一练(20230403)

1. 阶乘后的零 ????

2. 不同路径 II ????????

3. 爬楼梯 ????

1. 阶乘后的零

给定一个整数 n ，返回 n! 结果中尾随零的数量。

提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1

示例 1：

输入：n = 3
输出：0
解释：3! = 6 ，不含尾随 0

示例 2：

输入：n = 5
输出：1
解释：5! = 120 ，有一个尾随 0

示例 3：

输入：n = 0
输出：0

提示：

0 <= n <= 10^4

进阶：你可以设计并实现对数时间复杂度的算法来解决此问题吗？

出处：

https://edu.csdn.net/practice/24586472

代码：

#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    int trailingZeroes(int n)
    {
        int numOfZeros = 0;
        while (n > 0)
        {
            numOfZeros += numOf5(n);
            n--;
        }
        return numOfZeros;
    }
    int numOf5(int num)
    {
        int count = 0;
        while ((num > 1) && (num % 5 == 0))
        {
            count++;
            num /= 5;
        }
        return count;
    }
};

int main()
{
    Solution s;
    cout << s.trailingZeroes(3) << endl;
    cout << s.trailingZeroes(5) << endl;
    cout << s.trailingZeroes(0) << endl;
    cout << s.trailingZeroes(100) << endl;

    return 0;
}

输出：

0
1
0
24

代码2：

#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    int trailingZeroes(int n)
    {
        int numOfZeros = 0;
        int multiple = 5;
        while (n >= multiple)
        {
            numOfZeros += int(n / multiple);
            multiple *= 5;
        }
        return numOfZeros;
    }
};

int main()
{
    Solution s;
    cout << s.trailingZeroes(3) << endl;
    cout << s.trailingZeroes(5) << endl;
    cout << s.trailingZeroes(0) << endl;
    cout << s.trailingZeroes(100) << endl;
  
    return 0;
}

2. 不同路径 II

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

C/C++每日一练(20230403)

网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1：

C/C++每日一练(20230403)

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

示例 2：

C/C++每日一练(20230403)

输入：obstacleGrid = [[0,1],[0,0]]
输出：1

提示：

m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] 为 0 或 1

以下程序实现了这一功能，请你填补空白处内容：

```c++

#include <stdio.h>
#include <stdlib.h>
static int uniquePathsWithObstacles(int **obstacleGrid, int obstacleGridRowSize, int obstacleGridColSize)
{
int row, col;
int reset = 0;
for (row = 0; row < obstacleGridRowSize; row++)
{
if (reset)
{
obstacleGrid[row][0] = 1;
}
else
{
if (obstacleGrid[row][0] == 1)
{
reset = 1;
}
}
}
reset = 0;
for (col = 0; col < obstacleGridColSize; col++)
{
if (reset)
{
obstacleGrid[0][col] = 1;
}
else
{
if (obstacleGrid[0][col] == 1)
{
reset = 1;
}
}
}
for (row = 0; row < obstacleGridRowSize; row++)
{
int *line = obstacleGrid[row];
for (col = 0; col < obstacleGridColSize; col++)
{
line[col] ^= 1;
}
}
for (row = 1; row < obstacleGridRowSize; row++)
{
int *last_line = obstacleGrid[row - 1];
int *line = obstacleGrid[row];
for (col = 1; col < obstacleGridColSize; col++)
{
________________________;
}
}
return obstacleGrid[obstacleGridRowSize - 1][obstacleGridColSize - 1];
}
int main(int argc, char **argv)
{
if (argc < 3)
{
fprintf(stderr, "Usage: ./test m n\n");
exit(-1);
}
int i, j, k = 3;
int row_size = atoi(argv[1]);
int col_size = atoi(argv[2]);
int **grids = malloc(row_size * sizeof(int *));
for (i = 0; i < row_size; i++)
{
grids[i] = malloc(col_size * sizeof(int));
int *line = grids[i];
for (j = 0; j < col_size; j++)
{
line[j] = atoi(argv[k++]);
printf("%d ", line[j]);
}
printf("\n");
}
printf("%d\n", uniquePathsWithObstacles(grids, row_size, col_size));
return 0;
}

```

出处：

https://edu.csdn.net/practice/24586473

代码：

#include <iostream>
using namespace std;

static int uniquePathsWithObstacles(int **obstacleGrid, int obstacleGridRowSize, int obstacleGridColSize)
{
    int row, col;
    int reset = 0;
    for (row = 0; row < obstacleGridRowSize; row++)
    {
        if (reset)
        {
            obstacleGrid[row][0] = 1;
        }
        else
        {
            if (obstacleGrid[row][0] == 1)
            {
                reset = 1;
            }
        }
    }
    reset = 0;
    for (col = 0; col < obstacleGridColSize; col++)
    {
        if (reset)
        {
            obstacleGrid[0][col] = 1;
        }
        else
        {
            if (obstacleGrid[0][col] == 1)
            {
                reset = 1;
            }
        }
    }
    for (row = 0; row < obstacleGridRowSize; row++)
    {
        int *line = obstacleGrid[row];
        for (col = 0; col < obstacleGridColSize; col++)
        {
            line[col] ^= 1;
        }
    }
    for (row = 1; row < obstacleGridRowSize; row++)
    {
        int *last_line = obstacleGrid[row - 1];
        int *line = obstacleGrid[row];
        for (col = 1; col < obstacleGridColSize; col++)
        {
			if (line[col] != 0)
			{
			    line[col] = line[col - 1] + last_line[col];
			}
        }
    }
    return obstacleGrid[obstacleGridRowSize - 1][obstacleGridColSize - 1];
}

int main()
{
	int row = 3, col = 3;
	int **grids = new int*[row]{new int[col]{0,0,0}, new int[col]{0,1,0}, new int[col]{0,0,0}};
    cout << uniquePathsWithObstacles(grids, row, col) << endl;

	row = 2, col = 2;
	int **grids2 = new int*[row]{new int[col]{0,1}, new int[col]{0,0}};
    cout << uniquePathsWithObstacles(grids2, row, col) << endl;

    return 0;
}

输出：

2
1

数组改为vector：

#include <iostream>
#include <vector>
using namespace std;

static int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid)
{
    int obstacleGridRowSize = obstacleGrid.size();
    int obstacleGridColSize = obstacleGrid[0].size();
    int row, col, reset = 0;
    for (row = 0; row < obstacleGridRowSize; row++)
    {
        if (reset)
            obstacleGrid[row][0] = 1;
        else if (obstacleGrid[row][0] == 1)
            reset = 1;
    }
    reset = 0;
    for (col = 0; col < obstacleGridColSize; col++)
    {
        if (reset)
            obstacleGrid[0][col] = 1;
        else if (obstacleGrid[0][col] == 1)
            reset = 1;
    }
    for (row = 0; row < obstacleGridRowSize; row++)
    {
        vector<int>& line = obstacleGrid[row];
        for (int col = 0; col < obstacleGridColSize; col++)
            line[col] ^= 1;
    }
    for (row = 1; row < obstacleGridRowSize; row++)
    {
        vector<int>& last_line = obstacleGrid[row - 1];
        vector<int>& line = obstacleGrid[row];
        for (int col = 1; col < obstacleGridColSize; col++)
            if (line[col] != 0)
                line[col] = line[col - 1] + last_line[col];
    }
    return obstacleGrid[obstacleGridRowSize - 1][col - 1];
}

int main()
{
    vector<vector<int>> grids = {{0,0,0}, {0,1,0}, {0,0,0}};
    cout << uniquePathsWithObstacles(grids) << endl;
    vector<vector<int>> grids2 = {{0,1}, {0,0}};
    cout << uniquePathsWithObstacles(grids2) << endl;
    return 0;
}

3. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

出处：

https://edu.csdn.net/practice/24586474

代码：

#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    int climbStairs(int n)
    {
        int a = 1;
        int b = 2;
        int c = 0;
        for (int i = 3; i <= n; i++)
        {
            c = a + b;
            a = b;
            b = c;
        }
        return n == 1 ? a : (n == 2 ? b : c);
    }
};

输出：

略，这题简单的，本质就是斐波那契数列。

???? 每日一练刷题专栏 ????

✨ 持续，努力奋斗做强刷题搬运工！

???? 点赞，你的认可是我坚持的动力！

???? 收藏，你的青睐是我努力的方向！

✎ 评论，你的意见是我进步的财富！

☸ 主页：https://hannyang.blog.csdn.net/

	Golang每日一练专栏
	Python每日一练专栏
	C/C++每日一练专栏
	Java每日一练专栏

秒客网

C/C++每日一练(20230403)

1. 阶乘后的零

2. 不同路径 II

3. 爬楼梯

???? 每日一练刷题专栏 ????

Golang每日一练专栏

Python每日一练专栏

C/C++每日一练专栏

Java每日一练专栏

相关文章

C/C++每日一练(20230403)

1. 阶乘后的零

2. 不同路径 II

3. 爬楼梯

???? 每日一练刷题专栏 ????

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

相关文章

Golang每日一练专栏

Python每日一练专栏

C/C++每日一练专栏

Java每日一练专栏