LeetCode第107场周赛题解

2019-03-27 本文已影响0人独孤岳

925. 长按键入

题目难度Easy

你的朋友正在使用键盘输入他的名字 name。偶尔，在键入字符 c 时，按键可能会被长按，而字符可能被输入 1 次或多次。

你将会检查键盘输入的字符 typed。如果它对应的可能是你的朋友的名字（其中一些字符可能被长按），那么就返回 True。

示例 1：

输入：name = "alex", typed = "aaleex"
输出：true
解释：'alex' 中的 'a' 和 'e' 被长按。

示例 2：

输入：name = "saeed", typed = "ssaaedd"
输出：false
解释：'e' 一定需要被键入两次，但在 typed 的输出中不是这样。

示例 3：

输入：name = "leelee", typed = "lleeelee"
输出：true

示例 4：

输入：name = "laiden", typed = "laiden"
输出：true
解释：长按名字中的字符并不是必要的。

提示：

name.length <= 1000
typed.length <= 1000
name 和 typed 的字符都是小写字母。

思路：

两个指针分别指向name和typed，如果字符相等，就都右移一；
如果不等，检查typed中字符是否重复，如果不重复直接返回False，如果重复就一直指针一直右移到不重复为止；
重复前两个步骤直到其中一个指针遍历完成，如果name未遍历完成而typed遍历完成了，那么返回False，如果typed未遍历完成而name遍历完成了，那么要判断是否typed后面多余的字符都是name的最后一个字符，是则返回True，否则返回False。

时间复杂度 $O(N)$

空间复杂度 $O(1)$

代码：

class Solution:
    def isLongPressedName(self, name: str, typed: str) -> bool:
        p1 = 0
        p2 = 0
        while p1 < len(name) and p2 < len(typed):
            if name[p1] == typed[p2]:
                p1 += 1
                p2 += 1
            elif p2 > 0 and typed[p2] == typed[p2 - 1]:
                p2 += 1
            else:
                return False
        if p1 < len(name):
            return False
        while p2 < len(typed):
            if typed[p2] != typed[p2 - 1]:
                return False
            p2 += 1
        return True

926. 将字符串翻转到单调递增

题目难度Medium

如果一个由 '0' 和 '1' 组成的字符串，是以一些 '0'（可能没有 '0'）后面跟着一些 '1'（也可能没有 '1'）的形式组成的，那么该字符串是单调递增的。

我们给出一个由字符 '0' 和 '1' 组成的字符串 S，我们可以将任何 '0' 翻转为 '1' 或者将 '1' 翻转为 '0'。

返回使 S 单调递增的最小翻转次数。

示例 1：

输入："00110"
输出：1
解释：我们翻转最后一位得到 00111.

示例 2：

输入："010110"
输出：2
解释：我们翻转得到 011111，或者是 000111。

示例 3：

输入："00011000"
输出：2
解释：我们翻转得到 00000000。

提示：

1 <= S.length <= 20000
S 中只包含字符 '0' 和 '1'

思路：

本题有多种思路

用cnt0[i]表示第i位（包含）之前有多少个0，那么我们只需要寻找一个分割点i，让i之前的1和i之后的0数目之和最小。
从头遍历，从第一个1开始0的数目和1的数目赛跑，每次0的数目超过1的数目翻转前面的所有1，再找到下一个1从新计数，以此类推。最后0的数目不超过1的数目翻转后面剩下的0。程序中只需要计数，不需要真实的翻转。
某一位为1时，前面一位是0或者1都可以；某一位为0时，前面一位只能为0。
用one表示到第i位为止1的个数，用d表示1的个数减去0的个数，遍历时维护d的最小值，即可得到结果为d + len(S) - one。

时间复杂度 $O(N)$

空间复杂度 $O(N)$

代码：

class Solution:
    def minFlipsMonoIncr(self, S: str) -> int:
        l = len(S)
        cnt0 = [0] * (l + 1)
        for i in range(l):
            cnt0[i + 1] = cnt0[i]
            if S[i] == "0":
                cnt0[i + 1] += 1
        ans = l - cnt0[l]
        for i in range(l):
            ans = min(ans, i - cnt0[i] + cnt0[l] - cnt0[i])
        return ans

解法2：

class Solution:
    def minFlipsMonoIncr(self, S: str) -> int:
        p, ans, zero, one = 0, 0, 0, 0
        while p < len(S):
            if S[p] == '1':
                one += 1
            elif one > 0:
                zero += 1
            if zero > one:
                ans += one
                zero, one = 0, 0
            p += 1
        return ans + zero

解法3：

class Solution:
    def minFlipsMonoIncr(self, S: str) -> int:
        zero, one = 0, 0
        for i in S:
            if i == '1':
                one = min(zero, one)
                zero += 1
            else:
                one = min(zero, one) + 1
        return min(zero, one)

解法4：

class Solution:
    def minFlipsMonoIncr(self, S: str) -> int:
        one, d = 0, 0
        for i in range(0, len(S)):
            if S[i] == '1':
                one += 1
            elif d > one - (i + 1 - one):
                d = one - (i + 1 - one)
        return d + len(S) - one

927. 三等分

题目难度Hard

