leetcode100----双指针

简介: leetcode100----双指针

283. 移动零

给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

请注意 ,必须在不复制数组的情况下原地对数组进行操作。

示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:
输入: nums = [0]
输出: [0]

提示:

1 <= nums.length <= 104

-231 <= nums[i] <= 231 - 1

进阶:你能尽量减少完成的操作次数吗?

class Solution {
public void moveZeroes(int[] nums) {
    int n = nums.length;
    int slow = 0;
    int fast = 0;
    // 将非零元素前移
    while (fast < n) {
        if (nums[fast] != 0) {
            nums[slow] = nums[fast];
            slow++;
        }
        fast++;
    }
    // 将剩余元素置为零
    while (slow < n) {
        nums[slow] = 0;
        slow++;
    }
}
}

思路:快慢指针

11. 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明:你不能倾斜容器。

输入:[1,8,6,2,5,4,8,3,7]
输出:49 
解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。
示例 2:
输入:height = [1,1]
输出:1

提示:

n == height.length

2 <= n <= 105

0 <= height[i] <= 104

class Solution {
public int maxArea(int[] height) {
    int left = 0;
    int right = height.length - 1;
    int maxArea = 0;
    while (left < right) {
        int area = Math.min(height[left], height[right]) * (right - left);
        maxArea = Math.max(maxArea, area);
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return maxArea;
}
}

思路:双指针法:头尾指针,每次短的一端往中间靠近,(因为短的一端到另外一端已经是最大容量)

15. 三数之和

给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意:答案中不可以包含重复的三元组。

示例 1:
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
解释:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-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 。

要解决这个问题,可以使用双指针的方法来找到和为0的三元组。首先,对数组进行排序,然后固定一个数,使用双指针在剩余的区间内查找另外两个数,使得三个数的和为0。

以下是解决该问题的具体步骤:

1、对数组进行排序,以便于后续双指针的操作。

2、遍历排序后的数组,固定第一个数 nums[i]:

  • 若 nums[i] > 0,则说明后面的数都大于0,不可能存在和为0的三元组,直接返回结果。
  • 若 i > 0 且 nums[i] == nums[i-1],则说明当前数与前一个数相同,为了避免重复的三元组,跳过当前数。

3、使用双指针解决剩下的两数之和问题:

  • 初始化左指针 left 为 i+1,右指针 right 为数组末尾索引。
  • 在 left < right 的条件下,执行以下操作:
  • 计算三个数的和 sum = nums[i] + nums[left] + nums[right]。
  • 若 sum == 0,则将三个数加入结果列表中,并移动指针 left 和 right,同时跳过重复的元素。
  • 若 sum > 0,则说明右指针指向的数较大,需要将右指针向左移动。
  • 若 sum < 0,则说明左指针指向的数较小,需要将左指针向右移动。

4、返回结果列表。

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        int n = nums.length;
        Arrays.sort(nums);
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                break;
            }
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = n - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    // 跳过重复的元素
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    left++;
                    right--;
                } else if (sum > 0) {
                    right--;
                } else {
                    left++;
                }
            }
        }
        return result;
    }
}

思路:定一移二

42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出:6
解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 
示例 2:
输入:height = [4,2,0,3,2,5]
输出:9

提示:

n == height.length

1 <= n <= 2 * 104

0 <= height[i] <= 105

public class Solution {
    public int trap(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int maxLeft = 0;
        int maxRight = 0;
        int result = 0;
        while (left <= right) {
            if (height[left] <= height[right]) {
                if (height[left] >= maxLeft) {
                    maxLeft = height[left];
                } else {
                    result += maxLeft - height[left];
                }
                left++;
            } else {
                if (height[right] >= maxRight) {
                    maxRight = height[right];
                } else {
                    result += maxRight - height[right];
                }
                right--;
            }
        }
        return result;
    }
}

相关文章
|
3月前
|
Python
【Leetcode刷题Python】138. 复制带随机指针的链表
LeetCode上题目“138. 复制带随机指针的链表”的Python解决方案,包括两种方法:一种是在每个节点后复制一个新节点然后再分离出来形成新链表;另一种是构建一个字典来跟踪原始节点与其副本之间的映射关系,从而处理新链表的构建。
22 1
|
5月前
|
索引
力扣每日一题 6/17 枚举+双指针
力扣每日一题 6/17 枚举+双指针
33 1
|
5月前
|
存储 算法 数据可视化
【模拟面试问答】深入解析力扣163题:缺失的区间(线性扫描与双指针法详解)
【模拟面试问答】深入解析力扣163题:缺失的区间(线性扫描与双指针法详解)
|
5月前
|
算法 数据挖掘 Java
深入解析力扣167题:两数之和 II(双指针法详解及模拟面试问答)
深入解析力扣167题:两数之和 II(双指针法详解及模拟面试问答)
|
5月前
|
存储 算法 数据挖掘
【模拟面试问答】力扣165题:比较版本号(逐个比较与双指针法详解及模拟面试问答)
【模拟面试问答】力扣165题:比较版本号(逐个比较与双指针法详解及模拟面试问答)
|
5月前
|
存储 算法 数据可视化
深入解析力扣160题:相交链表的解决方法(哈希表法与双指针法详细图解)
深入解析力扣160题:相交链表的解决方法(哈希表法与双指针法详细图解)
|
6月前
|
算法
[优选算法]——双指针——Leetcode——1089. 复写零
[优选算法]——双指针——Leetcode——1089. 复写零
|
5月前
|
算法
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
|
5月前
|
算法 容器
【经典LeetCode算法题目专栏分类】【第1期】左右双指针系列:盛最多水的容器、接雨水、回文子串、三数之和
【经典LeetCode算法题目专栏分类】【第1期】左右双指针系列:盛最多水的容器、接雨水、回文子串、三数之和