type
status
date
slug
summary
tags
category
icon
password
1004.Max Consecutive Ones III
Sliding window
对比(自己):
241. Different Ways to Add Parentheses **
非常重要的做题方式和思路 很长时间没有做类似的题了
2232. Minimize Result by Adding Parentheses to Expression
2257. Count Unguarded Cells in the Grid
binary search in
2290. Minimum Obstacle Removal to Reach Corner
同样也是很久没做这个类型的 其实很常见 用greedy永远找目前最小obs路径
如果到了顶点直接就是结果
如果dfs遍历 更新所有 会很慢 没有很好的exit condition
Recursive dp → TLE
Dijkstra’s
Dijkstra’s -→ 0-1 BFS(当edge为0或1时)
ensure to always process path with fewer obs first
prioritize 0 weight edge
为什么只有0-1可以用 → 0, 1时1加到后面可以自动排序 不需要heappush 调顺序
如果不规定edge weight 加到后面顺序会乱 破坏搜索顺序
BFS 0-1 还有的优点是不需要在queue里记录 obs 因为都是自动排序 记录在dp中
要是讲的不清楚可以看这个 —>
‣
- Author:ran2323
- URL:https://www.blueif.me//article/12771a79-6e22-80df-981f-cb73b912d765
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
