2022-07-10

LeetCode Weekly Contest 301 自我解题思路

这周的周赛 Weekly Contest 301 难得一扫之前两次 1AC 惨败的阴霾，比较顺利的干掉了前三道。简单聊聊自己的思路。

¶Q1 2335. Minimum Amount of Time to Fill Cups

这道题其实属于 Tricky 题，也就是说严格来说并不是考察特定算法技巧，更多的其实是找特殊情况和归纳能力。

简单看一下题目条件：

You have a water dispenser that can dispense cold, warm, and hot water. Every second, you can either fill up 2 cups with different types of water, or 1 cup of any type of water.

You are given a 0-indexed integer array amount of length 3 where amount[0], amount[1], and amount[2] denote the number of cold, warm, and hot water cups you need to fill respectively. Return the minimum number of seconds needed to fill up all the cups.

总的来说就是有三种杯子，冷、温、热，各有若干个。每次可以往两个 不同的 水温要求的杯子的倒水；或者只往一个杯子里倒水。看看最少需要倒多少次可以倒满。

这个题目唯一需要注意的主要还是一类特殊情况。也就是量最多的那类杯子比其余两种杯子的总和还要多。那意味着多出来的部分两两相消是绝对消不掉的，只能一个个倒水。

然后其余情况下，就是两两相消的问题了，也就是直接 sum/2 + sum%2 就是需要操作的次数。那根据上述思路，代码自然就写出来了：

int cmp(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}
int fillCups(int* amount, int amountSize){
    qsort(amount, 3, sizeof(int), cmp);
    int res = 0;
    if (amount[2] > amount[0] + amount[1]) {
        res += amount[2] - amount[0] - amount[1];
        amount[2] = amount[0] + amount[1];
    }
    int sum = amount[0] + amount[1] + amount[2];
    res += sum/2; res += sum%2;
    return res;
}

这里稍微需要对杯子的 array 做一下 qsort() 处理。这样可以更方便获得数组的最大值。

¶Q2 2336. Smallest Number in Infinite Set

这次第二道倒是挺非主流的。并不是让你实现一个功能函数，而是一串函数。让人回想起在 C 里面手撸优先队列的恶心感。不过题设倒是比较完备的 PQ 要简单不少：

You have a set which contains all positive integers [1, 2, 3, 4, 5, ...].

Implement the SmallestInfiniteSet class:

SmallestInfiniteSet() Initializes the SmallestInfiniteSet object to contain all positive integers.
int popSmallest() Removes and returns the smallest integer contained in the infinite set.
void addBack(int num) Adds a positive integer num back into the infinite set, if it is not already in the infinite set.

说白了就是会有一个 int 数组，然后里面都是正整数。然后需要写一系列函数 SmallestInfiniteSet(Init)、Pop、AddBack，作用分别是初始化一个正整数数组，移除并返回当前数组种最小的数，往数组里加入一个数（如果此时不存在这个数的话）。
然后测试用例的话本质会输入两个显式入参和一个隐式入参。显示的分别为：

描述了函数调用数据的字符串数组。
描述上一数组入参的字符串数组。

隐式入参为：

完备无限正整数合集。

由于本题的 int 数组是有元素数量上限的，所以解决起来其实就比较舒服：

1 <= num <= 1000
At most 1000 calls will be made in total to popSmallest and addBack.

思路首先是描述 SmallestInfiniteSet 的变量结构。本质就是一个长度超过 1000 的 int 数组。没什么可以说的。

然后来到了初始化函数，这里初始化函数本质是就是创建一个上面刚刚定义的 SmallestInfiniteSet 结构体，然后对其进行 malloc 和初始化赋值。

接下来就是最困难的部分，Pop 函数赋值。这里就是我经常吐槽的 C 语言恶心的地方了，其他语言一行切片语法就能解决的问题， C 你必须手撸一个 for 循环来处理。内容倒是很简单，把数组中遇到的第一个非 0 整数找出来。由于后续说明里提到了 C 语言下系统会帮你调 Free 函数，所以只要找值为 0 的 index 就可以了。

而 AddBack 就更简要了，只需要把下一次 Pop 的触发指标加入数组即可。也就是把在 index = num 的元素设置为 0 即可。

typedef struct {
    int nums[1001];
} SmallestInfiniteSet;


SmallestInfiniteSet* smallestInfiniteSetCreate() {
    SmallestInfiniteSet *sis;
    sis = malloc(sizeof(SmallestInfiniteSet));
    memset(sis, 0, sizeof(SmallestInfiniteSet));
    return sis;
}

int smallestInfiniteSetPopSmallest(SmallestInfiniteSet* obj) {
    int i, tmp;
    for (i = 1; i < 1001; ++i) {
        if (obj->nums[i] == 0) {
            tmp = i;
            obj->nums[i] = i;
            return tmp;
        }
    }
    return i;
}

void smallestInfiniteSetAddBack(SmallestInfiniteSet* obj, int num) {
    obj->nums[num] = 0; return;
}

void smallestInfiniteSetFree(SmallestInfiniteSet* obj) {
    free(obj); return;
}

/**
 * Your SmallestInfiniteSet struct will be instantiated and called as such:
 * SmallestInfiniteSet* obj = smallestInfiniteSetCreate();
 * int param_1 = smallestInfiniteSetPopSmallest(obj);
 
 * smallestInfiniteSetAddBack(obj, num);
 
 * smallestInfiniteSetFree(obj);
*/

¶Q3 2337. Move Pieces to Obtain a String

这道题是这次 Contest 我自己最喜欢的一道题目。怎么说呢，个人偏好更喜欢 Tricky 的题目，这可能也是因为自己基础不扎实的原因。不过言归正传，来说说着这道题。

题干不复杂，就是给你两个字符串 start & target，长度一致，且只由三种字符 L、R、_ 组成。然后我们可以对 start 里的 L、R 字符做操作。其中：

L 能且只能和左边的 _ 做位置交换，次数无限。
R 能且只能和右边的 _ 做位置交换，次数无限。
如果经过不限次的位置交换后，start 可以变成 target，则返回 true，反之返回 false。

这里其实思路是，要把 _ 看作一个特殊字符，因为是可以被交换的。同时，由于 L 和 R 的位置不能交换，所以 start 和 target 必须满足以下条件，返回才是 true：

start 和 target 去掉所有的 _ 字符后，应该是完全一模一样的数组。
任何一个 start 中的 L 都不应该比其在 target 中对应的那个 L 更靠左。
任何一个 start 中的 R 都不应该比其在 target 中对应的那个 R 更靠右。

上面三个条件一出，那其实伪代码都已经有了，所以直接写答案即可：

bool canChange(char * start, char * target){
    int len = strlen(start);
    int p1 = 0, p2 = 0;
    while (p1 < len && p2 < len) {
        while (start[p1] == '_') {p1++;}
        while (target[p2] == '_') {p2++;}
        if (start[p1] != target[p2]) {
            return false;
        } else {
            if (start[p1] == 'L') {
                if (p1 < p2) {
                    return false;
                }
            } else {
                if (p1 > p2) {
                    return false;
                }
            }
            p1++; p2++;
        }
    }
    return true;
}

Thank u for reading.

Regards，

Kivinsae's Nest

化繁为简

LeetCode Weekly Contest 301 自我解题思路

¶Q1 2335. Minimum Amount of Time to Fill Cups

¶Q2 2336. Smallest Number in Infinite Set

¶Q3 2337. Move Pieces to Obtain a String