ARST打卡第256周

Linmin.Shan included in ARST

2024-03-30 1621 words 4 minutes

Contents

lc2952_需要添加的硬币的最小数量【TED演讲】您的年龄和成功机会之间的真实关系 ChatGPT消息发不出去解决方法 grpc重载成http开发途中发现一些有趣的东西

Algorithm

lc2952_需要添加的硬币的最小数量

被示例陷害

思路: 看示例全是添加的2的进制的数字，所以应该需要判断所有的2进制位置。

比如1，2，4能完成1-7. 1，2，4，8能完成1-15. 配合的其他数字就是别的数字能向上波动1-7或者1-15.

所以思路应该是先排序，然后把其他所有数字作为累加值，然后那种单独的一个2进制位数字就进行处理。判断能够逐步覆盖需要的全域。

二进制位就用index表示，index为0的时候，覆盖1 (2^1-1)，index为1，覆盖1，2，3 (2^2-1)。也就是覆盖的是 2^(index+1)-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


class Solution {
public:
    int minimumAddedCoins(vector<int>& coins, int target) {
        sort(coins.begin(), coins.end());
        int acc = 0;
        int index = 0;
        int ans = 0;
        for (int i = 0; i < coins.size(); i++) {
            while (coins[i] > 1 << index) {
                ans++;
                index++;
            }
            if (coins[i] == 1 << index) {
                index++;
            } else {
                acc += coins[i];
            }
            if (acc + (1 << (index + 1)) - 1 >= target) {
                return ans;
            }
        }
        // 还没达标
        while (acc + (1 << (index + 1)) - 1 < target) {
            ans++;
            index++;
        }
        return ans;
    }
};

WA了一发:

解答错误 289 / 628 个通过的测试用例

输入 coins = [1] target = 100000

输出 15 预期结果 16

发现判断的时候，已经index++过了，所以判断不用index++了。

然后还发现 accumulate 的 acc 也能够特化一些 index 二进制来。

 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


class Solution {
public:
    int minimumAddedCoins(vector<int>& coins, int target) {
        sort(coins.begin(), coins.end());
        int acc = 0;
        int index = 0;
        int ans = 0;
        for (int i = 0; i < coins.size(); i++) {
            while (coins[i] > acc + 1 << index) {
                ans++;
                index++;
            }
            // if (coins[i] == 1 << index) {
            //     index++;
            // } else {
                acc += coins[i];
                while (acc >= 1 << index) {
                    acc -= 1 << index;
                    index++;
                }
            // }
            if (acc + (1 << (index)) - 1 >= target) {
                return ans;
            }
        }
        // 还没达标
        while (acc + (1 << (index)) - 1 < target) {
            ans++;
            index++;
        }
        return ans;
    }
};

不用非要2进制数，直接翻倍即可

但是仍然一直WA，导致大脑糊涂了

然后去看了题解。

发现只需要添加累计值的2倍值就行，不一定是2的进制数….被示例陷害了…

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
public:
    int minimumAddedCoins(vector<int>& coins, int target) {
        sort(coins.begin(), coins.end());
        int ans = 0;
        int x = 1;
        int length = coins.size(), index = 0;
        while (x <= target) {
            if (index < length && coins[index] <= x) {
                x += coins[index];
                index++;
            } else {
                x <<= 1;
                ans++;
            }
        }
        return ans;
    }
};

Review

【TED演讲】您的年龄和成功机会之间的真实关系

成功概率是固定的，只要你尝试足够多，你就有机会把成功期望推动到1.

所以成功和年龄的关系是产能！当你年轻的时候，你尝试的频率比较大，因为成功的期望才比较高。

所以不要因为年龄而觉得没机会了。

只要持续尝试，就有机会提高成功期望。

Tips

ChatGPT消息发不出去解决方法

grpc重载成http开发途中发现一些有趣的东西:

Protobuf的go输出为啥都是指针类型，比如 int64 输出的 *int64, String 输出的事 *String

在 Go 中，Protocol Buffers（Protobuf）生成的 Go 代码中，字段类型通常被转换为指针类型。这是因为 Protobuf 的字段可以有默认值，而指针类型可以更好地表示一个值是否存在或者是否是默认值。这种设计决策主要是为了在序列化和反序列化过程中更好地处理零值。

例如，如果一个字段是 int64 类型，但在 Protobuf 消息中没有设置值，那么默认情况下这个字段将被序列化为零值 0。但在 Go 中，0 可能是一个合法的值。为了区分一个字段是否被设置过，生成的 Go 代码会将这个字段转换为指针类型 *int64，如果它为 nil，则表示这个字段未设置。

同样的情况也适用于字符串类型。在 Go 中，空字符串 "" 是一个合法的值。如果一个字段是字符串类型，但在 Protobuf 消息中没有设置值，那么默认情况下这个字段将被序列化为空字符串。为了区分字段是否被设置过，生成的 Go 代码会将这个字段转换为指针类型 *string，如果它为 nil，则表示这个字段未设置。

这种设计使得在 Go 中更容易地检查字段是否被设置，而不用担心默认值与实际设置的值之间的冲突。

原来如此。指针可以nil判断是否设置了。所以Protobuf生成的值都是指针值。

并且proto.Int64 可以直接返回 *int64 指针类型

json.Unmarshal可以让http-json字段和proto的字段可以轻松相互转换