讨论/技术交流/🏆 第 250 场力扣周赛/
🏆 第 250 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛】

image.png

3 分 - 可以输入的最大单词数
4 分 - 新增的最少台阶数
5 分 - 扣分后的最大得分
6 分 - 查询最大基因差

共 85 个回复

Leetcode 第250场周赛题解

Problem A - 可以输入的最大单词数

方法一:模拟

拆分成单词后,检查每个单词是否含有损坏的字母即可。

  • 时间复杂度O(∣S∣)\mathcal{O}(|S|)。
  • 空间复杂度O(∣S∣)\mathcal{O}(|S|)。

参考代码(Python 3)

class Solution: def canBeTypedWords(self, text: str, brokenLetters: str) -> int: words = text.split() broken = set(brokenLetters) ans = 0 for word in words: can = True for ch in word: if ch in broken: can = False break if can: ans += 1 return ans

Problem B - 新增的最少台阶数

方法一:贪心

要求新增台阶数最少,我们就贪心地尽可能用上每一块已有的台阶。如果相邻两块台阶之间的距离Δ\Delta超过了distdist,我们就增加⌊Δ−1dist⌋\left\lfloor\frac{\Delta-1}{dist}\right\rfloor块台阶。

  • 时间复杂度O(N)\mathcal{O}(N)。
  • 空间复杂度O(1)\mathcal{O}(1)。

参考代码(C++)

class Solution { public: int addRungs(vector<int>& rungs, int dist) { int now = 0, ans = 0; for (int rung : rungs) { ans += (rung - now - 1) / dist; now = rung; } return ans; } };

Problem C - 扣分后的最大得分

方法一:动态规划

显然当前行的分数只与上一行的选择有关,因此容易想到使用动态规划求解。但朴素的动态规划算法中,我们对于当前行的每一列,都需要考虑上一行的每一列,总时间复杂度为O(RC2)\mathcal{O}(RC^2)会超时。

如何进行优化呢?

对于某一列,我们可以考虑上一行所选定的列在其左侧还是在其右侧。

首先考虑左侧的情况。我们从左到右依次处理。假设当前来自左侧的最大值为lmaxlmax,则每次右移时,lmaxlmax会变为max(lmax−1,dp[i])max(lmax-1, dp[i])。这是因为,如果上一行选择的列在左边,不管它具体在哪一个位置,这次右移时一定会减少11的分数;而如果选择当前列正上方的格子,则不会扣除分数。

右侧的情况与之类似。

这样,我们就在O(C)\mathcal{O}(C)的时间里完成了一行的转移,从而将总时间复杂度降低到了O(RC)\mathcal{O}(RC)。

  • 时间复杂度O(RC)\mathcal{O}(RC)。
  • 空间复杂度O(C)\mathcal{O}(C)。

参考代码(C++)

class Solution { public: long long maxPoints(vector<vector<int>>& points) { int n = points.size(), m = points[0].size(); vector<long long> dp(m); for (int i = 0; i < n; ++i) { vector<long long> ndp(m); long long lmax = 0; for (int j = 0; j < m; ++j) { lmax = max(lmax - 1, dp[j]); ndp[j] = max(ndp[j], lmax); } long long rmax = 0; for (int j = m - 1; j >= 0; --j) { rmax = max(rmax - 1, dp[j]); ndp[j] = max(ndp[j], rmax); } for (int j = 0; j < m; ++j) ndp[j] += points[i][j]; dp = move(ndp); } return *max_element(dp.begin(), dp.end()); } };

Problem D - 查询最大基因差

方法一:0-1字典树+离线查询

在回答一次查询时,我们需要考虑的是nodeinode_i及其所有的祖先节点。注意到在DFS过程中,我们访问到一个节点时,栈中的元素恰好是其和其所有祖先节点,因此想到利用DFS来离线完成查询。

具体的做法是,把查询按照nodeinode_i进行分组,然后进行DFS。DFS到某一个节点时,完成所有询问这一节点的查询。

求最大异或和的经典方法是0-1字典树。字典树中越靠近根部的节点代表更高的二进制位。对于给定的valval,我们按照二进制位由高到低处理,对于第ii位,如果字典树中存在与valval的第ii位相异的节点,则进入对应分支,并将这一位对应的数值累加入最后的答案;否则,我们进入另一分支,同时答案保持不变。