给定一个由 0 和 1 组成的数组 A，将数组分成 3 个非空的部分，使得所有这些部分表示相同的二进制值。

如果可以做到，请返回任何 [i, j]，其中 i+1 < j，这样一来：

A[0], A[1], ..., A[i] 组成第一部分；
A[i+1], A[i+2], ..., A[j-1] 作为第二部分；
A[j], A[j+1], ..., A[A.length - 1] 是第三部分。
这三个部分所表示的二进制值相等。

如果无法做到，就返回 [-1, -1]。

注意，在考虑每个部分所表示的二进制时，应当将其看作一个整体。例如，[1,1,0] 表示十进制中的 6，而不会是 3。此外，前导零也是被允许的，所以 [0,1,1] 和 [1,1] 表示相同的值。

示例 1：

输入：[1,0,1,0,1]
输出：[0,3]

示例 2：

输出：[1,1,0,1,1]
输出：[-1,-1]

提示：

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

思路：

直接模拟判断：首先统计1的个数，如果1的个数不是3的倍数，那么直接返回无解；如果数组中没有1，那么直接返回[0, 2]。否则按照1的个数来划分数组，判断表示的二进制是否相等，注意最后一个数有多少个结尾0。

时间复杂度 $O(N)$

空间复杂度 $O(N)$

代码：

class Solution:
    def threeEqualParts(self, A: List[int]) -> List[int]:
        
        def check(A1, A2, A3):
            if not len(A1) == len(A2) == len(A3):
                return False
            for i in range(len(A1)):
                if not A1[i] == A2[i] == A2[i]:
                    return False
            return True
        
        cnt1 = 0
        for i in A:
            if i == 1:
                cnt1 += 1
        if cnt1 == 0:
            return [0, 2]
        if cnt1 % 3 != 0:
            return [-1, -1]
        interval = [[0, 0], [0, 0], [0, 0]]
        cnt = 0
        j = 0
        for i in range(len(A)):
            if A[i] == 1:
                if cnt == 0:
                    interval[j][0] = i
                cnt += 1
                if cnt == cnt1 // 3:
                    interval[j][1] = i + 1
                    j += 1
                    cnt = 0
        if check(A[interval[0][0]:interval[0][1]], A[interval[1][0]:interval[1][1]], A[interval[2][0]:interval[2][1]]):
            zero_last = len(A) - interval[2][1]
            if interval[1][0] - interval[0][1] >= zero_last and interval[2][0] - interval[1][1] >= zero_last:
                return [interval[0][1] - 1 + zero_last, interval[1][1] + zero_last]
            else:
                return [-1, -1]
        else:
            return [-1, -1]

更简单的写法：

class Solution:
    def threeEqualParts(self, A: List[int]) -> List[int]:
        N = len(A)
        pos = [i for i in range(N) if A[i] == 1]
        if not pos:return [0,N-1]
        rd1, rd2, rd3 = pos[0], pos[len(pos)//3], pos[len(pos)//3*2]
        sub = N - rd3
        if len(pos)%3 == 0 and A[rd1:rd1+sub] == A[rd2:rd2+sub] == A[rd3:]:
            return [rd1+sub-1,rd2+sub]
        return [-1,-1]

928. 尽量减少恶意软件的传播 II

题目难度Hard

(这个问题与 尽量减少恶意软件的传播 是一样的，不同之处用粗体表示。)

在节点网络中，只有当 graph[i][j] = 1 时，每个节点 i 能够直接连接到另一个节点 j。

一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。

假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。

我们可以从初始列表中删除一个节点，并完全移除该节点以及从该节点到任何其他节点的任何连接。如果移除这一节点将最小化 M(initial)，则返回该节点。如果有多个节点满足条件，就返回索引最小的节点。

示例 1：

输出：graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
输入：0

示例 2：

输入：graph = [[1,1,0],[1,1,1],[0,1,1]], initial = [0,1]
输出：1

示例 3：

输入：graph = [[1,1,0,0],[1,1,1,0],[0,1,1,1],[0,0,1,1]], initial = [0,1]
输出：1

提示：

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

思路：

根据题意直接进行initial.length遍BFS统计病毒感染数，最少的即为答案。BFS时，需要剔除第i个结点，直接先把它标记为被访问过即可。

时间复杂度 $O(NM)$

空间复杂度 $O(N)$

代码：

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        
        def bfs(g, init, i):
            ret = 0
            n = len(g)
            visited = [False] * n
            visited[init[i]] = True
            q = []
            for j in range(len(init)):
                if j != i:
                    q.append(init[j])
                    visited[init[j]] = True
            while q:
                t = []
                while q:
                    node = q.pop()
                    for j in range(n):
                        if not visited[j] and g[node][j]:
                            t.append(j)
                            visited[j] = True
                            ret += 1
                q = t
            return ret
        
        initial.sort()
        ans = initial[0]
        m = bfs(graph, initial, 0)
        for i in range(1, len(initial)):
            t = bfs(graph, initial, i)
            if t < m:
                m = t
                ans = initial[i]

        return ans

LeetCode第107场周赛题解

925. 长按键入

926. 将字符串翻转到单调递增

927. 三等分

928. 尽量减少恶意软件的传播 II

猜你喜欢

热点阅读