博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
leetcode| Count Numbers with Unique Digits
阅读量:4839 次
发布时间:2019-06-11

本文共 1814 字,大约阅读时间需要 6 分钟。

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])

题目:意思很明确,找出0 到10的n次方内没有重复数字构成的元素个数,11,101这类都不合格

思路:这道题目十分具有代表性,暴力解法当然是可以的,但是根据题目标签的提示,可以用backtrack和dynamic programming,这个两个算法很值得深入学习一番,看到许多书籍提到过

1,首先是backtrack,学名回溯算法,基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。

下面解法的思路是,对给定的数的范围0 ≤ x < 10^n,我们先区间内求1打头的,接着求2打头的.....到9打头的符合规则的数的数量,1打头里面

我们分别求11,12,13....19打头的,如此递归,设置一个boolean数组管理哪个数字为应该规避的,应该规避的数字设为true

public int countNumbersWithUniqueDigits(int n) {

  if (n > 10) {
    return countNumbersWithUniqueDigits(10);
  }
  int count = 1; // x == 0
  long max = (long) Math.pow(10, n);

  boolean[] used = new boolean[10];

  for (int i = 1; i < 10; i++) {

    used[i] = true;
    count += search(i, max, used);
    used[i] = false;
  }

  return count;

}

private static int search(long prev, long max, boolean[] used) {//查询prev打头的,范围为prev-max的个数

  int count = 0;//初始
  if (prev < max) {//递归出口
    count += 1;
  } else {
    return count;
}

/**

* 这段逻辑的意思是,假设prev = 1,i=2,这时used数组中used[1]为true,used[2]为true,curr =12,再接着去查询12打头,到max为止的个数
*/
for (int i = 0; i < 10; i++) {
  if (!used[i]) {
    used[i] = true;
    long cur = 10 * prev + i;
    count += search(cur, max, used);
    used[i] = false;
  }
}

  return count;

}

2,这种思路相对而言简单好理解一点,原理是把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的新方法

本题中我们可以发现,这样一个规律,我们用f(n)标示n位数的符合规则元素的个数,如f(2)标识10-99区间的数目

会发现f(n)符合这样的一个规律,f(n) = 9*9*8...(11-n),于是有如下代码

public int countNumbersWithUniqueDigits(int n) {

  if(n==0) return 1;
    int count = 10;
    int digit = 9;
  for(int i = 2;i<=n;i++){
    digit *= (11-i);
    count+=digit;
  }
  return count;
}

转载于:https://www.cnblogs.com/wujunjie/p/5687677.html

你可能感兴趣的文章
「Vue」nrm
查看>>
[汇编语言]-第五章段前缀及使用 一段安全的空间
查看>>
在Windows环境中利用Responder工具窃取NTLMv2哈希
查看>>
NOIP17提高模拟训练18 长途旅行(travel)
查看>>
字节输入流-InputStream demo5
查看>>
第四次面向对象博客_最后一次
查看>>
说下面试的技术点吧 [zhuan]
查看>>
tomcat 日志详解
查看>>
web storage的用法
查看>>
字符串操作
查看>>
蓝牙 简书
查看>>
SQL Server系统表sysobjects介绍与使用
查看>>
【转】C/C++除法实现方式及负数取模详解
查看>>
传输层协议
查看>>
Struts2 拦截器处理普通Http请求和Ajax请求时拦截配置
查看>>
例题---
查看>>
平安度过2012,新的一年新的希望
查看>>
MySQL prompt命令
查看>>
hbase读取文件
查看>>
2周《机电传动控制》学习笔记
查看>>