【011-Week1】学习总结

[Water-DD]

#111

基础知识

复杂度:
1.最坏情况时间复杂度：代码在最理想情况下执行的时间复杂度。
2.最好情况时间复杂度：代码在最坏情况下执行的时间复杂度。
3.平均时间复杂度：用代码在所有情况下执行的次数的加权平均值表示。
4.均摊时间复杂度：在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度
数组
数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
数组在不同语言中实现是不一样的,
C++ 实现如下:

Java的实现方式主要是通过引用引用不同内存的地址

链表
数组简单易用，在实现上使用的是连续的内存空间，可以借助 CPU 的缓存机制，预读数组中的数据，所以访问效率更高。而链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法有效预读
数组的内存是连续的，链表的内存是不连续的，数组支持根据下表的随机访问，链表执行根据链表节点的增删效率很高
栈
后进先出，常用的场景对栈的操作也比较简单，入栈push，出栈pop，查看栈顶元素peek，使用场景也比较特殊，在算法题中序号的合法性，解码

队列
队列也是一种“操作受限”的线性表，只支持两种基本操作：入队和出队。

队列的应用非常广泛，特别是一些具有某些额外特性的队列，比如循环队列、阻塞队列、并发队列。它们在很多偏底层的系统、框架、中间件的开发中，起着关键性的作用。

递归
终止条件
思维上一定要"信任"下一层的递归结果，不用把自己带入下一层的逻辑中
尾递归，解决栈溢出的问题，但是有的时候并不能很好的解决，可以用尾递归的都可以使用迭代实现
算法题实现总结
1.TwoSum
这个题比较简单，选择做这个题，主要是用来练习，算法课上学习的代码优化流程，第一遍直接使用暴力破解，获取O(n2)的算法复杂度，再优化考虑内层循环的索引优化问题，索引的优化可以使用二叉树，哈希，跳表等，哈希的索引效率最高为O(1)所以使用哈希进行优化
2.Add Two Numbers
这个题是一个链表题，链表实现主要是指针容易造成空指针，注意这一点，理清楚思路是没有问题的
学习感悟
按照老师的讲解去实践感觉比以前的思路要清晰很多，感觉学习，收获很多