leetcode 第 326 场算法比赛

作者: | 更新日期:

筛素数竟然出现两道题。

本文首发于公众号:天空的代码世界,微信号:tiankonguse

零、背景

这次比赛难度简单的令人发指。

一、统计能整除数字的位数

题目:给一个数字,问数字可以整除整数的各位数字的个数。

思路:枚举各位数字,判断是否能整除即可。

二、数组乘积中的不同质因数数目

题意:给一个数字数组,问数组中所有数字相乘后的结果包含的不同质约数个数。

思路:先打素数表,然后求数组每个数字的质约数,去重即可。

三、将字符串分割成值不超过 K 的子字符串

题目:给一个数字字符串,问字符串最少可以拆分为多少个子字符串,且每个子字符串的数字值都不大于 k。

思路:动态规划。
状态定义:dp[n] 前 n 个字符满足要求的答案。
状态转移方程:dp[n] = min(dp[i] + 1), val[i+1,n]<=k
复杂度分析:小于 k 的数字长度不超过 log(k)
复杂度:O(n log(k))

四、范围内最接近的两个质数

题意:给一个数组区间,求一个相邻质数,这组相邻质数差值最小的。

思路:先筛素数表,然后枚举区间内所有相邻质数,求最优答案即可。

五、最后

这次比赛比较简单,第二个和第四题的难度其实是一样的,第三题导致相比最难的。

加油,算法人。

《完》

-EOF-

本文公众号:天空的代码世界
个人微信号:tiankonguse
公众号ID:tiankonguse-code

本文首发于公众号:天空的代码世界,微信号:tiankonguse
如果你想留言,可以在微信里面关注公众号进行留言。

点击查看评论

关注公众号,接收最新消息

tiankonguse +
穿越