leetcode之双指针问题

发表于 | 分类于

shuangzhi双指针可以将时间复杂度从O(n*n)到o(n)

而在双指针的概念中，我们可以将双指针分为两种类型：快慢指针、相向指针，同向指针。

左右指针中间夹，快慢指针走到头，后序指针往回走.

快慢指针

快慢指针，顾名思义就是在使用时朝相同方向移动，一个指针的移动速度慢而另一个指针移动速度快，通过两个指针之间的移动所带来的差值，从而确定应用指针所在的数据结构中的某些数据或规律。

142.找出环型链表的入口处

判断是否有环。

  • 准备两个指针，快指针一次走两步，慢指针一次走一步。
  • 假如链表中有环的话，那么两个指针一定会相遇。

寻找入口处。

image.png

因为快指针一次两步，慢指针一次一步，所以快指针走的距离始终是慢指针的两倍。fast = 2*slow

即：
$$
2(F+a) = F+n(a+b)+a,n为快指针跑了多少圈
$$
即：
$$
F = (n-1)(a+b)+b
$$
因为a+b就是一圈环，所以，我们直接就可以看作F = b，即从头节点到入口处 = 第一次相遇点到入口处。

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
27
28
29
30
31
32
33
34
35
36
/**
     * 判断链表中一个环的入口处
     *
     * */

public ListNode getInteract(ListNode head){
    //注意判断head是否为null
    if(head==null) {
        return null;
    }
    ListNode slow = head;
    ListNode fast = head;
    while(fast!=null&&fast.next!=null){
        slow = slow.next;
        fast = fast.next.next;
        if(fast==slow){
            return fast;
        }
    }
    return null;
}

public ListNode detectCycle(ListNode head) {
    ListNode interact = getInteract(head);
    if(interact==null){
        return null;
    }

    ListNode start = head;
    while(start!=interact){
        start=start.next;
        interact=interact.next;
    }
    return start;

}

参考：环型链表官方题解

头尾指针

有序数组的 Two Sum

题目描述：在有序数组中找出两个数，使它们的和为 target。

通过头尾指针来解决。

当头指针+尾指针>value，尾指针–；

当头指针+尾指针<value，头指针++；

两者相等，返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
     * 使用头尾指针来解决
     * 当头+尾>target,头指针左移
     * 当头+尾<target，头指针右移
     * 头+尾=target，所求结果
     * */
public int[] calTwoSum(int[] numbers, int target) {
    int head = 0;
    int tail = numbers.length-1;
    int[] result ;
    while(head<tail){
        if(numbers[head]+numbers[tail]<target)
            head++;
        else if(numbers[head]+numbers[tail]>target)
            tail--;
        else
            return new int[]{head,tail};

    }
    return null;
}

两数平方和

题目描述：判断一个非负整数是否为两个整数的平方和。

可以看成是在元素为 0~target 的有序数组中查找两个数，使得这两个数的平方和为 target，如果能找到，则返回 true，表示 target 是两个整数的平方和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 *给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得a^2 + b^2 = c。
 * 使用头尾指针来解决
 * 取head = 0，tail = sqrt(c)
 *
 * */
public boolean judgeSquareSum(int c) {
    if(c<0){
        return false;
    }
    int head = 0;
    int tail = (int)Math.sqrt(c);
    while(head<=tail){
        if(head*head+tail*tail<c)
            head++;
        else if(head*head+tail*tail>c)
            tail--;
        else
            return true;
    }
    return false;
}

回文字符串

题目描述：可以删除一个字符，判断是否能构成回文字符串。

所谓的回文字符串，是指具有左右对称特点的字符串，例如 “abcba” 就是一个回文字符串。

使用双指针可以很容易判断一个字符串是否是回文字符串：令一个指针从左到右遍历，一个指针从右到左遍历，这两个指针同时移动一个位置，每次都判断两个指针指向的字符是否相同，如果都相同，字符串才是具有左右对称性质的回文字符串。

本题的关键是处理删除一个字符。在使用双指针遍历字符串时，如果出现两个指针指向的字符不相等的情况，我们就试着删除一个字符，再判断删除完之后的字符串是否是回文字符串。

在判断是否为回文字符串时，我们不需要判断整个字符串，因为左指针左边和右指针右边的字符之前已经判断过具有对称性质，所以只需要判断中间的子字符串即可。

在试着删除字符时，我们既可以删除左指针指向的字符，也可以删除右指针指向的字符。

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
27
28
29
public boolean validPalindrome(String s) {
    int head = 0;
    int tail = s.length()-1;
    /***假如头尾指针相等，继续移动
         * 头尾指针不等，分别删除head以及tail元素，看剩下的是否是回文的。
         * */
    while(head<tail){
        if(s.charAt(head)==s.charAt(tail)){
            head++;
            tail--;
        }else{
            //判断删除了一个字符会不会回文，两种情况，删除左指针以及右指针
            return (isPalindrome(s,head+1,tail)||isPalindrome(s,head,tail-1));
        }
    }
    return true;
}

public boolean isPalindrome(String s,int start,int end){
    while (start<end){
        if(s.charAt(start)==s.charAt(end)){
            start++;
            end--;
        }else{
            return false;
        }
    }
    return true;
}

两个头指针

最长子序列(524)

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * 给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。
 * 如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。
 *
 * **/

public String findLongestWord(String s, List<String> d) {
    String result = "";
    if(s.equals("")){
        return "";
    }
    for(String ele:d){
        if(ele!=null&&!(ele.equals(""))&&isSub(s,ele)){
            if(ele.length()>result.length()){
                result=ele;
            }else if(ele.length()==result.length()){
                if(ele.compareTo(result)<0){
                    result = ele;
                }
            }
        }
    }
    return result;
}


/**判断一个字符串是不是另一个字符串
*/
public boolean subLength(String s ,String ele){
    int sHead = 0;
    int eleHead = 0;
    int length = 0;
    while(eleHead<ele.length()&&sHead<s.length()){
        if(s.charAt(sHead)==ele.charAt(eleHead)){
            length++;
            sHead++;
            eleHead++;
        }else{
            sHead++;
        }
    }
    return ele.length()==length;
}

26. 删除排序数组中的重复项?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int removeDuplicates(int[] nums) {
    if(nums.length<=1){
        return nums.length;
    }
    int first = 0;
    int second = 1;
    while(second<nums.length){
        if(nums[first]==nums[second]){
            second++;
        }else{
            first++;
            nums[first] = nums[second];
            second++;
            index++;
        }
    }
    return first+1;
}
  • 基础技巧：分治、二分、贪心
  • 排序算法：快速排序、归并排序、计数排序
  • 搜索算法：回溯、递归、深度优先遍历，广度优先遍历，二叉搜索树等
  • 图论：最短路径、最小生成树
  • 动态规划：背包问题、最长子序列

数据结构，主要有如下几种：

  • 数组与链表：单 / 双向链表
  • 栈与队列
  • 哈希表
  • 堆：最大堆 ／ 最小堆
  • 树与图：最近公共祖先、并查集
  • 字符串：前缀树（字典树） ／ 后缀树