你如何计算从1到99,999,999(1亿的1短)的发生率,总计有1到1的数量

Question

我开始学习c#并完成这项任务.我已经这样做了这是代码:

string y = "";
int count = 0;
string x  = "";
string[] arr = new string[100000000];

for (int i = 0; i < 100000000; i++)
{ 
    x = i.ToString() + x;
}

Console.WriteLine(x);

for (int j = 0; j < x.Length; j++)
{
    y = x.Substring(j, 1);

    switch (y)
    {
        case "1":
             count ++;
             break;

        default:
            break;
    } 
}

Console.WriteLine(count);

代码在小范围(0到1000)的情况下正常工作但在运行它的范围为1亿时它不会产生任何结果(我等待但没有输出)加上看起来我的代码不是有效的方式.我现在的问题是这个代码中的问题是什么,以及是否有更好的解决方案来完成这项任务.

Answer 1

我认为你最大的问题是字符串连接.C#newbies犯的一个大错误就是认为字符串是可变的,因为它们对外部观察者的行为方式.事实上,它们在记忆中被视为不可改变的; 每次x = i.ToString() + x在循环中执行时,都会创建两个新字符串,其中一个字符串替换X保留的先前引用i.ToString(),旧x值保留范围,但在GC可以访问它们之前不会从内存中删除.因此,该算法使得运行时的内存管理层工作非常困难.

此外,你有一个1亿元素的数组,arr,占用了沙箱中的空间.这可能并没有真正减慢你的速度,但它肯定会浪费内存,因为它没有被使用.

"switch"语句对于你想要做的事情来说太过分了.完全相同的操作可以更简单地指定(和更少的底层操作)所以:if(y=="1") count++;.

最后,如果你想在大多数C风格的语言中使用字符串中的单个字符,你可以简单地将字符串视为一个字符数组(它是):y = x[j];将给你相同的结果y=x.Substring(j,1),它只是一个字符变量而不是一个单字符的字符串,它应该更快,因为你没有旋转String.Substring()方法中的逻辑.

相反,你只需按顺序取每个字符串并计算其中的1,然后将其添加到总计中即可得到相同的结果.如果以这种方式进行调整,您现有的实现将会起作用,但是一点Linq会使代码更清晰(尽管不一定更快):

for(var i=1; i < 100000000; i++)
    count += i.ToString().Count(c=>c=='1');

您甚至可以使用纯Linq解决方案对其进行单行处理:

var count = Enumerable.Range(1,99999999).Aggregate(0, (s, i) => s + i.ToString().Count(c=>c == '1'));

打破这个:

• Enumerable.Range 生成一个"可枚举"(单向可迭代系列),从第一个参数开始递增整数,并一直持续到第二个参数的数字已经产生.
• Aggregate基本上包裹一个复合循环; 它接受一个"种子"值(0),将其作为匿名方法的第一个参数与源集合的第一个元素一起传递,然后获取该方法的结果并将其反馈到lambda语句中下一个元素,依此类推,直到为每个元素完成此操作.
• lambda语句(s, i) => s + i.ToString().Count(c=>c == '1')采用两个整数(" seed"和" integer"),将整数转换为字符串,计算该字符串中"1"个字符的数量,并将该总数加到s.lambda的返回值就是总和.

其他需要考虑的事情:

• 在一般情况下,这可能不起作用,但是你知道你的系列中没有大于99,999,991的数字会有任何'1'数字,所以继续超过这个数字你只是浪费时间(在这种情况下不多,但仍然).

• 字符串解析也不错,但整数数学通常要快得多.对于每个数字,尝试除以10,然后以10为模数.这将产生数字的每个数字,您可以与1进行比较,如果为真则增加"计数".它将需要更多的代码行,但它可能仍然比ToString()更快地解决每个数字,因为这需要更多的计算步骤来确定每个数字的字符值并将它们放在一起(和更少的内存,作为整数值可以在更多或更少的位置上操作,因此不需要每个数字都需要一个字符串,整个循环需要三个整数变量):

  var count = 0;
  for(var i=1; i<100000000; i++)
  { 
      var j = i;
      while(j > 0)
      {
          if(j % 10) == 1) 
              count++;
          j /= 10;
      }
  }