C/C++每日一练(20230403)
目录
1. 阶乘后的零 🌟
2. 不同路径 II 🌟🌟
3. 爬楼梯 🌟
🌟 每日一练刷题专栏 🌟
Golang每日一练 专栏
Python每日一练 专栏
C/C++每日一练 专栏
Java每日一练 专栏
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”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 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.lengthn == obstacleGrid[i].length1 <= m, n <= 100obstacleGrid[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每日一练 专栏 |