[mock]10月11日

第二次mock。
出的题是，假设有一个地区不能使用7，都用之后的数字代替，比如8代表7,18代表16（中间有7和17）.那么给出一个这个地区的数X，求普通地区的数Y。
首先是找规律，发现其实就是找给出的数X之前带有7的个数diff，然后输出就是X-diff。
之后就是怎么找带有7的数字的个数。
想的过程中，隐隐约约觉得，比如求一个数1394，那么应该要用到10以内或100以内的带7的数字的个数，于是就想把它们存起来。
F[1]表示1~10之间的带7的数字，是1，然后F[2]表示1~100之间的，是19。
然后推出了递推公式，F[i+1]=F[i]*9 - 10 ^(i+2）
然后拿个数字做试验，结果一开始拿了个错误的数，678，还自以为有大于等于7和小于7的，但其实这个地区的数字不能有7。
那么就拿58举例子，算出来之后觉得有点小，然后意识到这只是diff。
接着写程序。中间犯过的小错误不断。一是x = x / 10之后，把x改掉了，但最后仍然ans = x - diff，就错了。二是写了10 ^ i当做求幂值，其实要用pow。三是循环里没有i++。然后是很多边界的i+1之类的。
但整体这次感觉反应还行。
代码：

int convert(int x)

{

    int F[50];

    F[0] = 0;

    for (int i = 1; i <= 50; i++)

    {

        F[i] = F[i - 1] * 9 + pow(10, i - 1); // F[2] = F[1] * 9 + 10 ^ 1; F[1] = F[0] * 9 + pow(10, 1-1) = 1;

    }

    int original = x;

    // calc how many num with 7 < x

    int diff = 0;

    int i = 0;

    while (x != 0)

    {

        int k = x % 10;

        x = x / 10;

        if (k < 7)

        {

            diff += F[i] * k;

        }

        else // k > 7

        {

            diff += F[i] * (k - 1) + pow(10, i);  // k == 8

        }

        i++;

    }

    int ans = original - diff;

    return ans;

}

巴特西

[mock]10月11日

最新文章

热门文章