基础算法学习

佳境Shmily 2020-04-27 15:45:00
技术

前言

算法与数据结构从现在开始重视还来得及!
为何要重视算法与数据结构?

基本概念

学习算法有帮助的一些基本概念。

顺序存储与链式存储

物理结构:是指数据的逻辑结构在计算机中的存储形式。
逻辑结构:是指数据对象中数据元素之间的互相关系。
alt LearnBasicAlgorithm-01

基础数据结构

数据结构是算法的基石。要做到对算法的融会贯通和举一反三,熟悉各种数据结构是必备的。优秀的算法取决于采用哪种数据结构。
重点:熟悉每种数据结构优缺点应用场景,熟练掌握其思想并灵活运用。

数组和字符串

特点:逻辑结构与物理结构一致
优点:构建简单,索引某个元素的复杂度O(1)
缺点:必须连续分配一段内存,查询过程遍历时间复杂度O(n),删除过程时间复杂度O(n)
场景:元素个数确定,经常按索引查询,不经常插入和删除

经典题目:
翻转字符串
字母异位词

链表

分为单向链表和双向链表
优点:能灵活分配内存空间,插入和删除元素效率高O(1)
缺点:不能通过下标读取,读取第n个位置元素复杂度O(n)
场景:元素个数不确定,经常插入和删除,不经常查询

经典题目:
快慢指针->判断是否有环
快慢指针->翻转链表
快慢指针->寻找倒数第K元素
快慢指针->找链表中间位置
构建虚假链表头

后进先出(LIFO),可以采用单链表实现复杂度O(1),虽然也可以用数组实现但时间复杂度可能较大
场景:解决问题时只关心最近一次操作,解决完后要找之前的操作。

经典题目:
匹配括号,判断是否有效

队列

先进先出(FIFO),可以采用双链表实现。
场景:按一定顺序处理过来的数据。

经典题目:
广度优先搜索

双端队列

和普通队列的区别是:可以在队头队尾都可以查看,添加和删除数据,复杂度都为O(1),可以采用双链表实现。
场景:实现长度动态变化的窗口或连续区间,动态窗口。

经典题目:
返回滑动窗口最大值

充分应用递归,树的问题基本都与递归有关
面试常考:普通二叉树,平衡二叉树,完全二叉树,二叉搜索树,四叉树,多叉树
需要了解:红黑树 ,AVL自平衡二叉搜索树

遍历方法:
前序遍历:根->左子树->右子树
中序遍历:左子树->根->右子树
后序遍历:左子树->右子树->根
深度优先遍历DFS:包含以上三种
广度优先遍历BFS:即层次遍历,每一层从左向右输出

经典题目:
二叉搜索树的第K个最小元素

如何学习数据结构与算法

好的学习方法往往能起到事半功倍的效果,这里根据算法大佬们的学习经历总结一下算法学习方法,警示自己督促自己养成正确学习方法吧。

参考链接

我是如何学习数据结构与算法的

斜体文本
斜体文本
粗体文本
粗体文本
粗斜体文本
粗斜体文本
带下划线文本