内容简介:题目地址:题目描述:
题目地址:
https://leetcode-cn.com/probl...
题目描述:
给定一个非负整数 n,计算各位数字都不同的数字 x 的个数,其中 0 ≤ x < 10的n次方 。
示例:
输入: 2
输出: 91
解释: 答案应为除去 11,22,33,44,55,66,77,88,99 外,在 [0,100) 区间内的所有数字。即这个数最多n位。
解答:
这一题就是利用回溯法求组合数,从(0,1,2,3,4,5,6,7,8,9)这个集合中求c(k,1)+...+c(k,k),k>=1,k<=n。求组合的代码很好写,需要注意的是第1为不能为0,所以不能从第1位开始调用,而是要从第2位开始(下面的backtrack(1,k,flag);这里的1就是第二位,因为从0开始算位数)。
java ac代码:
class Solution { int ans; public int countNumbersWithUniqueDigits(int n) { boolean[]flag = new boolean[10]; for(int k = 1;k <= n;k++) for(int j = 1; j <= 9;j++){ flag[j] = true; backtrack(1,k,flag); flag[j] = false; } return ans+1; } void backtrack(int i,int n,boolean[]flag) { if(i == n) { ans++; return; } for(int j = 0;j <= 9;j++) if(!flag[j]) { flag[j] = true; backtrack(i+1,n,flag); flag[j] = false; } } }
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
计算机程序设计艺术(第1卷)
[美] Donald E. Knuth / 清华大学出版社 / 2002-9 / 80.00元
第1卷首先介绍编程的基本概念和技术,然后详细讲解信息结构方面的内容,包括信息在计算机内部的表示方法、数据元素之间的结构关系,以及有效的信息处理方法。此外,书中还描述了编程在模拟、数值方法、符号计算、软件与系统设计等方面的初级应用。此第3版增加了数十项简单但重要的算法和技术,并根据当前研究发展趋势在数学预备知识方面做了大量修改。一起来看看 《计算机程序设计艺术(第1卷)》 这本书的介绍吧!