【算法比赛】统计从N到M中出现多少个1(N、M为正整数且N<M)。看谁的算法最快。

Question

为了方便调试和对比，统一测试数据和代码框架：
/// <summary>
/// 在N到M中出现多少个1
/// </summary>
/// <param name="N">最小数</param>
/// <param name="M">最大数</param>
/// <returns>返回出现了多少个1</returns>
private long Calc(uint N, uint M)
{
    /* TODO : 请在这里发挥 */
    return 0; 
}private void button1_Click(object sender, EventArgs e1) // 在控制台自己动手改这里
{
    // 不要改变如下代码
    uint N, M;
    long vTickCount = Environment.TickCount;
    N = 2008;
    M = 20080808;
    Console.WriteLine("从{0}到{1}中出现{2}个1", N, M, Calc(N, M));
    N = uint.MaxValue / 2;
    M = uint.MaxValue;
    Console.WriteLine("从{0}到{1}中出现{2}个1", N, M, Calc(N, M));
    N = uint.MinValue;
    Console.WriteLine("从{0}到{1}中出现{2}个1", N, M, Calc(N, M));
    Console.WriteLine("计算耗时{0}毫秒！", Environment.TickCount - vTickCount);
}奖励：
第一名100分
第二名50分
其他酌情散掉。ps:帖代码之前先自己跑一遍，运行在5分钟以上的就别帖了，测试起来费劲。。

Answer 1

int count=0; 
int max=200; 
int min=10;
void main(){ 
    for(int i=min;i <=max;i++){ 
        getCount(i); 
    } 
    Console.WriteLine(count); 
} function getCount(int i){ 
if(i>0){ 
    if(1==i%10){ 
        count++; 
        getCount(i/10); 
    } 
} 
} 

Answer 2

private long Calc(uint N, uint M)
{
/* TODO : 请在这里发挥 */
long iRet=0;
for(uint i=N;i<=M;i++)
{
iRet+=N.ToString().Split('1').Length ;
}
return iRet; 
}

Answer 3

..至于上升到算法的高度吗?using System;
using System.Collections.Generic;
using System.Text;namespace ConsoleApplication4
{
    class Program
    {
        private static Int64 intcount = 0;
        private static Int64 intmax = 6767677;
        private static Int64 intmin = 10;        static void Main(string[] args)
        {
            for (Int64 i = intmin; i <= intmax; i++)
            {
                getCount(i);
            }
            Console.WriteLine(intcount);  
        }
        private static void getCount(Int64 i)
        {
            if (i > 0)
            {
                if (1 == i % 10)
                {
                    intcount++;
                    
                }
                getCount(i / 10);
            }
        }      }
}
整理一下,正好玩玩

Answer 4

抛砖引玉先,手写段代码,还没环境测试效率,不过不会有五分钟那么恐怖吧....private long Calc(uint N, uint M)
{
    StringBuilder sb=new StringBuilder();
    for(int i=N;i<=m;i++)
    {
      sb.Append(i);
    }
    return sb.ToString().Split('1',StringSplitOptions.None).Length-1; 
}

Answer 5

呵呵，我就知道你们会拿这些代码来先在自己的机器里跑跑。。别说其他的，光一个这循环都要跑N久：
for (uint i = uint.MinValue; i <= uint.MaxValue; i++) ;加到字符串？内存都不够先有个印象：
0 -> 429496729540亿，如果保存为字符串至少需要36G以上的内存

Answer 6

1 -> 200
和
0 -> 4294967295 是两个不同的量级按用普通方法1 -> 200中耗1毫秒的时间，那么在0 -> 4294967295中可能就要用天计算了。

Answer 7

小于5分钟看来不现实啊...
有可能我机子烂什么的.
赛扬2.6的cpu,512m ddr2 266的内存,就跑这个代码都不只5分钟了....            /// <summary>
            /// 在N到M中出现多少个1
            /// </summary>
            /// <param name="N">最小数</param>
            /// <param name="M">最大数</param>
            /// <returns>返回出现了多少个1</returns>
            private long Calc(uint N, uint M)
            {
                long Result = 0;
                for (uint i = N; i <= M; i++)
                {
                    Result += 1;
                }
                return Result;
            }

Answer 8

不如稍稍扩展为：统计从N到M中出现多少个k(N、M为正整数且N<M，k为整数)。

Answer 9