本题中,我们需要在DFS过程中对0-1字典树进行动态更新。因为节点出栈时需要将其对应的贡献删去,这里为了简化操作,我们不删除字典树中节点,而是给每个节点增加一个计数值。在节点入栈时将其二进制位所对应的字典树节点加一,而在出栈时将对应节点减一。计数值为00的节点在查询时应当视同不存在。

  • 时间复杂度O((N+Q)K)\mathcal{O}((N+Q)K)。其中KK为考虑的二进制位数。
  • 空间复杂度O(N+Q+2K)\mathcal{O}(N+Q+2^K)。

参考代码(C++)

const int K = 20; struct TrieNode { int cnt = 0; TrieNode *children[2]{}; }; void dfs(int u, vector<vector<int>> &adj, vector<vector<pair<int, int>>> &groups, TrieNode *trie, vector<int> &ans) { TrieNode *p = trie; for (int k = K - 1; k >= 0; --k) { int nxt = (u & (1 << k)) ? 1 : 0; if (!p->children[nxt]) p->children[nxt] = new TrieNode(); p = p->children[nxt]; p->cnt++; } for (auto [val, idx] : groups[u]) { p = trie; int hi = 0; for (int k = K - 1; k >= 0; --k) { int nxt = (val & (1 << k)) ? 0 : 1; if (p->children[nxt] && p->children[nxt]->cnt) { p = p->children[nxt]; hi ^= (1 << k); } else { if (!p->children[nxt ^ 1]) p->children[nxt ^ 1] = new TrieNode(); p = p->children[nxt ^ 1]; } } ans[idx] = hi; } for (int v : adj[u]) { dfs(v, adj, groups, trie, ans); } p = trie; for (int k = K - 1; k >= 0; --k) { int nxt = (u & (1 << k)) ? 1 : 0; p = p->children[nxt]; p->cnt--; } } class Solution { public: vector<int> maxGeneticDifference(vector<int>& parents, vector<vector<int>>& queries) { int root = -1; int n = parents.size(); vector<vector<int>> adj(n); for (int i = 0; i < n; ++i) { if (parents[i] == -1) root = i; else adj[parents[i]].emplace_back(i); } assert(root != -1); int q = queries.size(); vector<int> ans(q); vector<vector<pair<int, int>>> groups(n); for (int i = 0; i < q; ++i) { int node = queries[i][0], val = queries[i][1]; groups[node].emplace_back(val, i); } TrieNode *trie = new TrieNode(); dfs(root, adj, groups, trie, ans); return ans; } };

方法二:可持久化字典树+在线查询

如果题目强制进行在线查询,我们可以使用可持久化字典树的方法,建立出根节点到每一个节点的范围内的节点所对应的字典树,然后利用这些字典树进行查询。其核心思想是,每次只增加一个或减少一个数时,并不需要重建整个字典树,至多只需要修改字典树中KK个节点。复用原有的节点,并新建至多KK个节点,我们就可以得到新状态对应的字典树。

具体实现略。

41

终究还是太菜了,只会两题。

31

简单写一下自己的做法。


A 题直接按照空格分割出单词,然后枚举每一个单词在不在限制集里面就行了。


B 题可以发现,在长度超过 dist 的时候需要加一个,超过 2*dist 的时候需要加两个,以此类推,那么对于一个距离,要加的个数就是 ⌊x−1dist⌋\lfloor\dfrac{x-1}{dist}\rfloor。


C 题我们假设 dp[i][j] 是前 i 行,第 i 行取了第 j 个的最大答案,很容易列方程:
dp[i][j] = max(dp[i-1][k] + abs(k-j)) + points[i][j]
在 k<=j 的情况中,我们发现 dp[i-1][k] + abs(k-j) = (dp[i-1][k] + k) - j,那么我们维护前缀中 dp[i-1][k] + k 的最大值,设为数组 L[i],那么答案的一部分就成为了 L[i][j] - j。
同理在 k>=j 的情况中,维护后缀中 dp[i-1] - k 的最大值,设为数组 R[i],那么答案的另一部分就是 R[i][j] + j
所以方程变成了 dp[i][j] = max(L[i][j] - j, R[i][j] + j) + points[i][j],可以 O(1) 算出。
由于 L 数组和 R 数组每次处理一行都是线性的,所以综合起来复杂度就是 O(n*m)。


