Backtracking总结

Backtracking本质上就是DFS，相当于不停地往深处进行dfs，遇到不可能的情况就停止dfs回到上层。
相当于有一些剪枝的DFS。

LinkedList Cycle问题

在LinkedList中查看是否存在cycle，使用的主要方法是Floyd’s Tortoise and Hare算法，原理就是设置两个快慢指针，如果存在cycle，那么快慢指针一定会相遇。
当然不止LinkedList可以使用这个方法，只要我们能把题目类比成LinkedList(也就是前一个数能找到后一个数，其实就是LinkedList的作用)，然后题目中存在环，那么也就可以使用这个方法。

Binary Search And Search Problem总结

Search问题的核心思想只有一个，就是每一步都会减少搜索域

买卖股票问题总结

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

约瑟夫环

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)

Integer to something 类型题总结

这种类型题的思路就是将可能的情况放到Array中，由小到大或者由大到小排列，将需要得到的结果依次减Array中的index得出结果。之前做过的Broadway Technology的OA也是同样类型的题。

Merge K sorted lists

首先要会做merge 2 sorted lists，这个比较简单，就是使用双指针进行merge。
Merge K sorted lists有两个做法：

• 使用一个list长度的Priority Queue，重新构写Comparator(按照lisstnode.val进行比较)，每次取出最小的listnode以后再向Priority Queue加入新的node。 时间复杂度是O(nlogk)，因为所有的node都要进到PQ中，而每个进去都是O(k)时间。空间复杂度O(k)。
• divide and conquer的思想，因为我们已经做过merge 2 sorted list的题，那么很自然可以想到将list不断地divide直到只剩一个，然后再两个两个的merge，思想与merge sort很像。时间复杂度也是O(nlogk)。

String Matching类型问题总结

这类问题的鼻祖问题Sequence Alignment(Edit distance)在算法课上学习过，但是理解不够深刻，本质上就是二维DP的问题。时间空间复杂度都是O(mn)。
这种String Matching或者DP的问题，一定不要上来就想*号该怎么处理，而是应该用一种recursive的思想去处理（算法的问题就是要把大问题逐渐变成更小的问题）：

• 对于两个string，想要把两个长string比较的大问题变成两个更短的string比较的问题，那么做法无疑就是比较两个string的最后一位，根据不同的情况可以使他们缩短，然后再比较缩短了的string，再缩短不断重复，这就是recursive的思想。
• 对于recursive，我们可以发现会有很多的子问题在其中，所以可以用dp[][]数组进行memorize。
• 进一步总结变成bottom up的DP解法。