您现在的位置是：首页 > Java

当前栏目

用javascript分类刷leetcode--双指针(图文视频讲解)

2023-02-19 12:20:10 时间

双指针

普通指针：两指针同一方向或不同方向
对撞指针：两指针互相靠拢
快慢指针：一快一慢141. 环形链表 (easy)

给你一个链表的头节点 head ，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。如果链表中存在环，则返回 true 。否则，返回 false 。示例 1：
解释：链表中有一个环，其尾部连接到第二个节点。示例 2：
中有一个环，其尾部连接到第一个节点。示例 3：
中没有环。提示：链表中节点的数目范围是 0, 104 -105 <= Node.val <= 105 pos 为 -1 或者链表中的一个有效索引。进阶：你能用 O(1)（即，常量）内存解决此问题吗？

方法1.哈希表或set:

动画过大，点击查看

思路：准备一个map或者set，然后循环链表，每次遍历到一个节点的时候，判断当前节点是否在map中存在，如果不存在就把当前节点加入map中，如果存在的话说明之前访问过此节点，也就说明了这条链表有环。
复杂度分析：时间复杂度O(n)，n是链表的数量，最差的情况下每个节点都要遍历。空间复杂度O(n)，n是存储遍历过的节点的map或者set

js:

var hasCycle = (head) => {
    let map = new Map();
    while (head) {
        if (map.has(head)) return true;//如果当前节点在map中存在就说明有环
        map.set(head, true);//否则就加入map
        head = head.next;//迭代节点
    }
    return false;//循环完成发现没有重复节点，说明没环
};

方法2.快慢指针

动画过大，点击查看

思路：准备两个指针fast和slow，循环链表，slow指针初始也指向head，每次循环向前走一步，fast指针初始指向head，每次循环向前两步，如果没有环，则快指针会抵达终点，如果有环，那么快指针会追上慢指针
复杂度：时间复杂度O(n)，空间复杂度O(1)

js:

var hasCycle = function (head) {
    //设置快慢指针
    let slow = head;
    let fast = head;
    //如果没有环，则快指针会抵达终点，否则继续移动双指针
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        //快慢指针相遇，说明含有环
        if (slow == fast) {
            return true;
        }
    }

    return false;
};

142. 环形链表 II (medium)

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改链表。示例 1：
1 的链表节点解释：链表中有一个环，其尾部连接到第二个节点。示例 2：
表节点解释：链表中有一个环，其尾部连接到第一个节点。示例 3：
链表中没有环。提示：链表中节点的数目范围在范围 0, 104 内 -105 <= Node.val <= 105 pos 的值为 -1 或者链表中的一个有效索引进阶：你是否可以使用 O(1) 空间解决此题？

方法1.哈希表

思路：遍历链表，将节点加入一个set中，每次判断当前节点是否在set中，如果存在重复的节点，这个节点就是入环节点
复杂度：时间复杂度O(n)，空间复杂度O(n)

js：

var detectCycle = function(head) {
    const visited = new Set();
    while (head !== null) {//终止条件，如果没有环 跳出循环
        if (visited.has(head)) {//如果存在重复的节点，这个节点就是入环节点
            return head;
        }
        visited.add(head);//将节点加入set中
        head = head.next;
    }
    return null;
};

方法2.快慢指针

动画过大，点击查看

ds_175

思路：慢指针移动两步，快指针移动一步，相遇之后，快指针变成头指针，然后每次快慢指针各走一步直到相遇，相遇的节点就是入环节点
复杂度：时间复杂度O(n)，空间复杂度O(1)

js：

var detectCycle = function(head) {
    if (head === null) {
        return null;
    }
    let slow = head, fast = head;
    while (fast !== null) {
        slow = slow.next;//慢指针移动两步，快指针移动一步
        if (fast.next !== null) {
            fast = fast.next.next;
        } else {
            return null;//如果没有环 之间返回null
        }
        if (fast === slow) {//有环
            let fast = head;
              //快指针指向头节点，然后每次快慢指针各走一步直到相遇，相遇的节点就是入环节点
            while (fast !== slow) {
                fast = fast.next;
                slow = slow.next;
            }
            return fast;
        }
    }
    return null;
};

