算法

leetCode学习
学习网站
leetcode:https://cn.leetcode.com

leetcode 英文:https://leetcode.com/

leetCode 题解:http://www.jiuzhang.com/solution/

leetCode 题解2:https://www.gitbook.com/book/siddontang/leetcode-solution/details

leetCode 题解是想:https://github.com/CyC2018/Interview-Notebook/blob/master/notes/Leetcode%20%E9%A2%98%E8%A7%A3.md

算法复杂度

常用复杂度

数据规模

当数据量大的时候,不同复杂度的算法之间才会有明显的差距,当数据规模很小的时候,不同的算法之间差异不大
算法的速度并非指的是时间,而是操作数的增速.

空间复杂度

空间复杂度是指除了原来数据存储必须的空间外,为了运行算法,额外需要开辟的空间才计入空间复杂度计算里头去。比如为了完成某个功能,具体就是一个函数,函数中我为了完成这个功能,额外开辟了多少内存,这个就是空间复杂度。如果和N没有关系,也就是常数的空间,那就是O(1),和N有关,那就是O(n),O(n^2)之类的。

如何写出正确程序

  • 明确变量含义
  • 循环不变量
  • 小数据量调试
  • 大数据量测试

tips

  • return 用于退出函数,所以在for循环中使用return会直接退出所有循环,确切来说是函数,不管函数里面有多少嵌套循环。
  • Python continue 语句跳出本次循环,确切是跳过当前循环的剩余语句,然后继续进行下一轮循环。而break跳出整个循环,当然如果是嵌套循环,break终止最里面的循环。continue和break可以用在while和for循环中
  • 在数据结构中进行查找是分情况的,按值查找和按索引查找是完全不同的,比如在数组中,按值查找如果是二分查找时间复杂度是O(logN),按索引查找则是O(1).

数组和链表的区别

数组支持随机访问,根据下标随机访问的时间复杂度为 O(1),链表适合插入,删除,时间复杂度是O(1)
数组必须是连续内存,这也是其支持随机访问的原因。
数组声明的时候必须制定大小,如果不够,只能再申请更大的内存,然后将数据复制过去,整个过程比较费事低效,而链表天然支持动态扩容

链表

链表有单链表,双向链表,循环链表,双向循环列表等
单链表和循环链表的每个结点由数据和后继指针组成(data+next),循环链表由数据,前驱指针和后继指针(pre+data+next)组成
第一个结点和最后一个结点分别叫头结点和尾结点,头结点记录链表的基地址,在单链表中尾结点指向一个空地址NULL,表示最后一个结点。循环链表中尾结点指向头结点

栈和队列

栈是一种操作受限的数据结构,只支持入栈和出栈操作。后进后出,可以用数组实现也可以用链表实现。数组实现的话就需要实现动态扩容,链表的天然支持扩容。不管怎样,两种实现在入栈和出栈操作上时间复杂度都是O(1)

散列表

  • 散列表是一种散列函数+数组或者链表 结合而成的复杂数据结构。查询效率很高,一般时间复杂度为O(1).
  • 散列函数就是将输入映射到数字的函数,常见的hash函数有md5,sha家族,函数最大的难度就在于如何处理散列冲突。

递归

堆栈溢出

这里的堆栈并不是指数据结构中的堆结构还是栈结构,而是指内存中的堆内存和栈内存

内存空间在逻辑上分为三部分:代码区、静态数据区和动态数据区,动态数据区又分为栈区和堆区。
代码区:存储方法体的二进制代码。高级调度(作业调度)、中级调度(内存调度)、低级调度(进程调度)控制代码区执行代码的切换。
静态数据区:存储全局变量、静态变量、常量,常量包括final修饰的常量和String常量。系统自动分配和回收。
栈区:存储运行方法的形参、局部变量、返回值。由系统自动分配和回收。
堆区:new一个对象的引用或地址存储在栈区,指向该对象存储在堆区中的真实数据。

当递归使用不当时,导致递推次数过多,或者无限递归出现,都会导致堆栈溢出。
在Python中通过

1
2
import sys
sys.getrecursionlimit()

可以获取最大递归深度,默认是1000,目的也是为了防止堆栈溢出。

排序

如何评价排序算法

  • 时间复杂度,包括最好最坏平均,以及最好最坏对应的原始数据
  • 空间复杂度,是否是原地排序,原地排序指的是空间复杂度为O(1)的算法
  • 稳定性

广度优先算法适合非加权图寻找最短路劲
狄克斯特拉算法适合加权图,且只适用于有向无环图(DAG),且权重必须为正,如果权重有负,可以使用贝尔曼-福德算法。

二叉树

  • 二叉树一般是通过链表存储,如果是完全二叉树,数组比较好,节省空间
  • 前序,中序,后序遍历时间复杂度都是O(N)
  • 二叉查找树,在树中的任意一个节点,其左子树中的每个节点的值,都要小于这个节点的值,而右子树节点的值都大于这个节点的值
  • 中序遍历二叉查找树,可以输出有序的数据序列,时间复杂度是 O(n),非常高效。因此,二叉查找树也叫作二叉排序树