LeetCode周赛 161场题解

CodeWeekly

3684

2019.11.04

2019.11.05

发布于未知归属地

学习分享

161 场比赛总结：本场比赛题目基本是经典问题的改版和变形，hard 是一道少见的数论题。

Easy 1247. 交换字符使得字符串相同

题目

有两个长度相同的字符串 s1 和 s2，且它们其中 只含有 字符 "x" 和 "y"，你需要通过「交换字符」的方式使这两个字符串相同。

每次「交换字符」的时候，你都可以在两个字符串中各选一个字符进行交换。

交换只能发生在两个不同的字符串之间，绝对不能发生在同一个字符串内部。也就是说，我们可以交换 s1[i] 和 s2[j]，但不能交换 s1[i] 和 s1[j]。

最后，请你返回使 s1 和 s2 相同的最小交换次数，如果没有方法能够使得这两个字符串相同，则返回 -1 。

示例 1：
输入： s1 = "xx", s2 = "yy"
输出： 1
解释： 交换 s1[0] 和 s2[1]，得到 s1 = "yx"，s2 = "yx"。

示例 2：
输入： s1 = "xy", s2 = "yx"
输出： 2
解释： 交换 s1[0] 和 s2[0]，得到 s1 = "yy"，s2 = "xx" 。
交换 s1[0] 和 s2[1]，得到 s1 = "xy"，s2 = "xy" 。
注意，你不能交换 s1[0] 和 s1[1] 使得 s1 变成 "yx"，因为我们只能交换属于两个不同字符串的字符。

示例 3：
输入： s1 = "xx", s2 = "xy"
输出： -1

示例 4：
**输入：**s1 = "xxyyxyxyxx", s2 = "xyyxyxxxyx"
**输出：**4

提示：

1 <= s1.length, s2.length <= 1000
s1, s2 只包含 'x' 或 'y'。

题目解析

由于字符串里只有两种字母 $x$ 和 $y$ ，那么如果我们统计位置的匹配情况，一共只有4种可能，即 $x - x$ , $x - y$ , $y - x$ , $y - y$ 。

其中 $x - x$ 和 $y - y$ 都是已经能匹配的情况，我们不需要做操作。那么剩余的就是：

$x - y$ ，假设有 $a$ 对。
$y - x$ ，假设有 $b$ 对。

那么对于两对 $x - y$ 或者两对 $y - x$ ，我们都是可以通过一次交换使得他们变为 $x - x$ , $y - y$ 的，而对于一对 $x - y$ 和一对 $y - x$ 的情况，我们需要通过两次操作使他们变为 $x - x$ , $y - y$ (这也是示例一的情形)。所以我们会优先使得两对一样的进行交换操作。

那么这样操作完以后，我们剩余的情况有以下几种：

$a, b$ 都是偶数，那么最后什么都没剩下，不需要额外操作了。
$a, b$ 一奇一偶，最后只会剩下一对不匹配字符，这样是无解的。
$a, b$ 都是奇数，那么最后会剩下一对 $x - y$ 和一对 $y - x$ ，需要额外 $2$ 次操作。

我们的主要计算代价是开头统计的时候会遍历字符串，所以时间复杂度为 $O (n)$ 。

Python

