算法讨论~

Question

题目是C++版块上的,我想用java实现:
http://topic.csdn.net/u/20081102/11/1c6136bb-ad44-49e1-868b-d848816456f6.html最笨的算法(计算111111111需要78秒....):package cn.array;/**
 * 计算enterNum之前正数所有1的个数，比如：1->1;10->2;11->4;12->5.......
 * @author liaoyi
 * @version 1.0.0
 * @2008-11-3 下午03:22:10
 */
public class HasOne {

public static void main(String args[]) {
System.out.println(new HasOne().f(111111111));
}

public int f(int enterNum){
int oneNum = 1;
for(int i=enterNum;i>1;i--){
String strNum = new Integer(i).toString();
for(int j = 0;j<strNum.length();j++){
if(strNum.substring(j, j+1).equals("1"))
oneNum++;
}
}
return oneNum;
}}
大家讨论一下~

Answer 1

没找到规律，我也只知道楼主的办法
等高人ing。。

Answer 2

你完全可以用字符串替换来做啊，看看我的这篇blog  有些是可以借鉴的 http://blog.csdn.net/justinavril/archive/2008/10/19/3105566.aspx就是把他们连接成一个字符串  然后把字符串1全部替换掉  然后看字符串长度的差值

Answer 3

http://www.msra.cn/Articles/ArticleItem.aspx?Guid=8ae08db5-e059-44bf-9181-83d40a67dadb
编程之美上的题目

Answer 4

{
        int num[][]=new int[2][454193];
num[0][head]=1;
num[1][head]=1;
for(int i=11;i<=1111111;i++)
{
int k=has1(i);
if(k>0)
{
head++;
num[0][head]=num[0][head-1]+k;
num[1][head]=i;
}
}
int i;
for(i=0;i<=head;i++)
if(num[1][i]>111111111)break;
cout<<num[0][i-1]<<endl;
}
int has1(int a)
{
int sum=0;
while(a/10)
{
if(a%10==1)sum++;
a=a/10;
}
return sum;
}

Answer 5

好像那年baidu的竞赛里也有这个题目

Answer 6

呵呵 借助前期的数学分析吧  
你一万多的电脑  大部分都是花在了显示器和显卡上面了  纯粹做浮点运算的机器的都是多CPU的

Answer 7

int x = 101;
int result = 0;
for( int i=10; i<=x*10; i=i*10) {
result += x/i*(i/10);//默认当前位数的值是0 
if (x%i/(i/10)==1) {//当前位数的值是1
result += x%(i/10)+1;
}else if(x%i/(i/10)>1) {//当前位数的值大于1
result += i/10;
}
}
System.out.println(result);
}[我的算法主要是从每一位的1出现次数考虑的：如101 1在个位出现的次数是101/10*1=10 当前位数的值（x%i/(i/10)==1）即个位是1所以 次数=10+1；同理求得十位和百位的值。这个我还没有验证过百位以上的不知道对不对，有不对的还请大家指正

Answer 8

int x =11111;
int result = 0;
int testresult = 0;
for( int i=10; i<=x*10; i=i*10) {
result += x/i*(i/10);//默认当前位数是0 
if (x%i/(i/10)==1) {//当前位数是1
result += x%(i/10)+1;
}else if(x%i/(i/10)>1) {//当前位数大于1
result += i/10;
}
}
for (int i=0; i<=x; i++) {
String s = i+"";
String s1 = s.replaceAll("1", "");
testresult +=s.length()-s1.length();
}
System.out.println(result);
System.out.println(testresult);
}
写了个测试的方法 发现刚刚的算法应该是没有错的

Answer 9

int x =11111111;
int result = 0;
int testresult = 0;
long start = System.currentTimeMillis();
for( int i=10; i<=x*10; i=i*10) {
result += x/i*(i/10);//默认当前位数是0 
if (x%i/(i/10)==1) {//当前位数是1
result += x%(i/10)+1;
}else if(x%i/(i/10)>1) {//当前位数大于1
result += i/10;
}
}
long end = System.currentTimeMillis();
long teststart = System.currentTimeMillis();
for (int i=0; i<=x; i++) {
String s = i+"";
String s1 = s.replaceAll("1", "");
testresult +=s.length()-s1.length();
}
long testend = System.currentTimeMillis();
System.out.println("花费时间："+(end-start));
System.out.println(result);
System.out.println("test花费时间："+(testend-teststart));
System.out.println(testresult);测试结果：花费时间：0
8888896
test花费时间：20265
8888896

Answer 10

