双指针

发表于 | 更新于: | 分类于 |

Question457 环形数组是否存在循环

双指针解法

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
// 双指针 快指针走两步 慢指针走一步
public static boolean circularArrayLoop(int[] nums) {
    int slow, fast;
    for (int i = 0; i < nums.length; i++) {
        slow = fast = i;
        fast = next(nums, fast);
        // 反向或者是有0元素 则跳出循环
        while (nums[slow] * nums[fast] > 0 && nums[fast] * nums[next(nums, fast)] > 0) {
            // 快慢指针相遇 如果不是自身循环 则返回true；
            if (slow == fast) {
                if (slow != next(nums, slow)) {
                    return true;
                } else {
                    break;
                }
            }
            slow = next(nums, slow);
            fast = next(nums, next(nums, fast));
        }
        // 如果同方向遇到自身循环 将快慢指针经过的所有元素置为0
        // 如果遇到不同方向 则将快指针之前的所有元素(也有可能包含快指针对应的元素，看奇数个还是偶数个）置为0：
        int rep = i;
        while (nums[rep] * nums[next(nums, rep)] > 0) {
            int temp = rep;
            rep = next(nums, rep);
            nums[temp] = 0;
        }
        nums[rep]=0;
    }
    return false;
}

// 返回快指针所对应的下标
public static int next(int[] nums, int fast) {
    int n = nums.length;
    // 此写法可以应对 正负两种情况
    return (nums[fast] + fast) % n + n;
}

图的遍历标记（使用新数组标记）

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
class Solution {   
    public boolean circularArrayLoop(int[] nums) {
        int n = nums.length;
        // 使用 vis 数组对每个下标进行标记
        // 如果下标为 i 的位置在第 idx 轮被标记，则有 vis[i] = idx
        int[] vis = new int[n];
        for (int start = 0, idx = 1; start < n; start++, idx++) {
            if (vis[start] != 0) continue;
            int cur = start;
            boolean flag = nums[cur] > 0;
            while (true) {
                int next = ((cur + nums[cur]) % n + n) % n;
                if (next == cur) break;
                if (vis[next] != 0) {
                    // 如果 next 点已经被标记过，并且不是在本轮被标记，那么往后的通路必然都被标记，且无环，跳出   
                    if (vis[next] != idx) break;
                    // 如果 next 点已被标记，并且是本来被标记，说明找到了环
                    else return true;
                }
                if (flag && nums[next] < 0) break;
                if (!flag && nums[next] > 0) break;
                vis[next] = idx;
                cur = next;
            }
        }
        return false;
    }
}

Question11 双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int maxArea(int[] height) {
        int i=0,j=height.length-1,mul,max=0;
        while(i!=j){
            // 从两边开始比较 哪边的值小 哪边移动一个
            // 为什么小的可以移动：
            // 1.另一边如果下次移动过程当中遇到一个比该值大的元素，就算这两个元素相乘也比这次相乘要小（横轴距离变短，高度不变)
            // 2. 另一边如果下次移动过程当中遇到一个比该值小的元素，比该值小的这个元素与这个元素相乘也比那一次的乘积小（因为横轴小于等于这次横轴距离，且高度小于这次的高度）
            if(height[i]<height[j]){
                mul=height[i]*(j-i);
                max=mul>max?mul:max;
                i++;
            }else{
                mul=height[j]*(j-i);
                max=mul>max?mul:max;
                j--;
            }
        }
        return max;
    }

时间复杂度

O(N) 有数组长度决定时间
空间复杂度
O(1) 只用了常量个空间