class Solution(object):
    def minimumSwap(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: int
        """
        x = 0; y = 0
        for i in range(len(s1)):
            if s1[i] != s2[i]:
                if s1[i] == 'x':
                    x += 1
                else:
                    y += 1
        if (x+y)%2 == 1: return -1
        ans = x // 2 + y // 2
        x = x%2+y%2
        if x == 2:
            ans += 2
        return ans

Medium 1248. 统计「优美子数组」

题目

给你一个整数数组 nums 和一个整数 k。

如果某个子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组 」。

请返回这个数组中「优美子数组」的数目。

示例 1：
输入： nums = [1,1,2,1,1], k = 3
输出： 2
解释： 包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。

示例 2：
输入： nums = [2,4,6], k = 1
输出： 0
解释： 数列中不包含任何奇数，所以不存在优美子数组。

示例 3：
输入： nums = [2,2,2,1,2,2,1,2,2,2], k = 2
输出： 16

提示：

1 <= nums.length <= 50000
1 <= nums[i] <= 10^5
1 <= k <= nums.length

题目解析

暴力解法

这道题也和一道很经典的题目很像，那道题目是求一个数组和等于目标值的子数组个数。那么这道题目，如果对于奇数我们看作1，对于偶数我们看作0，问题就转化为了求和为k的子数组个数。

题目的解法也很经典，我们遍历数组，记录从 $0$ 位置到当前位置的和。比如我们当前在 $x$ 位置，那么在遍历到 $x$ 的过程中， $[0, 0], [0, 1], ..., [0, x - 1]$ 的和我们都应该已经计算并知道了。如下图：

我们将这些和用一个 dict 保存下来，dict 中记录每个和 $s u m$ 一共出现了多少次。那么对于位置 $x$ ：

我们想知道以 $x$ 位置结尾的和为 $k$ 的子数组有多少个，假设从 $[0, x]$ 的和为 $s u m_{x}$ ，那么 dict 中 key 为 $s u m_{x} - k$ 的值都可以构成以 $x$ 结尾的和为 $k$ 的子数组。
计算完成后，我们将 $[0, x]$ 的和也存入 dict 中，即 dict[ $s u m_{x}$ ] += 1。

最后我们统计所有位置结尾的结果即可，总体时间复杂度为 $O (n)$ 。

Python

class Solution(object):
    def numberOfSubarrays(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        mp = {0:1}
        cur_odd = 0
        ans = 0
        for num in nums:
            if num % 2 == 1:
                cur_odd += 1
            if cur_odd - k in mp:
                ans += mp[cur_odd-k]
            if not cur_odd in mp:
                mp[cur_odd] = 0
            mp[cur_odd] += 1
            
        return ans

Medium 1249. 移除无效的括号

题目

给你一个由 '('、')' 和小写字母组成的字符串 s。

你需要从字符串中删除最少数目的 '(' 或者 ')' （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。

请返回任意一个合法字符串。

有效「括号字符串」应当符合以下 任意一条 要求：

空字符串或只包含小写字母的字符串
可以被写作 AB（A 连接 B）的字符串，其中 A 和 B 都是有效「括号字符串」
可以被写作 (A) 的字符串，其中 A 是一个有效的「括号字符串」

示例 1：
输入： s = "lee(t(c)o)de)"
输出： "lee(t(c)o)de"
解释： "lee(t(co)de)" , "lee(t(c)ode)" 也是一个可行答案。

示例 2：
输入： s = "a)b(c)d"
输出： "ab(c)d"

示例 3：
输入： s = "))(("
输出： ""
解释： 空字符串也是有效的

示例 4：
输入： s = "(a(b(c)d)"
输出： "a(b(c)d)"

提示：

1 <= s.length <= 10^5
s[i] 可能是 '('、')' 或英文小写字母

题目解析

用栈来解决括号匹配问题是很常见的栈应用场景，一个经典的题目是问最少删除多少个括号可以使括号序列合法。这道题目在此之上还需要我们求出具体的删除位置 (这样最后的字符串是最长的合法括号串)。

思考一下括号匹配的经典思路，我们会用一个栈维护括号状态，对于左括号，入栈，对于右括号，如果栈中有左括号，左括号出栈，视为完成一个匹配，具体来说，有以下几种情况：

左括号：直接进栈
右括号且栈不为空：左括号出栈
右括号且栈为空：当前右括号无法匹配
遍历完成后：栈中仍然留存的左括号无法匹配

前面提到，删除的括号最少，也就是保留的括号最多，我们只需要把无法匹配的括号删去即可，所以我们的栈保存的应该是左括号在原字符串中的位置。同样，在右括号无法匹配的时候也记录其在原字符串中的位置。最后，我们可以获取一个不匹配的括号位置集合。

有了不匹配的括号位置集合，我们只需要从原串中删除这些字符，就可以得到结果了，总体时间复杂度 $O (n)$ 。

PS：该题Python时限较紧， $O (n)$ 的解法也有超时风险，因此给出C++实现。

C++

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        stack<int> st;
        
        //遍历字符串，用栈维护左括号状态
        string ans = "";
        for (int i = 0 ; i < s.size() ; i ++ ){
            if (s[i] == '('){
                ans += s[i];
                st.push(ans.size()-1);
            }
            else if (s[i] == ')'){
                if (st.empty())
                    continue;
                else{
                    st.pop();
                    ans += s[i];
                }
            }
            else
                ans += s[i];
        }
        //从序列中删除不能匹配的字符
        string res = "";
        int idx = 0;
        for (int i = ans.size()-1 ; i >= 0 ; i --){
            if ( (!st.empty()) && i == st.top()){
                st.pop();
                continue;
            }
            res += ans[i];
        }
        reverse(res.begin(),res.end());
        return res;
    }
};

Hard 1250. 检查「好数组」

提示：hard难度题目在面试中比较少见，如果准备时间不够可以适当跳过。

题目

给你一个正整数数组 nums，你需要从中任选一些子集，然后将子集中每一个数乘以一个 任意整数 ，并求出他们的和。

假如该和结果为 1，那么原数组就是一个「好数组 」，则返回 True；否则请返回 False。

示例 1：

输入： nums = [12,5,7,23]
输出： true
解释： 挑选数字 5 和 7。
5*3 + 7*(-2) = 1

示例 2：

输入： nums = [29,6,10]
输出： true
解释： 挑选数字 29, 6 和 10。
29*1 + 6*(-3) + 10*(-1) = 1

示例 3：

输入： nums = [3,6]
输出： false

提示：
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9

题目解析

这是一道数论的题目，同学们平时一般接触比较少，这也能理解为什么这道题会被放到 hard 难度。但是一旦知道了知识点，这道题目马上就退化成 easy 了。

我们知道，对于两个不为 $1$ 的正整数，如果他们互斥，则他们的最大公约数为 $1$ 。但是如果你了解裴蜀定理[1]，就会知道还有另外一个定理是如果两个数 $x, y$ 互斥，则存在整数 $a, b$ ，使得 $a x + b y = 1$ 。

而推广到 $n$ 个整数，则：

如果 $n$ 个数的最大公约数为 $1$ ，则存在整数 $a, b, ...$ 使得 $a x + b y + ... = 1$ 。

那么问题就很简单了，我们直接求 $n$ 个数的最大公约数，然后判断是不是等于 $1$ 就好了。

求最大公约数时间复杂度为 $O (m)$ (辗转相除法)，要求 $n$ 次，所以总体时间复杂度为 $O (n l o g (m))$ ，其中 $m$ 为数字大小。

Python

class Solution(object):
    def isGoodArray(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        def gcd(a,b):
            if a % b == 0:
                return b
            else :
                return gcd(b,a%b)
        num = nums[0]
        for i in range(1,len(nums)):
            num = gcd(num,nums[i])
        return num == 1

[1] 裴蜀定理

如果你觉得很赞，为什么不点个赞呢~