例如， 1~13 中包含 1 的数字有 1 、 10 、 11 、 12 、 13 因此共出现 6 次
注意：11 这种情况算两次
数据范围： 
进阶：空间复杂度 %20%5C)
，时间复杂度 %20%5C)
[编程题]整数中1出现的次数（从1到n整数中1出现的次数）
咩咩jiang
class Solution {
public:
int NumberOf1Between1AndN_Solution(int n)
{
//主要思路：设定整数点（如1、10、100等等）作为位置点i（对应n的各位、十位、百位等等），分别对每个数位上有多少包含1的点进行分析
//根据设定的整数位置，对n进行分割，分为两部分，高位n/i，低位n%i
//当i表示百位，且百位对应的数>=2,如n=31456,i=100，则a=314,b=56，此时百位为1的次数有a/10+1=32（最高两位0~31），每一次都包含100个连续的点，即共有(a%10+1)*100个点的百位为1
//当i表示百位，且百位对应的数为1，如n=31156,i=100，则a=311,b=56，此时百位对应的就是1，则共有a%10(最高两位0-30)次是包含100个连续点，当最高两位为31（即a=311），本次只对应局部点00~56，共b+1次，所有点加起来共有（a%10*100）+(b+1)，这些点百位对应为1
//当i表示百位，且百位对应的数为0,如n=31056,i=100，则a=310,b=56，此时百位为1的次数有a/10=31（最高两位0~30）
//综合以上三种情况，当百位对应0或>=2时，有(a+8)/10次包含所有100个点，还有当百位为1(a%10==1)，需要增加局部点b+1
//之所以补8，是因为当百位为0，则a/10==(a+8)/10，当百位>=2，补8会产生进位位，效果等同于(a/10+1)
int count=0;
long long i=1;
for(i=1;i<=n;i*=10)
{
//i表示当前分析的是哪一个数位
int a = n/i,b = n%i;
count=count+(a+8)/10*i+(a%10==1)*(b+1);
}
return count;
}
};
编辑于 2015-08-18 23:21:43
回复(86)
import java.util.*;
public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
int exp=1;//当前位
int res=0;
while(exp<=n){
//举例：计算百位上1的个数，如果百位大于2，100-199百位上共一百个1，
//000-099和200-999中，百位都没有1，1100-1199，百位上有100个1，
//每增加1000,会产生100个百位上的1，得到(n/(exp*10))*exp
//当前位大于2时直接加100（即加exp）,等于1时取余+1(例如135，100-135在百位共有36个1)，
//小于1即为0，不用额外加
if(n%(exp*10)>=2*exp){//当前位大于2时，当前位取1的个数
res=res+(n/(exp*10))*exp+exp;
}else if(n%(exp*10)>=1*exp){//当前位为1时，取1的个数
res=res+(n/(exp*10))*exp+(n%exp)+1;
}else{//当前位取零时1的个数
res=res+(n/(exp*10))*exp;
}
exp*=10;
}
return res;
}
}
发表于 2023-07-08 14:09:51
回复(0)
人家说可以用数位dp做，俺也不懂，反正就是假设某位是1，剩余的位有多少种组合，B站视频连接
public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
int a = 0,temp = n;
int high =0,low = 0,count = 0;
int[] bit = new int[6];
while(temp != 0){
bit[a++] = temp % 10;
temp /= 10;
}
for(int i = 1; i <= a;i++){
high = n / (int)Math.pow(10,i);
low = n % (int)Math.pow(10,i-1);
count =count + high * (int)Math.pow(10,i-1);
if(bit[i-1] > 1){
count += 1*(int)Math.pow(10,i-1);
}
if(bit[i-1] == 1)
count += low + 1;
}
return count;
}
}
发表于 2022-06-16 16:58:22
回复(0)
为什么需要这么那么麻烦呢？是我想错了吗？
import java.util.*;
public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
int res = 0;
for(int i = 1; i <= n; i++) {
String str = String.valueOf(i);
int l = str.length() - str.replaceAll("1","").length();
res+=l;
}
return res;
}
}
发表于 2022-05-15 20:05:03
回复(0)
咱不会那么多花哨的数学技巧；
咱也看不懂那些高赞的牛掰回答；
咱只会暴力求解，因为咱本来就是粗人一个；
温柔的活说不来，但总能给你一个答复；
即便它不是最好的，但至少也有一个给你。
你说，这样不好么
public static int NumberOf1Between1AndN_Solution(int n) {
int cnt = 0, oldLen, newLen;
String number;
for (int i = 0; i <= n; i++) {
number = String.valueOf(i);
if (!number.contains("1")) {
// 但凡能让我节省一点点的时间
continue;
}
oldLen = number.length();
newLen = number.replace("1", "").length();
cnt += (oldLen - newLen);
}
return cnt;
// 超过1.49% 用Java提交的代码
}
发表于 2022-03-31 21:20:39
回复(1)
思路：一个数减1模上10如果是0的话说明它个位数是1，然后再除以10再减1模10这么判断有多少位为1，结束循环的条件是这个数一直除到变成0
public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
int oneTimes = 0;
for (int i = 1; i < n + 1; i++) {
int num = i;
while (num > 0) {
if ((num - 1) % 10 == 0)
oneTimes++;
num = num / 10;
}
}
return oneTimes;
}
}
发表于 2022-03-14 16:52:28
回复(0)
数学不好，于是用了最狗的方法。。。。。。。
转换为字符数组挨个对比（菜鸡的挣扎）
public class Solution2 {
public int compute(int n) {
// 定义一个计数器
int num = 0;
// 给定数值挨个循环
for (int i = 1; i <= n; i++) {
// 转换成字符数组，（i+""）是为了将其转换为字符串
char[] charArray = (i + "").toCharArray();
// 一个一个地找字符'1'
for (char c : charArray) {
if (c=='1') {
num++;
}
}
}
return num;
}
public static void main(String[] args) {
Solution2 s = new Solution2();
System.out.println(s.compute(13));
}
}
数学是硬伤啊。。。。。。。。
编辑于 2022-03-08 17:25:37
回复(0)
import java.lang.Math;
public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
String s = String.valueOf(n);
int cur = 0;
long digit,high,low;
int res = 0;
while(cur<s.length()){
char c = s.charAt(cur);
digit = (long)Math.pow(10.0,s.length()-cur-1);
high = n/(digit*10);
if(c=='0'){
res += digit*high;
} else if(c=='1'){
low = cur==s.length()-1?0:
Integer.parseInt(s.substring(cur+1,s.length()));
res += digit*high+low+1;
} else {
res += (high+1)*digit;
}
cur++;
}
return res;
}
}
发表于 2022-02-22 15:23:57
回复(0)
// 来自大神路飞的思路
public int NumberOf1Between1AndN_Solution(int n) {
int bit = 1, cnt = 0, low = 0, high = n / 10, cur = n % 10;
while (high != 0 || cur != 0) {
if (cur == 0) cnt += high * bit;
else if (cur == 1) cnt += high * bit + low + 1;
else cnt += (high+1) * bit;
low += cur * bit;
cur = high % 10;
high /= 10;
bit *= 10;
}
return cnt;
}
发表于 2022-02-17 12:52:13
回复(0)
解法1：暴力
public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
// 解法1：暴力
int count=0;
while(n > 0){
int k=n;
while(k>0){
// 看看个位是不是1
if(k%10==1)
count++;
// 右移一位
k/=10;
}
n--;
}
return count;
}
} 解法2：行李箱密码锁
public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
// 解法2：找规律（行李箱密码锁）
// 逐一计算每位数字为1的组合数目，将和相加，像转轮密码锁一样
// 比如一个3位数xxx，分别计算1xx,x1x和xx1的可能性
// 对于每一位又分3种可能，详见题解
int high = n/10;
int cur = n%10;
int low = 0;
int factor = 1;
int count=0;
while( high!=0 || cur!=0){
// 当前位==0
if(cur==0)
count += (high * factor);
// 当前位==1
else if(cur==1)
count += (high * factor+low+1);
// 当前位在2~9之间
else
count += ((high+1) * factor);
// 更新区域和指针
low += cur*factor;
factor *=10;
cur = high%10;
high /= 10;
}
return count;
}
}
发表于 2022-01-26 22:05:59
回复(0)
public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
int res=0;
for (int i = 0; i < n+1; i++) {
char[] chars = String.valueOf(i).toCharArray();
for (int j = 0; j < chars.length; j++) {
if (chars[j]=='1'){
res++;
}
}
}
return res;
}
public int NumberOf1Between1AndN_Solution(int n) {
int res=0;
for (int i = 0; i < n+1; i++) {
char[] chars = String.valueOf(i).toCharArray();
for (int j = 0; j < chars.length; j++) {
if (chars[j]=='1'){
res++;
}
}
}
return res;
}
}
//算不算投机取巧
发表于 2022-01-05 17:41:33
回复(0)
public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
if (n == 0)
return 0;
String inputStr = String.valueOf(n);
int len = inputStr.length();
int[] arr = new int[5];
int res = 0;
for (int i = 1; i <= n;i++){
// 除100模10得到百位，。。。。
String tempStr = String.valueOf(i);
int tempLen = tempStr.length();
for (int j = 0; j < tempLen; j++){
int a = (int)Math.pow(10,j);
arr[j] = (i / a) % 10;
}
for (int k = 0; k < arr.length; k++){
if (arr[k] == 1){
res++;
}
}
}
return res;
}
}
发表于 2021-12-16 10:48:23
回复(0)
public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
int result = 0;
int high = n / 10, cur = n % 10, base = 1, low = 0;
// 从低位到高位，累加每一位为1的数的个数
while (high != 0 || cur != 0) {
if (cur == 0) {
result += high * base;
} else if (cur == 1) {
result += high * base + low + 1;
} else {
result += high * base + base;
}
low = cur * base + low;
cur = high % 10;
high = high / 10;
base = base * 10;
}
return result;
}
}
发表于 2021-09-18 11:26:30
回复(0)
把每个数转成字符串，再遍历字符串，简单易懂
public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
int count=0;
for (int i = 0; i <= n; i++) {
String s = Integer.toString(i);
char[] chars = s.toCharArray();
for (char aChar : chars) {
if(aChar=='1'){
count++;
}
}
}
return count;
}
}
发表于 2021-09-07 08:59:02
回复(0)
/*
思路：
固定每一个位为1，然后看其它位一共有多少情况。
与字符串的全排列类似，但是这不是用的递归
(a+8)/10*i这个等价，很关键。（+8，等价）
举例：31456
固定百位为1
a=n/100,b=n%100
1.百位>=2，左边0~31，为32个。即为a/10+1。右边0~99，100个
所以一共(a/10+1)*i个。
2.百位=1
3.百位=0
可把分类1,2,3的前面等价为(a+8)/10.
思路：
固定每一个位为1，然后看其它位一共有多少情况。
与字符串的全排列类似，但是这不是用的递归
(a+8)/10*i这个等价，很关键。（+8，等价）
举例：31456
固定百位为1
a=n/100,b=n%100
1.百位>=2，左边0~31，为32个。即为a/10+1。右边0~99，100个
所以一共(a/10+1)*i个。
2.百位=1
3.百位=0
可把分类1,2,3的前面等价为(a+8)/10.
分类2，当a%10==1时，再加上(b+1)。
代码写完，直接抄就行，要不容易出错。
*/
/*
思路：
固定每一个位为1，然后看其它位一共有多少情况。
与字符串的全排列类似，但是这不是用的递归
(a+8)/10*i这个等价，很关键。（+8，等价）
举例：31456
固定百位为1
a=n/100,b=n%100
1.百位>=2，左边0~31，为32个。即为a/10+1。右边0~99，100个
所以一共(a/10+1)*i个。
2.百位=1
3.百位=0
可把分类1,2,3的前面等价为(a+8)/10.
分类2，当a%10==1时，再加上(b+1)。
*/
public int NumberOf1Between1AndN_Solution(int n) {
int sum = 0;
//当i=10时固定十位为1，当i=1时固定个位为1
//自己举个例子，当i=1时没错
for(long i = 1;i <= n;i *= 10){
long a = n/i,b = n%i;
sum += (a+8)/10*i;
if(a%10==1) sum += (b+1);
}
return sum;
}
发表于 2021-08-26 20:18:30
回复(0)
public int NumberOf1Between1AndN_Solution(int n) {
//一个10有1个1，一个100有10个1，一个1000有100个1……一个1*10^n有1*10^(n-1)个1
//2147483648
//1000000000,九个0
if(n==0) return 0;
int sum=0;
for(int i=1;i<10;i++){
double temp=Math.pow(10,i);
int tens=new Double(temp).intValue();
int res=n/tens;
//看余数是否>十分之一
int res1=n%tens;
if(res1>=tens/5-1) sum+=tens/10;
else if(res1<tens/10) sum+=0;
else{
sum+=res1-tens/10+1;
}
sum+=res*(tens/10);
if(res==0){
break;
}
}
return sum;
}
//一个10有1个1，一个100有10个1，一个1000有100个1……一个1*10^n有1*10^(n-1)个1
//2147483648
//1000000000,九个0
if(n==0) return 0;
int sum=0;
for(int i=1;i<10;i++){
double temp=Math.pow(10,i);
int tens=new Double(temp).intValue();
int res=n/tens;
//看余数是否>十分之一
int res1=n%tens;
if(res1>=tens/5-1) sum+=tens/10;
else if(res1<tens/10) sum+=0;
else{
sum+=res1-tens/10+1;
}
sum+=res*(tens/10);
if(res==0){
break;
}
}
return sum;
}
发表于 2021-08-23 20:44:39
回复(0)
问题信息
通过挑战的用户
查看代码-
2023-02-27 12:46:35
-
2023-02-05 18:55:56 -
2022-12-25 13:20:30 -
2022-12-03 14:41:56
-
2022-10-09 21:53:31
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
