[Python3] 领扣第22场周赛 题解

327. 计算距离和

描述 对于给定数组中的每个元素，计算它与值相同的所有其他元素的距离和，即索引差的绝对值之和，在数组中返回结果值。例如，如果数组中下标2和3的元素相等，则元素2的距离和为| 2 - 3 | =1，3号元素的距离和为| 3 - 2 | =1。 解：

感觉写麻烦了 ，没想过有没有简单点。。 class Solution: """ @param a: an integer array @return: an integer array """ def getDistanceMetrics(self, A): # write your code here. d = collections.defaultdict(list) for i, x in enumerate(A): d[x].append(i) def cal(A): C = [] for x in A: if not C: C.append(x) else: C.append(x + C[-1]) n = len(A) ret = [0] * n for i in range(n): if i > 0: ret[i] = C[-1]-2*C[i-1] + A[i] * (2*i-n) else: ret[i] = C[-1] + A[i] * (2*i-n) return ret for x in d: d[x] = cal(d[x]) ans = [] for i, x in enumerate(A): ans.append(d[x][0]) del d[x][0] return ans

322. 象棋游戏

描述 在棋盘上 给定一个长度为$N$的二元组数组$queen$，代表$N$个皇后棋子的坐标 给定一个长度为$M$的二元组数组$knight$，代表$M$个骑士棋子的坐标 每个皇后可以袭击同行，同列，或者同对角线的任意一个骑士棋子 请你返回一个长度为M的答案数组，依次代表每个骑士棋子是否会被攻击到

解：

打卡 class Solution: """ @param queen: queen‘coordinate @param knight: knight‘coordinate @return: if knight is attacked please return true，else return false """ def isAttacked(self, queen, knight): # write your code here row, col, dig, dig2 = set(), set(), set(), set() for x, y in queen: row.add(x) col.add(y) dig.add(x-y) dig2.add(x+y) ret = [] for x, y in knight: if x in row or y in col or x-y in dig or x+y in dig2: ret.append(True) else: ret.append(False) return ret

325. 足球比赛描述

考虑一个包含16支球队的淘汰赛足球赛，表示为$0，1，\dots ，15$。在每一轮的比赛中，所有仍在比赛中的球队都会按递增的顺序排列在一个名单中。然后，名单上的第一队与第二队比赛，第三队与第四队比赛，这些比赛的胜者晋级下一轮，输家被淘汰。四轮过后，只有一支球队保持不败，该队被宣布获胜。

给定一个矩阵$P=[p_{ij}]$，即$p_{ij}$是$i$队在比赛中击败j队的概率，决定哪支球队最有可能赢得锦标赛。

Hint：如果多支队伍获胜概率相同，优先返回下标最小的。 解：

全概率展开 class Solution: """ @param probability: the winning probability of 16 teams in pairs @return: return the index of the winner with the highest probability of winning """ def findWinner(self, P): # write your code here total_p = [0] * 16 def f(A, p): n = len(A) k = n >> 1 if n == 1: total_p[A[0]] += p return for i in range(1 << k): Q, np = [], p for j in range(k): if i & (1 << j) == 1 << j: Q.append(A[2*j]) np *= P[A[2*j]][A[2*j+1]] else: Q.append(A[2*j+1]) np *= 1 - P[A[2*j]][A[2*j+1]] f(Q, np) f([i for i in range(16)], 1.0) for i, x in enumerate(total_p): if x == max(total_p): return i

324. 正则表达式查询

描述 实现支持.,^,$,*,?,+和正则表达式查找。

. 匹配任意一个字符 ^ 匹配字符串的开头 $ 匹配字符串的结尾 * 匹配零个或者多个前面的字符。比如，ab*可以匹配a,ab,abb,abbb,... ? 匹配零个或者一个前面的字符。比如，ab?可以匹配a,ab + 匹配一个或者多个前面的字符。比如，ab+可以匹配ab,abb,abbb,...

现在给定一个格式串$formatString$和多个查询串$queryStrings$，请依次判断正则表达式$formatString$和每个查询字符串中的某个子串间是否有匹配。

如果你不能理解的匹配规则的话，可以去regex101尝试~

解：

dp[i][j] 表示pattern前0~i个元素，可以看做一个一个小pattern， 是否和以第j个元素结尾的字符串是否匹配。 数据量比较小算一下$2\ast 10^5$如果数据量大， 可以考虑用trie来做， 公共前缀可以不用重复计算。 class Solution: """ @param formatString: the format string @param queryStrings: the query strings @return: judge isMatch """ def isMatch(self, formatString, queryStrings): # write your code here def pf(x): return self.singlematch(formatString, x) return [*map(pf,queryStrings)] def singlematch(self, p, q): q = "^" + q + "$" n, m = len(p), len(q) dp = [[False] * m for _ in range(n)] # dp {pattern} {query} for j in range(m): for i in range(n): if q[j] == p[i] or (p[i] == '.' and q[j] != '^'): dp[i][j] = dp[i-1][j-1] if i - 1 >= 0 and j - 1 >= 0 else True elif p[i] == '?': dp[i][j] |= dp[i-2][j] if i -2 >= 0 else True if q[j] == p[i - 1] or (p[i - 1] == '.' and q[j] != '^'): dp[i][j] |= dp[i - 2][j - 1] if i - 2>= 0 and j - 1 >= 0 else True elif p[i] == '+' and (q[j] == p[i - 1] or (p[i - 1] == '.' and q[j] != '^')): dp[i][j] |= dp[i - 2][j - 1] if i - 2 >= 0 and j - 1 >= 0 else True dp[i][j] |= dp[i][j - 1] if j - 1 >= 0 else True elif p[i] == '*': dp[i][j] |= dp[i-2][j] if (p[i-1] == '.' and q[j] != '^') or p[i - 1] == q[j]: dp[i][j] |= dp[i][j-1] if i - 1 >= 0 and j - 1 >= 0 else True for j in range(m): if dp[-1][j]: return True return False if __name__ == "__main__": p = "^ab*c?d+.$" qs = ["adcc"] print(Solution().isMatch(p, qs)) print( True and False or False, 1 and 2, 1 & 2 )