欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

枚举算法的优化套路

程序员文章站 2022-05-29 12:42:28
最近接触了一门《ACM算法入门基础》的课程,个人感觉挺不错的,和大家分享一下。 ......

  

枚举算法的优化套路

 

  最近接触了一门《ACM算法入门基础》的课程,个人感觉挺不错的,所以特地整理了一下,和大家分享一下。

  希望能够给算法入门的小伙伴带来一点点帮助,水平不高,如果有错误或不足的地方,望见谅!

 

  持续学习更新中~

  


   

枚举的要点:

  • 确定需要枚举的变量
  • 确定枚举的范围
  • 优化手段
    • 改变/减少枚举变量
    • 缩小枚举范围
      • 二分 :二分查找、二分搜索非常有效,一般是复杂度从O(N)降到O(logN),使用范围也很广
      • 哈希:Hash,空间换时间
      • 双指针:Leetcode上对应的分类是two pointer,直译过来就是双指针,大概的思想就是滑动窗口
      • 前缀、后缀和:空间换时间

 


 

相关例题的优化分析:

  • 改变枚举的变量
  • 哈希
  •  双指针
    • hihoCoder 1745题 “最大顺子”
    • hihoCoder 1514题 “偶像的条件”
    • hihoCoder 1607题 “H行人的社交网络”
  • 前缀和
    • 蓝桥杯 —— K倍区间
    • 2017 美团校招笔试题 “K的倍数”
    • 2017 微软笔试题 “数组拆分”