汗
从 2008 跑到 200808 就用了145453ms
20080808就别跑了private static long Calc(uint N, uint M)
{
     int count = 0;
     for (uint i = N; i <= M; i++)
     {
         if (!i.ToString().Contains("1"))
              continue;
         count += System.Text.RegularExpressions.Regex.Replace(i.ToString(), @"[^1]", "").Length;
     }
     return count;
}PS：这种方法要比递归快些。

Answer 10

晕，弄错了。
从2008跑到20080808用了145453ms，
而递归仅用11453ms，差十倍啊...

Answer 11

zswang，我觉得你的结果肯定不对。你看2008道20080808中的1的个数是不是相当于2000到20080800的1的个数？这个个数肯定是被100整除的吧？你的最后两位60是怎么出来的？我有一个算法，但是还没有实现（我过会实现），我口算的结果是24008500个1。

Answer 12

        |--  f(n-cint(lg(n))^10)+ 1 ,n以1开头
f(n)=  -|
        |--  f(n-cint(lg(n))^10)+ 0 ,n以非1开头
f(n)返回n中1的个数
分情况讨论,求通项公式吧
暂时思考这么多

Answer 13

先算出每个数从0开始每位出现1的次数.
假如n=37; 则个位数出现1为  4,
           十位数出现1为  10,
   ......
     private long Calc(uint N, uint M)
        {
            if (N == 0) return total1(M, 1);
            else
                return total1(M, 1) - total1(N - 1, 1);
        }
        private long total1(uint num,uint a)
        {
          
            long n = num;
            long tol = 0;
            int pow = 1;
                      while(n!=0)
            {
               
                long m = n % 10;
                n = n / 10;                tol = tol + n * pow;
                if (m == a)
                {
                    tol = tol + num % pow  + 1;
                }
                else if (m > a)
                    tol = tol + pow ;                pow = pow * 10;            } 
            return tol;        }还没详细的测试.

Answer 14

using System;
using System.Collections.Generic;
using System.Text;namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            new Program().run();
            Console.ReadKey();
        }        private void run() // 在控制台自己动手改这里
        {
            // 不要改变如下代码
            uint N, M;
            long vTickCount = Environment.TickCount;
            N = 2008;
            M = 20080808;
            Console.WriteLine("从{0}到{1}中出现{2}个1", N, M, calc(N, M));
            N = uint.MaxValue / 2;
            M = uint.MaxValue;
            Console.WriteLine("从{0}到{1}中出现{2}个1", N, M, calc(N, M));
            N = uint.MinValue;
            Console.WriteLine("从{0}到{1}中出现{2}个1", N, M, calc(N, M));
            Console.WriteLine("计算耗时{0}毫秒！", Environment.TickCount - vTickCount);
        }
        
        //===============
        private long calc(uint N, uint M)
        {
            return calc(M) - calc(N-1);
        }        private long calc(uint N)
        {
            long Count = 0;            char[] arr = N.ToString().ToCharArray();
            uint size = (uint)arr.Length;            uint restN = N;
            for (uint i = 0; i < size - 1; i++)
            {
                uint number = uint.Parse(arr[i].ToString());
                uint position = size - i - 1;                restN = restN - (number * getPow(position));
                Count += getPosition(position) * number;                if (number == 1)
                {
                    Count += restN + 1;
                }
                else
                {
                    Count +=  getPow(position);
                }
            }            if (uint.Parse(arr[arr.Length-1].ToString()) >= 1)
                Count++;
            return Count;
        }        private uint getPosition(uint size)
        {
            return (uint)Math.Pow(10, size - 1) * size;
        }        private uint getPow(uint size)
        {
            return (uint)Math.Pow(10, size);
        }
    }
}

Answer 15

78毫秒 PD930 1G内存 不知结果对否

Answer 16

从2008到20080808中出现24040660个1          .......24040660
从2147483647到4294967295中出现1913443125个1   ....1965959478   ????
从0到4294967295中出现4936987260个1           ......4936987260
第二个数据不同. ????
1,2 计算耗时0毫秒
3 计算耗时8毫秒
老本本, 1600的CPU.

Answer 17

33楼h_w_king，是第一个写出来的，运行效率也在一毫秒以内。
思路和我的一样。验证的代码如下，在1到1000000中没有问题，以此类推正确：
uint count = 0, n = 1, m = 1000000;
for (uint i = n; i <= m; i++)
{
    for (uint j = i; j > 0; j /= 10)
        if (j % 10 == 1) count++;
    if (Total(i) != count)
    {
        Console.WriteLine("error{0},{1},{2}", i, Total(i), count);
        break;
    }
}
Console.WriteLine(count);

