Leetcode第 123 场周赛

周赛链接

989.数组形式的整数加法

题目链接
Leetcode上有许多与这个类似的题目,如两个数组表示的数字相加、两个链表表示的数字相加,而这里是一个数组表示的数字和一个整数相加。解法也很简单,只要记得进位即可。
Python代码:

class Solution:
    def addToArrayForm(self, A: 'List[int]', K: 'int') -> 'List[int]':
        n = len(A)
        i = n - 1
        while i >= 0 and K > 0:
            temp = A[i] + K % 10
            A[i] = temp % 10
            K //= 10
            K += temp // 10
            i -= 1
        while K > 0:
            A.insert(0, K % 10)
            K //= 10
        return A

990.等式方程的可满足性

题目链接
对于所给等式a==b,对应为a到b以及b到a的两条边。对于所给不等式,只需要使用深度或者广度优先遍历验证其是否与等式有矛盾即可。
Python代码:

class Solution:
    def equationsPossible(self, equations: 'List[str]') -> 'bool':
        def bfs(a, b):
            nonlocal counter
            vis = [False for i in range(26)]
            queue = [a]
            while len(queue) > 0:
                s = queue.pop(0)
                vis[s] = True
                if b in counter[s]:
                    return True
                for child in counter[s]:
                    if not vis[child]:
                        queue.append(child)
            return False
        counter = [set() for i in range(26)]
        nequations = []
        for equation in equations:
            a = ord(equation[0]) - 97
            b = ord(equation[3]) - 97
            if equation[1] == '=':
                counter[a].add(b)
                counter[b].add(a)
            else:
                if a == b:
                    return False
                nequations.append([a,b])
        for ne in nequations:
            a = ne[0]
            b = ne[1]
            if bfs(a, b) or bfs(b, a):
                return False
        return True

991.坏了的计算器

题目链接
当X < Y时,如果Y是偶数,则Y除以2;如果Y是奇数,则Y加上1。当X >= Y时,最少需要X-Y次操作。
Python代码:

class Solution:
    def brokenCalc(self, X: 'int', Y: 'int') -> 'int':
        res = 0
        while X < Y:
            if Y & 1 == 1:
                Y += 1
                res += 1
            Y //= 2
            res += 1
        res += X - Y
        return res

992.K 个不同整数的子数组

题目链接
枚举右端点,通过两个变量left和tail来获得左端点的最大值和最小值。
Python代码:

class Solution:
    def subarraysWithKDistinct(self, A: 'List[int]', K: 'int') -> 'int':
        res = 0
        left = 0
        right = 0
        n = len(A)
        counter = [0 for i in range(n+1)]
        tail = 0
        s = set()
        while right < n:
            counter[A[right]] += 1
            s.add(A[right])
            right += 1
            if len(s) == K:
                right -= 1
                counter[A[right]] -= 1
                s.remove(A[right])
                break
        while right < n:
            counter[A[right]] += 1
            s.add(A[right])
            while left < right and len(s) > K:
                counter[A[left]] -= 1
                if counter[A[left]] == 0:
                    s.remove(A[left])
                left += 1
                tail = 0
            while left < right:
                counter[A[left]] -= 1
                if counter[A[left]] == 0:
                    counter[A[left]] += 1
                    break
                left += 1
                tail += 1
            res += tail + 1
            right += 1
        return res