训练营总结

训练营打卡结束了，梳理一下两个月以来学习的知识点。

数组

数组是存放在连续内存空间上的相同类型的集合

链表

• 链表的种类主要为：单链表，双链表，循环链表
• 链表的存储方式：链表的节点在内存中是分散存储的，通过指针连在一起。
• 链表是如何进行增删改查的。
• 数组和链表在不同场景下的性能分析。

哈希表

哈希表都是用来快速判断一个元素是否出现集合里。

字符串

字符串类类型的题目，往往想法比较简单，但是实现起来并不容易，复杂的字符串题目非常考验对代码的掌控能力。

栈与队列

• 队列是先进先出
• 栈是先进后出

二叉树

• 深度优先遍历
  • 前序遍历
  • 中序遍历
  • 后续遍历
• 广度优先遍历
  • 层序遍历

回溯算法

回溯是递归的副产品，只要有递归就会有回溯

贪心算法

贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

动态规划

动态规划五部曲

• 确定dp数组（dp table）以及下标的含义
• 确定递推公式
• dp数组如何初始化
• 确定遍历顺序
• 举例推导dp数组

单调栈

单调栈可以维护一个序列中某些元素的单调性。它是一个栈，支持弹出栈顶元素，并且支持查询当前栈中前驱或后继元素的操作。具体而言，一个单调栈可以是单调递增的或单调递减的，这取决于元素的比较顺序。

单调栈的实质是以空间换取时间，因为在遍历过程中，需要使用一个栈来记录右侧第一个高于当前元素的元素，其优点在于只需遍历一次。