算法

一、链表

• 链接：点此跳转
• 总结：
  • 1.善用遍历

二、深度优先搜索

• 链接：点此跳转
• 经典例子：从前序与中序遍历序列构造二叉树
• 步骤：
  • 1.定义一个深度优先搜索的函数dfs()
  • 2.判断结束条件：边界和逻辑中止(如遇到当前值为1中止)
  • 3.执行搜索逻辑：如更新当前值等
  • 4.蔓延：前后左右执行dfs()
• 总结：
  • 1.看到题干有蔓延等同义词优先考虑深度优先搜索
  • 2.注意边界处理

三、移动窗口

• 链接：点此跳转
• 总结：
  • 1.该类型做得少，需要重做/多做
  • 2.注意边界处理

四、双指针

• 链接：点此跳转
• 思路：一个指针遍历，一个指针指向某个值(比如需要交换的值)
• 总结：
  • 1.该类型做得少，需要重做/多做

五、二分查找

• 链接：点此跳转
• 思路：
  • 1.定义头尾指针left和right
  • 2.while循环每次取中间值middle=left+(right-left)/2
  • 3.直到middle等于结果值则结束
• 总结：
  • 1.定义好二分查找的left、right、middle变量即可

六、回溯算法

• 链接：点此跳转
• 经典例子：全排列
• 思路：
  • 1.定义path记录路径，result记录结果，selected记录选择列表
  • 2.结束条件：到达决策数底层，无法再做选择
  • 3.通过做选择和撤销选择实现决策树的回溯
• 总结：
  • 1.题干有结束条件的一般要想到回溯
  • 2.该类型做得少，需要重做/多做

七、前缀和

• 链接：点此跳转
• 经典例子：和为K的子数组
• 总结：
  • 1.用来解决双重遍历时间复杂度很高的问题，引入前缀和，可以避免多次不必要的计算

八、排序

• 链接：点此跳转

九、动态规划

• 链接：点此跳转
• 思路：todo

十、单调栈

• 链接：点此跳转

十一、分治算法

• 链接：点此跳转
• 思路：todo
• 经典例子：从前序与中序遍历序列构造二叉树

十二、广度优先搜索

• 链接：点此跳转