Answer 18

简单测试了下using System;
using System.Collections.Generic;
using System.Text;namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(Calc(12345,56789)); //24939
            Console.WriteLine(new Program().calc(12345,56789)); //24939            Console.ReadKey();
        }        private long calc(uint N, uint M)
        {
            return calc(M) - calc(N - 1);
        }        private long calc(uint N)
        {
            long Count = 0;            char[] arr = N.ToString().ToCharArray();
            uint size = (uint)arr.Length;            uint restN = N;
            for (uint i = 0; i < size - 1; i++)
            {
                uint number = uint.Parse(arr[i].ToString());
                uint position = size - i - 1;                restN = restN - (number * getPow(position));
                Count += getPosition(position) * number;                if (number == 1)
                {
                    Count += restN + 1;
                }
                else
                {
                    Count += getPow(position);
                }
            }            if (uint.Parse(arr[arr.Length - 1].ToString()) >= 1)
                Count++;
            return Count;
        }        private uint getPosition(uint size)
        {
            return (uint)Math.Pow(10, size - 1) * size;
        }        private uint getPow(uint size)
        {
            return (uint)Math.Pow(10, size);
        }        //==枚举法测试用
        private static long Calc(uint N, uint M)
        {
            long Count = 0;
            for (uint i = N; i <= M; i++)
            {
                char[] arr = i.ToString().ToCharArray();
                foreach (char c in arr)
                {
                    if (c == '1')
                        Count++;
                }
            }
            return Count;
        }
    }
}

Answer 19

35楼的代码需要修改
error100,31,21
当100的时候，出现21个，不是31个。
请用38楼的代码验证。

Answer 20

我的代码和33楼一样。
/// <summary>
/// 统计1到N中出现多少个1
/// </summary>
/// <param name="N">最大数</param>
/// <returns>返回出现多少个1</returns>
private long Total(uint N)
{
    long vReturn = 0;
    long vBase = 1; // 基数每10个数级中有多少个1
    long vNumber = N;
    while (vNumber > 0)
    {
        long R = vNumber % 10;
        vNumber /= 10;
        vReturn += (vNumber + (R > 1 ? 1 : 0)) * vBase;
        if (R == 1) vReturn += N % vBase + 1;
        vBase *= 10;
    }
    return vReturn;
}/// <summary>
/// 在N到M中出现多少个1
/// </summary>
/// <param name="N">最小数</param>
/// <param name="M">最大数</param>
/// <returns>返回出现了多少个1</returns>
private long Calc(uint N, uint M)
{
    return Total(M) - Total(N > 0 ? N - 1 : N); 
}

Answer 21

不对，我第一次想错了，楼主的2008到2008080808结果是正确的。以下是我的代码和结果。怎么好像第二个结果不一样啊？楼主有没有测试过105到111这个例子？是不是10？      /// <summary>
        /// 在N到M中出现多少个1
        /// </summary>
        /// <param name="N">最小数</param>
        /// <param name="M">最大数</param>
        /// <returns>返回出现了多少个1</returns>
        private long Calc(uint N, uint M)
        {
            if (N > 0)
                return Calc(M) - Calc(N - 1);
            else
                return Calc(M);
        }        /// <summary>
        /// 在0到N中出现多少个1
        /// </summary>
        /// <param name="N">最小数</param>
        /// <returns>返回出现了多少个1</returns>
        private long Calc(uint N)
        {
            ArrayList digit = new ArrayList();            long sum = 0;            while (N!=0)
            {
               digit.Add(N%10);
               N /= 10;
            }//现在N是按位逆序存在digit里面。           // digit.Add(0);//在最前面加上一位0，便于统一计算            int size = digit.Count;
            for (int i = 0; i < size ; i++ )
            {
                //此时i表示从左往右数第几位                uint temp = 0;//前面位数之和
                for (int j = size-1; j > i; j--)
                {
                  temp *= 10;
                  temp += (uint)digit[j];
                 }                if ((uint)digit[i] == 0)
                {
                    sum += temp * (uint)Math.Pow(10, i);
                }
                else if ((uint)digit[i] > 1)
                {
                    sum += (temp+1) * (uint)Math.Pow(10, i);
                }
                else // digit[i] == 1
                {
                    uint temp2 = 0; //后面位数之和
                    for (int j = i - 1; j >= 0; j--)
                    {
                        temp2 *= 10;
                        temp2 += (uint)digit[j];
                    }
                    sum += temp * (uint)Math.Pow(10, i) + temp2 + 1;
                }            }            return sum;
            
        }
        
        
        
