剑指Offer:面试题32:从1到n整数中1出现的次数

xiaoxiao2021-02-28  8

题目: 输入一个整数n,求从1到n这n个整数的十进制表示中1出现的次数。 例如输入12,这些整数中包含1的数字有1,10,11,12,1一共出现了5次。 解题思路: 解法二告诉我们1~N中"1"的个数跟最高位有关,那我们换个角度思考,给定一个N,我们分析1-N中的数在每一位上出现1的次数的和,看看每一位上"1"出现的个数的和由什么决定。

import java.util.Scanner; public class Solution { public static void main(String[] args) { Scanner input=new Scanner(System.in); int number =input.nextInt(); int result=new Solution().NumberOf1Between1AndN_Solution(number); System.out.println(result); } public int NumberOf1Between1AndN_Solution(int n){ int judge=1; //判断从1到n judge的个数 int count=0; int i=1; long current; //当前位 long before; //所有高位 long after; //低一位 while((n/i)!=0){ current=(n/i); before=n/(i*10); after=n-(n/i)*i; if (current>judge) //如果当前位大于1 则当前位的1共有(before+1)*i个 count+=(before+1)*i; else if (current==judge) //如果当前位等于1 则当前位有before*i个 + (after+1)个 count+=(before*i+after+1); else //如果当前位小于1 则当前位有before*i个 count+=before*i; i=i*10; } return count; } }

举例: 当i=10时;当前为分为>1=1<1三种情况 1)2345 当前位为4; 高位为234 低位为5; 此时10位包含[0-4][5-14][15-24]....[215-224][225-234]共24段每一段的当前位包含1个1,考虑到当前是在10位[231]对应的是[2310~2319]10个数,所以当前十位包含24*10个1; 2)2315 当前位为1; 高位为234 低位为5; 此时相对于大于1的情况[2310-2315]共包含16个1,其他23段的十位1均对应10个个位数,所以一共是23*10+16个1; 3)2305 相对于2345的情况,[0-4]的最小段消失了所以只剩[0-10][11-20]...[221-230]共计23段,所以一共是23*10个1;

转载请注明原文地址: https://www.6miu.com/read-200209.html

最新回复(0)