143.Count Numbers with Unique Digits

2024-05-12 00:58
文章标签 numbers count 143 unique digits

本文主要是介绍143.Count Numbers with Unique Digits,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n.

Example:
Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding [11,22,33,44,55,66,77,88,99])

Hint:

  1. A direct way is to use the backtracking approach.
  2. Backtracking should contains three states which are (the current number, number of steps to get that number and a bitmask which represent which number is marked as visited so far in the current number). Start with state (0,0,0) and count all valid number till we reach number of steps equals to 10n.
  3. This problem can also be solved using a dynamic programming approach and some knowledge of combinatorics.
  4. Let f(k) = count of numbers with unique digits with length equals k.
  5. f(1) = 10, ..., f(k) = 9 * 9 * 8 * ... (9 - k + 2) [The first factor is 9 because a number cannot start with 0].

 /*** 对于k位数,统计出位数小于等于k的各个数字位上面数字均不相同的总个数。* 例如:k=1时,结果为10;k=2时,结果为91;k=3时,结果为739.* k=3时,三位数则根据排列计算9*9*8=648(首位是9是因为三位数的最高位不可为0)* 两位数则9*9=81,一位数为10,648+81+10=739.* * 令f(k)表示给定数字k时的结果,则f(k) = f(k-1) + 9*9*8***(9-k+2)* 故可采用动态规划的思想。* 如果是十一位数及以上,则符合各个位上数字不同的整数个数为0.**/public int CountNumbersWithUniqueDigits(int n){if(n == 0){return 1;}if(n == 1){return 10;}int f_k = 1;int f_k1 = 10;int pro = 9;//保存的是上一次计算的排列的结果for (int i = 2; i<=10 && i <= n;i++ ){pro = pro * (11 - i);f_k = f_k1 + pro;f_k1 = f_k;}return f_k;}

这篇关于143.Count Numbers with Unique Digits的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/981154

相关文章

uva 10061 How many zero's and how many digits ?(不同进制阶乘末尾几个0)+poj 1401

题意是求在base进制下的 n!的结果有几位数,末尾有几个0。 想起刚开始的时候做的一道10进制下的n阶乘末尾有几个零,以及之前有做过的一道n阶乘的位数。 当时都是在10进制下的。 10进制下的做法是: 1. n阶位数:直接 lg(n!)就是得数的位数。 2. n阶末尾0的个数:由于2 * 5 将会在得数中以0的形式存在,所以计算2或者计算5,由于因子中出现5必然出现2,所以直接一

ural 1014. Product of Digits贪心

1014. Product of Digits Time limit: 1.0 second Memory limit: 64 MB Your task is to find the minimal positive integer number  Q so that the product of digits of  Q is exactly equal to  N. Inpu

计蒜客 Half-consecutive Numbers 暴力打表找规律

The numbers 11, 33, 66, 1010, 1515, 2121, 2828, 3636, 4545 and t_i=\frac{1}{2}i(i+1)t​i​​=​2​​1​​i(i+1), are called half-consecutive. For given NN, find the smallest rr which is no smaller than NN

高精度打表-Factoring Large Numbers

求斐波那契数,不打表的话会超时,打表的话普通的高精度开不出来那么大的数组,不如一个int存8位,特殊处理一下,具体看代码 #include<stdio.h>#include<string.h>#define MAX_SIZE 5005#define LEN 150#define to 100000000/*一个int存8位*/int num[MAX_SIZE][LEN];void

leetcode#628. Maximum Product of Three Numbers

题目 Given an integer array, find three numbers whose product is maximum and output the maximum product. Example 1: Input: [1,2,3]Output: 6 Example 2: Input: [1,2,3,4]Output: 24 Note: The lengt

leetcode#38. Count and Say

The count-and-say sequence is the sequence of integers with the first five terms as following: 1. 12. 113. 214. 12115. 111221 1 is read off as “one 1” or 11. 11 is read off

leetCode#448. Find All Numbers Disappeared in an Array

Description Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once. Find all the elements of [1, n] inclusive that do not appear in this

第143天:内网安全-权限维持自启动映像劫持粘滞键辅助屏保后门WinLogon

案例一: 权限维持-域环境&单机版-自启动 自启动路径加载 路径地址 C:\Users\Administrator\AppData\Roaming\Microsoft\Windows\StartMenu\Programs\Startup\##英文C:\Users\Administrator\AppData\Roaming\Microsoft\Windows\开始菜单\程序\启动\ #

《Learning To Count Everything》CVPR2021

摘要 论文提出了一种新的方法来解决视觉计数问题,即在给定类别中仅有少量标注实例的情况下,对任何类别的对象进行计数。将计数问题视为一个少样本回归任务,并提出了一种新颖的方法,该方法通过查询图像和查询图像中的少量示例对象来预测图像中所有感兴趣对象的存在密度图。此外,还提出了一种新颖的适应策略,使网络能够在测试时仅使用新类别中的少量示例对象来适应任何新的视觉类别。为了支持这一任务,作者还引入了一个包含

class _ContiguousArrayStorage deallocated with non-zero retain count

Xcode报错 : Object 0x11c614000 of class _ContiguousArrayStorage deallocated with non-zero retain count 2. This object's deinit, or something called from it, may have created a strong reference to self w