从2008到20080808中出现24040660个1
从2147483647到4294967295中出现1965959478个1
从0到4294967295中出现4936987260个1
计算耗时6毫秒！

Answer 22

yatobiaf的代码也是正确的，就是效率需再考虑。

Answer 23

编程就两个方法：1、问题分解；2、逐步求精这个问题先分解为：
f(n, m)N-M中出现多少个1？
  g(x)1-N中出现多少个1？f(n, m) = g(m) - g(n - 1)
     h(x, n)每位上出现多少个1 g(x) = h(x, 1) + h(x, 2) .... h(x, n)
     每10个数会在个位出现1个1、每100个数会在十位出现10个1...然后就是逐步测试这个帖子先晒晒，不忙结贴

Answer 24

对于n位最大数字（全是9）
应该有
f(n)  = f(n-1) * 9 + 10**n

Answer 25

的确漏考虑一步 呵呵private long calc(uint N, uint M)
        {
            return calc(M) - calc(N - 1);
        }        private long calc(uint N)
        {
            long Count = 0;            char[] arr = N.ToString().ToCharArray();
            uint size = (uint)arr.Length;            uint restN = N;
            for (uint i = 0; i < size - 1; i++)
            {
                uint number = uint.Parse(arr[i].ToString());
                uint position = size - i - 1;                restN = restN - (number * getPow(position));
                Count += getPosition(position) * number;                if (number == 1)
                {
                    Count += restN + 1;
                }
                else
                {
                    if (number != 0)
                        Count += getPow(position);
                }
            }            if (uint.Parse(arr[arr.Length - 1].ToString()) >= 1)
                Count++;
            return Count;
        }        private uint getPosition(uint size)
        {
            return (uint)Math.Pow(10, size - 1) * size;
        }        private uint getPow(uint size)
        {
            return (uint)Math.Pow(10, size);
        }

Answer 26

