Contents

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值一致),然后缺点是如果机器性能不一样,就会出现弱鸡最终一直在执行

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