LeetCode第107场周赛题解

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
解释:长按名字中的字符并不是必要的。

提示:

  1. name.length <= 1000
  2. typed.length <= 1000
  3. nametyped 的字符都是小写字母。

思路:

  1. 两个指针分别指向nametyped,如果字符相等,就都右移一;
  2. 如果不等,检查typed中字符是否重复,如果不重复直接返回False,如果重复就一直指针一直右移到不重复为止;
  3. 重复前两个步骤直到其中一个指针遍历完成,如果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. 1 <= S.length <= 20000
  2. S 中只包含字符 '0''1'

思路:

本题有多种思路

  1. cnt0[i]表示第i位(包含)之前有多少个0,那么我们只需要寻找一个分割点i,让i之前的1i之后的0数目之和最小。
  2. 从头遍历,从第一个1开始0的数目和1的数目赛跑,每次0的数目超过1的数目翻转前面的所有1,再找到下一个1从新计数,以此类推。最后0的数目不超过1的数目翻转后面剩下的0。程序中只需要计数,不需要真实的翻转。
  3. 某一位为1时,前面一位是0或者1都可以;某一位为0时,前面一位只能为0
  4. 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

给定一个由 01 组成的数组 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]

提示:

  1. 3 <= A.length <= 30000
  2. A[i] == 0A[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. 1 < graph.length = graph[0].length <= 300
  2. 0 <= graph[i][j] == graph[j][i] <= 1
  3. graph[i][i] = 1
  4. 1 <= initial.length < graph.length
  5. 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
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 219,753评论 6 508
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 93,668评论 3 396
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 166,090评论 0 356
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 59,010评论 1 295
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 68,054评论 6 395
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,806评论 1 308
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,484评论 3 420
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 39,380评论 0 276
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,873评论 1 319
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 38,021评论 3 338
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 40,158评论 1 352
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,838评论 5 346
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 41,499评论 3 331
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 32,044评论 0 22
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,159评论 1 272
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 48,449评论 3 374
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 45,136评论 2 356

推荐阅读更多精彩内容

  • 922. 按奇偶排序数组 II 题目难度Easy 给定一个非负整数数组 A, A 中一半整数是奇数,一半整数是偶数...
    独孤岳阅读 452评论 0 0
  • 914. 卡牌分组 题目难度Easy 给定一副牌,每张牌上都写着一个整数。 此时,你需要选定一个数字 X,使我们可...
    独孤岳阅读 665评论 0 0
  • 900. RLE 迭代器 题目难度Medium 编写一个遍历游程编码序列的迭代器。 迭代器由 RLEIterato...
    独孤岳阅读 2,167评论 0 1
  • 阳光普照万物 不是为了祈求回报 只是为了平复自己燥动的心跳 萤虫之光 虽也明亮 但它只是为了把食物寻找 给予了 就...
    空梦幻花阅读 453评论 2 1
  • 初夏黄昏,夕阳西下。远方的天空在太阳的余辉照耀下一片金黄,地上是一望无垠的麦田,一阵微风吹来金黄色麦浪随风起伏。 ...
    萧萧秋雨阅读 928评论 37 31