测试一下，效率都是在一毫秒内....
using System;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;namespace WindowsApplication3
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }
        #region h_w_king
        private long h_w_king_Calc(uint N, uint M)
        {
            if (N == 0) return h_w_king_total1(M, 1);
            else return h_w_king_total1(M, 1) - h_w_king_total1(N - 1, 1);
        }        private long h_w_king_total1(uint num, uint a)
        {            long n = num;
            long tol = 0;
            int pow = 1;
            while (n != 0)
            {                long m = n % 10;
                n = n / 10;                tol = tol + n * pow;
                if (m == a)
                {
                    tol = tol + num % pow + 1;
                }
                else if (m > a)
                    tol = tol + pow;                pow = pow * 10;            }
            return tol;
        }
        #endregion h_w_king        #region yatobiaf
        private long yatobiaf_Calc(uint N, uint M)
        {
            if (N > 0)
                return yatobiaf_Calc(M) - yatobiaf_Calc(N - 1);
            else
                return yatobiaf_Calc(M);
        }        private long yatobiaf_Calc(uint N)
        {
            ArrayList digit = new ArrayList();            long sum = 0;            while (N != 0)
            {
                digit.Add(N % 10);
                N /= 10;
            }//现在N是按位逆序存在digit里面。            // digit.Add(0);//在最前面加上一位0，便于统一计算            int size = digit.Count;
            for (int i = 0; i < size; i++)
            {
                //此时i表示从左往右数第几位                uint temp = 0;//前面位数之和
                for (int j = size - 1; j > i; j--)
                {
                    temp *= 10;
                    temp += (uint)digit[j];
                }                if ((uint)digit[i] == 0)
                {
                    sum += temp * (uint)Math.Pow(10, i);
                }
                else if ((uint)digit[i] > 1)
                {
                    sum += (temp + 1) * (uint)Math.Pow(10, i);
                }
                else // digit[i] == 1
                {
                    uint temp2 = 0; //后面位数之和
                    for (int j = i - 1; j >= 0; j--)
                    {
                        temp2 *= 10;
                        temp2 += (uint)digit[j];
                    }
                    sum += temp * (uint)Math.Pow(10, i) + temp2 + 1;
                }            }            return sum;        }
        #endregion yatobiaf        #region jeremyyang824
        private long jeremyyang824_Calc(uint N, uint M)
        {
            return jeremyyang824_Calc(M) - jeremyyang824_Calc(N - 1);
        }        private long jeremyyang824_Calc(uint N)
        {
            long Count = 0;            char[] arr = N.ToString().ToCharArray();
            uint size = (uint)arr.Length;            uint restN = N;
            for (uint i = 0; i < size - 1; i++)
            {
                uint number = uint.Parse(arr[i].ToString());
                uint position = size - i - 1;                restN = restN - (number * jeremyyang824_getPow(position));
                Count += jeremyyang824_getPosition(position) * number;                if (number == 1)
                {
                    Count += restN + 1;
                }
                else
                {
                    if (number != 0)
                        Count += jeremyyang824_getPow(position);
                }
            }            if (uint.Parse(arr[arr.Length - 1].ToString()) >= 1)
                Count++;
            return Count;
        }        private uint jeremyyang824_getPosition(uint size)
        {
            return (uint)Math.Pow(10, size - 1) * size;
        }        private uint jeremyyang824_getPow(uint size)
        {
            return (uint)Math.Pow(10, size);
        }
        #endregion jeremyyang824        private void button1_Click(object sender, EventArgs e)
        {
            // 不要改变如下代码
            uint N, M;
            long vTickCount;            Console.WriteLine("---h_w_king_Calc----");
            vTickCount = Environment.TickCount;
            N = 2008;
            M = 20080808;
            Console.WriteLine("从{0}到{1}中出现{2}个1", N, M, h_w_king_Calc(N, M));
            N = uint.MaxValue / 2;
            M = uint.MaxValue;
            Console.WriteLine("从{0}到{1}中出现{2}个1", N, M, h_w_king_Calc(N, M));
            N = uint.MinValue;
            Console.WriteLine("从{0}到{1}中出现{2}个1", N, M, h_w_king_Calc(N, M));
            Console.WriteLine("计算耗时{0}毫秒！", Environment.TickCount - vTickCount);
            Console.WriteLine();            Console.WriteLine("---yatobiaf_Calc----");
            vTickCount = Environment.TickCount;
            N = 2008;
            M = 20080808;
            Console.WriteLine("从{0}到{1}中出现{2}个1", N, M, yatobiaf_Calc(N, M));
            N = uint.MaxValue / 2;
            M = uint.MaxValue;
            Console.WriteLine("从{0}到{1}中出现{2}个1", N, M, yatobiaf_Calc(N, M));
            N = uint.MinValue;
            Console.WriteLine("从{0}到{1}中出现{2}个1", N, M, yatobiaf_Calc(N, M));
            Console.WriteLine("计算耗时{0}毫秒！", Environment.TickCount - vTickCount);
            Console.WriteLine();            Console.WriteLine("---jeremyyang824_Calc----");
            vTickCount = Environment.TickCount;
            N = 2008;
            M = 20080808;
            Console.WriteLine("从{0}到{1}中出现{2}个1", N, M, jeremyyang824_Calc(N, M));
            N = uint.MaxValue / 2;
            M = uint.MaxValue;
            Console.WriteLine("从{0}到{1}中出现{2}个1", N, M, jeremyyang824_Calc(N, M));
            N = uint.MinValue;
            Console.WriteLine("从{0}到{1}中出现{2}个1", N, M, jeremyyang824_Calc(N, M));
            Console.WriteLine("计算耗时{0}毫秒！", Environment.TickCount - vTickCount);
            Console.WriteLine();
         }
    }
}

Answer 27

从代码的精干性和扩展性，目前33楼的h_w_king做得最好，也是第一个贴出可调试代码的。多谢大家参与。

Answer 28

从0到4294967295中出现0个1 -_-!!!
jeremyyang824的代码需要再看看

