922. 按奇偶排序数组 II
- 题目难度
Easy
给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。
对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。
你可以返回任何满足上述条件的数组作为答案。
示例：
输入：[4,2,5,7]
输出：[4,5,2,7]
解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。
提示：
2 <= A.length <= 20000A.length % 2 == 00 <= A[i] <= 1000
思路：
开一个ans数组，双指针遍历，p1代表偶数指针，初始指向ans[0]，p2代表奇数指针，初始指向ans[1]。遍历数组A，如果是偶数就写入p1指针所在位置，并将p1指针加2，否则就写入p2指针位置，并将p2加2。
时间复杂度
空间复杂度
代码：
class Solution:
def sortArrayByParityII(self, A: List[int]) -> List[int]:
l = len(A)
ans = [0] * l
p1 = 0
p2 = 1
for i in A:
if i % 2 == 0:
ans[p1] = i
p1 += 2
else:
ans[p2] = i
p2 += 2
return ans
921. 使括号有效的最少添加
- 题目难度
Medium
给定一个由 '(' 和 ')' 括号组成的字符串 S，我们需要添加最少的括号（ '(' 或是 ')'，可以在任何位置），以使得到的括号字符串有效。
从形式上讲，只有满足下面几点之一，括号字符串才是有效的：
- 它是一个空字符串，或者
- 它可以被写成
AB（A与B连接）, 其中A和B都是有效字符串，或者 - 它可以被写作
(A)，其中A是有效字符串。
给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。
示例 1：
输入："())"
输出：1
示例 2：
输入："((("
输出：3
示例 3：
输入："()"
输出：0
示例 4：
输入："()))(("
输出：4
提示：
S.length <= 1000-
S只包含'('和')'字符。
思路：
与判断括号是否合法算法一样，利用栈结构，左括号入栈，遇到右括号出栈，只不过是在判断过程中，如果非法（栈空）就补充一个左括号继续判断，结束后，如果栈非空，还要补充同样多数量的右括号，一共补充括号的数量就是答案。
时间复杂度
空间复杂度
代码：
class Solution:
def minAddToMakeValid(self, S: str) -> int:
s = []
ans = 0
for i in S:
if i == "(":
s.append(i)
else:
if not s:
ans += 1
else:
s.pop()
ans += len(s)
return ans
923. 三数之和的多种可能
- 题目难度
Medium
给定一个整数数组 A，以及一个整数 target 作为目标值，返回满足 i < j < k 且 A[i] + A[j] + A[k] == target 的元组 i, j, k 的数量。
由于结果会非常大，请返回 结果除以 10^9 + 7 的余数。
示例 1：
输入：A = [1,1,2,2,3,3,4,4,5,5], target = 8
输出：20
解释：
按值枚举（A[i]，A[j]，A[k]）：
(1, 2, 5) 出现 8 次；
(1, 3, 4) 出现 8 次；
(2, 2, 4) 出现 2 次；
(2, 3, 3) 出现 2 次。
示例 2：
输入：A = [1,1,2,2,2,2], target = 5
输出：12
解释：
A[i] = 1，A[j] = A[k] = 2 出现 12 次：
我们从 [1,1] 中选择一个 1，有 2 种情况，
从 [2,2,2,2] 中选出两个 2，有 6 种情况。
提示：
3 <= A.length <= 30000 <= A[i] <= 1000 <= target <= 300
思路：
先将数组A去重复，然后枚举三数之和可能的组合(i,j,k)满足i<=j<=k，最后用计数算这种组合对答案有多少贡献，累加得到答案。
时间复杂度
空间复杂度
代码：
class Solution:
def threeSumMulti(self, A: List[int], target: int) -> int:
mod = 1000000007
cnt = collections.Counter(A)
ans = 0
for i in range(min(101, target + 1)):
for j in range(i, target - i + 1):
k = target - i - j
cur = 0
if k < j:
break
if k > 100:
continue
if i == j and j == k:
cur = (cnt[i]) * (cnt[j] - 1) * (cnt[k] - 2) // 6 % mod;
elif i == j and j != k:
cur = (cnt[i]) * (cnt[j] - 1) // 2 * cnt[k] % mod;
elif i != j and j == k:
cur = (cnt[i]) * cnt[j] * (cnt[k] - 1) // 2 % mod;
else:
cur = (cnt[i]) * cnt[j] * cnt[k] % mod;
ans = (ans + cur) % mod;
return ans
924. 尽量减少恶意软件的传播
- 题目难度
Hard
在节点网络中，只有当 graph[i][j] = 1 时，每个节点 i 能够直接连接到另一个节点 j。
一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。
假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。
我们可以从初始列表中删除一个节点。如果移除这一节点将最小化 M(initial)， 则返回该节点。如果有多个节点满足条件，就返回索引最小的节点。
请注意，如果某个节点已从受感染节点的列表 initial 中删除，它以后可能仍然因恶意软件传播而受到感染。
示例 1：
输入：graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
输出：0
示例 2：
输入：graph = [[1,0,0],[0,1,0],[0,0,1]], initial = [0,2]
输出：0
示例 3：
输入：graph = [[1,1,1],[1,1,1],[1,1,1]], initial = [1,2]
输出：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
思路：
先用并查集求图的连通分量个数，再统计每个连通分量有多少个结点，然后求病毒所在连通分量，如果多个病毒在一个连通分量，那么删除其中任意一个病毒都不会使染毒结点减少，只有删除独占连通分量的病毒才有意义。那么遍历独占连通分量的病毒，看哪个独占连通分量的病毒影响结点数最多，即得出答案。
时间复杂度
空间复杂度
代码：
class Solution:
def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
n = len(graph)
# 并查集
father = [i for i in range(n)]
def get_father(i):
if father[i] == i:
return i
else:
father[i] = get_father(father[i])
return father[i]
for i in range(n - 1):
for j in range(i + 1, n):
if graph[i][j]:
fi = get_father(i)
fj = get_father(j)
if fi != fj:
father[fj] = fi
# 初始结点从小到大排序
initial.sort()
v_n = len(initial)
num = [0] * n
# 统计连通分量大小
for i in range(n):
num[get_father(i)] += 1
# 求每个病毒结点属于哪个连通分量
v_fa = [0] * v_n
for i in range(v_n):
v_fa[i] = get_father(initial[i])
# 如果多个病毒属于一个连通分量，那么删除哪个都不会使最终结果减小
cnt = collections.Counter(v_fa)
m = 0
ans = initial[0]
for i in range(v_n):
# 只有删除独占一个连通分量的病毒才有意义
if cnt[v_fa[i]] == 1 and num[v_fa[i]] > m:
ans = initial[i]
m = num[v_fa[i]]
return ans
