1376. Time Needed to Inform All Employees
Analysis
题目真长,不过意思还算简单,实质上就是在求树的最长路径,而通知时间就是结点与结点之间的边权,这与图很类似。
Code
bfs
从 bfs 的角度来思考可能会容易一些。
1 | class Solution { |
可惜,这段代码提交上去超时了,原因是找子结点的时候是又重复遍历了一次数组。既然这样,那就按照根结点来统计一下子结点的下标:
1 | class Solution { |
这种思路虽然可以通过,但是时间、空间消耗都比较大。
仔细一看,这种思路实际上是利用邻接表遍历图,并求出最长路径,那干脆直接按照图的方式来写:
1 | class Solution { |
把 unordered_map 换成 vector 时间、空间消耗都减少很多😂。另外,因为不存在环(题目给的都是树),所以 visit 数组就可以省去了。
dfs
再回头想想 dfs 怎么写,按照前面的思路,当作图来写 dfs:
1 | class Solution { |
同样,因为没有环,所以也不需要 visit 数组。
49. Group Anagrams
Analysis
这个题第一眼看过去,没读懂,仔细又读了一下,原来是个分类的题目,只需要将字母异位词组合在一起就可以了。
话说,求字母异位词好像就是求字母的全排列,不得不又联想到昨天做的那个题😂。
不过这个题,感觉用 hash 会好一点。
Code
一开始总数想让 hash 直接映射成不同类型字母异位词的下标,倒腾半天 map<vector<int>, int>
,没倒腾出来,只能用暴力一点的解法了。
1 | class Solution { |
这段代码姑且算是能出结果了,可惜提交上去超时了。突然发现,自己有点被题目绕晕了。而且,这个题的难点好像是在如何合理使用 STL 来表示 hash 上。
省去了一些重复的判断:
1 | class Solution { |
还是超时的,是我把这个问题想的太复杂了吗?
分析一下上面的代码,判断两个词是字母异位词是基于两个词的字符个数相同,这就需要分别对两个词中的字符进行统计并判断是否相同。同时,设置了一个 hash 表来标记这个词是否被统计过,统计过了就说明是其他词的字母异位词,就不再统计了。strs 的长度范围是 ,词的长度范围是 ,极端情况下,就是 ,按理说这种思路,虽然很慢,应该是可以过的。不过,这种思路下,可能会产生很多无效统计。
既然事实已经证明,这种方法不行了,就得换个思路了。
瞅了两眼官方题解,突然发现官方题解不是用字符串的字母统计结果当作 map 的映射,而是将字符串先排序,如果字符串的排序结果一致就说明是字母异位词,真鸡贼啊😂~
等等,好像发现了什么东西,回到一开始的思路,重新写了一下:
1 | class Solution { |
干,一开始的思路是可以通过的,尽管时间和空间消耗不忍直视。突然发现好像一开始倒腾半天没出来的原因是语法写错了,感觉今天不在状态(我还傻傻的一个一个去判断🙃)。既然明确了这个思路,那不妨写的更简单一点:
1 | class Solution { |
...还真能这样写啊(C++ 的语法跟 STL 的知识还得补🙃)。另外,unordered_map 好像不能把 vector 当作 key。
现在回到官方题解的思路上来:
1 | class Solution { |
相比自己的思路,时间、空间消耗都少了一半。
官方题解的第二种思路与自己的思路是一样的,只是用了稍微复杂一点的语法:
1 | class Solution { |
有好多看不懂的语法...暂时放着吧。
Summary
感觉今天脑子有点迷迷糊糊的,不太清醒。
话说,老是做题,都没有具体的看看书,也没有好好的总结一下