讨论/题目交流/🏆 第 184 场力扣周赛/
🏆 第 184 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 数组中的字符串匹配
4 分 - 查询带键的排列
5 分 - HTML 实体解析器
7 分 - 给 N x 3 网格图涂色的方案数

展开讨论
力扣 (LeetCode)发起于 2020-04-12
共 46 个讨论

python 题解 https://leetcode-cn.com/circle/article/oCBsqp/

5380.数组中的字符串匹配

暴力二重循环,因为 words 长度小于 100,肯定不会超时,但是注意每次找到了子串要 break,否则可能有重复。

class Solution:
    def stringMatching(self, words: List[str]) -> List[str]:
        ans = []
        for i in range(len(words)):
            for j in range(len(words)):
                if i == j: continue
                if words[i] in words[j]:
                    ans.append(words[i])
                    break
        return ans

5381.查询带键的排列

这题没有想到好的解法,直接写了最普通的模拟,本地试了下,还挺快的,应该会有更好的办法吧。

class Solution:
    def processQueries(self, queries: List[int], m: int) -> List[int]:
        m = min(m, max(queries))
        p = [i+1 for i in range(m)]
        ans = []
        for x in queries:
            i = p.index(x)
            ans.append(i)
            x = p.pop(i)
            p.insert(0, x)
        return ans

5382.HTML 实体解析器

这题对于 python 来说形同虚设。我直接用了替换函数,注意 python 的字符串是不可变类型,每次生成新对象。

