【2022-10-18每日一题】902. 最大为 N 的数字组合[Hard]
2022-10-18
2分钟阅读时长
2022-10-18每日一题：902. 最大为 N 的数字组合
难度：Hard
标签：数组 、 数学 、 字符串 、 二分查找 、 动态规划
给定一个按 非递减顺序 排列的数字数组 digits 。你可以用任意次数 digits[i] 来写的数字。例如，如果 digits = ['1','3','5']，我们可以写数字，如 '13', '551', 和 '1351315'。
返回 可以生成的小于或等于给定整数 n 的正整数的个数 。
示例 1：
输入：digits = ["1","3","5","7"], n = 100 输出：20 解释： 可写出的 20 个数字是： 1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.
示例 2：
输入：digits = ["1","4","9"], n = 1000000000 输出：29523 解释： 我们可以写 3 个一位数字，9 个两位数字，27 个三位数字， 81 个四位数字，243 个五位数字，729 个六位数字， 2187 个七位数字，6561 个八位数字和 19683 个九位数字。 总共，可以使用D中的数字写出 29523 个整数。
示例 3:
输入：digits = ["7"], n = 8 输出：1
提示：
1 <= digits.length <= 9digits[i].length == 1digits[i]是从'1'到'9'的数digits中的所有值都 不同digits按 非递减顺序 排列1 <= n <= 109
方法一：数位动态规划
详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读
func atMostNGivenDigitSet(digits []string, n int) int {
m, s := len(digits), strconv.Itoa(n)
k := len(s)
dp := make([][2]int, k+1)
dp[0][1] = 1
for i := 1; i <= k; i++ {
for _, d := range digits {
if d[0] == s[i-1] {
dp[i][1] = dp[i-1][1]
} else if d[0] < s[i-1] {
dp[i][0] += dp[i-1][1]
} else {
break
}
}
if i > 1 {
dp[i][0] += m + dp[i-1][0]*m
}
}
return dp[k][0] + dp[k][1]
}
复杂度分析
- 时间复杂度：O(logn×k)，其中 n 为给定数字，k 表示给定的数字的种类。
- 空间复杂度：O(logn)，其中 n 为给定数字。
方法二：数学
func atMostNGivenDigitSet(digits []string, n int) (ans int) {
m := len(digits)
s := strconv.Itoa(n)
bits := []int{}
isLimit := true
for _, c := range s {
if !isLimit {
bits = append(bits, m-1)
continue
}
selectIndex := -1
for j, d := range digits {
if d[0] > byte(c) {
break
}
selectIndex = j
}
if selectIndex >= 0 {
bits = append(bits, selectIndex)
if digits[selectIndex][0] < byte(c) {
isLimit = false
}
} else {
sz := len(bits)
for len(bits) > 0 && bits[len(bits)-1] == 0 {
bits = bits[:len(bits)-1]
}
if len(bits) > 0 {
bits[len(bits)-1]--
} else {
sz--
}
for len(bits) <= sz {
bits = append(bits, m-1)
}
isLimit = false
}
}
for _, b := range bits {
ans = ans*m + b + 1
}
return
}
复杂度分析
- 时间复杂度：O(logn×k)，其中 n 为给定数字，k 表示给定的数字的种类。
- 空间复杂度：O(logn)，其中 n 为给定数字。