LC吐血整理之weekly_contest篇

Posted on | In
12.29开始做周赛！

169场周赛

5296.两棵二叉搜索树中的所有元素

我的做法：遍历两棵二叉搜索树得到两个数组，然后合并数组并排序（走了一下捷径，排序直接使用sort()，时间有限，就在直接用了..我有罪 ==
Tips-1: 二叉搜索树
我是用前序遍历得到两个list，经同学指点后，发现题目有指出二叉树为二叉搜索树，原谅我还没弄清楚二叉搜索树的概念…

二叉查找树（Binary Search Tree）：
又称二叉搜索树、二叉排序树，是指一棵空树或者具有下列性质的二叉树：
① 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
② 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
③ 没有键值相等的节点。

关于二叉搜索树的查找、插入、遍历可以去了解一下

5297.跳跃游戏III

简单的DFS，有条件查找
如果思路清晰的话，可以不构建图，我是构建了一下下标跳跃的图，方便DFS~

170场周赛

5303.解码字母到整数映射

既然题目不难做，就一定要快准狠！这个考的主要是字符串的分割和字符ASCII码的转换 chr() ord()

5304.子数组异或查询

重点：异或归零律：x⊕x=0 异或恒等律：x⊕0=x

5305. 获取你好友已观看的视频

今日份Tips： sorted(iterable,key,reverse)
iterable: 表示可迭代的对象，例如dict.keys(), dict.items()
key: 是一个函数，用来选择参与排序的元素
reverse: 默认为False(升序)，reverse=True(表示降序) 

1
2
3
4
5
6
7
# 善用sorted中的key完成多条件排序
# 举个栗子 对dicta先按value进行升序排序 如果value相同则按key升序排序(字典序)
>>> a = {'amilyxy': 4, 'guying': 2, 'love': 1, 'loveme': 1, 'loi': 1, 'grace':2, 'not':6}
>>> sorted(a.items(), key = lambda x:(x[1], x[0]))
[('loi', 1), ('love', 1), ('loveme', 1), ('grace', 2), ('guying', 2), ('amilyxy', 4), ('not', 6)]
>>> sorted(a.items(), key = lambda x:(-x[1], x[0]))   # value 降序
[('not', 6), ('amilyxy', 4), ('grace', 2), ('guying', 2), ('l', 1), ('loi', 1), ('love', 1), ('loveme', 1)]

2020.2.22后续补充： 今日份Tips： sorted()自定义排序函数
题目：剑指offer-把数组排成最小的数
sorted()是一个高阶函数，可接受一个比较函数来实现自定义排序，python3中sort()和sorted()中取消了cmp参数, 但可以使用functools中的cmp_to_key函数。 

1
2
3
4
5
6
7
8
9
10
# 比如需要实现逆序
>>> def compare(a, b):
...    if a>b:
...        return -1
...    else:
...        return 1
>>> nums  = [-1, 2, 1, -3, 7, 0]
>>> import functools
>>> sorted(nums, key = functools.cmp_to_key(compare))
[7, 2, 1, 0, -1, -3]

　　python3将python2中的比较函数转化为关键字函数，与接收key function的工具一同使用（如sorted()、min()、heapq.nlargest()等）, key主要作用是将程序转成python3格式。

171场周赛

5307. 将整数转换为两个无零整数的和

　　感觉我做的有点投机取巧了，直接str去判断0是否存在，看了一下两个题解（区别就是如何判断0的存在）：
① 有一个跟我差不多，也是转成string类型，然后判断是否含‘0’；
② 通过x%10?=0来筛选。

5308. 或运算的最小翻转次数

　　昨天做201和89题都用到了位运算，可惜我这个题根本就没有用位运算做…哎，再一次投机取巧，太难了…

5309. 连通网络的操作次数

　　刚开始没想那么多，按照单连通域去做的，跑到第25个测试用例的时候报错才发现问题，幸好发现问题了哈哈哈，还没写过求连通块的题。
看题解提到了图的连通度这个概念，查了一下，好像跟这个没啥关系，连通度有点复杂，有机会再看吧…
求解思路：
Ⅰ 构建Graph，DFS/BFS遍历求子图数
具体方法：
　　对图中每一个顶点进行DFS，DFS的条件是该顶点没有被遍历过，如果子图具有连通性，那么从子图中某个顶点出发，一次DFS就遍历所有子图中的顶点。
　　这个方法缺点就是，面对大型图，效率偏低，实践了一下，如果按照常规不做任何处理的DFS方式求解该题，在第34个测试用例处报超出时间限制错误。
Ⅱ 并查集Union-Find
并查集是解决动态连通性问题的一类非常高效的数据结构，也可以说是一种算法（暂不考虑连通路径。
⑴ Quick-Find算法
Quick-Find包括三个步骤：

① 初始化n个组分别代表N中的n个节点（N为描述图的若干连接对，形似[[0,1],[0,2],[0,3],[1,2],[1,3]]）；
② 对于N中的每一对连接i，判断节点i[0]和节点i[1]是否属于同一组，如果属于同一组则不需要任何处理，如果不属于同一组则将i[0]和i[1]组中所有节点归为一组（其实，重点就在于如果合并两个组）；
③ 遍历N之后，计算互不相交的组数。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 伪代码 其中n为N中涉及的所有节点，N为连接对
def union_find(n, N):
    # 构建一个dict初始化设置查集
    dic = {}
    for i in range(n):  
        dic[i] = i
    # 遍历所有连接对
    for i in N:
        if dic[i[0]]!=dic[i[1]]:
            temp = dic[i[0]]
            for j in range(n):
                if dic[j] == temp:
                    dic[j] = dic[i[1]]
    # 计算dic中组数
    return len(set(dic.values()))

