本文主要是介绍从1到n整数中1出现的次数（Java），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。例如输入12，从1到12这些整数中包含1的数字有1， 10, 11和12；1一共出现了5次。
第一思路：
利用for循环累加从1到n中每个整数出现1的次数。判断每个整数是否出现1，利用对整数每次对10求余，判断整数的个位数字是不是1。如果这个数字大于10，除以10之后再判断个位数字是不是1。
代码实现：
/*** 求1到n中的每个整数中1出现的总共有多少次*/
public static int numberOf1Between1AndN(int n){if(n<0){ return 0;}int count = 0;for (int i = 1; i <= n; i++) {count += numberOf1(i);}return count;
}/*** 求每个整数中1出现的次数* @param n* @return*/
private static int numberOf1(int n) {int count = 0;while(n>0){if(n % 10 == 1){++count;}n = n / 10;}return count;
}最优思路：从数字规律着手，提高时间效率
1：如果第i位（从低位向高位开始）上的数字是0，那么第i位可能出现1的次数仅由更高位决定（如果没有高位，则视高位为0），等于更高位数字*当前位数的权重10^(i-1)；
2：如果第i位上的数字为1，则第i位上可能出现1的次数不仅受更高位影响还受低位影响（如果没有低位，则视低位为0），等于更高位数字*当前位数的权重10^(i-1) + (低位数字+1)；
3：如果第i位上的数字大于1，则第i位上可能出现1的次数仅由更高位决定（如果没有高位，则视高位为0），等于（更高位数字+1）*当前位数的权重10^(i-1)。
注：（这里的 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){ //等于xtotal += high*(int)Math.pow(10, i-1)+ low + 1;}else if(curr < x){ //小于xtotal += high*(int) Math.pow(10, i-1);}else{ //大于xtotal += (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);}
}
小结：优中选优是拿下offer的王道。
这篇关于从1到n整数中1出现的次数（Java）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
