# Leetcode 第68场双周赛题解

# Problem A - 句子中的最多单词数 (opens new window)

# 方法一:暴力

在题目给定的条件下,统计单词数实际上就是统计空格数。

  • 时间复杂度O(W)\mathcal{O}(\sum|W|)。其中W|W|表示单词的长度。
  • 空间复杂度O(N)\mathcal{O}(N)
参考代码(Python 3)
class Solution:
    def mostWordsFound(self, sentences: List[str]) -> int:
        return max(map(lambda x: x.count(' ') + 1, sentences))
1
2
3

# Problem B - 从给定原材料中找到所有可以做出的菜 (opens new window)

# 方法一:暴力

首先排除那些绝对不可能做出来的菜,也即配方中包含了既不在食谱也不在现有食材中的菜。

接下来,我们从初始状态(只有食材)开始,反复遍历所有的配方,并检查是否能做出对应的菜。这里为了加速,使用了bitset

如果某一轮遍历中都没有做出新的菜,说明已经不可能做出新的菜了,终止。

  • 时间复杂度O(N3/W)\mathcal{O}(N^3/W)。其中WW为字长。
  • 空间复杂度O(N3/W)\mathcal{O}(N^3/W)
参考代码(C++)
class Solution {
public:
    vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
        int n = recipes.size();
        
        unordered_map<string, int> mp;
        int idx = 0;
        for (auto &s : recipes)
            mp[s] = idx++;
        for (auto &s : supplies)
            mp[s] = idx++;
        
        bitset<200> bs;
        for (auto &s : supplies)
            bs.set(mp[s]);
        
        vector<bitset<200>> vi(n);
        vector<bool> can(n, true);
        for (int i = 0; i < n; ++i) {
            for (auto &s : ingredients[i]) {
                if (!mp.count(s)) {
                    can[i] = false;
                    break;
                }
                vi[i].set(mp[s]);
            }
        }
        
        bool changed = true;
        for (int i = 0; i < n; ++i) {
            changed = false;
            for (int j = 0; j < n; ++j) {
                if (!can[j] || bs[j])
                    continue;
                if ((bs | vi[j]) == bs)
                    bs.set(j), changed = true;
            }
            if (!changed)
                break;
        }
        
        vector<string> ans;
        for (int i = 0; i < n; ++i)
            if (bs[i])
                ans.push_back(recipes[i]);
        
        return ans;
    }
};
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

# Problem C - 判断一个括号字符串是否有效 (opens new window)

# 方法一:记录可能的最大和最小平衡值

令平衡值表示某一位置处,累积的(数量与)数量的差值,则我们知道,一个有效括号字符串必须满足:

  • 所有位置处的平衡值非负
  • 结尾处的平衡值为零

那么,我们的解题思路就是:依次遍历每个位置,根据每个位置处的字符和上锁情况来更新当前所有可能的平衡值。

本题NN最大10510^5,记录所有的平衡值可能会超时。但可以注意到,任意时刻,所有可能的平衡值必然构成一个公差为22的等差数列,所以我们只需要记录最大和最小平衡值即可。

如果当前字符为(,则最大平衡值必然增加一;而最小平衡值的变化则要看是否上锁:如果上锁,则最小值也需要增加一,否则最小值可以减少一(注意如果当前最小值已经为00,则新的最小值只能为11)。

如果当前字符为),则最小平衡值必须减少一;而最大平衡值的变化则要看是否上锁;如果上锁,最大值也要减少一,否则可以增加一。如果出现最小值大于最大值的情况,则说明无解。

最后,如果最小值为00,说明有解,否则无解。

  • 时间复杂度O(N)\mathcal{O}(N)
  • 空间复杂度O(1)\mathcal{O}(1)
参考代码(C++)
class Solution {
public:
    bool canBeValid(string s, string locked) {
        int n = s.size();
        if (n % 2 == 1)
            return false;
        
        int lo = 0, hi = 0;
        
        for (int i = 0; i < n; ++i) {            
            if (s[i] == '(') { 
                hi++;
                if (locked[i] == '1')
                    lo++;
                else
                    lo = lo == 0 ? 1 : lo - 1;
            } else {
                lo = lo == 0 ? 1 : lo - 1;
                if (locked[i] == '1')
                    hi--;
                else
                    hi++;
                if (lo > hi)
                    return false;
            }
        }
        
        return lo == 0;
    }
};
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

# Problem D - 一个区间内所有数乘积的缩写 (opens new window)

# 方法一:数学

首先,对于区间长度比较小的情况,可以直接计算出精确结果(如果语言支持高精度运算的话)。

在区间长度长到无法直接计算的时候,我们分三部分考虑:

  • 末尾00的数量:经典题,统计区间内的数有多少个22的因子和55的因子即可;

  • 末尾五位:去除2255后,对所有数进行模数为100000100000的带模乘法,并记得在最后乘上没有用掉的2255

  • 开头五位:对所有数取以1010为底的对数并求和,保留小数部分再还原即可得到。

  • 时间复杂度O(NlogN)\mathcal{O}(N\log N)

  • 空间复杂度O(N)\mathcal{O}(N)

参考代码(Python 3)
from functools import reduce
from math import log10

MOD = 100000

class Solution:
    def abbreviateProduct(self, left: int, right: int) -> str:
        if right - left + 1 <= 50:
            ans = reduce(lambda x, y: x * y, range(left, right + 1), 1)
            s = str(ans)
            t = s.rstrip('0')
            z = len(s) - len(t)
            if len(t) <= 10:
                return t + 'e' + str(z)
            else:
                return t[:5] + '...' + t[-5:] + 'e' + str(z)
        else:
            l = sum(map(log10, range(left, right + 1)))
            L = str(10 ** (l - trunc(l)) * 10000)[:5]
            
            R = 1
            two = 0
            five = 0
            for i in range(left, right + 1):
                num = i
                while num % 2 == 0:
                    two += 1
                    num >>= 1
                while num % 5 == 0:
                    five += 1
                    num //= 5
                R = R * num % MOD
                
            z = min(two, five)
            R = R * pow(2, two - z, MOD) % MOD
            R = R * pow(5, five - z, MOD) % MOD
            return L + '...' + str(R).rjust(5, '0') + 'e' + str(z)
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