Answer 29

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
using System.Threading;namespace WindowsApplication16
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }        
        uint[] count=new uint[100000];
        /// <summary>
        /// 在N到M中出现多少个1
        /// </summary>
        /// <param name="N">最小数</param>
        /// <param name="M">最大数</param>
        /// <returns>返回出现了多少个1</returns>
        private long Calc(uint N, uint M)
        {
            long Return = 0;
            
            for (uint a = N; a < M; a++)
            {
                uint temp=a;
                while (temp > 0)
                {
                    uint bi1 = temp % 100000;
                    temp /= 100000;
                    Return += count[bi1];
                }
                
                
                           }
            return Return;
        }        private void button1_Click(object sender, EventArgs e1) // 在控制台自己动手改这里
        {
            
            
            
            // 不要改变如下代码
            uint N, M;
            long vTickCount = Environment.TickCount;            for (int a = 0; a < 100000; a++)
            {
                if (!a.ToString().Contains("1"))
                    continue;
                count[a] = (uint)System.Text.RegularExpressions.Regex.Replace(a.ToString(), @"[^1]", "").Length;
            }
            N = 2008;
            M = 20080808;            Console.WriteLine("从{0}到{1}中出现{2}个1", N, M, Calc(N, M));
            N = uint.MaxValue / 2;
            M = uint.MaxValue;
            Console.WriteLine("从{0}到{1}中出现{2}个1", N, M, Calc(N, M));
            N = uint.MinValue;
            Console.WriteLine("从{0}到{1}中出现{2}个1", N, M, Calc(N, M));
            Console.WriteLine("计算耗时{0}毫秒！", Environment.TickCount - vTickCount);
        }    }
}看了看,没把我吓到,以为N = uint.MinValue到M = uint.MaxValue也是0呢...
这才是解决这个问题的最好算法呢..

Answer 30

        Private Function Calc(ByVal N As UInteger, ByVal M As UInteger) As Long
            Return count(M) - count(N)
        End Function        Private Function count(ByVal x As UInteger) As Long
        If x < 10 Then
            Return 1
        End If
        Dim total As ULong = 0
        Dim l As Integer = x.ToString.Length
        Dim sum_temp As ULong = sum(l - 1)
        Dim firstnum As Integer = Int(x / 10 ^ (l - 1))
        Select Case firstnum
            Case 1
                total += sum_temp + count(x - 10 ^ (l - 1)) + (x - 10 ^ (l - 1) + 1)
            Case Else                total += sum_temp * firstnum
                total += count(x - (10 ^ (l - 1)) * firstnum)
                total += 10 ^ (l - 1)
        End Select
        Return total
    End Function    Private Function f(ByVal x As Integer) As ULong
        If x = 1 Then
            Return 1
        Else
            Return sum(x - 1) * 9 + 10 ^ (x - 1)
        End If
    End Function    Private Function sum(ByVal x As Integer) As ULong
        Dim total As ULong = 0
        For i As Integer = 1 To x
            total += f(i)
        Next
        Return total
    End Function从2008到20080808中出现24040660个1
从2147483647到4294967295中出现1965959478个1
从0到4294967295中出现4936987260个1
计算耗时8毫秒！

Answer 31

又粗心了...
private long calc(uint N, uint M)
{
    if (N < 1)
         return calc(M);
    return calc(M) - calc(N - 1);
}

Answer 32

63楼，结果有一点误差N=1,M=200
从1到200中出现140个1N=2,M=200
从2到200中出现140个1明显不对另外，这段代码是不是这样改？合理些Private Function Calc(ByVal N As UInteger, ByVal M As UInteger) As Long
    Return count(M) - count(IIf(N > 0, N - 1, N))
End Function

Answer 33

定参数的方法算不算:
如果把1X,1XX,2XXX...的预先知道了,计算就很快了

Answer 34

using System;
using System.Collections.Generic;
using System.Text;namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                // 不要改变如下代码
                uint N, M;
                long vTickCount = Environment.TickCount;
                N = Convert.ToUInt32(Console.ReadLine());
                M = Convert.ToUInt32(Console.ReadLine());
                Console.WriteLine("从{0}到{1}中出现{2}个1", N, M, Calc(N, M));
                N = uint.MaxValue / 2;
                M = uint.MaxValue;
                Console.WriteLine("从{0}到{1}中出现{2}个1", N, M, Calc(N, M));
                N = uint.MinValue;
                Console.WriteLine("从{0}到{1}中出现{2}个1", N, M, Calc(N, M));
                Console.WriteLine("计算耗时{0}毫秒！", Environment.TickCount - vTickCount);
            }
        }
        /// <summary>
        /// 在N到M中出现多少个1
        /// </summary>
        /// <param name="N">最小数</param>
        /// <param name="M">最大数</param>
        /// <returns>返回出现了多少个1</returns>
        private static long Calc(uint N, uint M)
        {
            /* TODO : 请在这里发挥 */
            long length = 0;            length = Calc1(M) - Calc1(N) + 1;
            return length;
        }
        /// <summary>
        /// 在N到M中出现多少个1
        /// </summary>
        /// <param name="N">最小数</param>
        /// <param name="M">最大数</param>
        /// <returns>返回出现了多少个1</returns>
        private static long Calc1(uint M)
        {
            /* TODO : 请在这里发挥 */
            long length = 0;            string strm = M.ToString();            for (int i = 0; i < strm.Length; i++)
            {
                //得到个位数
                string str = strm.Substring(strm.Length -(i+1), 1);                Int32 b = Int32.Parse(str);//原来的数字                Int32 x = 0;//要加的数字                Int32 y = 0;//要乘以的数字                if (i==0)//个位数
                {
                    x = 1;
                }
                else
                {
                    x = b1(i);
                }
                y = b2(i);                length += x + b * y;
            }
                        return length;
        }
        private static Int32 b1(Int32 i)
        {
            int a = i + 1;            int return1 = 1;            return1 = Convert.ToInt32(return1.ToString().PadRight(a, '0'));
            return return1;
        }
        private static Int32 b2(Int32 i)
        {
            int a = i;            int return1 = 0;            return1 = Convert.ToInt32(a.ToString().PadRight(i,'0'));            return return1;
        }
      }}

