LeetCode笔记：Weekly Contest 215 比赛记录_输入四个整数m、n、introvertscount和extrovertscount。有一个m*n网格

• LeetCode笔记：Weekly Contest 215
  • 0. 赛后总结
  • 1. 题目一
    • 1. 解题思路
    • 2. 代码实现
  • 2. 题目二
    • 1. 解题思路
    • 2. 代码实现
  • 3. 题目三
    • 1. 解题思路
    • 2. 代码实现
  • 4. 题目四
    • 1. 解题思路
    • 2. 代码实现
    • 4. 算法优化

0. 赛后总结

这一次的比赛排名的话还算是凑合，国内327，世界830，总算也是在前10%，但是过程真的是呵呵了，整整错了4次，其中有3次都是极其愚蠢的错误，然后最后还提前了半小时放弃了，最后一题真心完全没有思路，因此整体的感觉就极其的糟心。

唉，啥时候才能稳稳地把4题全部搞定啊。。。

加油吧，少年。

1. 题目一

给出题目一的试题链接如下：

• 5601. 设计有序流

1. 解题思路

这一题本质上来说难点完全在于读题上面，看懂了题目也就能直接把这题搞定了，看不懂题目的话就呵呵了。。。

其实本质来说，这一题就是给了一个乱序序列，然后给了一个初始的位置指针ptr为1，然后逐个将乱序序列进行填入，当填入的元素恰好为ptr位置指向的元素时，将ptr向后移动至下一个还未被填入元素的位置，并返回这些值。

2. 代码实现

给出python的代码实现如下：

class OrderedStream:

    def __init__(self, n: int):
        self.val = ["" for _ in range(n+1)]
        self.flag = 1
        self.n = n


    def insert(self, id: int, value: str) -> List[str]:
        self.val[id] = value
        res = []
        if id == self.flag:
            while self.flag <= self.n and self.val[self.flag] != "":
                res.append(self.val[self.flag])
                self.flag += 1
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

提交代码评测得到：耗时220ms，占用内存14.7MB。

当前最优的代码实现耗时216ms，其实现方式和我们略有不同，我们保留了元素，使用了一个list来保存元素，而他们直接使用了一个储存元素。

但是，本质来说，并没有什么太大的差异，因此就不多做展开了。

2. 题目二

给出题目二的试题链接如下：

• 5603. 确定两个字符串是否接近

1. 解题思路

这一题本质在于题目的分析，虽然我在这道题目上粗心翻车了一次，不过分析清楚了题目的条件之后事实上这道题目是十分简单的：

1. 由于可以任意次调换两元素的位置，因此序列是顺序无关的；
2. 由于可以将任意两元素种类整体进行调换，因此，序列是字母种类无关的。

因此，只要满足下述两个条件，两个字符串（记作s1与s2）就是接近的：

1. 两个字符串有着相同种类的字母，即一个字母出现在s1中，则必须出现在s2中，反之亦然；
2. s1中每个字母的数量集合与s2中字母的数量集合是完全一致的，即s1中如果有三种字符，数量分别为[a,b,c]，则s2中的三种字符的个数必须同样为[a,b,c]。

2. 代码实现

给出python代码实现如下：

class Solution:
    def closeStrings(self, word1: str, word2: str) -> bool:
        s1 = Counter(word1)
        s2 = Counter(word2)
        return sorted(s1.keys()) == sorted(s2.keys()) and sorted(s1.values()) == sorted(s2.values())
1
2
3
4
5

提交代码评测得到：耗时128ms，占用内存14.6MB。属于当前的最优代码实现。

3. 题目三

给出题目三的试题链接如下：

• 5602. 将 x 减到 0 的最小操作数

1. 解题思路

这题拿到题目后我的第一思路就是使用一个dp算法暴力求解，然后就超时了。。。

