[0-n]范围内有多少个整数的十进制表示中至少包含一个 9？

Question

有没有一个通用的公式可以解决这个问题？

这是我试图解决的编码问题的一部分，简单的解决方案（例如遍历每个整数并检查它是否包含数字 9）太慢了。

到目前为止，我最接近的（使用 c# 工作）是这样的：

using System;
using System.Numerics;

public static class Kata {
  
  public static BigInteger Nines(BigInteger n) 
  { 
    BigInteger a = 0;
    for (BigInteger i = 0; i < BigInteger.Parse((Math.Floor(Math.Log10((double)n))+1).ToString()); i++)
    {
      long c = (long)((Math.Floor((double)n /Math.Pow(10,(double)i)) % 10));
      a = c < 9 ? (long)(((double)c*(Math.Pow(9,(double)i))) + (double)a) : (long)(c*(Math.Pow(9,(double)i)));
    }
    return n-a;
  }
}

但是我注意到，例如，当 n=3950 时，我开始得到不正确的值（对于这种特定情况，函数返回 1034 而不是 1035，我不确定哪里出了问题。对于较大的值，错误会变得更大的 n)

Answer 1

我想可能有点左字段，但你可以尝试在代表largeInt的字符串上使用正则表达式。

来自：https://learn.microsoft.com/en-us/dotnet/api/system.text.regularexpressions.match?view=net-8.0#examples

如果Regex.Match方法无法匹配正则表达式 模式，它返回一个等于 Match.Empty 的 Match 对象。你 可以使用 Success 属性来确定匹配是否成功 成功的。以下示例提供了说明。

using System.Text.RegularExpressions;

...
...

string input= n.toString(); //your large int

string pattern = @"9";

Match match = Regex.Match(input, pattern);
     
if (match.success) {
 //DONE!
}