Skip to main content

第 234 场周赛

Problem A - 字符串中不同整数的数目​

方法一：模拟​

手动模拟，取出每一段整数部分。

  • 时间复杂度O(∣S∣)\mathcal{O}(|S|)。
  • 空间复杂度O(∣S∣)\mathcal{O}(|S|)。
参考代码（Python 3）
class Solution:
    def numDifferentIntegers(self, word: str) -> int:
        nums = set()
        l = 0
        while l < len(word):
            if word[l].isnumeric():
                r = l
                while r + 1 < len(word) and word[r + 1].isnumeric():
                    r += 1
                nums.add(int(word[l:r + 1]))
                l = r + 1
            else:
                l += 1
        return len(nums)

方法二：正则表达式​

使用re.split()切分字母部分。

参考代码（Python 3）
class Solution:
    def numDifferentIntegers(self, word: str) -> int:
        return len(set(map(int, filter(lambda x: len(x) > 0, re.split(r'[a-z]+', word)))))

或者利用re.findall()提取数字部分。

参考代码（Python 3）
class Solution:
    def numDifferentIntegers(self, word: str) -> int:
        return len(set(map(int, re.findall(r'\d+', word))))

Problem B - 还原排列的最少操作步数​

方法一：模拟​

模拟进行操作；在每次操作后检查是否还原到初始状态。

  • 时间复杂度O(N2)\mathcal{O}(N^2)。
  • 空间复杂度O(N)\mathcal{O}(N)。
参考代码（Python 3）
class Solution:
    def reinitializePermutation(self, n: int) -> int:
        perm = [i for i in range(n)]
        orig = list(perm)
        ops = 0
        while True:
            ops += 1
            perm = [perm[i // 2] if i % 2 == 0 else perm[n // 2 + (i - 1) // 2] for i in range(n)]
            if perm == orig:
                break
        return ops

方法二：模拟1的位置​

事实上，我们只需要模拟11的位置变动即可。当11回到原位时，所有元素都处在原位。

设11的当前位置为pospos，将变换规则反向，我们可以知道：

  • 如果pos<N2pos<\dfrac{N}{2}，则pos→2pospos\rightarrow 2pos
  • 否则，pos→2(pos−N2)+1pos\rightarrow 2(pos-\dfrac{N}{2})+1

这一方法的

  • 时间复杂度O(N)\mathcal{O}(N)。
  • 空间复杂度O(1)\mathcal{O}(1)。
参考代码（Python 3）
class Solution:
    def reinitializePermutation(self, n: int) -> int:
        pos = 1
        ops = 0
        while True:
            ops += 1
            if pos < n // 2:
                pos <<= 1
            else:
                pos = 1 + ((pos - n // 2) << 1)
            if pos == 1:
                break
        return ops

思考​

可以进一步用数学方法求解吗？

Problem C - 替换字符串中的括号内容​

方法一：模拟​

手动模拟替换操作。

  • 时间复杂度O(∣S∣)\mathcal{O}(|S|)。
  • 空间复杂度O(N)\mathcal{O}(N)。
参考代码（Python 3）
class Solution:
    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:
        d = dict()
        for key, val in knowledge:
            d[key] = val
        ans = []
        l = 0
        while l < len(s):
            if s[l] == '(':
                r = l + 1
                while s[r] != ')':
                    r += 1
                key = s[l+1:r]
                if key in d:
                    ans.append(d[key])
                else:
                    ans.append('?')
                l = r + 1
            else:
                ans.append(s[l])
                l += 1
        return ''.join(ans)

方法二：正则表达式​

使用正则表达式结合lambda函数进行替换。

参考代码（Python 3）
class Solution:
    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:
        d = collections.defaultdict(lambda: '?')
        for key, val in knowledge:
            d[key] = val
        return re.sub(r'\(([a-z]+)\)', lambda x: d[x.group(1)], s)

Problem D - 好因子的最大数目​

由乘法原理容易看出，质因数的分解确定后，好因子的数目等于每个不同的质因数的个数的乘积。

因此，本题与LC343 - 整数拆分几乎等价（N≤3N\leq3的情况有所区别，因为本题中可以不进行拆分）。

由于数据范围扩大了，我们需要用快速幂来计算最后的结果。这里利用了Python中pow()函数的可选参数mod。

  • 时间复杂度O(log⁡N)\mathcal{O}(\log N)。
  • 空间复杂度O(1)\mathcal{O}(1)。
参考代码（Python 3）
MOD = 1000000007

class Solution:
    def maxNiceDivisors(self, n: int) -> int:
        if n <= 3:
            return n
        if n % 3 == 1:
            return 4 * pow(3, (n - 4) // 3, MOD) % MOD
        elif n % 3 == 2:
            return 2 * pow(3, n // 3, MOD) % MOD
        else:
            return pow(3, n // 3, MOD)