Answer 35

74楼的代码 Calc1(10) = 12

Answer 36

good idea.

Answer 37

/// <summary>
        /// 在N到M中出现多少个1
        /// </summary>
        /// <param name="N">最小数</param>
        /// <param name="M">最大数</param>
        /// <returns>返回出现了多少个1</returns>
        private long Calc(uint N, uint M)
        {
            /* TODO : 请在这里发挥 */
            return Calc(M) - Calc(N);            //uint i = Calc(11);
        }
        private uint Calc(uint M)
        {
            uint temp = M;            uint i = 0;
            while (M > 10)
            {
                M = M / 10;
                i++;
            }
            if (i == 0 && M >= 1)
            {
                return 1;
            }
            if (i == 0 && M < 1)
            {
                return 0;
            }            uint baseNumber = i;
            uint number = 0;
            for (int k = 1; k < i; k++)
            {
                baseNumber *= 10;
            }            if (M == 1)
            {
                return baseNumber + temp - baseNumber / i * 10 + Calc(temp - baseNumber / i * 10);
            }
            else
            {
                number += baseNumber + baseNumber / i * 10 + baseNumber;
                for (int k = 2; k < M; k++)
                {
                    number += baseNumber;
                }
                return number + Calc(temp - baseNumber/i*10*M);
            }
        }
从0到9999999中出?7000000个1
从2147483647到4294967295中出?1965959478个1
从0到4294967295中出?642019964个1
?算耗?0毫秒！哈哈 。。
快吧

Answer 38

