双指针技巧

leetcode
6 minutes read (About 969 words)

双指针有两类：

  • 快慢指针
    • 一般用于解决链表相关的问题，如判断链表是否存在环
  • 左右指针
    • 一般用于解决数组相关的问题，如二分查找

快慢指针


快慢指针一般都初始化指向链表的头结点 head，前进时快指针 fast 在前，慢指针 slow 在后，巧妙解决一些链表中的问题。

判断链表中是否存在环

因为单链表的特点是每个节点只知道下一个节点，所以一个指针的话无法判断链表中是否含有环的。

使用快慢指针的思想解决链表中是否存在环的问题，其实是非常简单的，快慢指针初始时都指向链表头结点，慢指针每次前进一步，快指针每次前进两步。

  • 如果链表不存在环，那么快指针最终会运行到链表的终端节点
  • 如果链表存在环，那么快指针会多跑一会然后追上慢指针，此时说明链表存在环。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
boolean hasCycle(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;

    while(fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;

        if (fast == slow) {
            return true;
        }
    }
    return false;
}

已知链表中存在环，返回环的的起始位置

<
br />

关于计算环的起点这个，需要用到一点的数学知识，我们假定快慢指针在4这个位置相遇了。同时我们做如下约定：

  • 表头1到环起点3之间的距离我们记录为m
  • 节点3和节点4之间的距离我们记录为n
  • 环的长度我们记录为r
  • slow指针从表头1到当前位置4一共经过的距离我们记录为k

因此我们会有如下结论：

  • slow指针走的距离为k, 我们很容易得出k=m+n，那么fast指针走的距离就会是2k, 假定相遇时fast走了p圈，所以fast指针走的距离为：m + pr + n
  • 根据上一步的推理，我们会有如下的等式：pr + n + m = 2k = 2m + 2n
  • 所以pr = m + n. 所以我们可以得出，节点4顺时针到节点3的距离为 pr - n = m。其实可以推断出p = 1的。所以节点4顺时针到节点3的距离和节点1到节点3的距离是相等的。因此我们的算法代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
boolean getCycleStartPosition(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;

        //第一次相遇推出循环
        if (fast == slow) {
            break;
        }
    }

    //将慢指针设置为起点，然后快慢指针都每次走一步
    slow = head;
    while(slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}

寻找链表中间节点


这个问题的解法思路也是用快慢指针，期初2个指针都指向链表头部，然后慢指针每次走一步，快指针每次走两步，当快指针到达链表结尾时，慢指针的位置就是链表的中间节点。

1
2
3
4
5
6
7
8
9
10

