1. 双指针
- 快慢指针-【链表】
- 判定链表是否由闭环
- 链表中点二分
- 链表
- 归并排序
- 左右指针-【数组/字符串】
- 【有序】数组/字符串,二分搜索
- 反转数组
- 滑动窗口
2. 如何判断是双指针
3. 双指针步骤
快慢指针
- 快慢指针初始化在头节点head
- 前进时fast在前,slow在后
左右指针
- 左指针left初始边缘0,右指针right初始数组最大边缘length-1
- left <(=) right时循环调用,取两者中间坐标赋给left或right
3. 双指针框架
快慢指针
js
var hasCycle = function(head) {
var fast = head,
slow = head;
while(fast && fast.next) { // 判断fast及其下一个节点
fast = fast.next.next // 重点:fast前进2 slow前进1
slow = slow.next
if(fast === slow) {
return true
}
}
return false
};
左右指针
js
var twoSum = function(numbers, target) {
var left = 0,
right = numbers.length - 1
while(left < right) { // 如果左右指针不允许选择同一个元素重复利用,则不可以相等
var sum = numbers[left] + numbers[right]
if(sum === target) {
return [left + 1, right + 1]
}
if(sum < target) { // 重点:根据条件控制左指针或右指针变动
left++
} else {
right--
}
}
return null
};
4. 细化问题点
4.1 时间复杂度低,O(N)
根据其框架逻辑,循环一次depth增加一次,找到终点时能保证距离最短。最坏情况下在满二叉树时,从根节点起点,找底层最后一个树节点时,就需要全部节点穷举过,所以是O(N) DFS也是O(N),但永远都是需要所有分叉都走完才能对比,实际比BFS慢很多。BFS是面,DFS是线。BFS是集体行动,DFS是单打独斗。
4.2 空间复杂度高,为O(N)
空间复杂度为O(N)。最坏情况下在满二叉树时,存了最底部的树节点N/2,所以最坏空间复杂度O(N)。而DFS是递归,是一条线,最坏情况下也是树的高度,即O(logN)
4.3 双向BFS-优化
从起点和终点同时扩散,相遇(有交集)时停止。最坏时还是O(N),但实际中,如果是起点根节点,满二叉树底部的中间终点,便只要遍历半棵树。
总结
- BFS与DFS
- BFS的实际时间复杂度低,但空间复杂度高,而DFS相反。
- 时间复杂度
BFS: O(N)
DFS: O(N) - 空间复杂度
BFS: O(N)
DFS: O(logN)