前言
算法与数据结构从现在开始重视还来得及!
为何要重视算法与数据结构?
- 算法能力代表了基本功水平,能代表一个程序员功底是否扎实。
- 算法和数据结构的思想以及时间复杂度空间复杂度的概念是提高工作效率,学习能力和成长潜力的重要途径。
- 算法能力是设计一个系统(造轮子)的重要基础。
- 下层基础决定上层建筑!
算法与数据结构是我的薄弱项,需要多做总结!
尽量对每个数据结构的经典题目做总结,尽量使用LeetCode原题来帮助理解。
LeetCode主页先贴这里:**Shmilyqjj的力扣主页**,大家互相监督学习呦!
基本概念
学习算法有帮助的一些基本概念。
顺序存储与链式存储
物理结构:是指数据的逻辑结构在计算机中的存储形式。
逻辑结构:是指数据对象中数据元素之间的互相关系。
基础数据结构
数据结构是算法的基石。要做到对算法的融会贯通和举一反三,熟悉各种数据结构是必备的。优秀的算法取决于采用哪种数据结构。
重点:熟悉每种数据结构优缺点,应用场景,熟练掌握其思想并灵活运用。
数组和字符串
特点:逻辑结构与物理结构一致
优点:构建简单,索引某个元素的复杂度O(1)
缺点:必须连续分配一段内存,查询过程遍历时间复杂度O(n),删除过程时间复杂度O(n)
场景:元素个数确定,经常按索引查询,不经常插入和删除
链表
分为单向链表和双向链表
优点:能灵活分配内存空间,插入和删除元素效率高O(1)
缺点:不能通过下标读取,读取第n个位置元素复杂度O(n)
场景:元素个数不确定,经常插入和删除,不经常查询
经典题目:
快慢指针->判断是否有环
快慢指针->翻转链表
快慢指针->寻找倒数第K元素
快慢指针->找链表中间位置
构建虚假链表头
栈
后进先出(LIFO),可以采用单链表实现复杂度O(1),虽然也可以用数组实现但时间复杂度可能较大
场景:解决问题时只关心最近一次操作,解决完后要找之前的操作。
经典题目:
匹配括号,判断是否有效
队列
先进先出(FIFO),可以采用双链表实现。
场景:按一定顺序处理过来的数据。
经典题目:
广度优先搜索
双端队列
和普通队列的区别是:可以在队头队尾都可以查看,添加和删除数据,复杂度都为O(1),可以采用双链表实现。
场景:实现长度动态变化的窗口或连续区间,动态窗口。
经典题目:
返回滑动窗口最大值
树
充分应用递归,树的问题基本都与递归有关
面试常考:普通二叉树,平衡二叉树,完全二叉树,二叉搜索树,四叉树,多叉树
需要了解:红黑树 ,AVL自平衡二叉搜索树
遍历方法:
前序遍历:根->左子树->右子树
中序遍历:左子树->根->右子树
后序遍历:左子树->右子树->根
深度优先遍历DFS:包含以上三种
广度优先遍历BFS:即层次遍历,每一层从左向右输出
经典题目:
二叉搜索树的第K个最小元素
如何学习数据结构与算法
好的学习方法往往能起到事半功倍的效果,这里根据算法大佬们的学习经历总结一下算法学习方法,警示自己督促自己养成正确学习方法吧。
参考链接
斜体文本
斜体文本
粗体文本
粗体文本
粗斜体文本
粗斜体文本
带下划线文本