import javax.swing.*;
public class phenixHasOne{
public static void main(String[]args){
String strNumber=JOptionPane.showInputDialog("please input the number ");
//int number=Integer.parseInt(strNumber);
int oneNumbers=0;
for(int i=strNumber.length()-1,j=0;i>=0;i--,j++)
{
String strbefore=strNumber.substring(0,i);
String strlast=strNumber.substring(i+1,strNumber.length());
String strcurrentNumber=strNumber.substring(i,i+1);
//只有一位的时候
if(strbefore.equals("")&&strlast.equals("")){
oneNumbers+=OneNumbers(0,0,Integer.parseInt(strcurrentNumber),(int)Math.pow(10.0,(double)j));
break;
}
//当是第一次=的时候
if(i==strNumber.length()-1)
{
strlast="";
System.out.println("前边数字:"+strbefore);
System.out.println("后边数字"+strlast);
System.out.println("当前数字"+strcurrentNumber);
oneNumbers+=OneNumbers(Integer.parseInt(strbefore),0,Integer.parseInt(strcurrentNumber),(int)Math.pow(10.0,(double)j));
continue;
}
//最后一次的时候
if(i==0)
{
strbefore="";
System.out.println("前边数字:"+strbefore);
System.out.println("后边数字"+strlast);
System.out.println("当前数字"+strcurrentNumber);
oneNumbers+=OneNumbers(0,Integer.parseInt(strlast),Integer.parseInt(strcurrentNumber),(int)Math.pow(10.0,(double)j));
continue;
}
System.out.println("前边数字:"+strbefore);
System.out.println("后边数字"+strlast);
System.out.println("当前数字"+strcurrentNumber);
oneNumbers+=OneNumbers(Integer.parseInt(strbefore),Integer.parseInt(strlast),Integer.parseInt(strcurrentNumber),(int)Math.pow(10.0,(double)j));
System.out.println(".......................................");
}
System.out.println("total numbers of one is "+oneNumbers);}
public static int OneNumbers(int before,int last,int currentNumber,int metric){
int number=0;
if(currentNumber>1)
{
number=(before+1)*metric;
}
if(currentNumber==1)
{
//说明是个位
if(metric==1){
number=before+1;
}
else{
number=(before)*metric+(last+1);
}
}
if(currentNumber==0)
{
number=before*metric;
}

return number;} }//看看这个行不？

Answer 11

package net.csdn.community;public class Test {
public static int ccccc(int num, int tens, int a) {
if (tens == 0) return 0;
int ak = num / tens;
if (ak > a) {
return tens + ccccc(num % tens, tens / 10, a) + ak * ccccc(tens - 1, tens / 10, a);
}
else
if (ak == a) {
return num % tens + 1 + ak * ccccc(tens - 1, tens / 10, a) + ccccc(num % tens, tens / 10, a);
}
else {
return ccccc(num % tens, tens / 10, a) + ak * ccccc(tens - 1, tens / 10, a);
}
}

public static void main(String[] args) {
System.out.println(ccccc(200, 100, 1));

}}吃飯前看到這貼,搞到吃飯都在發呆...

Answer 12

num是數字,tens是num的最長的10^k的數,a是你要找的位數...由於在做這題時都是考慮1來做的,所以先不要試其他囉,呵

Answer 13

各位大侠看下小弟的推导对不对：
一位的时候   1的个数是     1；
二位的时候   1的个数是     1+10+1；
三位的时候   1的个数是     12+100+12；
...
i位的时候    1的个数是     i*10的i-1次方+2倍的i-1位的和，其中条件i要大于一；这样可以用递归来求解

Answer 14

如果ccccc(200,100,0)的話,1時會被看作001,10會被看作010,所以在位數看齊的情況下也是對的...142個0

Answer 15

/**
 * 思想:遍历由1到n的这个数组,分析每一个数
 *     让这个数除以它10的位数-1次方,如123除以100会得到1,
 *     然后取余得到23,再除以10,得到2,
 *     取余得到3,再除以1得到3,取余得0,结束
 * 效率是O(n)乘以n的位数
 * @author 星情
 *
 */
public class Test4 {
    
    public static void main(String args[]) {
        int num = 11111111;
        long i1 = System.currentTimeMillis();
        System.out.println(num + "总共有" + new Test4().oneNums(num));
        long i2 = System.currentTimeMillis();
        System.out.println("运行时间:" + (i2 - i1) + "毫秒");
    }
    
    /**
     * 计算总共出现1的次数
     * @param num
     * @return
     */
    private int oneNums(int num) {
        //出现1的次数
        int oneCount = 0;
        for (int i = 1; i <= num; i++) {
            //遍历每个数,oneNum返回该数含有1的个数
            oneCount += oneNum(i);
        }
        return oneCount;
    }    /**
     * 单个数字里面出现1的次数
     * @param i 要计算的数
     * @return 该数字中出现1的次数,如121出现1的次数2
     */
    private int oneNum(int i) {
        //在这个数中,含有1的个数
        int count = 0;
        //等于参数i的值,目的是计算出i是几位数,如i是52364,得出i的值10000
        int num = i;
        //计算出num
        int bit = 1;
        while (num > 9) {
            bit = bit * 10;
            num = num / 10;
        }
        
        /*
         * 此时,bit是10的i位数-1次方,每次循环会得到最高位的值,循环完成后
         * 会得到该数具有1的个数,如i的值是1321
         * 第一次循环i/bit(1321/1000)等于1,count++(此时count=1),然后i%bit,bit降一位
         * 第二次循环321/100等于3,然后ii%bit,bit降一位
         * 第三次循环21/10等于2,然后ii%bit,bit降一位
         * 第四次循环1/1等于1,count++(此时count=2)然后ii%bit,bit降一位
         * 第五次循环时,因为i取i%bit==0,所以循环结束
         */
        while (i != 0) {
            if (i / bit == 1)
                count++;
            i = i % bit;
            bit = bit / 10;
        }
        return count;
    }
}
这是我写的算法,没有用字符串,不过效率好像也不是很高,等待改善