15. 三数之和 (medium)

给你一个整数数组 nums ，判断是否存在三元组 [numsi, numsj, numsk] 满足 i != j、i != k 且 j != k ，同时还满足 numsi + numsj + numsk == 0 。请你返回所有和为 0 且不重复的三元组。注意：答案中不可以包含重复的三元组。示例 1：输入：nums = -1,0,1,2,-1,-4 输出：[-1,-1,2,-1,0,1] 解释： nums0 + nums1 + nums2 = (-1) + 0 + 1 = 0 。 nums1 + nums2 + nums4 = 0 + 1 + (-1) = 0 。 nums0 + nums3 + nums4 = (-1) + 2 + (-1) = 0 。不同的三元组是 -1,0,1 和 -1,-1,2 。注意，输出的顺序和三元组的顺序并不重要。示例 2：输入：nums = 0,1,1 输出：[] 解释：唯一可能的三元组和不为 0 。示例 3：输入：nums = 0,0,0 输出：[0,0,0] 解释：唯一可能的三元组和为 0 。提示：3 <= nums.length <= 3000 -105 <= numsi <= 105

方法1.暴力求解，对于三个数字，循环3次，分别计算和，时间复杂度O(n^3)

方法2.c=-(a+b): 确定了a和b，那就可以想两数之和一样，在map中寻找-(a+b)，减少一层循环，时间复杂度O(n^2)，空间复杂度O(n)。

方法3.排序然后查找

动画过大，点击查看

思路：先排序数组，数组长度必须大于3，循环数组，假如当前循环到了i索引，则定义两个指针L = i+1，和R = nums.length-1,如果和sum=nums[i] + nums[L] + nums[R]小于0，则向右移动左指针，如果sum大于0，则左移右指针，如果sum等于0，则正好找到了这3个数，然后在尝试L++,R--，继续寻找中间是否有三个数之和等于0，注意在循环的过程中遇见相同的三个数需要去重。
复杂度分析：时间复杂度O(n^2)，n为数组的长度。空间复杂度O(logn)，即排序所需要的空间

js:

var threeSum = function(nums) {
    let ans = [];
    const len = nums.length;
    if(nums == null || len < 3) return ans;//数组的长度大于3
    nums.sort((a, b) => a - b); // 排序
    for (let i = 0; i < len ; i++) {
        if(nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
        if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
        let L = i+1;
        let R = len-1;
        while(L < R){//虽然里面还有两个循环，但是整体的L和R移动的时间内复杂度还是o(n)
            const sum = nums[i] + nums[L] + nums[R];
            if(sum == 0){
                ans.push([nums[i],nums[L],nums[R]]);
                while (L<R && nums[L] == nums[L+1]) L++; // 去重
                while (L<R && nums[R] == nums[R-1]) R--; // 去重
                L++;
                R--;
            }
            else if (sum < 0) L++;
            else if (sum > 0) R--;
        }
    }        
    return ans;
};

160. 相交链表（easy）

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。图示两个链表在节点 c1 开始相交：
保持其原始结构。自定义评测：评测系统的输入如下（你设计的程序不适用此输入）：intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0 listA - 第一个链表 listB - 第二个链表 skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数 skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被视作正确答案。示例 1：
,5, listB = 5,6,1,8,4,5, skipA = 2, skipB = 3 输出：Intersected at '8' 解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 4,1,8,4,5，链表 B 为 5,6,1,8,4,5。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。 — 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。示例 2：
,4, listB = 3,2,4, skipA = 3, skipB = 1 输出：Intersected at '2' 解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 1,9,1,2,4，链表 B 为 3,2,4。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。示例 3：
listB = 1,5, skipA = 3, skipB = 2 输出：null 解释：从各自的表头开始算起，链表 A 为 2,6,4，链表 B 为 1,5。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。这两个链表不相交，因此返回 null 。提示：listA 中节点数目为 m listB 中节点数目为 n 1 <= m, n <= 3 * 104 1 <= Node.val <= 105 0 <= skipA <= m 0 <= skipB <= n 如果 listA 和 listB 没有交点，intersectVal 为 0 如果 listA 和 listB 有交点，intersectVal == listAskipA == listBskipB进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？

方法1:哈希表

思路：将链表A存入set中，第一个相同的节点就是重合的节点
复杂度：时间复杂度O(m+n)，m、n分别是两个链表的长度。空间复杂度O(m)

js：

var getIntersectionNode = function(headA, headB) {
    const visited = new Set();
    let temp = headA;
    while (temp !== null) {//将链表A存入set中
        visited.add(temp);
        temp = temp.next;
    }
    temp = headB;
    while (temp !== null) {
        if (visited.has(temp)) {//第一个相同的节点就是重合的节点
            return temp;
        }
        temp = temp.next;
    }
    return null;
};

方法2:双指

动画过大，点击查看

思路：用双指针pA 、pB循环俩个链表，链表A循环结束就循环链表B，链表A循环结束就循环链表B，当pA == pB时就是交点，因为两个指针移动的步数一样
复杂度：时间复杂度O(m+n)，m、n分别是两个链表的长度。空间复杂度O(1)

js：

var getIntersectionNode = function(headA, headB) {
    if (headA === null || headB === null) {
        return null;
    }
    let pA = headA, pB = headB;
    while (pA !== pB) {
        pA = pA === null ? headB : pA.next;//链表A循环结束就循环链表B    
        pB = pB === null ? headA : pB.next;//链表A循环结束就循环链表B    
    }
    return pA;//当pA == pB时就是交点
};

11. 盛最多水的容器（medium）

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, heighti) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。说明：你不能倾斜容器。示例 1：
表输入数组 1,8,6,2,5,4,8,3,7。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。示例 2：输入：height = 1,1 输出：1提示：n == height.length 2 <= n <= 105 0 <= heighti <= 104