后来仔细考虑了一下这道题目，感觉和双向搜索算法有点类似，因为元素都是大于0的，因此，我们首先给出所有的元素都来自右侧时能够达到x，然后看需要多少元素，然后每次在左侧加入一个元素，然后从右侧删除元素，使之重新达到x。

重复上述过程，直至所有的元素都来自左侧。

2. 代码实现

给出python代码实现如下：

class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        tot = sum(nums)
        if tot < x:
            return -1
        elif tot == x:
            return len(nums)
        
        n = len(nums)
        l, r = 0, n-1
        s = 0
        used = 0
        while s < x:
            s += nums[r]
            r -= 1
            used += 1
        res = -1 if s != x else used
        while r < n-1 and l <= r :
            used -= 1
            r += 1
            s -= nums[r]
            while s < x and l <= r:
                s += nums[l]
                l += 1
                used += 1
            if s == x:
                res = used if res == -1 else min(res, used)
        return res
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

提交代码评测得到：耗时1164ms，占用内存28.9MB。

当前最优的代码实现耗时652ms，看了一下他的算法，本质上来说和我们没有什么太大的差别，不过他用了一个字典来保存之前的和，从而优化了效率。

有兴趣的读者可以自行去看一下，这里我就不过多展开了。

4. 题目四

给出题目四的试题链接如下：

• 5604. 最大化网格幸福感

1. 解题思路

这一题我们在比赛中完全没有思路，比赛结束之后参考了awice大佬的解法，给出一种动态规划的思路如下：

• 每次装填一行，考察每一次合法装填之后的的分数变化，知道全部的行都被装填完毕。

2. 代码实现

给出python代码实现如下：

class Solution:
    def getMaxGridHappiness(self, m: int, n: int, introvertsCount: int, extrovertsCount: int) -> int:        
        @lru_cache(None)
        def dp(r, intro, extro, prev):
            if r >= m:
                return 0
            ans = 0
            for row in itertools.product(range(3), repeat=n):
                _intro = row.count(1)
                _extro = row.count(2)
                if _intro > intro or _extro > extro:
                    continue
                score = 0
                for i in range(n):
                    if row[i] == 0:
                        continue
                    elif row[i] == 1:
                        score += 120
                        if i-1 >= 0 and row[i-1] != 0:
                            score -= 30
                        if i+1 < n and row[i+1] != 0:
                            score -= 30
                        if prev[i] == 1:
                            score -= 60
                        elif prev[i] == 2:
                            score -= 10
                    else:
                        score += 40
                        if i-1 >= 0 and row[i-1] != 0:
                            score += 20
                        if i+1 < n and row[i+1] != 0:
                            score += 20
                        if prev[i] == 1:
                            score -= 10
                        elif prev[i] == 2:
                            score += 40
                score += dp(r+1, intro - _intro, extro - _extro, tuple(row))
                ans = max(ans, score)
            return ans

        return dp(0, introvertsCount, extrovertsCount, tuple([0] * n))
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

但是，上述代码出现了超时问题，因此，我们不得不完全地按照awice大佬的方式强行加上两个对于复杂情况的特殊处理，从而使得勉强不会超时：

1. 列数小于行数，此时对于每一行要考虑的情况会更少；
2. 针对5*5的情况，可以不会冲突地摆入所有的人，因此可以直接在外部处理掉；

因此，修正代码得到：