　　可以看到，使用dict查找非常快，但合并组时需要遍历dic，时间复杂度非常高，在这个题中在第32个测试用例，当n=1000时超时。
⑵ Quick-Union算法
怎么快速合并呢？？（大佬们）提供了一种树结构解决方案。
Quick-Union包括个步骤：
① 初始化n个根节点的树代表N中的n个节点；
② 对于N中每一组连接i，findroot()查找节点i[0]和节点i[1]的父节点，通过相同则属于同一棵树不做处理，如果不是同一个父节点，将i[0]的父节点设置为i[1]的父节点，并将根节点数减一；
③ 计算根节点数目作为连通块数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def union_find(n, N):
    # 初始化n个根节点的树（这里可能用dict会好点？？？）
    tree = [i for i in range(n)]
    count = n 
    # 查询父节点
    def findroot(node):
        while node != tree[node]:
            node = tree[node]
        return node
    # 遍历N中的连接对
    for i in connections:
        rootl,  rootr = findroot(i[0]), findroot(i[1])
        if rootl != rootr:
            tree[rootl] = rootr
            count -= 1
    return count
```   
**⑶ Weighted Quick Union算法**       
⑵中快速合并算法只是简单的将两棵树合并，但没有考虑树的大小，改进方法可以是，在union之前，先判断两个树的大小（节点数量），将小点的树附加到大点的树上，称为加权快速合并算法。  
**代码模板：**    
```python
def union_find(n, N):
    # 初始化n个根节点的树（这里可能用dict会好点？？？）
    tree = [i for i in range(n)]
    size = [1 for _ in range(n)]
    count = n 
    # 查询父节点
    def findroot(node):
        while node != tree[node]:
            node = tree[node]
        return node
    # 遍历N中的连接对
    for i in connections:
        rootl,  rootr = findroot(i[0]), findroot(i[1])
        if rootl != rootr:
            if size[rootl]<size[rootr]:
                tree[rootl] = rootr
                size[rootl]+=size[rootr]
            else:
                tree[rootr] = rootl
                size[rootr] += size[rootl]          
            count -= 1
    return count

测试了一下，Quick-Union方法耗时1252ms，加权后耗时980ms，好像差别不是很大，可能在大型图下会体现出来吧…
⑷ 后续还有压缩路径方法，可进一步减小时间复杂度，有兴趣在进一步了解哈…

172场周赛

5315. 6 和 9 组成的最大数字

这个题很简单，从左至右找到第一个出现的6就可以，实现可以直接出发除法取余、int转str、内置函数replace等等，具体可以看github。

5316.竖直打印单词

解决方式：
① 暴力补空格：max(map(len()))找到最大长度，暴力取值。
② zip_longest()

5317.删除给定值的叶子节点

　　不得不说，我写的答案时间复杂度真的好大，我是遍历一遍树剔除满足条件的叶节点，然后再次遍历树…直到找不到满足条件的叶节点….
　　看了答案之后，我还是太年轻，明明一次遍历就能做的事….
　　有空多补一下DFS可行？？？

176场周赛

5340.统计有序矩阵中的负数

这个跟剑指offer中二维数组的查找很类似，从右上角找，时间复杂度为O(m+n)，周赛数据比较水，试了一下暴力也可以通过，时间差不多。

5341.最后k个数的乘积

敲重点：①0的位置 ②前缀积
刚开始直接暴力相乘，结果超时了（就说不会这么容易

5342.最多可以参加的会议数目

方法一：
　　（又超时了，我可真难）但是我看评论有和我一样的思想，java和c++都过了呀…破案了，遍历方向不一样，佛了，一念之差，一眼万年….
　　具体：①数组升序排序events = sorted(events, key=lambda x: (x[1],x[0]))，②倒序遍历找到符合条件（不在set中）的时间点，添加到set中，break。 方法二：
　　优先队列的方法，heaq好像前几天刚接触但是没仔细看，这里又用到了。

5343.多次求和构造目标数组

　　看来真的需要系统的学一下heapq了，突然发现暴力也能过，果然评论说的数据水szd。
　　这个题的思路就是不断地用数组中最大值减去剩下所有数的和得到上一个数组，关键就在于怎么获取最大值 (熟悉优先队列的人肯定立马蹦出来)，还有一个需要注意的是评论说的[1000000, 1](这个看题解吧，不多说了）。 今日份Tips： heapq常用方法 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 创建堆的两种方式 1.heappush  2.heapify
>>> li = [9, 5, 3, 6, 7, 2]
>>> heap = []
>>> for i in li:
...   heapq.heappush(heap, i)
>>> heapq.heapify(li)
# 删除与替换值
>>> heapq.heappop(li)
>>> heapq.heapreplace(li, 8)
# 寻找极值
>>> heapq.nlargest(3, li)
[9,7,6]
>>> heapq.nsmallest(3, li)
[2,3,5]

注意: python的heapq不支持最大堆，在stackoverflow上看到了一个巧妙的实现：我们还是用小根堆来进行逻辑操作，在做push的时候，我们把最大数的相反数存进去，那么它的相反数就是最小数，仍然是堆顶元素。