方法1:双指针

动画过大，点击查看

思路：用双指针i，j循环height数，i，j对应高度较小的那个先向内移动，不断计算面积，更新最大面积
复杂度：时间复杂度O(n)，n是数组height的长度，遍历一次。空间复杂度O(1)

js：

var maxArea = function(height) {
    let max = 0;
    for (let i = 0, j = height.length - 1; i < j;) {//双指针i，j循环height数组
          //i，j较小的那个先向内移动 如果高的指针先移动，那肯定不如当前的面积大
        const minHeight = height[i] < height[j] ? height[i++] : height[j--];
        const area = (j - i + 1) * minHeight;//计算面积
        max = Math.max(max, area);//更新最大面积
    }
    return max;
};

猜你喜欢

最长无重复子串
写技术博客的一些心得分享
Java 多线程（七）：线程池
Java 多线程（五）：锁（三）
Java 多线程（四）：锁（二）
Java 多线程（三）：锁（一）
Java 多线程（二）：并发编程的三大特性
线性时间非比较类排序
Java 多线程（一）：基础
合并k个已排序的链表
HDFS 高可用分布式环境搭建
合并两个有序数组
连续子数组的最大和
HDFS 分布式环境搭建
容器盛水问题
大数加法
HDFS 伪分布式环境搭建
设计LRU缓存结构
两数之和
使用单调栈来解决的一些问题

zl程序教程

当前栏目

用javascript分类刷leetcode--双指针(图文视频讲解)

双指针

方法1.哈希表或set:

方法2.快慢指针

142. 环形链表 II (medium)

方法1.哈希表

方法2.快慢指针

15. 三数之和 (medium)

160. 相交链表（easy）

方法1:哈希表

方法2:双指

11. 盛最多水的容器（medium）

方法1:双指针

876. 链表的中间结点（easy)

相关文章

当前栏目

用javascript分类刷leetcode--双指针(图文视频讲解)

双指针

方法1.哈希表或set:

方法2.快慢指针

142. 环形链表 II (medium)

方法1.哈希表

方法2.快慢指针

15. 三数之和 (medium)

160. 相交链表 （easy）

方法1:哈希表

方法2:双指

11. 盛最多水的容器 （medium）

方法1:双指针

876. 链表的中间结点（easy)

相关文章

160. 相交链表（easy）

11. 盛最多水的容器（medium）