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

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

image.png

4 分 - 交换字符使得字符串相同
4 分 - 统计「优美子数组」
5 分 - 移除无效的括号
6 分 - 检查「好数组」

展开讨论

第一题
首先,不合法的,一是长度不一样,这个肯定做不到,二是,x和y的个数是奇数个,这个也肯定没法分成两个
然后,考虑最少的交换次数,首先,把所有相同的去掉,因为这些没有必要交换,然后看剩下的
s1 = "xxyyxyxyxx"
s2 = "xyyxyxxxyx"
去掉相同的
s1 = "xyxyyx"
s2 = "yxyxxy"
这样看起来有点乱
s1 = "xxxyyy"
s2 = "yyyxxx"
这样就比较清晰了

然后,我们要认识到
xx
yy

yy
xx
两种情况是等价的,都只需要1次就能换好

xy
yx
则需要有两次
因此,只需要统计xy和yx的个数,
然后让它们尽量两两配对,从最终数量中减去即可

class Solution(object):
    def minimumSwap(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: int
        """
        if (len(s1) != len(s2)):
            return -1
        length = len(s1)
        cnt = {'x' : 0, 'y' : 0}
        tot = 0
        tot_xy = 0
        tot_yx = 0
        for i in range(length):
            cnt[s1[i]] += 1
            cnt[s2[i]] += 1
            if (s1[i] != s2[i]):
                tot += 1
                if (s1[i] == 'x'):
                    tot_xy += 1
                else:
                    tot_yx += 1
        
        if (cnt['x'] & 1):
            return -1 
        return tot - tot_xy / 2 - tot_yx / 2

第二题
这题数字是多少不关键,关键是奇偶,以奇数为分界线,将整个数组拆成若干个子块,然后将偶数个数进行压缩,如
nums = [2,2,2,1,2,2,1,2,2,2]

num = [3, 2, 3]
表示,第一个奇数前有3个偶数,第一个和第二个奇数之间有2个偶数,第三个奇数后有3个偶数
那么,当k=1时,每个奇数的左右两边的偶数都可以任意扩展,即(3+1)*(2+1)+(2+1)*(3+1)
当k=2时,类似(3+1)*(3+1),这里+1是因为,奇数本身也可以作为边界

class Solution(object):
    def numberOfSubarrays(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        num = []
        length = len(nums)
        ls = 0
        for i in range(length):
            if (nums[i] & 1):
                num.append(ls)
                ls = 0
            else:
                ls = ls + 1
        
        num.append(ls)
        ans = 0
        N = len(num)
        for i in range(0, N-k):
            ans = ans + (num[i]+1) * (num[i+k]+1)
        
        return ans

第三题
就是一个栈来做括号匹配,如果遇到左括号,先压栈,遇到右括号,如果栈内有左括号,则弹出栈顶左括号,否则右括号不压栈
当整个字符串处理完后,如果还剩左括号,则将这些左括号删除(这里直接用了python的切片,写得比较丑陋)

class Solution(object):
    def minRemoveToMakeValid(self, s):
        """
        :type s: str
        :rtype: str
        """
        stack = []
        length = len(s)
        result = ""
        for i in range(length):
            if (s[i] == "("):
                result = result+s[i]
                stack.append(len(result))
            elif (s[i] == ")"):
                if (len(stack) > 0):
                    stack = stack[:-1]
                    result = result+s[i]
            else:
                result = result + s[i]
        for i in range(len(stack)-1, -1, -1):
            result = result[:stack[i]-1]+result[stack[i]:]
        
        return result

第四题
一开始想偏了一点点,从两个数开始想的
如果一个数组中有任意两个数互质,则它们能很容易得到1
如果两个数不互质,则它们能得到所有最大公约数的倍数
从而递归的想,如
[6, 18, 10, 15]
6和18可以等价为6,得到
[6, 10, 15]
6和10可以等价为2,得到
[2, 15]
2和15等价为1
[1]
但本质上,就是求所有数的最大公约数,题解一里的裴蜀定理可以作为参考

class Solution(object):
    def isGoodArray(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        length = len(nums)
        
        num = nums[0]
        for k in range(length):
            num = self.Ex_divide(num, nums[k])
        
        return num == 1
    
    def Ex_divide(self, a, b):
        while (a % b != 0):
            a, b = b, a % b
        return b
展开全部 25 讨论