3. 统计数字暴力破解找规律
3. 统计数字暴力破解找规律
计算数字k在0到n中的出现的次数，k可能是0~9的一个值 样例: 例如n=12，k=1，在 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]，我们发现1出现了5次 (1, 10, 11, 12)
暴力破解
把每个数的每一个位都拿出来和k来比较，如果相同的话计数器加1就可以了，这也是最容易想到的一个方法，其实我还想过全部转化成字符串加起来，然后通过字符串去统计，估计也是可以的，先把暴力破解放在下面，有个小问题需要注意：循环条件是到0停止的，所以如果k是0的话，是要再加上一个的。
int digitCounts(int k, int n) {
int res = 0;
int temp;
for (int i = 0; i <= n; i++)
{
temp = i;
//这里一定要用临时变量把i替换掉，如果直接处理i,就死循环了。
while (temp!=0)
{
if (temp%10 == k)
res++;
temp/= 10;
}
}
if(k==0)
return res+1;
return res;
}tips:一开始直接在循环里把i拿来直接处理了，这样是不可以的，这种for循环不要再循环体内处理循环变量，虽然很傻逼的错误，但是不注意真的就会犯。
找规律
这个题一看也是一个数学题，我试着找了一下规律并不是很好找，于是就去百度了。 把这个问题分解成统计每一位上这个数出现的次数，以一个5位数位例：ABCDE,假设我们要找2出现的次数，我们以百位为例： 要分成下面几种情况： 百位小于2： 比如12123：百位一共可能出现多少个2 呢？
200~299 1200~1299 2200~2299 3200~3299 …… 11200~11299 这里面一共是多少个呢？ 一共有12100个，高位（比百位高的位）100（百位）
百位等于2： 比如12223
等于2的话情况稍微复杂一点，除了上述所说的这些呢，还有就是因为百位可以是2，那么低位的数就决定了要多多少个： 这里应该是：12*100+23
百位大于2： 比如12323
大于2的话，就表明前面的数可以再往上取一个： 200~299 1200~1299 2200~2299 3200~3299 …… 11200~11299 12200~12299 这样的话一共是 (12+1)*100
这样总结一下就是： 假设当前位位数用1，10，100等表示，分别代表个位，十位，百位等。 当前位<k: res=(高位)当前位数 当前位==k: res=(高位)当前位数+低位数+1 当前位>k: res=(高位+1)*当前位数
对于非零的来说，都是这样的，但是如果要查找的是0，这样就是不对的，如果查找的是0，只会进入后两种情况：
如果当前位等于0的话，比如12023 那么会有多少呢： 1000-1099 2000~2099 …… 11000~11099 再加上 12000~12023一共是24个。 那么应该是（高位-1）*当前位数+地位数+1；
如果当前位大于0的话：比如12223 除了上面的这些，还应加上12000~12099，所以应该是： （高位）*当前位数。
不过对于0的话还要处理两种特殊情况： 最高位不能查找0，所以如果是最高位查找0，则跳过； 最低位的0要加一个：因为会多一个0。 比如对于123：要查找个位的0，应该是13个，高位从0~12， 但是对于123：对于十位呢:应该是12*10，比公式要少，因为高位不能是0。 所以0是特殊情况：建议把查找0的单独来处理，这样逻辑上会清晰一些，也可把零归入前面的几种情况，但是对于是不是0要做额外处理。我一开始找的一个答案,对零的处理是不对的，没有考虑当前为也是0的情况，所以如果用103类似的这种数测试就是跑不过的，但是可以跑过lintcode的测试集（我怀疑里面根本没有包含这种情况），改了一点可以了：
int digitCounts(int k, int n)
{
if(k==0&&n==0) //先处理特殊情况
return 1;
int res=0; //计数器
int pow=1; //看是那一位，1代表个位，10代表十位，以此类推
int temp=n; //因为要求每一位的数，先把n存起来
while(temp!=0)
{
int dig=temp%10; //当前位
if(dig<k)
{
res+=(temp/10)*pow; //小于k的情况
}
else if(dig==k) //等于k的情况
{
if(k==0&&pow!=1) //如果不是最低位要-1
res+=(temp/10-1)*pow+n%pow+1;
else //如果是最低位，就不用减1了
res+=(temp/10)*pow+n%pow+1;
}
else //大于k的情况
{
if(!(k==0&&temp/10==0))
//排除没有最高位，寻找的数为0的情况，最高位是不可能有0的
{
if(k==0&&pow!=1)
{
res+=(temp/10)*pow;
}
else
{
res+=(temp/10+1)*pow; //总感觉这里有点问题，
}
}
}
temp/=10;
pow*=10;
}
return res;
}但是我还是想想把0单独来处理，这样好写很多，逻辑也更清晰：
int digitCounts(int k, int n)
{
if(k==0&&n==0) //先处理特殊情况
return 1;
int res=0; //计数器
int pow=1; //看是那一位，1代表个位，10代表十位，以此类推
int temp=n; //因为要求每一位的数，先把n存起来
if(k==0) //查找的是0
{
while(temp!=0)
{
int dig=temp%10;
if(dig==k)
{
res+=(temp/10-1)*pow+n%pow+1;
}
else if(dig>k&&temp/10!=0) //不允许最高位查找0
{
res+=(temp/10)*pow;
}
temp/=10;
pow*=10;
}
return res+1; //这里是加上0这一个
}
//查找的不是0
while(temp!=0)
{
int dig=temp%10; //当前位
if(dig<k)
{
res+=(temp/10)*pow; //小于k的情况
}
else if(dig==k) //等于k的情况
{
res+=(temp/10)*pow+n%pow+1;
}
else //大于k的情况
{
res+=(temp/10+1)*pow;
}
temp/=10;
pow*=10;
}
return res;
}