数据结构与算法思路

16 Mar 2022   |   Algorithm  |  

程序

深刻认识到程序=数据结构+算法，使用程序解决特定的问题，特定的问题使用何种数据结构，为了高效的得到结果，使用什么算法。

数据结构

最基础的数据结构是数组和链表，数组占用连续空间，通过下标实现O(1)时间复杂度访问；链表使用额外的指针连接数据节点，需要O(N)时间复杂度访问目标数据。

基于数组和链表组成多种高级数据结构：

• 哈希表：数组+链表；
• 二叉树：链表；
• 栈 / 队列：数组或者链表；
• 图：数组+链表。

算法

算法的本质是在特定的数据结构上更高效的穷举所有结果。

• 回溯算法；
• 贪心算法；
• 分治算法；
• 动态规划。

常用技巧

• 双指针

在单链表中使用快慢指针寻找中间节点；在有序数组中高效的寻找目标数据；在滑动窗口中，右指针不断向前，满足条件后，左指针开始不断收缩。在回文字符串中，从中心不断向左右扩散，直到不满足条件；在盛水容器中，左右指针从两边开始移动，值小的不断移动。在nSum问题中，不断寻找目标值。

• 二分搜索

在有序序列中查找数据，分析清楚左边界和右边界，循环结束条件。可以泛化到一般单调性函数上使用。

• 单调栈/队列

遇到下个更大元素的问题，就直接使用单调栈吧。单调队列用在滑动窗口中求最大值。

• 递归

想清楚递归函数的定义，假设已经知道了f(n-1)的结果，结合nums(i)如何计算f(n)。千万不要不断递归下去，这样会把自己陷进去。

递归在二叉树中应用很广。二叉树的遍历有前序，中序，后序三种方式。解决二叉树的各种问题，要考虑清楚使用哪种遍历方式，然后重点考虑当前节点需要作什么操作才能满足递归函数的定义。

• 动态规划

动态规划常用于最值问题，它的数学证明很难，我们也不需要去做。想清楚dp()的定义，如果知道了dp(i-1)，dp(i)怎么利用dp(i-1)计算出结果。中间过程有哪些参数会影响到结果？这些参数很有可能就是状态变量。在考虑用动态规划之前，不妨试试递归+备忘录的方式能否解决呢，他们俩的效率是一样的。

• 回溯

如果要得到所有可能性的结果集，一般就可以考虑使用回溯。回溯就是穷举所有可能的结果，在循环中调用递归。在递归之前做出选择，在递归之后撤销选择。为了提高效率，考虑在每次递归前进行剪枝。

刷题

• 从二叉树开始
• 没有思路，直接看题解
• 一道题目至少刷五遍