九月刷题给米接龙活动（小伙伴们冲冲冲）

lic10 发表于 2020-9-26 13:53
day 25打卡。

求加米，必回加。一起加油！

老铁来份米~我在1482楼

9/25 打卡第25天， 刷了2道题

179. Largest Number
sort(key=functions.cmp_to_key(mycmp))
def mycmp(s1, s2):
   return 1 if s2+s1>s1+s2 else -1

174. Dungeon Game
dynamic programming
need = min(dp[i+1][j], dp[i][j+1])-dungeon[i][j]
dp[i][j] = 1 if need<=0 else need

9/25 今天出门给侄女过生日，只刷了两题

九月Day19 几道topology的题

Sep 25 打卡
一些反转字符串相关的问题，锻炼字符串基本操作，不用库函数
344. Reverse String
541. Reverse String II
151. Reverse Words in a String
186. Reverse Words in a String II

9月打卡第25天，5道题，把之前attempted的都解决了，终于刷了一半了。。

String Compression II： dfs + memo，dfs的时候需要记录上一个字符和上一个字符出现了多少次，然后dfs的时候考虑当前字符和上一个字符一样或不一样的情况
Minimum Possible Integer After at Most K Adjacent Swaps On Digits： 记录所有数字出现的index，然后从小到大循环向前move index，要注意index shift的情况
Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree： 对于每个edge 可以block或者直接加入，然后判断weight是大于min weight还是等于。用Union find找MST
Maximum Sum of Two Non-Overlapping Subarrays： dp扫一遍，记录左边L，M长度的presum max，然后再在后面append 长度为M，L array的sum，更新全局最大就行
The Maze II：dijstra，注意这里用了dijstra也不能保证每个visit的点就是最小值，因为每个点每次走的步数不一样，所以提前到达的点不一定是step最小的，提前到达的点只能保证上一次开始走的时候step是最小的。所以visit不能用set，需要用dict来比较step来更新。

925打卡，一道题：743，没什么说的，经典dijkstra。不过面试要是真考手写dijkstra还真没什么意思，不如two sum

Sep 25th

随便复习了几题
另外看了下kmp，没完全看懂。。

9.25 今天做的都是这几天或者之前做过的题，所以做起来蛮快的，同时也复习了思路，接下来几天把oracle tag刷完！