D 题看到处理一堆数和一个数异或最大值的问题,直接考虑 01-Trie。由于我们不能暴力直接把每一个点到根路径的点编号全部放在 01-Trie,但是我们可以在 dfs 的过程中把每一个点到根的路径都获取。在每次 dfs 的开始,加上所在点,然后搜索儿子,最后减去所在点就好了。
我们可以把每个点的询问分开,搜索到每一个点的时候就顺便计算完对应的询问答案就行。
关于 01-Trie 的删除数字,为了写的方便,可以直接进行子树大小的删减而不需要再进行内存回收。

10

两题选手

10

手速差了点,无缘键盘.jpg

9

人麻了,没做第三题去做第四题,在结束后 30 秒提交成功。。

5

[T1]
枚举

class Solution(object): def canBeTypedWords(self, text, brokenLetters): """ :type text: str :type brokenLetters: str :rtype: int """ text = text.split(" ") ans = 0 for v in text: flag = 1 for t in v: if t in brokenLetters: flag = 0 ans += flag return ans

[T2]
数学

class Solution(object): def addRungs(self, rungs, dist): """ :type rungs: List[int] :type dist: int :rtype: int """ now = 0 ans = 0 for v in rungs: ans += (v-now-1) // dist now = v return ans

[T3]
DP,很容易想出转移方程f[i][j]=max(f[i-1][k]-abs(j-k))+points[i][j],但这里需要枚举i,j,k,复杂度变成O(nm^2),即使根据长宽转置,m最少也是300多,nm^2大概是3kw的数量级(c++其实有可能可以过,毕竟常数很小)。

那么如何进行优化呢,注意到,上面式子可以进行拆分:
对于f[i][j],当k<j时,f[i][j] = max(f[i-1][k]-j+k)+points[i][j]=max(f[i-1][k]+k)-j+points[i][j],这里的max(f[i-1][k]+k),是所有k<j的最大值,这个值可以O(1)进行维护,从而复杂度中的循环k就被优化掉了,总的复杂度是O(nm),对于python也绰绰有余。

(注意k<j和k>=j要循环两次)

class Solution(object): def maxPoints(self, points): """ :type points: List[List[int]] :rtype: int """ n = len(points) m = len(points[0]) f = [[0] * m for i in range(n)] for i in range(n): if i == 0: for j in range(m): f[i][j] = points[i][j] else: Max = 0 for j in range(m): Max = max(Max-1, f[i-1][j]) f[i][j] = Max + points[i][j] Max = 0 for j in range(m-1, -1, -1): Max = max(Max-1, f[i-1][j]) f[i][j] = max(f[i][j], Max + points[i][j]) return max(f[n-1])

[T4]
xor+可持久化建树

从给定集合中寻找一个和指定数xor和最大的问题,是非常经典的问题,做法就是将集合中所有数根据其二进制表现进行建树,然后对于指定数,从高位向低位,尽可能在树上找和它值相反的点(这样xor就为1)

但是该题中的集合有所差别,它不是一个区间,而是一颗树,每次询问的区间是从一个节点到根节点的所有节点,这时候,就需要对每个节点到根节点的路径上所有点的集合进行建树,如果暴力做,肯定会超时。

这时候,就要用到“可持久化”的技术。具体来说,就是对于节点i和其父亲parents,他们到根节点的集合其实只差i这一个点,也就是说i节点建的树,对于parents[i]来说,只有log个节点需要修改,所以,第i个节点,不需要完全重新建树,而只需要基于parents[i]建好的树,只修改发生变化的节点。而没有变化的节点,则直接指过去即可(如下图,红色为修改的节点)。

1626579544(1).png

而查询的时候,只需要调出节点i的树,即表示从i到根节点的所有元素集合,直接贪心查询即可。

我一开始实现了python版本,结果TLE了,10w点*20次的循环python就要跪,以后循环次数上百万尽量避免python。但相对来说python更容易理解一些,这里把两个版本都贴上来:

