leetcode contest 106 solution

本文是leetcode contest 106的题解，包括：

921. Minimum Add to Make Parentheses Valid
922. Sort Array By Parity II
923. 3Sum With Multiplicity
924. Minimize Malware Spread

好久没打比赛了，一个多小时AK。。

921. Minimum Add to Make Parentheses Valid

Given a string S of '(' and ')' parentheses, we add the minimum number of parentheses ( '(' or ')', and in any positions ) so that the resulting parentheses string is valid.

Formally, a parentheses string is valid if and only if:

It is the empty string, or

It can be written as AB (A concatenated with B), where A and B are valid strings, or

It can be written as (A), where A is a valid string.

Given a parentheses string, return the minimum number of parentheses we must add to make the resulting string valid.

Example 1:
1
2
Input: "())"
Output: 1
Example 2:
1
2
"((("
Output: 3
Example 3:
1
2
3
Input: "()"
Output:0
Example 4:
1
2
Input:"()))(("
Output:4

题目地址：leetcode Minimum Add to Make Parentheses Valid

题目大意：给定一个只包含左右括号的字符串，求最小加入多少个括号能使得该字符串合法？

思路：用一个变量left统计左括号的个数，遇到右括号则left--，如果left<0，说明左括号个数不够，答案+1。当遍历完之后，若left不为0，说明没有足够的右括号与左括号匹配，还需要加入left个。复杂度O(n)

class Solution(object):
    def minAddToMakeValid(self, S):
        """
        :type S: str
        :rtype: int
        """
        left = ans = 0
        for c in S:
            if c == '(':
                left += 1
            else:
                left -= 1
                if left < 0:
                    ans += 1
                    left = 0
        return ans + left

922. Sort Array By Parity II

Given an array A of non-negative integers, half of the integers in A are odd, and half of the integers are even.

Sort the array so that whenever A[i] is odd, i is odd; and whenever A[i] is even, i is even.

You may return any answer array that satisfies this condition.

Example 1:
1
2
3
Input: [4,2,5,7]
Output: [4,5,2,7]
Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.

题目地址：leetcode Sort Array By Parity II

题目大意：给定一个非负的数组A，A的长度为偶数。在A中，一半的数字是奇数，另一半数字是偶数，现在要让你排序，使得数组A满足对于所有的i

如果A[i]是奇数，则i也要是奇数
如果A[i]是偶数，则i也要是偶数

思路：用一个even表示下标even应该放置偶数，但该位置目前放置的是奇数。然后用odd遍历奇数位置，遇到奇数的位置上放的是偶数就和even交换。复杂度O(n)

Python

class Solution(object):
    def sortArrayByParityII(self, A):
        """
        :type A: List[int]
        :rtype: List[int]
        """
        even = 0
        for odd in range(1, len(A), 2):
            if A[odd] & 1:
                continue
            while even < len(A):
                if A[even] & 1:
                    break
                even += 2
            if even == len(A): return A
            A[even], A[odd] = A[odd], A[even]
        return A

923. 3Sum With Multiplicity

Given an integer array A, and an integer target, return the number of tuples i, j, k such that i < j < k and A[i] + A[j] + A[k] == target.

As the answer can be very large, return it modulo 10^9 + 7.

Example 1:
1
2
3
4
5
6
7
8
9
Input: A = [1,1,2,2,3,3,4,4,5,5], target = 8
Output:20
Explanation: 
Enumerating by the values (A[i], A[j], A[k]):
(1, 2, 5) occurs 8 times;
(1, 3, 4) occurs 8 times;
(2, 2, 4) occurs 2 times;
(2, 3, 3) occurs 2 times.
Example 2:
1
2
3
4
5
6
7
Input: A = , target = 5
Output: 12
Explanation: 
A[i] = 1, A[j] = A[k] = 2 occurs 12 times:
We choose one 1 from [1,1] in 2 ways,
and two 2s from [2,2,2,2] in 6 ways.
Note:

3 <= A.length <= 3000

0 <= A[i] <= 100

0 <= target <= 300

题目地址：leetcode 3Sum With Multiplicity

题目大意：给定数组A和一个数target，求所有的满足A[i] + A[j] + A[k] == target且i < j < k的i, j, k的个数。

思路：和3sum问题类似，我们可以枚举第一个下标k，然后用双指针的方法查找i和j。

但是有个问题就是当A[i] == A[j]的时候，下一次是应该i++？还是j--? 这里我是将相同数去掉，这种情况只会在i==j的时候出现，只需要判断cnt[i] >= 2 然后计算组合数C(cnt[i], 2)。

还有一个细节是i应该从k的位置开始，比如第一个example中的(2, 2, 4)。计算的时候要判断一下（比如还有i= j = k，相当于组合数C(cnt[i], 3)）

Python

