【每日一题 春季14】1381. 阶乘 & 1006. 笨阶乘

Day14 AcWing 1381. 阶乘
Day14 LeetCode 1006. 笨阶乘

思路

  1. n!末尾有k个0,求n!10kmod10
  2. 栈模拟,将所有需要进行乘除的数字计算好,然后加入栈中计算加减,实现加减乘除的优先级计算。

拓展

  1. AcWing 197. 阶乘分解
  2. 150. 逆波兰表达式求值
  3. 224. 基本计算器
  4. 227. 基本计算器 II
  5. 寒假每日一题Day16

代码

1381. 阶乘
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 30;

int n, m;
int path[N];

void dfs(int u, int start)
{
if (u > m)
{
for (int i = 1; i <= m; i ++ )
printf("%d ", path[i]);
puts("");
}
else
{
for (int i = start; i <= n; i ++ )
{
path[u] = i;
dfs(u + 1, i + 1);
path[u] = 0;
}
}
}

int main()
{
scanf("%d%d", &n, &m);
dfs(1, 1);
return 0;
}
复制
1006. 笨阶乘
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
int clumsy(int N) {
stack<int> stk;
stk.push(N);
N--;

int index = 0; // 用于控制乘、除、加、减
while (N > 0) {
if (index % 4 == 0) {
stk.top() *= N;
} else if (index % 4 == 1) {
stk.top() /= N;
} else if (index % 4 == 2) {
stk.push(N);
} else {
stk.push(-N);
}
index++;
N--;
}

// 把栈中所有的数字依次弹出求和
int sum = 0;
while (!stk.empty()) {
sum += stk.top();
stk.pop();
}
return sum;
}
};
复制
来发评论吧~
Powered By Valine
v1.5.2