VIVO算法题——数位之积

记录算法究极无敌菜菜菜鸟的垃圾思维

题目：
现给定任意正整数 n，请寻找并输出最小的正整数 m（m>9），使得 m 的各位（个位、十位、百位 … …）之乘积等于n，若不存在则输出 -1。

菜鸟思维Recording【30分钟左右】

大学四年没碰过算法，小学生思维，勿喷勿喷

最开始我想使用查找表的方式先将所有结果都记录在一个table中，然后后续根据index去查找答案。

#include<stdio.h>
#include<limits.h>#define MAX 10000
int table[MAX];
/**
* 构造查找表
*/
void createTable(){int i, temp, multi;//初始化全局变量为最大值，否则默认为0for(i = 0; i < MAX; i++){table[i] = INT_MAX;}i = 0;while(i<MAX){multi = 1;temp = i;while(temp > 0){multi = multi*(temp%10);temp = temp/10;}if(table[multi] > i){table[multi] = i;}i++;}
}/*@param input:输入字符串序列@return int:返回正确的结果
*/
int func(char* input) {createTable();// Please fill this blank//将char*转换为intint num = 0, i = 0;while(input[i] != '\0'){num = num*10+input[i] -'0';i++;}return table[num];
}int main() {char str[100];printf("请输入一个字符串\n");scanf("%s", str);printf("%d", func(str));return 0;
}

分析

• 题目并没有说明输入的字符的最大数量，在我的代码里人为定义了MAX，会造成内存溢出的问题（ERR）
• createTable的成本太高太高太高。内层while次数取决于位数，可以近似等于log(i)。所以总的时间复杂度应该是O(nlog(n))

参考题解

因为限制了最小正整数m>9，所以对于小于10的数，返回结果应该是（10+num）；对于大于等于10的数，高位越小，那么得到的数字肯定越小，结果其实就是这个整数的因子的一个组合，要得到最小的组合的整数，那么低位就应该尽可能的取大值，这样才能保证高位得到的是最小的。如果没有余数就表示这个数是有结果的，有余数就表示这个数不存在。

#include <stdio.h>
int func(char* input){
//将str转换为intint i = 0, num = 0, res = 0, pos = 1;while(input[i]!='\0'){num = num*10 + input[i]-'0';i++;}if(num < 10) return (10+num);for(i = 9; i > 1; i--){while(num% i == 0){//pos表示位数res += i*pos;pos *= 10;num/=i;}}if(num> 1) return -1;else return res;
}int main() {char str[1000];printf("请输入一个字符串\n");scanf("%s", str);printf("%d", func(str));return 0;
}

分析

时间复杂度应该是O(log(n))，因为这里char转换为整型也存在可能内存溢出的情况，但是没有上面的严重。