算法一千零一夜

算法基础: 数组

常见基本思路:

• 搜索有序数组: 二分法
• 以O(n)的空间复杂度修改有序数组: 快慢指针
• 不一样的有序数组: 前后快慢指针
• 需要范围的快慢指针:滑动窗口
• 螺旋矩阵: 螺旋矩阵

Data Structure: LinkedList

• create sentinel node
• use two pointers to traverse the linked list
• check if there's loop: two pointer with different speed
• adding or removing nodes: change the prev/next pointer of the node, instead of changing the node itself

算法基础: 哈希表

哈希表基础

• 字母异位词
  • 有效的字母异位词
  • 字母异位词分组
  • 找到字符串中的所有字母异位词
  • 哈希表统计出现次数
• Set作为哈希表(常见于没有限制数值大小的情况)
  • 两个数组的交集
  • 快乐数
• Map哈希处理需要多维数据且数量不限制
  • 两数之和
  • 四数相加II
• 哈希表不擅长处理需要去重的情况(用双指针更好)
  • 三数相加
  • 四数相加I

算法基础: 字符串

• 双指针法
  • 替换空格
• 常见思路: 反转
  • 反转字符串
• 常见思路: 局部反转 + 整体反转
  • 反转字符串中的单词
  • 左旋转字符串
• 常见思路: KMP
  • 实现strStr
  • 重复的子字符串

算法基础: 双指针

双指针法并不隶属于某一种数据结构，在数组，链表，字符串都用到了双指针法.

• 数组
  • 移除元素
• 字符串
  • 反转字符串
  • 替换空格
  • 反转字符串中的单词
• 链表
  • 反转链表
  • 删除链表的倒数第N个节点
  • 链表相交
  • 环形链表
• 哈希
  • 三数之和
  • 四数之和

算法基础: 栈和队列

栈

先进后出, 后进先出 FILO

• 用队列实现栈
• 判断有效的括号
• 删除字符串中相邻的重复项
• 逆波兰表达式

队列

先进先出, 后进后出 FIFO

• 用栈(数组)实现队列
• 滑动窗口最大值
• 前K个高频元素

算法基础: 二叉树

概念和常见题型