Leetcode 第 43 场双周赛题解
周赛日期：2020/01/09
Hercy 想要为购买第一辆车存钱。他 每天 都往力扣银行里存钱。
最开始，他在周一的时候存入 1 块钱。从周二到周日，他每天都比前一天多存入 1 块钱。在接下来每一个周一，他都会比 前一个周一 多存入 1 块钱。
给你 n ，请你返回在第 n 天结束的时候他在力扣银行总共存了多少块钱。
示例 1：
输入：n = 4
输出：10
解释：第 4 天后，总额为 1 + 2 + 3 + 4 = 10 。
示例 2：
输入：n = 10
输出：37
解释：第 10 天后，总额为 (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4) = 37 。注意到第二个星期一，Hercy 存入 2 块钱。
示例 3：
输入：n = 20
输出：96
解释：第 20 天后，总额为 (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4 + 5 + 6 + 7 + 8) + (3 + 4 + 5 + 6 + 7 + 8) = 96 。
提示：
1 <= n <= 1000。
题解：模拟or公式
本题上手题，n不大于1000，可以直接模拟，也可以直接计算一下求和公式，这里给出公式法。
class Solution:
def totalMoney(self, n: int) -> int:
times = n // 7
yu = n % 7
res = 21 * times + (7 * (1 + times) * times) // 2 # 整周
res += times * yu + (1 + yu) * yu // 2 # 剩余天数
return res
给你一个字符串 s 和两个整数 x 和 y 。你可以执行下面两种操作任意次。
删除子字符串 "ab" 并得到 x 分。
比方说，从 "cabxbae" 删除 ab ，得到 "cxbae" 。
删除子字符串"ba" 并得到 y 分。
比方说，从 "cabxbae" 删除 ba ，得到 "cabxe" 。
请返回对 s 字符串执行上面操作若干次能得到的最大得分。
示例 1：
输入：s = "cdbcbbaaabab", x = 4, y = 5
输出：19
解释：
- 删除 "cdbcbbaaabab" 中加粗的 "ba" ，得到 s = "cdbcbbaaab" ，加 5 分。
- 删除 "cdbcbbaaab" 中加粗的 "ab" ，得到 s = "cdbcbbaa" ，加 4 分。
- 删除 "cdbcbbaa" 中加粗的 "ba" ，得到 s = "cdbcba" ，加 5 分。
- 删除 "cdbcba" 中加粗的 "ba" ，得到 s = "cdbc" ，加 5 分。
总得分为 5 + 4 + 5 + 5 = 19 。
示例 2：
输入：s = "aabbaaxybbaabb", x = 5, y = 4
输出：20
提示：
1 <= s.length <= 105
1 <= x, y <= 104
s 只包含小写英文字母。
题解：贪心
x, y谁大，就先消除完那个字符串，由于考虑时间复杂度，可以使用栈来进行操作，方便回删
class Solution:
def maximumGain(self, s: str, x: int, y: int) -> int:
a, b = 'ab', 'ba'
if x < y:
a, b = b, a
x, y = y, x
res = 0
stack = []
for c in s:
if stack and stack[-1] == a[0] and c == a[1]:
stack.pop()
res += x
else:
stack.append(c)
stack_2 = []
for c in stack:
if stack_2 and stack_2[-1] == b[0] and c == b[1]:
stack_2.pop()
res += y
else:
stack_2.append(c)
return res
给你一个整数 n ，请你找到满足下面条件的一个序列：
整数 1 在序列中只出现一次。
2 到 n 之间每个整数都恰好出现两次。
对于每个 2 到 n 之间的整数 i ，两个 i 之间出现的距离恰好为 i 。
序列里面两个数 a[i] 和 a[j] 之间的 距离 ，我们定义为它们下标绝对值之差 |j - i| 。
请你返回满足上述条件中 字典序最大 的序列。题目保证在给定限制条件下，一定存在解。
一个序列 a 被认为比序列 b （两者长度相同）字典序更大的条件是： a 和 b 中第一个不一样的数字处，a 序列的数字比 b 序列的数字大。比方说，[0,1,9,0] 比 [0,1,5,6] 字典序更大，因为第一个不同的位置是第三个数字，且 9 比 5 大。
示例 1：
输入：n = 3
输出：[3,1,2,3,2]
解释：[2,3,2,1,3] 也是一个可行的序列，但是 [3,1,2,3,2] 是字典序最大的序列。
示例 2：
输入：n = 5
输出：[5,3,1,4,3,5,2,4,2]
提示：
1 <= n <= 20
题解：深度优先搜索+贪心
对于前面的数字，肯定是越大越好，所以我们先把大的数字塞在前面，只要找到一个符合条件且尽量大的数都在前面的序列，就是最大的解。
这里使用深度优先搜索去放每一个位置，每一次尽量放当前能放的数字中的最大的数，通过回溯和剪枝来找到第一个符合要求的答案，找到就直接返回。
class Solution:
def constructDistancedSequence(self, n: int) -> List[int]:
res = [0] * (2*n-1) # 返回的数组
index = 0 # 指针
st = [False] * (n+1) # 访问状态
def dfs(index, cnt, n):
if cnt == n: return True # 如果所有数都用过了，说明答案找到
if index >= 2 * n - 1: return False # 如果指针超过数组长度，未找到答案
flag = False # 判断是否找到答案
for i in range(n, 0, -1):
if st[i]: continue # 访问过则跳到下一个数
# 找到右边最近没有使用过的地址
while index < (2 * n - 1) and res[index] != 0: index += 1
# 如果不是1并且第二个i超出范围或者已经被只能用，则不成立，跳到下一个数字
if i != 1 and (index + i >= (2 * n - 1) or res[index + i] != 0): continue
res[index] = i # 加入到数组
if i != 1: res[index+i] = i # 如果不是1则加第二个
st[i] = True
flag = dfs(index+1, cnt+1, n)
if not flag:
st[i] = False # 恢复
res[index] = 0
if i != 1: res[index+i] = 0
else: return flag
return flag
dfs(0, 0, n)
return res
给你一个数组 pairs ，其中 pairs[i] = [xi, yi] ，并且满足：
pairs 中没有重复元素
xi < yi
令 ways 为满足下面条件的有根树的方案数：
树所包含的所有节点值都在 pairs 中。
一个数对 [xi, yi] 出现在 pairs 中 当且仅当 xi 是 yi 的祖先或者 yi 是 xi 的祖先。
注意：构造出来的树不一定是二叉树。
两棵树被视为不同的方案当存在至少一个节点在两棵树中有不同的父节点。
请你返回：
如果 ways == 0 ，返回 0 。
如果 ways == 1 ，返回 1 。
如果 ways > 1 ，返回 2 。
一棵 有根树 指的是只有一个根节点的树，所有边都是从根往外的方向。
我们称从根到一个节点路径上的任意一个节点（除去节点本身）都是该节点的 祖先 。根节点没有祖先。
示例 1：
输入：pairs = [[1,2],[2,3]]
输出：1
解释：如上图所示，有且只有一个符合规定的有根树。
示例 2：
输入：pairs = [[1,2],[2,3],[1,3]]
输出：2
解释：有多个符合规定的有根树，其中三个如上图所示。
示例 3：
输入：pairs = [[1,2],[2,3],[2,4],[1,5]]
输出：0
解释：没有符合规定的有根树。
提示：
1 <= pairs.length <= 105
1 <= xi < yi <= 500
pairs 中的元素互不相同。
题解：类拓扑排序+模拟
这题非常难，竞赛中只有不到10个人在规定时间内完成了，考察的知识点非常不明显，很难直接想到一个确切的做法，这里博主总结了一个比较好理解的解法。
首先我们需要理解题意，可以找到以下规律：
- 如果树存在，那么根节点和其他所有节点必有一个pair，所以根节点的出度为n-1，（由于这里很难判断是入度还是出度，我们直接用关系数（relate）来表示）。
- 如果两个节点有关系，同时他们的关系数一样，说明这两个点可以互换位置，属于等价关系，这时候如果树存在，则至少有两种方案。
- 如果x是y的祖先，那么relate[x] >= relate[y]， 如果x有分支，y与分支下的节点无法有关系。
找到以上几种规律后，我们可以通过一种关系数大小的方法从上到下构建一棵树，这样的方法有点像拓扑排序。
解法如下：
- 首先使用邻接表的方式读入边，同时记录每一个点的关系数relate。
- 按照rerate降序排序，获取排序后的节点顺序->sorted_idx。
- 判断是否存在一个节点x，relate[x] == n-1，如果不存在说明没有根节点，则没有方案树，返回0。
- 判断是否有等价关系的两个点，如果有，同时存在方案，则代表返回值2，将res设为2。
- 开始将判断是否存在至少一种树：
- 用pre代表当前点的父节点，我们通过不断加入到父节点底下来构建一棵树。
- 首先将所有的点都加入到根节点下。
- 遍历sorted_idx中的节点x，遍历节点x的所有关系点y，如果y之前没有访问过，则说明relate[y] <= relate[x]，那它应该属于x底下，这时候判断它的父节点和x的父节点是否一样，如果不一样说明存在冲突，则无解，返回0，如果一样，则将它纳入x节点麾下。
- 最后如果还没返回，说明有解，返回res。
class Solution:
def checkWays(self, pairs: List[List[int]]) -> int:
from collections import defaultdict
adj = defaultdict(list) # 邻接表
relate = defaultdict(int) # 记录关系数
for x, y in pairs:
adj[x].append(y); adj[y].append(x)
relate[x] += 1; relate[y] += 1
res = 1
n = len(adj) # 代表节点个数
sorted_idx = sorted(relate.keys(), key = lambda x: -relate[x]) # 按照关系数进行排序
if relate[sorted_idx[0]] != n - 1: return 0 # 如果最大关系数不为n-1，说明无法组成树
for x, y in pairs:
if relate[x] == relate[y]: # 如果存在关系数相同，说明他们可以调换位置
res = 2
break
pre = {}
visit = set([sorted_idx[0]])
for x in sorted_idx:
pre[x] = sorted_idx[0] # 先将所有的点挂在根节点下
for i in range(1, n):
cur = sorted_idx[i] # 当前节点idx
visit.add(cur)
for v in adj[cur]:
if v not in visit:
if pre[v] != pre[cur]: # 不在同一根下，说明有问题
return 0
pre[v] = cur # 将该节点纳入自己的麾下
return res
