C/C++每日一练(20230403) 阶乘后的零、不同路径II、爬楼梯-阿里云开发者社区

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;
}

输出：

代码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”）。

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

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

示例 1：

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

输出：2

解释：3x3 网格的正中间有一个障碍物。从左上角到右下角一共有 2 条不同的路径：

1. 向右 -> 向右 -> 向下 -> 向下

2. 向下 -> 向下 -> 向右 -> 向右

示例 2：

输入：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;
}

输出：

数组改为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);
    }
};