ARST打卡第150周[150/521]

Algorithm

lc1012_至少有1位重复的数字

思路: 应该是不同的位数有一个规律，然后规律可以传递过去

n = 120的时候，包含100的数量，然后还有110 - 119这里有 10个，中间111是两者之间的

也就是说n有x位的时候，有前两位组成的重复，可以覆盖掉后面的所有数字10^{x-2}，然后再间隔一位，就是n为x-2位的时候的答案

所有先转化一下n为字符串(len为x)，看其第一位是否小于等于第二位

• 是则(str[i] - '0')*10^{x-2} + f(10^{x-2})
• 否则(str[i] - '0' - 1)*10^{x-2} + f(10^{x-2})

顺推就是在满位的时候(9,99,999) dp[1]=0, dp[2]=9, dp[3] = 9*10=90 dp[4]=9*100+dp[2]=909

所以对于其中的n=1000，可以认为是 dp[3] + 1 = 91，但是题目答案是262

所以发现漏了一些情况

比如说100,200,300

所以dp[3]不仅是9*10=90 (11x,22x,33x,…)

还有9*dp[2]=81(1xx,2xx,3xx)

还要减去重复的10个(111,222,333)

所以f(999) = 161

所以f(1000)= f(999) + 1 = 162

但是还是少考虑了f(999)应该还要包括dp[2] + dp[1],就是1位，和2位的情况，那也只加了9啊…

30分钟了，还是不完备，看看题解吧

作者：guanzhanyi 链接：https://leetcode-cn.com/problems/numbers-with-repeated-digits/solution/shuang-bai-suan-fa-by-guanzhanyi/

发现题解是反向思路…折腾了1个半小时…菜了

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

class Solution {
   public:
    int A(int m, int n) { 
        if (0 == n) {
            return 1;
        }
        int ans = 1;
        while (n--) {
            ans *= m;
            m--;
        }
        return ans;
    }
    int numDupDigitsAtMostN(int N) {
        //求N的位数n
        string strN = to_string(N);
        int n = strN.size();

        int used[10] = {0};
        int total = 0;

        //位数比n小的
        for (int i = 1; i < n; i++) {
            total += 9 * A(9, i - 1);
        }

        //位数和n一样的
        for (int i = 0; i < n; i++) {
            int num = strN[i] - 48;
            for (int j = (i == 0 ? 1 : 0); j < num; j++) {
                if (used[j] != 0)
                    continue;
                // 1-9中减去选掉的数位i(一开始选掉0位), n - (i + 1) 为剩余的位数
                total += A(9 - i, n - (i + 1));
            }
            if (++used[num] > 1)
                break;
            if (i == n - 1)
                total += 1;
        }
        return N - total;
    }
};

Review

【TED演讲】美国公立学校如何让孩子陷入贫困

投入多少教育资源，就会收获多少教育回报，不要让公共教育变成贫困保险，每一个孩子都值得好的教育资源，而不是被奖励教育资源，如果你有更大的能力，希望你捐赠他们，让他们也能有真正基本的教育保证，真正的公共教育

又想到整个世界都在让我们变成更好的人，但是不断竞争让我们总有人需要处于一个后面的排名，时常会心痛那些活得比我艰难的人，同时也会羡慕那些活得比我更加精彩的人，但是想了想，所有的结果，都是自己原生资源下面时间投入选择导致的结果，所以如果能过好自己的一生，做好自己的选择，那就和自己去做自己，而不要再去羡慕嫉妒别人的生活了，总之，和自己加油，并选择花点时间享受自己的生活，如此的生活，也许拿不到顶级的成就，但是始终在自己的能力线上不断进取，并且能享受生活的一个状态，这是我认为的一个好的人生状态，也许是平庸的重力，但至少自己不痛苦，也会有贡献价值的满足，从而过好幸福的自己，这不也是一种成功吗？因为人最终都只能和自己对比的。

Tips

C语言：inline，static inline

Share-消息队列和一致性hash在分发任务时的优劣对比

一致性hash的优点是均分，而且只用维护变动的节点(其他hash值一致)，然后缺点是如果机器性能不一样，就会出现弱鸡最终一直在执行

然后消息队列可能不能均分，以及节点变化需要其他进程来处理，但是如果机器性能不一样，可以让快机器做很多的事情，从而提高整体任务进度