class Solution:
    def entityParser(self, text: str) -> str:
        text = text.replace('"', '"')
        text = text.replace(''', '\'')
        text = text.replace('&', '&')
        text = text.replace('>', '>')
        text = text.replace('&lt;', '<')
        text = text.replace('&frasl;', '/')
        return text

感谢评论去两位同学指正,这个代码如果 遇到 &amp;gt; 输出的结果是 > ,但是这个实际上是把 &amp; 转义出的 &gt; 组合了,所以代码可以把 text = text.replace('&amp;', '&') 放到最后一句以来避免,代码如下:

class Solution:
    def entityParser(self, text: str) -> str:
        text = text.replace('&quot;', '"')
        text = text.replace('&apos;', '\'')
        text = text.replace('&amp;', '&')
        text = text.replace('&gt;', '>')
        text = text.replace('&lt;', '<')
        text = text.replace('&frasl;', '/')
        return text

但是我又发现,判题系统目前对 &amp;gt; 的输出实际上是 >
那么再试下 "&amp;gt;" 输出是 "&amp;gt;",又没有递归处理,看了是判题机有问题。
image.png
image.png

5383.给 N x 3 网格图涂色的方案数

有一个很类似的题目,就是 一个 n 位的数组,每个位置可以填 0,1,2,但是相邻的不能重复,求一共有多少中填法。(好像还有点别的附加条件)

这道题目三种颜色没有任何区别,就用 ABC 来代表,n = 1 时
A 开头有:
ABA ABC ACA ACB
B 开头有:
BAB BAC BCA BCB
C 开头有:
CAB CAC CBA CBC

这里总结起来只有两种模式:ABA 即第一第三个一样 和 ABC 即三个都不同。

ABA 模式有 6 种:ABA ACA BAB BCB CAC CBC
ABC 模式有 6 种:ABC ACB BAC BCA CAB CBA

第二层需要再第一层的基础上安排,而且只和他的模式有关,而与具体颜色无关。

如果第一层是 ABA 模式(这个模式里的任意情况都会造成相同的结果):

第一层   ABA   ABA   ABA   ABA   ABA
         |||   |||   |||   |||   |||
第二层   BAB   BAC   BCB   CAC   CAB

结果有 5 种,同样,我们只看模式,不看具体颜色,结果种有 ABA 模式 3 种,ABC 模式 2 种

如果第一层是 ABC 模式(这个模式里的任意情况都会造成相同的结果):

第一层   ABC   ABC   ABC   ABC
         |||   |||   |||   |||
第二层   BAB   BCA   BCB   CAB

结果有 4 种,同样,我们只看模式,不看具体颜色,结果种有 ABA 模式 2 种,ABC 模式 2 种

我们代码里用 aba 表示当前层的 ABA 模式种数,abc 表示当前层 ABC 模式种数,而 aba2,abc2 表示下一层。这样就可以地推计算种类数量:

MOD = 1000000007
aba2 = (aba * 3 + abc * 2) % MOD
abc2 = (aba * 2 + abc * 2) % MOD

aba 和 abc 初始都为 6

class Solution:
    def numOfWays(self, n: int) -> int:
        aba = 6
        abc = 6
        MOD = 1000000007
        for _ in range(n-1):
            aba2 = (aba * 3 + abc * 2) % MOD
            abc2 = (aba * 2 + abc * 2) % MOD
            aba, abc = aba2, abc2
        return (aba + abc) % MOD
25

A: 数组中的字符串匹配

注意到数组的长度只有 100,可以逐一枚举数组内的字符串,当它是其他串的子串时可以作为答案。

B: 查询带键的排列

注意到 m 只有 1000,操作次数(queries.length)也只有 1000,直接暴力模拟这个过程即可:

  1. 扫描数组确定数字所在下标
  2. 删除该数字
  3. 将该数字插入数组的头部

这种操作场景,用 deque 比 vector 性能更好。

C: HTML 实体解析器

  1. 能被替换的字符串都是以 '&' 开头的
  2. 顺序扫描原串 text,遇到非 '&' 直接保留
  3. 遇到是 '&' 则判断后面连续的 4 ~ 7 个字符组成的子串是否为需要替换的字符串(最短的是 ">" 最长的是 "⁄" 长度分别为 4 和 7)
  4. 替换完后,扫描 text 的指针直接跳跃到替换后的字符下标;因此该指针不会回溯移动

D: 给 N x 3 网格图涂色的方案数

要确定一行的颜色,受两个因素影响:该行的相邻格子的颜色,上一行的配色。可见这是个递推关系。

每个格子能填 3 种颜色,因此一共有 27 种方案,以状态压缩的方式,用整数 [0, 26] 表示每种配色。但其中只有 12 种是合法的,即 Example 1 里面的 12 种。因此我们可以先把 12 种配色保存下来。

还要考虑上一行的配色对本行配色的影响。当上一行的配色确定后,本行可选的配色也可以确定。也把这个限制关系保存下来。

确定状态方程:

  1. dp[row][col] 表示合法构造了前 row 行且第 row 的配色为 col 的总方案数
  2. dp[row][col] = sum(dp[row-1][col_1]),其中 col 和 col_1 是不冲突的两种配色
  3. 最终答案 result = sum(dp[n-1][col]),col 来自那合法的 12 种方案

关注微信公众号查看代码

关注微信公众号 不爱睡觉的大猪,查看完成代码吧!
tmp.jpg

10

前三题好像都是暴力过去的,放一个第四题的思路,纪念我自己最短的一次第四题题解。

class Solution:
    def numOfWays(self, n: int) -> int:        
        same, diff = 6, 6    # 代表初始时第一行两类各6种
        for k in range(1,n):            
            same, diff = same * 3 + diff * 2, same * 2 + diff * 2
        return (same + diff) % (10 ** 9 + 7)
    
    
    # 所有排列其实只有两种:
    #     第一类:第一格和第三格相同的:
    #     第一类:第一格和第三格不同的
    # 具体是什么颜色不重要,只要区分这两类就行了
    # 在已知上一行时,下一行的演化是:
    #     如果上一行是第一类:共5种可能,其中3种一类,2种二类
    #     如果上一行是第二类:共4种可能,其中2种一类,2种二类
    #     然后更新这一行每一类的个数,一直迭代下去就行了
3

LeetCode 第 184 场周赛解题报告 (C++)

5380. 数组中的字符串匹配

O(n^2) 暴力枚举,具体思路见注释。介绍一下 string 的 find 函数。

  • std::string::find 函数。接收一个字符串,返回该字符串第一次出现的位置。
  • 如果没有找到,返回 std::string::npos。
class Solution {
public:
    vector<string> stringMatching(vector<string>& words) {
        vector<string> res;
        //枚举每个字符串作为子串。
        for(int i = 0; i < words.size(); i++) {
            //对于每个子串,枚举所有字符串作为其母串。
            for(int j = 0; j < words.size(); j++) {
                //母串和子串不能是同一个字符串,所以需要 i != j
                //检查words[i] 是否是 words[j] 的子串。
                if(i != j && words[j].find(words[i]) != std::string::npos) {
                    res.push_back(words[i]);
                    break;
                }
            }
        }
        return res;
    }
};

5381. 查询带键的排列

O(m*q) 暴力枚举。使用链表模拟即可,具体思路见注释。简单介绍下 std::list 的 insert 和 erase 函数。

  • std::list::insert 可以接受一个std::list::iterator iter和一个待插入元素 p。该函数会将 p 插入到 iter 之前。
  • std::list::erase 可以接受一个std::list::iterator iter。该函数会删除 iter 指向的结点。
class Solution {
public:
    vector<int> processQueries(vector<int>& queries, int m) {
        list<int> dataList;
        //初始化排列。
        for(int i = 1; i <= m; i++) {
            dataList.push_back(i);
        }
        vector<int> res;
        //处理每个请求
        for(auto v : queries) {
            auto it = dataList.begin();
            int ans = 0;
            //O(m)的查找当前询问的位置。
            for(auto it = dataList.begin(); it != dataList.end(); ++it, ++ans) {
                // 找到了
                if(*it == v) { 
                    res.push_back(ans); //记录答案
                    //在链表的头部插入该元素。
                    dataList.insert(dataList.begin(), *it);
                    //删除旧的元素。
                    dataList.erase(it);
                    break;
                }
            }
        }
        return res;
    }
};

5382. HTML 实体解析器

准备数据容器

使用 unordered_map<string, string> 记录HTML的特殊字符和它们对应的字符实体。
使用一个新的string记录答案。

遍历 text

从头遍历 text,如果以 text[i] 为起点的字符串在 unordered_map 中出现了,那么将对应的字符实体放入 string 中。否则直接将 text[i] 放入string中。具体细节见注释。

class Solution {
public:
    string entityParser(string text) {
        string res;
        unordered_map<string, string> dict; //将特殊字符和字符实体放入 dict 中。
        dict["&quot;"] = "\"";
        dict["&apos;"] = "'";
        dict["&amp;"] = "&";
        dict["&gt;"] = ">"; 
        dict["&lt;"] = "<";
        dict["&frasl;"] = "/";
        
        for(int i = 0, n = text.size(); i < n; ) {//遍历text
            bool match = false;
            //判断以text[i]为起点的字符串是否是特殊字符
            for(auto p = dict.cbegin(); p != dict.cend(); p++) {
                //匹配上了
                if(text.substr(i, p->first.size()) == p->first) {
                    res += p->second;
                    i += p->first.size(); //i 后移 p->first.size()
                    match = true; //标记已匹配
                    break;
                } 
            }
            if(match) {
                continue;
            }
            res += text[i++]; //未匹配上,将 text[i] 放入 res。i 后移一位。
        }
        return res;
    }
};

5383. 给 N x 3 网格图涂色的方案数

解题套路:状态压缩 + 递推。

状态压缩

用一个数字表示集合的一种状态。
比如在本题中,三个并列的格子可以看作是一个集合。我们用数字表示这个集合的状态,也就是染色方案。
具体的表示方法如下:
因为只有三种颜色,所以可以用三进制数字来表示染色方案。用 0,1,2 分别代表红黄绿。因为每个集合只有三个格子,所以只需要用三位数字
比如21 = 0 + 31 + 92,代表第一个格子为红色,第二个格子为黄色,第三个格子为绿色。
我们可以把这个数字称为状态码

关于状态码的取值范围

当三个格子都染成红色时,状态码取得最小值即 0 + 03 + 09 = 0。
当三个格子都染成绿色时,状态码取得最大值即 2 + 23 + 29 = 26。
所以状态码的取值范围为[0,26]。

递归

设 dp[n][sc] 为将前 n 层都染上颜色,且第n层的染色为 sc。sc 即上述的状态码。
当 n 等于 1时,dp[n][sc] 很好计算,即判断sc代表的染色方案是否合法即可。
如果合法 dp[1][sc] = 1,否则 dp[1][sc] = 0。

当 n > 1 时,dp[n][sc] 由 dp[n-1][psc] 推导得出。sc 为 第n行的染色方案,psc为 n-1行的染色方案。递推式子如下:
dp[n][sc] += dp[n-1][psc] (0 <= psc < 27)。

class Solution {
public:
    const int mod = 1000000007;
    int dp[5001][27] = {0};
    //根据每个格子的颜色获取状态码
    int sc(int i, int j, int k) {
        return i + j*3 + k *9;
    }
    //根据状态码获取每个格子的颜色
    void cs(int statusCode, int &a, int &b, int &c) {
        a = statusCode % 3;
        b = (statusCode - a)%9/3;
        c = statusCode/9;
    }
    
    int numOfWays(int n) {
        初始化 n = 1 的方案数。
        for(int i = 0; i <= 2; i++) {
            for(int j = 0; j <= 2; j++) {
                for(int k = 0; k <= 2; k++) {
                    if(i != j && j != k) {
                        dp[1][sc(i,j,k)] = 1;
                    }
                }
            }
        }
        //枚举行数
        for(int level = 2; level <= n; level++) {
            //枚举前一行的染色方案
            for(int pre = 0; pre < 27; ++pre) {
                int a, b, c;
                cs(pre, a, b, c);
                if(a == b || b == c) {
                    continue;
                }
                //枚举当前行的染色方案
                for(int i = 0; i <= 2; i++) {
                    if(i == a) { continue; } //检查是否冲突
                    for(int j = 0; j <= 2; j++) {
                        if(i == j || j == b) { continue; } //检查是否冲突
                        for(int k = 0; k <= 2; k++) {
                            if(j == k || k == c) { continue; } //检查是否冲突
                            (dp[level][sc(i,j,k)] += dp[level-1][pre]) %= mod; //当前染色方案可行,累加方案数。
                        }
                    }
                }
            }
        }
        int ans = 0;
        for(int i = 0; i < 27; i++) {
            (ans += dp[n][i]) %= mod; //计算总的方案数。
        }
        return ans;
    }
};
3

就搞三题,第四题直接放弃

2

第一次AK,我竟然把最后一题答案给猜出来了

1

我太菜了,第三题一直超时

1

我第四题还是一个小时没思路....................................................太菜了

1

随便写个第四题的
分两种情况讨论,上一行涂色方案是三种颜色,即ABC三色,以及上一行是两种颜色即ABA类。
首先说上一行是ABA类的:

  • ABA
    本行能涂:
    BCB
    BAB
    BAC
    CAB
    CAC
    以上共5种方案,其中ABC类的2种,ABA类的3种
    同理,上一行是ABC类的:
  • ABC
    本行能涂:
    BAB
    BCA
    BCB
    CAB
    以上共5种方案,其中ABC类2种,ABA类2种。

当n=1时,ABA类6种,ABC类6种。
第i行的ABC涂法 = 2*(i-1行ABC涂法) + 2*(i-1行ABA涂法)
第i行的ABA涂法 = 2*(i-1行ABC涂法) + 3*(i-1行ABA涂法)

1

第一题暴力
第二题暴力
第三题re.sub一把梭
第四题玩得是数学好吗?

这礼拜周赛就结束了。