面试题 各个位上的数字乘积最大的数

缘起

面试题

1
2
给你n, 要你求出1~n中各位数字乘积最大的那个数. 例如n=100, 则就是99, 因为 9*9=81最大
n<=100000

分析

水题一道. 令f[n]是答案. 则 f[n]按照取不取最高位分类讨论就知道了.

1
2
3
举个例子吧, 例如n=689, 则如果用最高位的话, 则最大就是 6*f[89]
如果不用最高位的话,则答案就是(最高位-1)*9^2, 所以f[689]就是两者取大即可
所以本题只需要知道n的范围, 然后缓存9的幂次. 然后递归即可

不难写下如下代码

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
37
38
39
#include "stdafx.h"
#include <stdio.h>
#include <algorithm>
using namespace std;
#define LOCAL

int n, nine[10], ten[10];

int kk(int x, int y) // 返回1~x中各位数字乘积的最大值, y是x的位数
{
	if (y==1)
	{
		return x;
	}
	int a = x/ten[y-1]; // a是x的最高位
	return max(a*nine[y-1], ((a-1)?(a-1):1)*kk(x%ten[y-1], y-1)); // 用不用最高位? 即最高位是否打满?
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d", &n);
	nine[0] = ten[0] = 1;
	for (int i = 1;i<=8;i++)
	{
		nine[i] = nine[i-1]*9;
		ten[i] = ten[i-1]*10;
	} // 缓存9的幂次和10的幂次
	int m = n, t = 0; // t是n的位数
	while(m)
	{
		m/=10;
		t++;
	}
	printf("%d\n", kk(n,t));
	return 0;
}

当然， 99°兄（【1】）给出了更简洁的代码, 不是讨论最高位是否使用，而是个位数字的使用情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include "stdafx.h"
#include <algorithm>
using namespace std;
#include <stdio.h>

#define ll long long

ll dfs(int n) {
	if(n==0) return 1;
	if(n<10) return n;
	return max(dfs(n/10-1)*9,dfs(n/10)*(n%10));
}

int main() {
	int n;
	scanf("%d",&n);
	printf("%lld",dfs(n));
	return 0;
}

例如 6506， 如果使用个位数字的话, 就是6*f[650], 如果不使用的话, 就是 6499, 则就是 9*f[649] 代码写的更加简练. 很赞!

参考

【1】https://e99net.github.io/2019/09/24/cmbcc/