枚举算法的优化套路
程序员文章站
2023-04-06 10:52:48
最近接触了一门《ACM算法入门基础》的课程，个人感觉挺不错的，和大家分享一下。 ......
枚举算法的优化套路
最近接触了一门《ACM算法入门基础》的课程，个人感觉挺不错的，所以特地整理了一下，和大家分享一下。
希望能够给算法入门的小伙伴带来一点点帮助，水平不高，如果有错误或不足的地方，望见谅！
持续学习更新中~
枚举的要点：
- 确定需要枚举的变量
- 确定枚举的范围
-
优化手段
- 改变/减少枚举变量
- 缩小枚举范围
- 二分 ：二分查找、二分搜索非常有效，一般是复杂度从O(N)降到O(logN)，使用范围也很广
- 哈希：Hash，空间换时间
- 双指针：Leetcode上对应的分类是two pointer，直译过来就是双指针，大概的思想就是滑动窗口
- 前缀、后缀和：空间换时间
相关例题的优化分析：
- 改变枚举的变量
- 哈希
- 双指针
- hihoCoder 1745题 “最大顺子”
- hihoCoder 1514题 “偶像的条件”
- hihoCoder 1607题 “H行人的社交网络”
- 前缀和
- 蓝桥杯 —— K倍区间
- 2017 美团校招笔试题 “K的倍数”
- 2017 微软笔试题 “数组拆分”