很早以前写的回复了,当时只看代码简单,用字符串处理效率肯定不高的,不过还是能做些优化,下面的五分钟能跑完了private long Calc(uint N, uint M) 
{ 
    int count=0; 
    for(int i=N;i <=m;i++) 
    { 
      if(i.ToString().Contains(“1”)
      {
        count+=i.ToString().Split('1').Length-1;
      } 
    } 
    return count;
}
用统计的不知道楼上有代码没，下班回去看看怎么写

Answer 39

long contain(long num)
{
int xi[100],cou=0;
long base=1,zi=0,re=0;
for(;num>9;num/=10){base*=10;zi++;xi[cou++]=num%10;}
xi[cou]=num;
for(;cou>=0;base/=10,cou--)
re+=base+xi[cou]*(zi--)*base/10;
return re;
}

Answer 40

long contain(long num)
{
int xi[100],cou=0;
long base=1,zi=0,re=0;
for(;num>9;num/=10){base*=10;zi++;xi[cou++]=num%10;}
xi[cou]=num;
for(;cou>=0;base/=10,cou--)
re+=base+xi[cou]*(zi--)*base/10;
return re;
}

Answer 41

long contain(long num)
{
int xi[100],cou=0;
long base=1,zi=0,re=0;
for(;num>9;num/=10){base*=10;zi++;xi[cou++]=num%10;}
xi[cou]=num;
for(;cou>=0;base/=10,cou--)
re+=base+xi[cou]*(zi--)*base/10;
return re;
}

Answer 42

        public static long Cal(int n, int m)
        {
            long ret = 0;
            for (int i = n; i <= m; i++)
            {
                foreach (char c in i.ToString())
                {
                    if (c == '1')
                        ret++;
                }
            }
            return ret;
        }

Answer 43

自己用C#写了下,62ms,机器比较破,最主要还是没C效率高

Answer 44

毫无睡意让我来终结该帖吧.
static void Main(string[] args)
        {
           int n = 2008;  //开始数   
            int m = 20080808;   //结束数 
            int sum = 0;   //统计出现1的个数
            int momey = 0; //临时1的个数
            int mod = 0;
            int num = 0;//计算了几次 10进位(可能出现1,这步比较麻烦点)  11肯定会出现一个1;            num = ((int)n % 10); //计算起始位置            if (num == 1)  //如果有 这是第一个1
            {
                sum++;
            }            //个位1不计算在内
            for (int i = 10; ; i = i * 10)
            {
                mod = i * 10;
                if ((n * 10) >= mod)
                {
                    int t = n % mod;
                    if (i <= t && t < 2 * i)
                    {
                        momey++;
                    }
                }
                else
                {
                    mod = 0;//清除这个数
                    break;
                }
            }
            for (; n <= m; n++, num++)
            {
                if (num == 10)  //这里需要进位了 所以重新计算下
                {
                    int b = 0;
                    int c = 0;
                    for (int j = 10; ; j = j * 10) //这里进行的是进制 换算
                    {
                        mod = j * 10;                        if ((n * 10) >= mod)
                        {
                            b = (n - 1) % mod; //往后退一位
                            if (b < j)
                            {
                                momey++;
                                break;
                            }
                            else if ((c = ((int)(b / j))) < 9)//减少循环次数
                            {
                                if (c == 1)
                                {
                                    momey--; //说明这里会覆盖掉原来的一个1
                                }
                                break;
                            }
                        }
                        else
                        {
                            break;
                        }                    }
                }
                sum += momey; 
                if (num == 11)
                {
                    sum++;
                    num = 1;
                }
            }
            Console.Write(sum.ToString());
        }

Answer 45

C#毕竟不是C/C++,毕竟很少用到算法，更别说去找其中的数学规律了.
C# 把程序员都学傻了.
哎.......
他妈的要不是做界面 那个类属性搞来搞去,要不就是做数据库相关系统 靠 用存储过程都能实现全部业务逻辑,更别想用到高深算法了.在深入一点 MVF 还不是调用几个管道类搞来搞去,需要算法吗,不需要....
这个版块 我出个数据库相关题目吧.删除无限级下拉菜单某个节点,将删除其下所有子节点(子节点不限制层数和个数), parnetid  = 0 说明位顶级节点
如格式如下:
id 自动编号
txt 说明字符 任意值
prinetid  是从id里面取值id   txt   parnetid
1    "a"   0
2    "b"   1
3    "c"   2
4    "d"   3
5    "e"   4    ---不限制层数 无限层数
6    "a"   4
7    "a"   4
8    "a"   4   --- 子节点不限制个数
9    "a"   0   ---  顶级节点为任意个
10    "a"   9在说明一下题目 如删除某个节点 如  id =0 节点 则 删除其下所有子节点(1~8)
                              id = 2  则其删除的节点是(2~7)存储过程实现 
例如
m_id  是传入节点值
sql server 格式
CREATE PROCEDURE 
  @m_id int    
AS
-- 自由发挥
GOmysql格式
CREATE PROCEDURE sp_name (m_id int)
begin
-- 自由发挥
end;
呵呵,这个有实际意义哦.
当年我做这个功能可让我费了不少脑细胞.

Answer 46

TO:94楼  我上面的算法  可直接拿到C里面跑,最后输出sum就可以了.语言不重要 关键是要知道怎么推导.

Answer 47

还是可以减少循环次数的.
直接处理+10的问题
      n -= num; //让个位从0开始
      for( ; n <= m ;n +=10)
{

int b = 0 ;
int c = 0;
for(int j = 10;;j =j*10) //发现数据类型超出范围问题 int 设置 long 
{
mod = j*10;

if( n >= (mod*10))
{
b = (n-1)%mod; //往后退一位
if( b < j)
{
momey++;
break;  
}else if( (c = ((int)(b/j))) < 9)//减少循环次数
{
if( c == 1)
{
momey--; //说明这里会覆盖掉原来的一个1
}
break;
}
}else
{
break;
}
}
sum += momey; 
if(n-9 <= m ) //判断+10 过头的原因  公式=(n-10)+1
{
sum++; 
}
}
这样的循环因该是最少的了.