专栏首页木又AI帮【leetcode刷题】T168-计算各个位数不同的数字个数

【leetcode刷题】T168-计算各个位数不同的数字个数

木又连续日更第4天(4/100)


木又的第168篇leetcode解题报告

动态规划类型第13篇解题报告

leetcode第357题:计算各个位数不同的数字个数

https://leetcode-cn.com/problems/count-numbers-with-unique-digits/


【题目】

给定一个非负整数 n,计算各位数字都不同的数字 x 的个数,其中 0 ≤ x < 10^n 。

示例:
输入: 2
输出: 91 
解释: 答案应为除去 11,22,33,44,55,66,77,88,99 外,在 [0,100) 区间内的所有数字。

【思路】

这道题主要用到排列组合知识。

首先考虑特殊情况,n>10,肯定会存在重复数字,所以返回0。

使用dp[i]存储i位数符合条件的个数(不包含最高位为0的数),最后返回sum(dp)。

n==0时,dp[i]=1

n==1时,dp[i]=9*dp[0]

n==2时,dp[i]=9*dp[1],相当于首位数有9种可能(1->9),第二位数也存在9种可能(0->9除了首位数)

n==3时,dp[i]=8*dp[i],首位数有9种可能(1->9),第二位数存在9种可能(0->9除了首位数),第三位数存在8种可能(0->9除了首位数和第二位数)

同理得到n>1时,dp[i] = (10-i+1)*dp[i-1],相当于前面几位都排序好,接下来一位只存在(10-i+1)种可能。

【代码】

python版本

class Solution(object):
    def countNumbersWithUniqueDigits(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n > 10:
            return 0
        dp = [1] * (n+1)
        for i in range(1, n+1):
            if i < 3:
                dp[i] = dp[i-1] * 9
            else:
                dp[i] = dp[i-1] * (10-i+1)
        return sum(dp)

C++版本

class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        if(n > 10)
            return 0;
        vector<int> dp(n+1, 1);
        for(int i=1; i<n+1; i++){
            if(i < 3)
                dp[i] = 9 * dp[i-1];
            else
                dp[i] = (10-i+1) * dp[i-1];
        }
        // 求和
        int sum = 0;
        for(auto tmp: dp)
            sum += tmp;
        return sum;
    }
};

本文分享自微信公众号 - 木又AI帮(gh_eaa31cab4b91),作者:木又

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-09-20

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 打卡群刷题总结0801——解码方法

    PS:刷了打卡群的题,再刷另一道题,并且总结,确实耗费很多时间。如果时间不够,以后的更新会总结打卡群的题。

    木又AI帮
  • 【leetcode刷题】T157-不同路径 II

    一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。

    木又AI帮
  • 【leetcode刷题】T167-整数拆分

    https://leetcode-cn.com/problems/integer-break/

    木又AI帮
  • 挑战程序竞赛系列(2):2.3优化递推关系式

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 打卡群刷题总结0801——解码方法

    PS:刷了打卡群的题,再刷另一道题,并且总结,确实耗费很多时间。如果时间不够,以后的更新会总结打卡群的题。

    木又AI帮
  • HOJ 2124 &POJ 2663Tri Tiling(动态规划)

    Tri Tiling Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 9...

    ShenduCC
  • Leetcode 91 Decode Ways

    A message containing letters from A-Z is being encoded to numbers using the fol...

    triplebee
  • 《剑指offer》第25天:最简单的动态规划

    这种思想的本质是:一个规模比较大的问题(可以用两三个参数表示的问题),可以通过若干规模较小的问题的结果来得到的(通常会寻求到一些特殊的计算逻辑,如求最值等),如...

    程序员小浩
  • 最长上升子序列(LIS)算法

    LIS(Longest Increasing Subsequence)最长上升子序列 一个数的序列bi,当b1 < b2 < … < bS的时候,我们称这个序列...

    ACM算法日常
  • 动态规划此一篇就够了 万字总结

    动态规划,一直以来听着就是一种很高深莫测的算法思想。尤其是上学时候算法的第一堂课,老师巴拉巴拉列了一大堆的算法核心思想,贪心、回溯、动态规划... ...,开始...

    Johngo

扫码关注云+社区

领取腾讯云代金券