从1到n整数中1出现的次数（Java）
题目
给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。
示例:
输入: 13
输出: 6
解释: 数字 1 出现在以下数字中: 1, 10, 11, 12, 13 。public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
if(n <= 0){
return 0;
}
if(n < 10){
return 1;
}
String str = String.valueOf(n);
int len = str.length();
int first = str.charAt(0)-'0';
String after = str.substring(1,len);
int firstCount = 0;
int SecondCount = 0;
int third = 0;
if(first== 1){
firstCount = Integer.valueOf(after)+1;
}else{
firstCount = (int) Math.pow(10,len-1);
}
SecondCount = (int) ((first)*(len-1)*Math.pow(10,len-2));
third = NumberOf1Between1AndN_Solution(Integer.valueOf(after));
return firstCount+SecondCount+third;
}
}
思考一
注：（这里的 X∈[1,9] ，因为 X=0 不符合下列规律，需要单独计算）。
首先要知道以下的规律：
从 1 至 10，在它们的个位数中，任意的 X 都出现了 1 次。
从 1 至 100，在它们的十位数中，任意的 X 都出现了 10 次。
从 1 至 1000，在它们的百位数中，任意的 X 都出现了 100 次。
依此类推，从 1 至 10^ i ，在它们的左数第二位（右数第 i 位）中，任意的 X 都出现了 10^(i-1) 次。
以21354为例，寻找1出现的次数：
个位：从1至21350中包含了2135个10，因此1出现了2135次，21351，21352，21353，21354其中21351包含了一个1，故个位出现1的次数为：2135*10(1-1) + 1 = 2136次；
公式：( 2135+1）* 10^(1-1) = 2136；
十位：从1到21300中包含了213个100，因此1出现了213 * 10^(2-1) = 2130次，剩下的数字是21301到21354，它们的十位数字是5 > 1；因此它会包含10个1；故总数为2130 + 10 = 2140次；
公式：（213 + 1）* 10^(2-1) = 2140次；
百位：从1到21000中包含了21个1000，因此1出现了21 * 10^(3-1) = 2100次，剩下的数字是21001到21354，它们的百位数字是3 > 1；因此它会包含100个1；故总数为2100 + 100 = 2200次；
公式：（21 + 1）* 10^(3-1) = 2200次；
千位：从1到20000中包含了2个10000，因此1出现了2 * 10^(4-1) = 2000次，剩下的数字是20001到21354，它们的千位数字是1 = 1；情况稍微复杂些，354 + 1 = 355；故1的总数为2000 + 355 = 2355次；
公式：2 * 10^(4-1) + 354 + 1 = 2355次；
万位：万位是2 > 1，没有更高位；因此1出现的次数是1 * 10^(5-1) = 10000次；
公式：（0 + 1）*10^(5-1) = 10000次；
故总共为：2136+2140+2200+2355+10000=18831次；
故总结：
1、取第 i 位左边的数字（高位），乘以 10 ^(i−1) ，得到基础值 a 。
2、取第 i 位数字，计算修正值：
1、如果大于 X，则结果为 a+ 10 ^(i−1) 。
2、如果小于 X，则结果为 a 。
3、如果等 X，则取第 i 位右边（低位）数字，设为 b ，最后结果为 a+b+1 。
代码一
public class Main1 {
public int numberOf1Between1AndN(int n, int x){
if(n < 0 || x < 1 || x > 9){
return 0;
}
int curr, low, temp, high = n, i = 1, total = 0;
while(high!=0){
high = n / (int)Math.pow(10, i); //获取第i位的高位
temp = n % (int)Math.pow(10, i); //
curr = temp / (int)Math.pow(10, i-1); //获取第i位
low = temp%(int)Math.pow(10, i-1); //获取第i位的低位
if(curr == x){ //等于x
total += high*(int)Math.pow(10, i-1)+ low + 1;
}else if(curr < x){ //小于x
total += high*(int) Math.pow(10, i-1);
}else{ //大于x
total += (high + 1) * (int)Math.pow(10, i-1);
}
i++;
}
return total;
}
public static void main(String[] args) {
Main1 m1 = new Main1();
int nums = m1.numberOf1Between1AndN(21354, 1);
System.out.println(nums);
}
}思考2
解法一 找规律
- 第一步，最高位带来的1的个数。
- 第二步，非最高位带来的1的个数
- 第三步，第一段数字带来的1的个数
以2123为例。
将2123转成字符串s=”2123″。方便处理。
为了便于统计1的个数，将1到2123分成几段。
第一段：1~123
第二段：1000~1999
第三段：2000~2123 x124~x999。其中x124~x999就是原先124~999，将其移动2123之后的。
第一步，最高位带来的1的个数。
这对应上面的第二段数字。
s[0]=2 > 1。此时一定含有最高位是1的数。
最高位是1的数有：1000~1999，共1000个。
这段数据形如1xxx。
数字总个数与最高位之后的数位个数有关。共3个数位，每个数位可放0-9。
总个数 = 10^( 最高位之后的数位个数 ) = 10 ^ 3=1000
但是，当最高位刚好是1时，步能这么算。例如1123.
此时，总个数 = 去掉最高位剩余的数字+1
对于1123，总个数 = 123+1=124
第二步，非最高位带来的1的个数
这对应上面的第三段数字。 2000~2123 x124~x999
不考虑最高位，这段数字形如:Y000~Y999。
非最高位共有三个数位。每个数位都可放1。会得到多少1了？
Y100~Y199，共10^2=100个。
Y010~Y919，共10^2=100个。
Y001~Y991，共10^2=100个。
总个数 = 非最高数位个数 * 10 ^ ( 非最高数位个数 – 1)
第三步，第一段数字带来的1的个数
1~123总共有多少个1？
这个跟1~2123总共有多少个1，没有任何区别。因此，可以递归解决。
综上
count(s,i){
if(i>=s.length) 返回0;
ans=0;
//第一步
if(s[i] == 1){
sub=s[i+1:];
if(sub不空) ans += sub转数字;
ans += 1;
}else if(s[i] > 1){
非最高位数位个数 = s.length-i-1;
ans += 10 ^ 非最高位数位个数;
}
//第二步
非最高位数位个数 = s.length-i-1;
ans += 非最高位数位个数 * 10 ^ (非最高位数位个数-1);
//第三步
ans += count(s,i+1);
返回ans;
}
代码2
public int numberOf1Between1AndN(int n){
if(n<=0) {
return 0;
}
String strNumber = String.valueOf(n);
//将数字转换成字符串
int length = strNumber.length();
int firstDigit = strNumber.charAt(0) - '0';
//将字符串转换成数字,Returns the char value at the specified index.
//只有个位
if(length == 1 && firstDigit == 0) {
return 0;
}
if(length ==1 && firstDigit > 0) {
return 1;
}
//除首位外，剩下的数字
String remainedString = strNumber.substring(1);
//从1开始到最后的位置，返回一个子字符串；substring(int beginIndex);
// Returns a new string that is a substring of this string.
int remainedNumber = Integer.parseInt(remainedString);
//字符串转换成十进制数字，parseInt(String s),
// Parses解析 the string argument as a signed decimal integer.
//1出现在首位的次数
int countOfFirstDigit;
if(firstDigit == 1){
//如果首位数字等于1，比如从10000~12345，则最高位出现1的次数为2345+1=2346次，
countOfFirstDigit = remainedNumber +1;
//（2）是把除高位外的字符串转化为整数。10000~12345中最高位出现1个次
// 数为除去最高数字滞后于剩下的数字再加1.
} else{
//（1）1345~21345中，万位上出现1的数字在10000~19999中，有10^4个。
// 如果n的长度为length，则共有10^(length-1)次。
countOfFirstDigit = (int)Math.pow(10,length-1);
}
//(length-1):任选一位为1；10^(length0-2):其余位从0-9中选；
//firstDigit：首位可选的数字
//除了第一位的数之外，其他位上有1的次数：再把1346~21345分成2段，1346~11346,11236~21346，
//每一段中除去其中的一个数为1之外，其他的每位均可以取0~9，所以有2*10^3次。即共有first*10^(length-2)次
int countOfOtherDigit = firstDigit *(length -1)*(int)Math.pow(10, length-2);
// 递归求在剩下数字中1出现的次数
int remainedCount = numberOf1Between1AndN(remainedNumber);
int result = countOfFirstDigit + countOfOtherDigit + remainedCount;
return result;
}
京公网安备 11010502036488号