6151. 统计特殊整数

如果一个正整数每一个数位都是 互不相同 的，我们称它是 特殊整数 。

给你一个 正 整数 n ，请你返回区间 [1, n] 之间特殊整数的数目。

示例 1：

输入：n = 20
输出：19
解释：1 到 20 之间所有整数除了 11 以外都是特殊整数。所以总共有 19 个特殊整数。

示例 2：

输入：n = 5
输出：5
解释：1 到 5 所有整数都是特殊整数。

示例 3：

输入：n = 135
输出：110
解释：从 1 到 135 总共有 110 个整数是特殊整数。
不特殊的部分数字为：22 ，114 和 131 。

提示：

• 1 <= n <= 2 * 1e9

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/count-special-integers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

做题结果

成功，但是比赛t4第一解2000多ms，如果rejudge取第二次解就很慢T T。而且第二解也没有缓存，几百毫秒，不知道会不会有例子会卡。其实我知道有答案可以抄，之前刚好写过，但是写过不熟，就顺便练练【其实很有底气的话，反而会抄，因为符合规则，而且自身有把握，自己是会的】。原题来自：1012. 至少有 1 位重复的数字，用总数减掉这个答案就可以了，基本完全一样

方法：数学+DFS

先排序组合算少一位的，再算刚刚好的

class Solution {
        public int countSpecialNumbers(int n) {
            char[] cs = String.valueOf(n).toCharArray();
            int len = cs.length;
            int pre = 1;
            int sum = 0;
            int[] time = new int[]{9,9,8,7,6,5,4,3,2,1};
            for(int i = 0; i < len-1; i++){
                pre=pre*time[i];
                sum += pre;
            }
 
            return sum + dfs(cs,n,0,0,new boolean[10],true);
        }
 
        private int dfs(char[] cs, int num, int v,int index, boolean[] visited,boolean limit){
            if(index == cs.length) return 1;
            int ans = 0;
            int max = limit?cs[index]-'0':9;
            for(int i = 0; i <= max; i++){
                if(i==0&&index==0) continue;
                if((long)v*10+i>num) continue;
                if(visited[i]) continue;
                visited[i] = true;
                ans += dfs(cs,num,v*10+i,index+1,visited,limit && i==max);
                visited[i] = false;
            }
            return ans;
        }
    }

方法：记忆化搜索（这里取的是自己1012改，那个写的好一点）

1. 把所有因素，是否有前导0，是否访问过，当前值，索引，是否前面取的数字踩线这些因素，合成 key, 记忆答案

2. 逐个取值即可，注意到达末尾时可取一个

3. 哈希去重：因为不能出现重复需要提前记忆

4. 最后一个0：最后会多算一个0，需要减掉

5. 限定：如果前面刚好取到最大值，则后续值不能超过当前数字限定值

6. 前导0：前导0不必考虑数字去重

class Solution {
    public int countSpecialNumbers(int n) {
        Deque deque = new LinkedList<>();
        int v = n;
        while (v>0){
            deque.offerFirst(v%10);
            v = v/10;
        }
 
        return dfs(new ArrayList<>(deque),0, 0,0,true,true)-1;
    }
 
    Map cnts = new HashMap<>();
    private int dfs(List n, int visited,int curr,int index,boolean limit,boolean isLeadingZero){
        if(index==n.size()){
            return 1;
        }
 
        int key = ((visited*4+(limit?2:0)+(isLeadingZero?1:0))<<4)+index;
        if(cnts.containsKey(key)) {
            return cnts.get(key);
        }
        int ans = 0;
        int max = limit?n.get(index):9;
        for(int i = 0; i <= max; i++){
            if(((visited>>i)&1)==0){
                if(!isLeadingZero || i!=0) visited = (visited|(1<
 
                ans += dfs(n,visited,curr*10+i,index+1,limit&&i==max,isLeadingZero&&i==0);
 
                if(!isLeadingZero || i!=0) visited = (visited^(1<
            }
        }
        cnts.put(key,ans);
        return ans;
    }
}