薯队长在平时工作中需要经常跟数字打交道，某一天薯队长收到了一个满是数字的表格，薯队长注意到这些数字里边很多数字都包含1，比如101里边包含两个1，616里包含一个1。
请你设计一个程序帮薯队长计算任意一个正整数n(0<n<=2147483647)，从1到n（包括n）的所有整数数字里含有多少个1。
[编程题]好奇的薯队长
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.next();
int n = Integer.parseInt(str);
sc.close();
long count = 0;
int a = str.length();
int m = n;
for (int j = 0; j < a; j++) {
long p=(long) Math.pow(10,j);
int b=m%10;
m=m/10;
if(b==0) {
count=count+m*p;
}else if(b==1){
count=count+m*p+n%p+1;
}else if (b>1) {
count=count+(m+1)*p;
}
}
System.out.println(count);
}
}
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.next();
int n = Integer.parseInt(str);
sc.close();
long count = 0;
int a = str.length();
int m = n;
for (int j = 0; j < a; j++) {
long p=(long) Math.pow(10,j);
int b=m%10;
m=m/10;
if(b==0) {
count=count+m*p;
}else if(b==1){
count=count+m*p+n%p+1;
}else if (b>1) {
count=count+(m+1)*p;
}
}
System.out.println(count);
}
}
发表于 2019-05-10 15:04:52
回复(0)
def NumberOf1Between1AndN_Solution(n):
mult, sumTimes = 1, 0
while n//mult > 0:
high, mod = divmod(n, mult*10)
curNum, low = divmod(mod, mult)
if curNum > 1:
sumTimes += high*mult + mult
elif curNum == 1:
sumTimes += high*mult + low + 1
else:
sumTimes += high*mult
mult = mult*10
print(sumTimes)
if __name__ == '__main__':
n = int(input())
NumberOf1Between1AndN_Solution(n)
编辑于 2019-05-12 14:57:22
回复(2)
#include<iostream>
using namespace std;
int main()
{
long long res = 0,n;
long long left=0, right = 0, base = 1;
cin>>n;
if(n<=0) cout<<0<<endl;
else{
while (n>=base) {
left = n/base;
right = n%base;
if((left%10)>1) res+= (left/10+1)*base;
else if((left%10)==1) res+=(left/10)*base+(right+1);
else res+=(left/10)*base;
base *=10;
}
cout<<res<<endl;
}
return 0;
}
发表于 2019-05-17 11:48:11
回复(1)
#include <iostream>
using namespace std;
int main()
{
long long n;
cin>>n;
long long num_1;
long long tmp=n;
long long multi=1;
while(tmp>0)
{
int left=n%multi;
num_1+=(tmp/10)*multi;
if(tmp%10>1) num_1+=multi;
else if(tmp%10==1)num_1+=left+1;
multi*=10;
tmp=tmp/10;
}
cout<<num_1<<endl;
return 0;
}
发表于 2020-12-17 20:13:35
回复(0)
提供一个另类思路：从左到右依次统计每个数位上为1时可以组成的不超过n的数字个数。
n = input() m = len(n) def turn(s): if s: return int(s) return 0 ans = 0 for i in range(m): if n[i] > '1': ans += (turn(n[:i]) + 1) * 10 **(m-i-1) elif n[i] == '1': ans += (turn(n[i+1:]) + 1) + turn(n[:i]) * 10 ** (m-i-1) else: ans += turn(n[:i]) * 10 ** (m-i-1) print(ans)
发表于 2020-05-30 23:28:26
回复(0)
importjava.util.Scanner;
publicclassMain {
publicstaticvoidmain(String[] args) {
Scanner sc =newScanner(System.in);
intn = sc.nextInt();
System.out.println(count1(n));
}
publicstaticintcount1(intn) {
intnum=0;
for(inti=1;i<=n;i++) {
if(i%10==1) {
num++;
}
inta =i;
while(a>=10) {
a=a/10;
if(a%10==1) {
num++;
}
}
}
returnnum;
}
}
运行时间为2S，超时
发表于 2019-09-27 00:58:32
回复(0)
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
System.out.println("n：");
int n = sc.nextInt();
int ret1 = returnOf(n);
if(ret1 != -1){
System.out .println(ret1);
}
}
public static int returnOf (int n){
int ret = 0;
if(n <= 0 || n >2147483647 ){
System.out.println("输入超出范围，重新输入！");
ret = -1;
return ret;
}
for(int i = 1; i <= n;i++){
String newn = String.valueOf(i);
int L=newn.length();
for(int j = 0;j < L;j++){
int digit = newn.charAt(j)-'0';
if(digit == 1){
ret++;
}
}
}
return ret;
}
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
System.out.println("n：");
int n = sc.nextInt();
int ret1 = returnOf(n);
if(ret1 != -1){
System.out .println(ret1);
}
}
public static int returnOf (int n){
int ret = 0;
if(n <= 0 || n >2147483647 ){
System.out.println("输入超出范围，重新输入！");
ret = -1;
return ret;
}
for(int i = 1; i <= n;i++){
String newn = String.valueOf(i);
int L=newn.length();
for(int j = 0;j < L;j++){
int digit = newn.charAt(j)-'0';
if(digit == 1){
ret++;
}
}
}
return ret;
}
}
求大神解答，哪里出错了，编译不过
发表于 2019-05-23 15:50:19
回复(0)
package com.shenyue.beedi.controller; import java.util.Scanner; public class Test { public static void main(String[] args) { System.out.println("请输入一个数字"); Scanner in = new Scanner(System.in); int num = in.nextInt(); int count = 0; for(int i=1;i<=num;i++){ String s = Integer.toString(i); String[] numArr = s.split(""); for (String s1 : numArr) { if(s1.equals("1")){ count++; } } } System.out.println(count); in.close(); } }
发表于 2019-05-15 16:06:36
回复(0)
//左神书中原题，时间复杂度O(logN*logN)
#include <cmath>
#include <iostream>
using namespace std;
int getlength(int num){
int len=0;
while (num>0){
++len;
num/=10;
}
return len;
}
long getCount(int num){
if (num<1) return 0;
int len=getlength(num);
if (len==1) return 1;
long tmp=pow(10,len-1);
int first=num/tmp;
int fcount= first==1? num%tmp+1 : tmp;
long othercount=first*(len-1)*(tmp/10);
return fcount+othercount+getCount(num%tmp);
}
int main(){
int num;
long ans;
cin>>num;
ans=getCount(num);
cout<<ans<<endl;
return 0;
}
发表于 2019-05-09 09:38:52
回复(2)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