class Solution(object):
    def combination_cal(self, n, k=2):
        t = n
        for i in range(1, k):
            t *= (n - i)
        for x in range(2, k + 1):
            t //= x
        return t

    def threeSumMulti(self, A, target):
        """
        :type A: List[int]
        :type target: int
        :rtype: int
        """
        temp = sorted(collections.Counter(A).items())
        A = [i[0] for i in temp]
        cnt = [i[1] for i in temp]

        ans = 0
        for k in range(len(A)):
            t = target - A[k]
            i = k
            j = len(A) - 1
            while i <= j:
                if A[i] + A[j] < t:
                    i += 1
                elif A[i] + A[j] > t:
                    j -= 1
                else:
                    if i == j:
                        if cnt[i] >= 2:
                            if i == k:
                                ans += int(self.combination_cal(cnt[i], 3))
                            else:
                                ans += cnt[k] * int(self.combination_cal(cnt[i], 2))
                    else:
                        if i == k:
                            ans += int(self.combination_cal(cnt[i], 2)) * cnt[j]
                        else:
                            ans += cnt[k] * cnt[i] * cnt[j]
                    i += 1
                    j -= 1
        return ans % (10 ** 9 + 7)

924. Minimize Malware Spread

In a network of nodes, each node i is directly connected to another node j if and only if graph[i][j] = 1.

Some nodes initial are initially infected by malware. Whenever two nodes are directly connected and at least one of those two nodes is infected by malware, both nodes will be infected by malware. This spread of malware will continue until no more nodes can be infected in this manner.

Suppose M(initial) is the final number of nodes infected with malware in the entire network, after the spread of malware stops.

We will remove one node from the initial list. Return the node that if removed, would minimize M(initial). If multiple nodes could be removed to minimize M(initial), return such a node with the smallest index.

Note that if a node was removed from the initial list of infected nodes, it may still be infected later as a result of the malware spread.

Example 1:
1
2
3
Input: graph =[[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
Output: 0
Example 2:
1
2
3
Input: graph = [[1,0,0],[0,1,0],[0,0,1]], initial = [0,2]
Output: 0
Example 3:
1
2
Input: graph = [[1,1,1],[1,1,1],[1,1,1]], initial =[1,2]
Output: 1
Note:

1 < graph.length = graph[0].length <= 300

0 <= graph[i][j] == graph[j][i] <= 1

graph[i][i] = 1

1 <= initial.length < graph.length

0 <= initial[i] < graph.length

题目地址：leetcode Minimize Malware Spread

题目大意：给定一张电脑网络连接图，如果g[i][j] = 1，说明电脑i连接到电脑j。初始的时候initial中的电脑感染了病毒，感染病毒的电脑会传播到和它直接相连的电脑中。不断的进行传播，最后设M为最终感染的数目。现在要让你从initial中去掉某个电脑，使得去掉后感染的电脑数最少。

思路：

直接dfs对Initial数组中每一个求可到的结点数，去掉最高的就行了。

Python

class Solution(object):
    def dfs(self, from_, g, vis, ini_):
        vis[from_] = True
        for to in range(len(g[from_])):
            if not g[from_][to] or vis[to]:
                continue
            self.dfs(to, g, vis, ini_)

    def minMalwareSpread(self, graph, initial):
        """
        :type graph: List[List[int]]
        :type initial: List[int]
        :rtype: int
        """
        cnt = [0] * len(graph)
        initial.sort()
        for ini_ in initial:
            vis = [False] * len(graph)
            self.dfs(ini_, graph, vis, ini_)
            cnt[ini_] = sum(vis)
        max_node = initial[0]
        for node in initial:
            if cnt[node] > cnt[max_node]:
                max_node = node
        return max_node

上面的方法可以进行优化：假如a能到b，由于是无向图，那么b也能到达a，那么只需要先对initial数组排序，然后对没有访问的结点dfs就行了

class Solution(object):
    def dfs(self, cur, g, vis, source, cnt):
        vis[cur] = True
        cnt[source] += 1
        for to in range(len(g[cur])):
            if not g[cur][to] or vis[to]:
                continue
            self.dfs(to, g, vis, source, cnt)

    def minMalwareSpread(self, graph, initial):
        """
        :type graph: List[List[int]]
        :type initial: List[int]
        :rtype: int
        """
        cnt = [0] * len(graph)
        vis = [False] * len(graph)
        initial.sort()
        for from_ in initial:
            self.dfs(from_, graph, vis, from_, cnt)
        max_node = initial[0]
        for node in initial:
            if cnt[node] > cnt[max_node]:
                max_node = node
        return max_node

本文是leetcode如下的题解

921. Minimum Add to Make Parentheses Valid
922. Sort Array By Parity II
923. 3Sum With Multiplicity
924. Minimize Malware Spread

更多题解可以查看： https://www.hrwhisper.me/leetcode-algorithm-solution/