实际上,如果在每个节点上再进行计数,则可以处理更复杂的版本:
如:
从一个节点到它往上的某个节点之间的集合
任意两个节点的集合(先求LCA,再合并分别从两个节点到LCA的路径集合)

const int MAXN = 120000; int Head[MAXN], Next[MAXN], Des[MAXN]; int top, N, M; int Left[MAXN * 20], Right[MAXN * 20]; int Tree[MAXN]; void Link(int a, int b) { Next[++top] = Head[a], Head[a] = top, Des[top] = b; } int Insert(int x, int val) { int nx = ++M; Left[M] = Left[x], Right[M] = Right[x]; int now = nx; for (int i = 20; i >= 0; i--) { int L = 0, R = 0; if ((val & (1<<i)) != 0) { if (Right[now] != 0) { L = Left[Right[now]]; R = Right[Right[now]]; } Right[now] = ++M; now = Right[now]; Left[now] = L; Right[now] = R; } else { if (Left[now] != 0) { L = Left[Left[now]]; R = Right[Left[now]]; } Left[now] = ++M; now = Left[now]; Left[now] = L; Right[now] = R; } } return nx; } void Dfs(int x, int Node) { Tree[x] = Insert(Node, x); for (int i = Head[x]; i; i = Next[i]) Dfs(Des[i], Tree[x]); } class Solution { public: vector<int> maxGeneticDifference(vector<int>& parents, vector<vector<int>>& queries) { memset(Head, 0, sizeof(Head)); memset(Next, 0, sizeof(Next)); memset(Des, 0, sizeof(Des)); memset(Left, 0, sizeof(Left)); memset(Right, 0, sizeof(Right)); N = parents.size(); top = 0; int root = -1; for (int i = 0; i < N; ++i) { if (parents[i] != -1) Link(parents[i], i); else root = i; } M = 1; Dfs(root, 0); vector<int> ans; ans.clear(); N = queries.size(); for (int i = 0; i < N; ++i) { int node = queries[i][0], val = queries[i][1]; int now = Tree[node]; int A = 0; for (int i = 20; i >= 0; --i) { if ((val & (1 <<i)) == 0) { if (Right[now] != 0) { A += 1<<i; now = Right[now]; } else { now = Left[now]; } } else { if (Left[now] != 0) { A += 1<<i; now = Left[now]; } else { now = Right[now]; } } } ans.push_back(A); } return ans; } };

(python 超时版本)

class TreeNode(object): def __init__(self): self.left = None self.right = None class Solution(object): def Insert(self, x, val): nx = TreeNode() nx.left = x.left nx.right = x.right now = nx for i in range(20, -1, -1): l, r = None, None if val & (1<<i) != 0: if now.right != None: l = now.right.left r = now.right.right now.right = TreeNode() now = now.right now.left = l now.right = r else: if now.left != None: l = now.left.left r = now.left.right now.left = TreeNode() now = now.left now.left = l now.right = r return nx def Dfs(self, x, Node): self.Tree[x] = self.Insert(Node, x) for e in self.E[x]: self.Dfs(e, self.Tree[x]) def maxGeneticDifference(self, parents, queries): """ :type parents: List[int] :type queries: List[List[int]] :rtype: List[int] """ self.E = dict() N = len(parents) for i in range(N): self.E[i] = [] for i in range(N): if parents[i] != -1: self.E[parents[i]].append(i) else: root = i self.Tree = dict() self.Dfs(root, TreeNode()) ans = [] for node, val in queries: now = self.Tree[node] A = 0 for i in range(20, -1, -1): if val & (1<<i) == 0: if now.right != None: A += 1 << i now = now.right else: now = now.left else: if now.left != None: A += 1 << i now = now.left else: now = now.right ans.append(A) return ans
4

用KK是因为没有根据NN的大小来建字典树,而是采取了统一值,这样不需要根据valval跟NN的大小关系来分别讨论。

空间复杂度的话,从头到尾只有一棵字典树,全扩展开也就是2K2^K。如果可持久化字典树确实会变成NKNK。

2

第一次参加,只会做前两题,第二题花的时间太多了各种用整除取余多其实好像挺简单的。。。第三题想用DP来着但是递推式没想清楚,写着写着写成DPS了orz

2

我也是。。我真是使出吃奶的力气剪了

2