问题描述 给定一个非负整数 n,计算各位数字都不同的数字 x 的个数,其中 0 ≤ x < 10n 示例: 输入: 2 输出: 91 解释: 答案应为除去 11,22,33,44,55,66,77,88,99 外,在 [0,100) 区间内的所有数字。 动态规划思考及解决 读完该问题,会想到动态规划+排列组合来决解,因为是求的不同数字的个数,所以要将每一个满足的值加起来,故采用动态规划是很方便的。 第一步:创建一个dp数组,记录下n=0-2的个数(dp=[1,10,91]); 第二步:判断n>=3,满足进行遍历3-n,利用排列组合计算出不同的数字个数; 第三步:将满足的个数加上前一个的个数并放入dp数组中,最后返回dp数组的最后一个值。 代码:
回溯思考及解决 当然该题也能用递归来进行解答,回溯算法则更加的简洁,不需要设很多的未知数。 第一步:创建一个递归函数,将一个空字符串res与字符串l=’1234567890’,传入该函数中;在构造函数中创建一个self.num=0来记录个数; 第二步:遍历字符串l,并进行函数递归操作,将取到的字符从l中取出; 第三步:设置递归终止条件,且执行一次递归self.num+=1,最终返回self.num。 代码:
本文主要是讲了从动态规划+排列组合来解答该题,和回溯算法解答该题的思路以及代码,当然两种方法都可,虽然回溯算法易理解且简洁,但算法时间复杂度过高。 主 编 | 王文星 责 编 | 王卓越 where2go 团队 |
|