Answer 16

我的算法复杂度只是n的位数次循环 应该是最低的 下面的转成string的原始算法只是比较，谁知这样一来大家就看不出来了，郁闷中。。，

Answer 17

ccccc(111111111, 100000000, 1);第一個參數是n,第二個是你的位數,兩位數100,三位數1000,so forth,第三個是你要找的數字

Answer 18

 int x =111111111;
        int result = 0;
        int testresult = 0;
        long start = System.currentTimeMillis();//纪录循环开始时间
        for( int i=10; i<=x*10; i=i*10) {
            result += x/i*(i/10);//默认当前位数是0 
            if (x%i/(i/10)==1) {//当前位数是1
                result += x%(i/10)+1;
            }else if(x%i/(i/10)>1) {//当前位数大于1
                result += i/10;
            }
        }
        long end = System.currentTimeMillis();//结束时间
        System.out.println("花费时间："+(end-start));
        System.out.println(result); 
---测试结果
花费时间：0
100000008

Answer 19

我这里加时间主要是为了和long teststart = System.currentTimeMillis();
        for (int i=0; i<=x; i++) {
            String s = i+"";
            String s1 = s.replaceAll("1", "");
            testresult +=s.length()-s1.length();
        }
        long testend = System.currentTimeMillis();
这个较慢的算法作比较，所以时间精度很低的，时间精度高的我也不会， 呵呵 还望高手指点下 求运行时间的方法

Answer 20

嗯,記得以前做個運行時間很長的測試,得出來也是幾十millisecond...

Answer 21

public class Test {
public static void main(String []args){
System.out.println(new Test().countOne(12));
}
public int countOne(int i){
int k=i;
int sum=0;//1的个数
int n=0;
if(i>=1&&i<=9)return 1;
do{
int j=i%10;
if(n==0){
if(j!=0)
sum+=1;
}else{
if(j==1){
int l=(int)(k%(Math.pow(10, n)));
sum+=(int)(j*n*Math.pow(10, n-1)+l+1);
}else{
sum+=(int)(j*n*Math.pow(10, n-1)+Math.pow(10, n));
}
}
i/=10;
}while(k>Math.pow(10, ++n));

return sum;
}
}我测试了，可以，而且，速度也绝对不慢。具体细节见
http://blog.csdn.net/wenlz123/archive/2008/11/05/3226234.aspx

Answer 22

public static int count(int num,int base){
if(base==1){
return num>=1?1:0;
}
int n = num/base;
int tail = num-n*base;
int temp = 0;
switch(n){
case 0:break;
case 1:temp = tail+1;break;
default:temp = base;
}
return temp+n*(count(base-1,base/10))+count(tail,base/10);
}
public static void main(String[] args){
long now = System.currentTimeMillis();
System.out.println(count(111111111,100000000));
now = System.currentTimeMillis()-now;
System.out.println(now);
}

Answer 23

import java.util.Arrays;public class Factorial {
public static void main(String args[]) {
 System.out.println(new Factorial().f(11111111));
} public int f(int enterNum) {
int oneNum = 1;
int Index1 = 0;
int lastIndex1 = 0;
for (int i = 10; i <= enterNum; i++) {
String strNum = String.valueOf(i);
char[] cha = strNum.toCharArray();
Arrays.sort(cha);
strNum = new String(cha);
Index1 = strNum.indexOf("1");
lastIndex1 = strNum.lastIndexOf("1")+1;
if(Index1 > -1) {
oneNum += strNum.substring(Index1, lastIndex1).length();
}
}
return oneNum;
}
}
效率并不算高，但代码比较简单。

Answer 24

int x =111111111;
        int result = 0;
        long start = System.nanoTime();//纪录循环开始时间
        for( int i=10; i<=x*10; i=i*10) {
            result += x/i*(i/10);//默认当前位数是0 
            if (x%i/(i/10)==1) {//当前位数是1
                result += x%(i/10)+1;
            }else if(x%i/(i/10)>1) {//当前位数大于1
                result += i/10;
            }
        }
        long end = System.nanoTime();//结束时间
        System.out.println("花费时间："+(end-start)+"毫微秒");
        System.out.println(result);
修改了一下测试时间的精度 System.nanoTime();这个是毫微秒级的测试结果：
花费时间：3254毫微秒
100000008

Answer 25

吃饭去,一会上课了,不看了,脑子有点乱了KAO

Answer 26

想快 数学必须要说得过得去，（看过小学奥数）
用大量除的，大量mod的基本上很慢，
用字符串的，速度差10^6倍吧

Answer 27

楼主的算法，
charAt方法，要比substring的效率要高，因为楼主只是想比较某一个字符。
试试if(strNum.charAt(j)=='1')...
应该会快很多。当然，支持使用 用数学计算的方法。