oj刷题——双指针篇：双指针的原理和使用场景

2024-09-12 12:35:56 浏览数 (18)

前言：

双指针一般在做与数组有关的题是经常容易用到的，在很多场景下都能得到很好的应用，下面我将通过多个多指针的题（力扣上面的），来总结一下双指针的原理和使用场景 需知：我在讲解一个题时主要分为三步：题意解析、讲解算法原理和编写代码

一. 复写0

1.1 题意解析

力扣1089

给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。

注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。

示例 1：

代码语言：javascript复制
输入：arr = [1,0,2,3,0,4,5,0]
输出：[1,0,0,2,3,0,0,4]
解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]

示例 2：

代码语言：javascript复制
输入：arr = [1,2,3]
输出：[1,2,3]
解释：调用函数后，输入的数组将被修改为：[1,2,3]

提示：

  • 1 <= arr.length <= 104
  • 0 <= arr[i] <= 9

题目的重点就是如何在不改变数组长度的情况下将0复写一遍，并将非0元素右移

1.2 算法原理

编写代码

代码语言：javascript复制
void duplicateZeros(vector<int>& arr) {
    //1.先找到最后一个数
    int cur = 0, dest = -1, n = arr.size();
    while (cur < n){
        if (arr[cur]) dest  ;
        else dest  = 2;
        if (dest >= n - 1) break;
        cur  ;
    }
    //2.处理一下边界问题
    if (dest == n){
        arr[n - 1] = 0;
        cur--;  dest -= 2;
    }
    //3.从后往前完成复写操作
    while (cur >= 0){
        if (arr[cur]){
            arr[dest] = arr[cur];
            dest--;  cur--;
        }
        else{
            arr[dest] = arr[dest - 1] = 0;
            dest -= 2;   cur--;
        }
    }
}

二、快乐数

题意解析

力扣 202

题目描述

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

  • 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
  • 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
  • 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：

代码语言：javascript复制
输入：n = 19
输出：true
解释：
12   92 = 82
82   22 = 68
62   82 = 100
12   02   02 = 1

算法原理

编写代码

代码语言：javascript复制
int bitSum(int x) {
    int sum = 0;
    while (x > 0)
    {
        sum  = (x % 10) * (x % 10);
        x /= 10;
    }
    return sum;
}
bool isHappy(int n) {
    int fast = bitSum(n), slow = n;
    while (slow != fast)
    {
        slow = bitSum(slow);
        fast = bitSum(bitSum(fast));
    }
    return slow == 1;
}

三、盛最多水的容器

题意解析

力扣11

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

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

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

说明：你不能倾斜容器。

示例 1：

代码语言：javascript复制
输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

代码语言：javascript复制
输入：height = [1,1]
输出：1

提示：

  • n == height.length
  • 2 <= n <= 105
  • 0 <= height[i] <= 104

算法原理

代码实现

代码语言：javascript复制
int maxArea(vector<int>& height) {
    int slow = 0, fast = height.size() - 1;
    int ret = 0;
    while (slow < fast)
    {
        int capacity = min(height[slow], height[fast]) * (fast - slow);
        ret = max(ret, capacity);
        if (height[slow] < height[fast])   slow;
        else --fast;
    }
    return ret;
}

四、有效三角形个数

题意解析

力扣611

给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

示例 1:

代码语言：javascript复制
输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是: 
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

示例 2:

代码语言：javascript复制
输入: nums = [4,2,3,4]
输出: 4

提示:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000

算法原理

代码实现

代码语言：javascript复制
int triangleNumber(vector<int>& nums) {
    int ret = 0;
    sort(nums.begin(), nums.end());
    for (int i = nums.size() - 1; i >= 2; i--)
    {
        int left = 0, right = i - 1;
        while (left < right)
        {
            if (nums[left]   nums[right] > nums[i])
            {
                ret  = right - left;
                right--;
            }
            else left  ;
        }
    }
    return ret;
}

五、总结

以上就是双指针在oj刷题中常见的几个题，通过这几个题，我们可以观察到双指针的题在处理数组划分，还有数组操作中经常用到，在我们平时做数组相关的题时要有往双指针这方面想的意识

感谢各位大佬观看，创作不易，还望各位大佬点赞支持！！！

指针 容器 数组 算法 原理

0 人点赞