925. 長(zhǎng)按鍵入
- 題目難度
Easy
你的朋友正在使用鍵盤(pán)輸入他的名字 name。偶爾杨拐，在鍵入字符 c 時(shí)棕所，按鍵可能會(huì)被長(zhǎng)按糊肠，而字符可能被輸入 1 次或多次辨宠。
你將會(huì)檢查鍵盤(pán)輸入的字符 typed。如果它對(duì)應(yīng)的可能是你的朋友的名字（其中一些字符可能被長(zhǎng)按）货裹，那么就返回 True嗤形。
示例 1：
輸入：name = "alex", typed = "aaleex"
輸出：true
解釋：'alex' 中的 'a' 和 'e' 被長(zhǎng)按。
示例 2：
輸入：name = "saeed", typed = "ssaaedd"
輸出：false
解釋：'e' 一定需要被鍵入兩次弧圆，但在 typed 的輸出中不是這樣派殷。
示例 3：
輸入：name = "leelee", typed = "lleeelee"
輸出：true
示例 4：
輸入：name = "laiden", typed = "laiden"
輸出：true
解釋：長(zhǎng)按名字中的字符并不是必要的还最。
提示：
name.length <= 1000typed.length <= 1000-
name和typed的字符都是小寫(xiě)字母。
思路：
- 兩個(gè)指針?lè)謩e指向
name和typed毡惜，如果字符相等拓轻，就都右移一； - 如果不等经伙，檢查
typed中字符是否重復(fù)扶叉，如果不重復(fù)直接返回False，如果重復(fù)就一直指針一直右移到不重復(fù)為止帕膜； - 重復(fù)前兩個(gè)步驟直到其中一個(gè)指針遍歷完成枣氧，如果
name未遍歷完成而typed遍歷完成了，那么返回False垮刹，如果typed未遍歷完成而name遍歷完成了达吞，那么要判斷是否typed后面多余的字符都是name的最后一個(gè)字符，是則返回True荒典，否則返回False酪劫。
時(shí)間復(fù)雜度
空間復(fù)雜度
代碼：
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. 將字符串翻轉(zhuǎn)到單調(diào)遞增
- 題目難度
Medium
如果一個(gè)由 '0' 和 '1' 組成的字符串，是以一些 '0'（可能沒(méi)有 '0'）后面跟著一些 '1'（也可能沒(méi)有 '1'）的形式組成的寺董，那么該字符串是單調(diào)遞增的覆糟。
我們給出一個(gè)由字符 '0' 和 '1' 組成的字符串 S，我們可以將任何 '0' 翻轉(zhuǎn)為 '1' 或者將 '1' 翻轉(zhuǎn)為 '0'遮咖。
返回使 S 單調(diào)遞增的最小翻轉(zhuǎn)次數(shù)滩字。
示例 1：
輸入："00110"
輸出：1
解釋：我們翻轉(zhuǎn)最后一位得到 00111.
示例 2：
輸入："010110"
輸出：2
解釋：我們翻轉(zhuǎn)得到 011111，或者是 000111御吞。
示例 3：
輸入："00011000"
輸出：2
解釋：我們翻轉(zhuǎn)得到 00000000麦箍。
提示：
1 <= S.length <= 20000-
S中只包含字符'0'和'1'
思路：
本題有多種思路
- 用
cnt0[i]表示第i位（包含）之前有多少個(gè)0，那么我們只需要尋找一個(gè)分割點(diǎn)i陶珠，讓i之前的1和i之后的0數(shù)目之和最小挟裂。 - 從頭遍歷，從第一個(gè)
1開(kāi)始0的數(shù)目和1的數(shù)目賽跑背率，每次0的數(shù)目超過(guò)1的數(shù)目翻轉(zhuǎn)前面的所有1，再找到下一個(gè)1從新計(jì)數(shù)嫩与，以此類推寝姿。最后0的數(shù)目不超過(guò)1的數(shù)目翻轉(zhuǎn)后面剩下的0。程序中只需要計(jì)數(shù)划滋，不需要真實(shí)的翻轉(zhuǎn)饵筑。 - 某一位為
1時(shí)，前面一位是0或者1都可以处坪；某一位為0時(shí)根资，前面一位只能為0架专。 - 用
one表示到第i位為止1的個(gè)數(shù)，用d表示1的個(gè)數(shù)減去0的個(gè)數(shù)玄帕，遍歷時(shí)維護(hù)d的最小值部脚，即可得到結(jié)果為d + len(S) - one。
時(shí)間復(fù)雜度
空間復(fù)雜度
代碼：
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
給定一個(gè)由 0 和 1 組成的數(shù)組 A裤纹，將數(shù)組分成 3 個(gè)非空的部分委刘，使得所有這些部分表示相同的二進(jìn)制值。
如果可以做到鹰椒，請(qǐng)返回任何 [i, j]锡移，其中 i+1 < j，這樣一來(lái)：
-
A[0], A[1], ..., A[i]組成第一部分漆际； -
A[i+1], A[i+2], ..., A[j-1]作為第二部分淆珊； -
A[j], A[j+1], ..., A[A.length - 1]是第三部分。 - 這三個(gè)部分所表示的二進(jìn)制值相等奸汇。
如果無(wú)法做到施符，就返回 [-1, -1]。
注意茫蛹，在考慮每個(gè)部分所表示的二進(jìn)制時(shí)操刀，應(yīng)當(dāng)將其看作一個(gè)整體。例如婴洼，[1,1,0] 表示十進(jìn)制中的 6骨坑，而不會(huì)是 3。此外柬采，前導(dǎo)零也是被允許的欢唾，所以 [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
思路：
直接模擬判斷：首先統(tǒng)計(jì)1的個(gè)數(shù)粉捻，如果1的個(gè)數(shù)不是3的倍數(shù)礁遣，那么直接返回?zé)o解；如果數(shù)組中沒(méi)有1肩刃，那么直接返回[0, 2]祟霍。否則按照1的個(gè)數(shù)來(lái)劃分?jǐn)?shù)組，判斷表示的二進(jìn)制是否相等盈包，注意最后一個(gè)數(shù)有多少個(gè)結(jié)尾0沸呐。
時(shí)間復(fù)雜度
空間復(fù)雜度
代碼：
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]
更簡(jiǎn)單的寫(xiě)法：
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
(這個(gè)問(wèn)題與 盡量減少惡意軟件的傳播 是一樣的，不同之處用粗體表示呢燥。)
在節(jié)點(diǎn)網(wǎng)絡(luò)中崭添，只有當(dāng) graph[i][j] = 1 時(shí)，每個(gè)節(jié)點(diǎn) i 能夠直接連接到另一個(gè)節(jié)點(diǎn) j叛氨。
一些節(jié)點(diǎn) initial 最初被惡意軟件感染呼渣。只要兩個(gè)節(jié)點(diǎn)直接連接棘伴，且其中至少一個(gè)節(jié)點(diǎn)受到惡意軟件的感染，那么兩個(gè)節(jié)點(diǎn)都將被惡意軟件感染屁置。這種惡意軟件的傳播將繼續(xù)焊夸，直到?jīng)]有更多的節(jié)點(diǎn)可以被這種方式感染。
假設(shè) M(initial) 是在惡意軟件停止傳播之后缰犁，整個(gè)網(wǎng)絡(luò)中感染惡意軟件的最終節(jié)點(diǎn)數(shù)淳地。
我們可以從初始列表中刪除一個(gè)節(jié)點(diǎn)，并完全移除該節(jié)點(diǎn)以及從該節(jié)點(diǎn)到任何其他節(jié)點(diǎn)的任何連接帅容。如果移除這一節(jié)點(diǎn)將最小化 M(initial)颇象， 則返回該節(jié)點(diǎn)。如果有多個(gè)節(jié)點(diǎn)滿足條件并徘，就返回索引最小的節(jié)點(diǎn)遣钳。
示例 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 <= 3000 <= graph[i][j] == graph[j][i] <= 1graph[i][i] = 11 <= initial.length < graph.length0 <= initial[i] < graph.length
思路：
根據(jù)題意直接進(jìn)行initial.length遍BFS統(tǒng)計(jì)病毒感染數(shù)，最少的即為答案麦乞。BFS時(shí)蕴茴，需要剔除第i個(gè)結(jié)點(diǎn)，直接先把它標(biāo)記為被訪問(wèn)過(guò)即可姐直。
時(shí)間復(fù)雜度
空間復(fù)雜度
代碼：
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