class Solution:
    def getMaxGridHappiness(self, m: int, n: int, introvertsCount: int, extrovertsCount: int) -> int:
        if m < n:
            return self.getMaxGridHappiness(n, m, introvertsCount, extrovertsCount)
        
        if n >= 5:
            bonus = {0:0, 1:0, 2:40, 3:80, 4:160, 5:200, 6:280}
            return 120 * introvertsCount + 40 * extrovertsCount + bonus[extrovertsCount]
        
        @lru_cache(None)
        def dp(r, intro, extro, prev):
            if r >= m:
                return 0
            ans = 0
            for row in itertools.product(range(3), repeat=n):
                _intro = row.count(1)
                _extro = row.count(2)
                if _intro > intro or _extro > extro:
                    continue
                score = 0
                for i in range(n):
                    if row[i] == 0:
                        continue
                    elif row[i] == 1:
                        score += 120
                        if i-1 >= 0 and row[i-1] != 0:
                            score -= 30
                        if i+1 < n and row[i+1] != 0:
                            score -= 30
                        if prev[i] == 1:
                            score -= 60
                        elif prev[i] == 2:
                            score -= 10
                    else:
                        score += 40
                        if i-1 >= 0 and row[i-1] != 0:
                            score += 20
                        if i+1 < n and row[i+1] != 0:
                            score += 20
                        if prev[i] == 1:
                            score -= 10
                        elif prev[i] == 2:
                            score += 40
                score += dp(r+1, intro - _intro, extro - _extro, tuple(row))
                ans = max(ans, score)
            return ans

        return dp(0, introvertsCount, extrovertsCount, tuple([0] * n))
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
44
45
46
47
48

提交代码评测得到：耗时4524ms，占用内存24.3MB。

而当前的最优代码实现耗时仅604ms，因此还需要进一步对代码进行优化。

4. 算法优化

上述代码中最为累赘的部分在于对于每一行都考察了所有可能的排布，但事实上由于introCounts和extroCounts的限制，其中只会有少部分才会是合法的，因此会产生大量的计算冗余。

看了一下当前的最优解法，他是直接采用了dfs的计算方式进行了代码实现，即考虑每一个点可能的填入情况。

但是，这里需要注意以下两点：

1. 当剩下所有的所有人都拿到最高分都无法达到历史最高分时，可以直接终止dfs过程；
2. 每个点都应该被尽可能地利用起来，即只有当当前点的前一个点和上一个点至少有一个不为空的情况下才允许当前点不填，否则必须填入一个人。

下面，我们仿照其给出我们自己的代码实现。

class Solution:
    def getMaxGridHappiness(self, m: int, n: int, introvertsCount: int, extrovertsCount: int) -> int:
        grid = [[0 for _ in range(n)] for _ in range(m)]
        score = 0
        
        def get_score(r, c):
            nonlocal grid
            if grid[r][c] == 1:
                score = 120
                if r-1 >= 0:
                    if grid[r-1][c] == 1:
                        score -= 60
                    elif grid[r-1][c] == 2:
                        score -= 10
                if c-1 >= 0:
                    if grid[r][c-1] == 1:
                        score -= 60
                    elif grid[r][c-1] == 2:
                        score -= 10
            else:
                score = 40
                if r-1 >= 0:
                    if grid[r-1][c] == 1:
                        score -= 10
                    elif grid[r-1][c] == 2:
                        score += 40
                if c-1 >= 0:
                    if grid[r][c-1] == 1:
                        score -= 10
                    elif grid[r][c-1] == 2:
                        score += 40
            return score
        
        def dfs(r, c, intro, extro, _score):
            nonlocal grid, score
            if c >= n:
                dfs(r+1, 0, intro, extro, _score)
                return
            if r >= m or (intro == 0 and extro == 0):
                score = max(_score, score)
                return
            if _score + 120 * (intro + extro) < score:
                return
            if intro > 0:
                grid[r][c] = 1
                dfs(r, c+1, intro-1, extro, _score + get_score(r,c))
                grid[r][c] = 0
            if extro > 0:
                grid[r][c] = 2
                dfs(r, c+1, intro, extro-1, _score + get_score(r,c))
                grid[r][c] = 0
            if (r > 0 and grid[r-1][c] != 0) or (c > 0 and grid[r][c-1] != 0):
                dfs(r, c+1, intro, extro, _score)
            return
        
        dfs(0, 0, introvertsCount, extrovertsCount, 0)
        return score
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57

提交代码评测得到：耗时916ms，占用内存14.2MB。