leetcode contest 107 solution

本文是leetcode contest 107的题解:

• 925. Long Pressed Name
• 926. Flip String to Monotone Increasing
• 927. Three Equal Parts
• 928. Minimize Malware Spread II

925. Long Pressed Name

Your friend is typing his name into a keyboard.  Sometimes, when typing a character c, the key might get long pressed, and the character will be typed 1 or more times.

You examine the typed characters of the keyboard.  Return True if it is possible that it was your friends name, with some characters (possibly none) being long pressed.

Example 1:

Input: name = "alex", typed = "aaleex" Output: true Explanation: 'a' and 'e' in 'alex' were long pressed.

Example 2:

Input: name = "saeed", typed = "ssaaedd" Output: false Explanation: 'e' must have been pressed twice, but it wasn't in the typed output.

Example 3:

Input: name = "leelee", typed = "lleeelee" Output: true

Example 4:

Input: name = "laiden", typed = "laiden" Output: true Explanation: It's not necessary to long press any character.

Note:

name.length <= 1000 typed.length <= 1000 The characters of name and typed are lowercase letters.

题目地址：leetcode Long Pressed Name

题目大意：给定一个name和一个typed的字符串，判断typed是否是由name中重复一些字母得到的

思路：

直接比较即可。。。遇到不相等的看typed[i] 是否等于name[j - 1]

Python

class Solution(object):
    def isLongPressedName(self, name, typed):
        """
        :type name: str
        :type typed: str
        :rtype: bool
        """
        if not name: return not typed
        i = j = 0
        while i < len(typed) and j < len(name):
            if name[j] == typed[i]:
                i += 1
                j += 1
            else:
                if j > 0 and typed[i] == name[j - 1]:
                    i += 1
                else:
                    return False
        return j == len(name)

 

---

926. Flip String to Monotone Increasing

A string of '0's and '1's is monotone increasing if it consists of some number of '0's (possibly 0), followed by some number of '1's (also possibly 0.)

We are given a string S of '0's and '1's, and we may flip any '0' to a '1' or a '1' to a '0'.

Return the minimum number of flips to make S monotone increasing.

Example 1:

Input: "00110" Output: 1 Explanation: We flip the last digit to get 00111.

Example 2:

Input: "010110" Output: 2 Explanation: We flip to get 011111, or alternatively 000111.

Example 3:

Input: "00011000" Output: 2 Explanation: We flip to get 00000000.

Note:

1 <= S.length <= 20000 S only consists of '0' and '1' characters.

题目地址：leetcode Flip String to Monotone Increasing

题目大意：给定只由0和1组成的字符串，让你替换一些字符，使得字符串是单调上升的，即0000111这样，问最少替换几个字符。

思路：

双状态DP，设one[i]以1结尾的上升字符串最少替换次数，zero[i]为以0结尾的单调上升字符串的最少替换次数

则s[i] == '0'：

• one[i] = min(one[i - 1] ,zero [i - 1]) + 1 即要替换当前的为1
• zero[i] = zero[i - 1]

s[i] == '1':

• one[i] = min(one[i - 1], zero[i - 1]) #不用替换
• zero[i] = zero[i - 1] + 1 # 替换为0

Python

