LeetCode1015. 至少有 1 位重复的数字

问题描述

给定正整数 N，返回小于等于 N 且具有至少 1 位重复数字的正整数。

示例 1：
输入：20
输出：1
解释：具有至少 1 位重复数字的正数（<= 20）只有 11 。
示例 2：
输入：100
输出：10
解释：具有至少 1 位重复数字的正数（<= 100）有 11，22，33，44，55，66，77，88，99 和 100 。
示例 3：
输入：1000
输出：262

提示：1 <= N <= 10^9`

思路

看到题的第一反应，循环遍历一把梭，干呗，等等等一下，困难？看来循环要超时啊。
至少有一位重复，那就求全部不重复的吧。
诶呀卧槽，情况好多，好乱好复杂，果然做不出来呢。看评论大佬们都在提数位DP，What？啥？年迈的萌新瑟瑟发抖。又到了GGSDDU的时候了，百度谷歌就是干。

一天过去了......

咳咳，数位DP的话，最主要的就是找到状态值了，怎么用一个数字来标记之前用过的那些数字呢，0-9共10位，不妨用10位的二进制来存储吧，完美！
第一次做这类题，注释很全。

具体实现

func numDupDigitsAtMostN(N int) int {
    num = make([]int, 0)
    t := N
    i := 0
    for t > 0 {
        num = append(num, t%10)
        t /= 10
        i++
    }
    return N + 1 - dfs(i-1, 0, true)/*用来寻找不符合条件的数字*/
}

//空间换时间 dp[i][j]就表示 在j的情况下 第i位的值
//比如12XXX 和 21XXX 不具有重复数字的个数一定相等
//此时j = 6 (0000000110) i=3 (倒数索引为3) 
//当计算过12XXX时将其记忆化 下次直接调取结果
var dp =[][]int{make([]int,1024),
    make([]int,1024),
    make([]int,1024),
    make([]int,1024),
    make([]int,1024),
    make([]int,1024),
    make([]int,1024),
    make([]int,1024),
    make([]int,1024),
    make([]int,1024),
}
var num = make([]int, 0)
//假定i=5 t=0 这里的方法用来寻找 0~100000中 各个位都不重复的个数 即不符合条件的数
//t用来存储之前用过的数字 10位二进制数字 1000000111 就代表用过了0 1 2 9
func dfs(i /*数位*/ int, t /*记录前几位数字*/ int, limit /*是否是边界*/ bool) int {
    if i == -1 {
        return 1
    }
    if !limit && dp[i][t]!=0{ return dp[i][t]};
    res := 0
    //比如数字是54321 当第一位是5 第二位是4 那么此时就是边界值 第三位只能是0~3 
    //否则 可以为0~9
    u  := 9
    if limit {
        u = num[i]
    }
    for d := 0; d <= u; d++ {
        a := t / (1<<uint8(d)) & 1
        if a == 1 {
            //假定此时t = 10(0000001010) 那么当前位不能位 1 和 3
            continue
        }
        var tt int
        //当t是0 且当前位也是0 代表下一位是首位数字 此时下一位还可以用0 不做记录
        if !(t==0 && d == 0) {
            //以二进制记录下已经用过的值
            tt = t + (1<<uint8(d))
        }
        res += dfs(i-1, tt , d == num[i] && limit)
    }
    if !limit {
        //记忆化
        dp[i][t]=res
    }
    return res
}

最后编辑于：2019.03.22 00:12:50