java基础题

Question

  对于一个整数n，有一个函数f（n） 可以计算到0到n之间的出现“1“的个数。
  例如：f（1） = 1，f（13） = 6，
  因为 1,2,3,4,5,6,7,8,9,10,11,12,13 数数1的个数正好是6。
 实现这个函数 int f（int n） 
 只能用递归解答！
请高手指点一下！

Answer 1

public static int test(int i) {
if (1 == i) {
return 1;
}
return (String.valueOf(i).indexOf("1") == -1 ? 0 : 1) + test(i - 1);
} public static void main(String[] args) {
System.out.println("包含1个数: " + test(13));
}

Answer 2

import java.util.Scanner;public class OneCount { public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
System.out.println(count(n));
} private static int count(int n) { if (0 >= n) {
return 0;
} else {
return count(n-1) + getOneCount(n);
}
} private static int getOneCount(int n) { int count = 0;
String str = String.valueOf(n);
for (int i = 0; i < str.length(); i++) {
if('1' == str.charAt(i))
count++;
}
return count;
}}
13:是6个

Answer 3

貌似是 6 ，11算2个1吗？
public static int f(int i) {
        if (i == 1) {
            return 1;
        }
        else{
            int data = String.valueOf(i).repalceAll("[^1]","").length();
            return data + test(i-1);
        }
       
    }    public static void main(String[] args){
        System.out.println(test(100));
    }

Answer 4

 System.out.println(f(100));
见笑了，代码都不改，copy惹的祸啊。

Answer 5

哦，对对，sorry，大意了，4楼 5楼的正解~

Answer 6

其实用递归才更简单，因为思路是递归的。你的写法自然是符合题意的，但是原题的意思我相信不是让你在n这个数值上递归（那样基本上就是把一个1到n的循环改成递归，没有意义的），题目的愿意更倾向于让你递归getOneCount这个方法来求解

Answer 7

用递归，效率太低了，这个有个规律的
#include <iostream>
using namespace std;int main()
{
int num = 121212,saveNum = 1,countNum = 0,lastNum=0,numCopy = num;
        while(num!=0)
       {
        lastNum = num%10;
  num/=10;
if(lastNum == 0){
  countNum +=(num)*saveNum;
}else if(lastNum == 1){
  countNum += num * saveNum + numCopy%(saveNum) + 1;
}else{
  countNum +=(num+1)*saveNum;
}
  saveNum*=10;
}
cout<<countNum<<endl;
return 0;
}
分析过程对于abcd这个数
公式：(abc+1)*1+(ab+1)*10+(a+1)*100+(1)*1000
依次类推。
对应：2234
(223+1)*1+(22+1)*10+(2+1)*100+(1)*1000
=224+230+300+1000
=1754
编程思路：
按照个位、十位、百位、千位……计算首先个位：例如88在下面表中可以看到，
  88一直竖着向上 会有8+1个1（8来自十位上的数，8 7 6 ... ...）
    
之后十位：十位上，要看88 这个数没有百位。因为没有百位。
  所以是（0+1）*10
88验证
 (8+1)*1 + 1*10
=19
*******************
295验证
 (29+1)*1 + (2+1)*10 + (1)*100
=30+30+100
=160
*******************
对于位数有1的得特殊处理例如121
当用上面方法检测到1的时候
那么看1后面的数 21 这说明有21一个1是百位的
其他的仍然是循环上面的方法0 1 特殊处理 代码中体现了

Answer 8

public class CountOnes {

private static int getCount(int number) {
if ((number !=0 ) && ((number % 10) == 1))  {
return (getCount(number / 10) + 1);
} else if ((number !=0 ) && ((number % 10) != 1)) {
return getCount(number / 10);
} else {
return 0;
}
}

private static int calcCountNumber(int number) {
int result = 0;
for (int i = 0; i < (number + 1); i++) {
result += getCount(i);
}
return result;
}

public static void main(String [] args) {
System.out.println(calcCountNumber(13));
}
}
这样可以么

Answer 9

尝试写了一下，利用递归思考的方式。时间复杂度O(N^2)，其中N=log(n)（准确的说是n对10取对数，也即n这个数用十进制表示的长度）
比不上9楼朋友的公式，但是比“遍历所有数逐个数1的个数”要好一些
同时因为递归的原因，引入O(N)的空间复杂度private static int oneCount(int n) {
     if (n == 0) return 0;
    
     int base = 1;
     while (base * 10 <= n)
     base = base * 10;
     int msb = n / base, tail = n - base * msb;
    
     return oneCount(base - 1) * msb + oneCount(tail) +
     (msb == 1 ? (tail + 1) : base);
    }

Answer 10

public class Test {    /**
     * @param args
     */
public static void main(String []args)
{
int a=CountNumber(13);
System.out.println(a);
}
public static int CountNumber(int OverNumber)
{
int CountNumber=0;
for(int i=1;i<=OverNumber;i++)
{
String a=i+" ";
if(a.indexOf("1")==-1)
{
continue;
}
else
{
CountNumber++;
continue;
}
}
return CountNumber;
}
   
   
    }

Answer 11

static int f(int n)
{
String s = null;
for (int i = 1; i <= n; i++)
{
s += i;
}
Pattern p = Pattern.compile("1");
Matcher m = p.matcher(s);
int result = 0;
while (m.find())
result++; return result;
}
正则做的...

Answer 12

static int f(int n)
{
Pattern p = Pattern.compile("1");
int result = 0;
for (int i = 1; i <= n; i++)
{
Matcher m = p.matcher("" + i);
while (m.find())
result++;
}
return result;
}
好像这样更好些...

Answer 13

public class test{
public static int text(int i) {
        if (1 == i) {
            return 1;
        }
        if(String.valueOf(i).indexOf("1") == -1) 
         return 0+text(i - 1); //判断i中的是否含有1，没有的话就返回0，然后计算下一个数字
        if(!(String.valueOf(i).indexOf("1") == -1))
            {
         char temp[]=String.valueOf(i).toCharArray();//如果数字中含有1，将数字分割成一个字符数组
         int m=0;
         for(int k=0;k<temp.length;k++) //判断计算数组中字符'1'的个数m
         {if(temp[k]=='1'){
         m=m+1;
         }
         }
         return m+text(i - 1);
            }
        return 0+text(i - 1);
    }    public static void main(String[] args) {
        System.out.println("包含1个数: " + text(13));
    }
}

Answer 14

    public static int func(int param){
        
        int i = 0;
        int count = 0;
        do{
            i++;
            String num = Integer.toString(i);
            for(char ch : num.toCharArray()){
                if(ch == '1'){
                    count++;
                }
            }
        }while(i < param);
        
        return count;
    }