数据结构

算法

算法的定义

解决特定问题步骤的描述
形式有：伪代码，文字描述

算法的基本特征

输入输出
有穷性
确定性
可行性

算法要求

正确性
可读性
健壮性

递归

递归的本质：自己调用自己

系统栈的作用

保存上下文
传递参数
保存临时变量栈帧

递归与动态规划

为什么需要改动态规划？
存在重复计算，利用缓存
什么是贪心算法？
迪杰斯特拉算法：每次选择最小的路径

哈希函数

MD5 SHA

单向性
不可逆
碰撞约束
相同输入，输出要相同
不同输入，允许碰撞，但要足够小
分布均匀

hash应用

找一个大文件中相同的两行文件
一个2T文件，计算机的内存256MB
通过hash，每行进行映射，相同行的输出相同

排序

稳定性：鸡毛插龟壳鸡：基数排序毛：冒泡排序
插：插入排序龟：归并排序
nlogn的时间复杂度：快排，归并，堆排序
o（nlogn）不一定比o（n）快，看常数项

上面是基于比较的，下面不基于比较

对全国年龄排序计数排序
0-100岁 array[100]

指针与引用

指针可以有多层，引用只能一层

new和malloc的区别

new=构造函数+malloc

什么是栈？什么是堆？

堆是由程序员分配的
栈由操作系统控制

内存泄漏: 没有free （占着茅坑不拉屎）

静态变量

static静态局部变量和局部变量区别
静态变量只初始化一次

快排代码

o（log2n）树高

hashmap

拉链法

数据结构面试