XieNaoban's Blog
0%

LeetCode 第 38 场双周赛

发表于 分类于 ， 阅读次数： 评论次数：
本文字数： 2.7k 阅读时长 ≈ 2 分钟

一阵子没打了, 竟然四题都做出来了.

5539. 按照频率将数组升序排序

题解

很暴力地构建 {数值: 频率} 字典, 再很暴力地根据频率构建 {频率: 降序数值列表}. 最后根据频率升序输出.

垃圾代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def frequencySort(self, nums: List[int]) -> List[int]:
        mp = {}
        for n in nums: mp[n] = mp.get(n, 0) + 1
        mp2 = {}
        for k, v in mp.items():
            mp2.setdefault(v, []).append(k)
        res = []
        for k in sorted(mp2.keys()):
            v = sorted(mp2[k], reverse=True)
            for n in v:
                for i in range(int(k)):
                    res.append(n)
        return res

5540. 两点之间不包含任何点的最宽垂直面积

题解

Point.Y 是干扰项, 没用. 直接对每个 Point.X 排序, 找出相邻 Point.X 最大的间隔. 比第一题还水.

垃圾代码

1
2
3
4
5
6
7
8
9
class Solution:
    def maxWidthOfVerticalArea(self, points: List[List[int]]) -> int:
        lst = []
        for p in points: lst.append(p[0])
        lst.sort()
        x = 0
        for i in range(1, len(lst)):
            x = max(x, lst[i] - lst[i - 1])
        return x

5541. 统计只差一个字符的子串数目

题解

对 t 构造前缀树 trie, 同时 trie 每一层保存从根节点到目前位置的字串个数. 然后以 s 的每个字符作为起点去递归匹配 trie, 递归匹配时考虑 目前仍无字符不同 与 目前已有一个字符不同 两种情况, 返回所有子情况的个数的求和.

垃圾代码 (讲道理 Python 写 Trie 属实方便)

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:
    def countSubstrings(self, s: str, t: str) -> int:
        trie = {}
        for i in range(len(t)):
            nxt = trie
            for c in t[i:]:
                nxt = nxt.setdefault(c, {})
                nxt[''] = nxt.get('', 0) + 1
        # print(trie)
        res = 0
        for i in range(len(s)):
            res += self.cal(s, i, trie)
        return res
            
    def cal(self, s, idx, trie, diff=False):
        res = 0
        if idx >= len(s): return res
        for c in trie:
            if c == '': continue
            next_trie = trie[c]
            if c == s[idx]:
                if diff: res += next_trie['']
                res += self.cal(s, idx + 1, next_trie, diff)
            else:
                if diff: pass
                else:
                    res += next_trie['']
                    res += self.cal(s, idx + 1, next_trie, True)
        return res

5542. 通过给定词典构造目标字符串的方案数

题解

动态规划. 设 \(Words\) 每个 \(Word\) 长度为 \(L_w\), \(Target\) 长度为 \(L_t\), \(N(i, j)\) 为 \(Target\) 第 \(i\) 个字符在 \(Words\) 第 \(j\) 列出现次数. \(Words\) 用前 \(j\) 个字符成功匹配 \(Target\) 前 \(i\) 个字符的可能情况数 \(DP(i, j)\) 为

\[ DP(i, j) = DP(i - 1, j - 1) \times N(i, j) + DP(i, j - 1) \]

遍历时 \(j\) 从 \(i\) 而不是 \(0\) 开始, 因为大于等于 \(i\) 个字符才可能匹配上 \(i\) 个字. 同理 \(j\) 大于 \(L_w - L_t + i\) 时剩下的字符也不可能匹配得完, 即 \(j \in [i, L_w - L_t + i]\).

可以看到状态转移方程只跟 \(i\) 和 \(i - 1\) 有关, 所以可以将 DP 空间从 \(L_w \times L_t\) 降为 \(L_w\), 遍历 \(j\) 时从后往前遍历以免覆盖 \(i - 1\) 的状态.

其实还能进一步降 DP 空间降到 \(L_w - L_t + 1\), 因为 \(j\) 每次遍历的范围就是 \([i, L_w - L_t + i]\). 但是我懒.

不是很垃圾的代码

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 numWays(String[] words, String target) {
        final int MOD = (int)1e9 + 7;
        int lw = words[0].length(), lt = target.length();
        long[] dpa = new long[lw];
        long[][] n26 = new long[lw][26];
        for (String w : words) {
            for (int i = 0; i < lw; ++i) {
                ++n26[i][w.charAt(i) - 'a'];
            }
        }
        // System.out.println(Arrays.deepToString(n26));
        int c = target.charAt(0) - 'a';
        for (int j = 0; j <= lw - lt; ++j) {
            dpa[j] = n26[j][c];
            if (j > 0) dpa[j] += dpa[j - 1];
        }
        // System.out.println(Arrays.toString(dpa));
        for (int i = 1; i < lt; ++i) {
            c = target.charAt(i) - 'a';
            for (int j = lw - (lt - i); j >= i; --j) {
                dpa[j] = dpa[j - 1] * n26[j][c];
                dpa[j] %= MOD;
            }
            for (int j = i + 1; j <= lw - (lt - i); ++j) {
                dpa[j] += dpa[j - 1];
                dpa[j] %= MOD;
            }
        // System.out.println(Arrays.toString(dpa));
        }
        return (int)dpa[lw - 1];
    }
}