ListNode getMidNode(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    while(fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
}

当链表的长度是奇数时，slow 恰巧停在中点位置；如果长度是偶数，slow 最终的位置是中间偏右

寻找链表的倒数第 k 个元素

这个问题换是快慢指针的事情，这次快慢指针都是每次走一步，但是得先让快指针提前走k步而已。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ListNode getLastKNode(ListNode head, int k) {
    if (head == null || k < 0) {
        return null;
    }
    ListNode fast = head;
    ListNode slow = head;

    for(int i = 0; i < k; i++) {
        fast = fast.next;
        if (fast == null) {
            return null;
        }
    }

    while(fast != null && fast.next != null) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

二分查找一般解法

leetcode
7 minutes read (About 986 words)

二分查找模板

二分查找一般容易犯错的地方有3个：

  • 应该给mid加1还是应该减1，还是不加不减
  • 上层的while循环里面的条件应该是left < right还是 left <= right
  • 计算mid时，最好是采用mid = left + (right - left)/2而不是mid = (left + right) /2。因为这样可以避免int溢出。


二分查找的一般框架为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int binarySearch(int[] nums, int target) {
	int left = 0;
    int right = nums.length ...;
    
    while(...) {
      int mid = left + (right - left) / 2;
      if (nums[mid] == target) {
          ...
      } else if (nums[mid] < target) {
          ...
      } else if (nums[mid] > target) {
          ...
      }
    }
    return ...
}

上面框架中省略的地方，其实就是比较容易出问题的地方。


下面直接给出二分查找的算法模板，一般只需要熟记其中之一就好了。我一般都采样第一个：


总结一下2个模板的记忆方法：

  • 如果初始化right = nums.length -1, 那么使用left <= right，并且right = mid - 1
  • 如果初始化right = nums.length那么使用left < right, 并且right = mid

    模板1

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    int binarySearch(int[] nums, int target) {
    	int left = 0;
        int right = nums.length - 1; //注意
        
        while( left <= right ) { //注意
          int mid = left + (right - left) / 2;
          if (nums[mid] == target) {
              //找到目标值的相关逻辑
              return mid;
          } else if (nums[mid] < target) {
              left = mid + 1;  //注意
          } else if (nums[mid] > target) {
              right = mid - 1; //注意
          }
        }
        //没找到目标值的相关逻辑
        return -1;
    }

    模板2

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    int binarySearch(int[] nums, int target) {
    	int left = 0;
        int right = nums.length;  //注意
        
        while( left < right ) { //注意
          int mid = left + (right - left) / 2;
          if (nums[mid] == target) {
              //找到目标值的相关逻辑
              return mid; 
          } else if (nums[mid] < target) {
              left = mid + 1;
          } else if (nums[mid] > target) {
              right = mid //注意
          }
        }
        //没找到目标值的相关逻辑
        return -1;
    }


下面通过一些例子来使用一下模板

寻找一个数

这个场景是最简单的，肯能也是大家最熟悉的，即在递增序列中搜索一个数，如果存在，返回其索引，否则返回 -1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int binarySearch(int[] nums, int target) {
	int left = 0;
    int right = nums.length - 1; //注意
    
    while(left <= right) {
      int mid = left + (right - left) / 2;
      if (nums[mid] == target) {
          return mid;
      } else if (nums[mid] < target) {
         left = mid + 1; //注意
      } else if (nums[mid] > target) {
          right = mid - 1; //注意
      }
    }
    return -1;
}

LeetCode上面有一个题目，[374. 猜数字大小] 其实就是最简单和标准的二分查找算法。

二分查找的变种问题

查找左右边界


这类题目一般的特点为：

  • 数组有序，但是有重复元素
  • 数组部分有序，不包含重复元素
  • 数组部分有序，包含重复元素。

查找左边界


既然要寻找左边界，搜索范围就需要从右边开始，不断往左边收缩，也就是说即使我们找到了nums[mid] == target, 这个mid的位置也不一定就是最左侧的那个边界，我们还是要向左侧查找，所以我们在nums[mid]偏大或nums[mid]就等于目标值的时候，继续收缩右边界, 不过需要注意最终while循环外需要外检查一下边界情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    // 搜索区间为 [left, right]
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            // 搜索区间变为 [mid+1, right]
            left = mid + 1;
        } else if (nums[mid] > target) {
            // 搜索区间变为 [left, mid-1]
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 收缩右侧边界
            right = mid - 1;
        }
    }
    // 检查出界情况
    if (left >= nums.length || nums[left] != target)
        return -1;
    return left;
}

### 查找右边界 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 这里改成收缩左侧边界即可
            left = mid + 1;
        }
    }
    // 这里改为检查 right 越界的情况，见下图
    if (right < 0 || nums[right] != target)
        return -1;
    return right;
}
## 参考文章：

leetcode-28 实现strStr()

leetcode
a minute read (About 174 words)

题目描述:

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/implement-strstr
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的第一版答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int strStr(String haystack, String needle) {
        if (haystack == null) return 0;
        if (needle == null) return 0;
        int haystackLength = haystack.length();
        int needleLength = needle.length();
        if (needleLength > haystackLength) {
            return -1;
        }
        
        for (int i = 0; i < (haystack.length() - needleLength + 1); i++) {
            int j =0;
            while(j < needleLength) {
                if (haystack.charAt(i + j) == needle.charAt(j)) {
                    j ++;
                } else {
                    break;
                }
            }
            if (j == needleLength) {
                return i;
            }
        }
        return -1;
    }
}
我的技术随笔

Categories

Tag Cloud

arthas avro bistoury cache concurrent dubbo elasticsearch fe git idea java javascript javscript kafka kettle leetcode lettuce linux mac maven mybatis mysql netty nginx python redis redisson spark spring tomcat trace zookeeper 中间件 杂谈 源码阅读 系统设计
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×