数据结构与算法

按照我自己学习时的理解难易，将算法分为初级、中级、高级这几个难度。

学习老师：左神。

初级（简单、低中等）： 稍微学习，比如听一遍就会了，最多学习不超过三遍；主要是那种需要巧妙的方法，不学习不会，一学醍醐灌顶
中级（高中等、低困难）： 需要多理解几遍，需要多花点时间理解，琢磨
高级（高困难）： 就是那种难的、复杂的算法

【例】代表的是练习的算法题，算法题描述写在java文件的注释里

初级算法

• 迭代和递归
• 异或
• 链表
  • 快慢指针
• 排序
  • 冒泡排序
  • 插入排序
• 二叉树
  • 先序、中序、后序遍历
  • 判断二叉树是否是***树
• 前缀树

中级算法

• 递归

  • 【例】汉诺塔
  • 【例】打印字符串的所有子字符串
  • 【例】打印字符串的排列组合
  • 【例】不使用额外空间，反转一个栈

• 排序

  • 基数排序
  • 堆排序
  • 快速排序
  • 合并排序

• 图

  • 最小生成树（无向图的最短路径算法）
    • Kruskal算法
    • Prim算法
  • 有向图的最短路径算法
    • Dijkstra算法（迪杰斯特拉）
    • floyd算法

• 并查集

• 从暴力递归到动态规划（递归 -> 记忆化搜索 -> 真正的动态规划）
  记忆化搜索 = 从顶向下的动态规划

  • 【例】机器人从原始位置到目标位置移动路径问题
  • 【例】甲、乙两个玩家拿数字博弈问题
  • 【例】经典的背包问题

• 滑动窗口

• 单调栈 (Monotonous Stack)

高级算法

• KMP（字符串匹配）
• manacher（查找最大回文字符串）
• bfprt（应用在TopK问题，在无序数组中，找出第k大的数，优点是时间复杂度低）
• morris（空间复杂度较低的二叉树遍历算法）
• 线段树 (Segment Tree) (生成前缀和之后，原数组L到R范围的修改后，依然能维护前缀和的使用)
• Index Tree（分段维护前缀和，修改x位置的值后，能够logN复杂度修改完前缀和）
• AC自动机 (AC Automation) (在大文章中搜索是否出现指定的某些关键词)

其他、冷门、技巧

• 置换环

收藏并推荐的算法题

强烈推荐的算法题，或者是具有启发性的算法题；从容易到难排序

No.	Problems	Solutions	Tag
32	Longest Valid Parentheses	Java	DP, Stack

leetcode

推荐

No.	Problems	Solutions	Tag
32	Longest Valid Parentheses	Java	DP, Stack

周赛 (weekly-content)

No.	Solutions	Completion Date
196	Java	2020.07.05

刷题记录

No.	Problems	Solutions	Completion Date
329	Longest Increasing Path in a Matrix	Java	2020.07.26
16	最接近的三数之和	Java	2020.07.22
856	Score of Parentheses	Java	2020.07.21
95	Unique Binary Search Trees II	Java	2020.07.21
785	Is Graph Bipartite?	Java	2020.07.16
96	Unique Binary Search Trees	Java	2020.07.15
174	Dungeon Game	Java	2020.07.12
309	Best Time to Buy and Sell Stock with Cooldown	Java	2020.07.10
120	Triangle	Java	2020.07.06
142	Linked List Cycle II	Java	2020.07.06
63	Unique Paths II	Java	2020.07.06
32	Longest Valid Parentheses	Java	2020.07.04
108	Convert Sorted Array to Binary Search Tree	Java	2020.07.03
378	Kth Smallest Element in a Sorted Matrix	Java	2020.07.02
718	Maximum Length of Repeated Subarray	Java	2020.07.01
168	Excel Sheet Column Title	Java	2020.06.30
1139	Largest 1-Bordered Square	Java	2020.06.29
215	Kth Largest Element in an Array	Java	2020.06.29
209	Minimum Size Subarray Sum	Java	2020.06.28
41	First Missing Positive	Java	2020.06.27
139	Word Break	Java	2020.06.25
67	Add Binary	Java	2020.06.23
889	根据前序和后序遍历构造二叉树	Java	2020.06.22
289	Game of Life	Java	2020.05.20
125	Valid Palindrome	Java	2020.06.19
1190	Reverse Substrings Between Each Pair of Parentheses	Java	2021.05.27

面试题部分

No.	Problems	Solutions	Completion Date
17.13	Re-Space LCCI	Java	2020.07.09
16.11	Diving Board LCCI	Java	2020.07.08
02.01	Remove Duplicate Node	Java	2020.06.26

剑指Offer

No.	Problems	Solutions	Completion Date
09	用两个栈实现队列	Java	2020.06.30

常用算法练习

quick sort Recursion && Iteration

字节跳动

数组与排序

Problems	Solutions	Completion Date
岛屿的最大面积	Java	2020.06.30

牛客网