买卖股票问题总结

买卖股票问题是dp的代表类型题目。

Master Theorem(主定理)

主定理用于在divide&conquer问题中求时间复杂度，以前总是记不住，今天总结了一下，方便记忆。

Example: merge sort: T(n) = 2*T(n/2)+O(n)

a = 2, b =2, n^logba == n, 所以符合2.1, 所以结果是O(nlogn)

约瑟夫环

https://blog.csdn.net/u011500062/article/details/72855826

Sliding Window

sliding window问题的思想并不复杂，就是设立一个start和一个end指针进行遍历，end不停地在前进，start只有在条件不符合的时候前进，但是在进行过程中由于变量的更改会出现有思路写不出来的问题，所以总结一下模板。

sliding window思路：

1
2
3
4
5

while(end<length){
    1. 处理end位置的character，end++
    2. 如果达到了某种条件，我们使用while loop或者if打破这种条件，start++
    3. 更新结果，这个时候的end是还没处理过的，start是处理过的，所以如果求长度什么的是end-start而不是end-start+1
}

Deep copy类型题总结

这种类型题不难，只有两道代表类型题，一道是deep copy linkedlist，一道是deep copy graph。

最直观的想法就是就是使用HashMap，首先把node都先copy一遍，然后再连接他们。

提升一点的做法是使用dfs，在copy的过程中边copy边连接。注意，对于使用dfs copy graph我们不需要visited[]数组，我们可以直接通过判断Map中有没有该node来确认是否visited。

对于copy linkedlist，有一个提升空间复杂度的做法。Follow Up 如果不适用额外的辅助存储空间：

第一步：将每个节点复制并插入相邻节点中。如1->2->3->NULL变为：1->1’->2->2’->3->3’->NULL。

第二步：接下来连接Random指针，如果存在一条Random指针从A指向B，那么将A->next的Random指针指向B->next。

第三步：将链表拆开。A=head, A’=head->next; A->next=A->next->next；A’->next=A’->next->next; …

时间复杂度O(n)，额外空间复杂度O(1)

Behavior Questions

The STAR format stands for Situation, Task, Action, Result:

Situation: An event, project, or challenge faced
Task: Your responsibilities and assignments for the situation
Action: Steps or procedure taken to relieve or rectify situation
Result: Results of actions taken.

Garbage Collection

The java virtual machine(JVM) that runs your program uses hideden data structures to manage memory.

https://www.cnblogs.com/ktao/p/8586966.html

https://www.jianshu.com/p/b72d3ab9e54a

https://blog.csdn.net/whoamiyang/article/details/51926985

1. 数据库索引是一种数据结构，用于加快查询表的速度
2. B Tree(Balanced Tree)是平衡多叉树，所以它的高度要远低于红黑树等平衡二叉树，也就是说他很扁，可以有效地提升查询的效率
3. B树的非叶子节点和叶子节点都是既有索引，也有数据。B+树的非叶子节点只保存索引,不保存实际的数据,数据都保存在叶子节点的有序链表中。

有三种情况将使得元素脱离文档流，分别是浮动(float left or right)、绝对定位(position:absolute)、固定定位(position:fixed)。