class Solution(object):
    def minFlipsMonoIncr(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s: return 0
        one, zero = [0] * len(s), [0] * len(s)
        if s[0] == '0':
            one[0] = 1
        else:
            zero[0] = 1

        for i in range(1, len(s)):
            if s[i] == '0':
                one[i] = min(one[i - 1], zero[i - 1]) + 1
                zero[i] = zero[i - 1]
            else:  # s[i] is '1'
                one[i] = min(one[i - 1], zero[i - 1])
                zero[i] = zero[i - 1] + 1
        return min(zero[-1], one[-1])

 

---

927. Three Equal Parts

Given an array A of 0s and 1s, divide the array into 3 non-empty parts such that all of these parts represent the same binary value.

If it is possible, return any [i, j] with i+1 < j, such that:

A[0], A[1], ..., A[i] is the first part; A[i+1], A[i+2], ..., A[j-1] is the second part, and A[j], A[j+1], ..., A[A.length - 1] is the third part. All three parts have equal binary value.

If it is not possible, return [-1, -1].

Note that the entire part is used when considering what binary value it represents.  For example, [1,1,0] represents 6 in decimal, not 3.  Also, leading zeros are allowed, so [0,1,1] and [1,1] represent the same value.

Example 1:

Input: [1,0,1,0,1] Output: [0,3]

Example 2:

Input: [1,1,0,1,1] Output: [-1,-1]

Note:

3 <= A.length <= 30000 A[i] == 0 or A[i] == 1

题目地址：leetcode Three Equal Parts

题目大意：给定只由0和1组成的数组，求两个下标[i, j]使得这个下标将数组划分为3个部分，每个部分的二进制相等。

思路：这题的难点在于在哪里划分，因为有前导0比如[0,1,1]和[1,1]代表同一个二进制值。一个trick是只需要根据1划分就可以了。因为最后不管怎么划分，1的个数必然相等，也不用管最前面有几个0.

因此，首先统计1的个数，然后看其是否能被3整除。

然后设target = total_ones / 3，这样每部分需要的1的个数就确定了。

接着，设一分点为first[0], first[1]，分别代表下标从first[0]到first[1]的位置中，1的个数都为target

设二分点为second[0], second[1]，分别代表下标从second[0]到second[1]的位置中，1的个数都为target * 2

其实也就是说明first[0] + 1...first[1]中都是0，这些0可能是第一部分也可能是第二部分的。

同理second[0] + 1....second[1]都是0，这些0可能是第二部分也可能是第三部分的。

这里可以用一个trick是划分后必然有他们的尾部是相等的，可以从最后一部分开始往前推。

可以计算出最后尾部有多少个0，设为need_zero。那么second[0] + need_zero则为第二部分的结尾，first[0] + need_zero则为第一部分的结尾。

最后判断三个部分是否相等即可。

Python

class Solution(object):
    def is_equal(self, A, s1, e1, s2, e2):
        i = e1
        j = e2
        while i >= s1 and j >= s2:
            if A[i] != A[j]:
                return False
            i -= 1
            j -= 1
        return True

    def threeEqualParts(self, A):
        """
        :type A: List[int]
        :rtype: List[int]
        """
        if len(A) < 3: return False
        cnt = [0] * len(A)
        cnt[0] = 1 if A[0] == 1 else 0
        for i in range(1, len(A)):
            cnt[i] = cnt[i - 1] + (A[i] == 1)

        if cnt[-1] % 3 != 0:
            return [-1, -1]

        if cnt[-1] == 0:
            return [0, len(A) - 1]

        target = cnt[-1] // 3
        first = []
        second = []
        for i in range(len(A)):
            if cnt[i] == target:
                if not first:
                    first = [i, i]
                else:
                    first[1] = i
            elif cnt[i] == target << 1:
                if not second:
                    second = [i, i]
                else:
                    second[1] = i

        j = len(A) - 1
        while A[j] == 0:
            j -= 1

        need_zero = len(A) - j - 1
        ans = [-1, -1]

        if second[1] - second[0] + 1 < need_zero or first[1] - first[0] + 1 < need_zero:
            return ans

        ans[1] = second[0] + need_zero
        ans[0] = first[0] + need_zero

        if self.is_equal(A, 0, ans[0], ans[0] + 1, ans[1]) and \
                self.is_equal(A, 0, ans[0], ans[1] + 1, len(A) - 1):
            return [ans[0], ans[1] + 1]
        return [-1, -1]

 

---

928. Minimize Malware Spread II

(This problem is the same as Minimize Malware Spread, with the differences bolded.)

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, completely removing it and any connections from this node to any other node.  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.

Example 1:

Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1] Output: 0

Example 2:

Input: graph = [[1,1,0],[1,1,1],[0,1,1]], initial = [0,1] Output: 1

Example 3:

Input: graph = [[1,1,0,0],[1,1,1,0],[0,1,1,1],[0,0,1,1]], initial = [0,1] 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 II

题目大意：和924. Minimize Malware Spread类似，给定一张电脑网络连接图，如果g[i][j] = 1，说明电脑i连接到电脑j。初始的时候initial中的电脑感染了病毒，感染病毒的电脑会传播到和它直接相连的电脑中。不断的进行传播，最后设M为最终感染的数目。现在要让你从initial中去掉某个电脑，去掉该电脑后，其边的关系也被去除。问去掉哪个电脑可以使得去掉后感染的电脑数最少。

思路：和924题类似，那题可以贪心的计算出某个结点最大可达的结点个数，这题就计算去掉之后被感染的，然后找最小的即可。

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] or to == ini_:
                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)
            for i in initial:
                if i != ini_:
                    self.dfs(i, graph, vis, ini_)
            cnt[ini_] = sum(vis)

        min_node = initial[0]
        for node in initial:
            if cnt[node] < cnt[min_node]:
                min_node = node
        return min_node

 

本文是leetcode contest 107的题解:

• 925. Long Pressed Name
• 926. Flip String to Monotone Increasing
• 927. Three Equal Parts
• 928. Minimize Malware Spread II

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