Open
Description
04.19
基础
数组
- 内存中连续的存储空间
- 适合指定下标获取元素
- 中间插入、删除后，移动后续的元素，都需要较高的时间成本
- 固定大小，需要扩容时，需要一块新的内存空间，而且需要复制元素的时间成本
- 无序数组，
- 有序数组，要使用二分查找，都必须是有序的数组，如果是不变化的数组，要多次查找，一般采用1次排序，多次查询
- 典型场景
固定范围(可以通过O(1)映射到具体的数组下标)，比如只有小写字母的一个字符串，每个a-z的字符k，可以通过k-a直接映射到数组下标，再通过下标直接获取元素
链表
- 每个节点，独立存在内存中(可以不连续)，通过指针/引用建立节点之间的关系
- 插入、删除节点容易
- 如果指定一个节点value去删除一个元素，首先得通过遍历，查找到这个节点
- 如果指定一个节点的前序指针/应用，那么删除就不需要遍历查找(单链表，双链表都可以)，
- 如果指定一个节点的指针/引用 ，单链表还是需要遍历找到该节点的前序节点，才能删除；这种情况双向链表就不再需要遍历查询的步骤
栈
特殊的后进先出，常用的场景对栈的操作也比较简单，入栈push，出栈pop，查看栈顶元素peek，使用场景也比较特殊，比如常见的：表达式的合法性检查、浏览器的前进后退；基本也不会对栈进行排序、查找等操作。可以进一步自己使用数组、链表自己实现一个栈。(后面根据Leetcode的题练习一下其他的使用场景)
递归
有2点真的很重要
- 终止条件
- 思维上一定要"信任"下一层的递归结果，不用把自己带入下一层的逻辑中
排序
以前学习排序，老是去记各种排序算法的具体实现，没有总结特殊、使用背景，一段时间就忘记。这次根据老师分析的时间复杂度、是否是稳定性排序、是否是原地排序；为什么要用稳定排序，像订单排序中，先用订单号(不重复)排序，再用金额(重复)排序，后面的用金额排序就需要用稳定排序。归并、快排都是利用分治思想，快排不稳定，归并不是原地排序，都需要根据场景来决定排序，不死记硬背。
二分查找
基本都是使用在排序好的数组上？
- 有序的才有意义，否则不好比较
- 数组能快速容易的用下标折半定位
进阶
- 更多的场景是有相同的元素，注意边界条件
- 大于某个数的第一个元素的查找等
学习态度
追求掌握，训练思维，有没学会自己最清楚;一定要动手实现
Metadata
Metadata
Assignees
Labels
No labels