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); } };
输出：
略，这题简单的，本质就是斐波那契数列。
