面试手撕算法高频专题：数组的双指针思想及应用（算法村第三关白银挑战）

所谓的双指针其实就是两个变量，不一定真的是指针。

  1. 快慢指针：一起向前走
  2. 对撞指针、相向指针：从两头向中间走
  3. 背向指针：从中间向两头走

移除值为val的元素

题目描述

27. 移除元素 - 力扣（LeetCode）

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,3,0,4]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示：

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 50
  • 0 <= val <= 100

快慢指针

/**
 * @return 移除后val后数组的新长度
 */
public int removeElement(int[] nums, int val)
{
    int slow = 0;

    for (int fast = 0; fast < nums.length; fast++)
    {
        //nums[fast] == val时slow等待，直到下一个nums[fast]（!= val），然后将nums[slow]覆盖
        if (nums[fast] != val)
        {
            nums[slow] = nums[fast];
            slow++; //slow移动到下一个待写位置
        }
    }

    return slow;
}

在这里插入图片描述

上图的val=2

对撞指针+交换

/**
 * 核心思想：从右侧找到不是val的值来顶替左侧是val的值
 */
public int removeElement(int[] nums, int val)
{
    int left = 0;
    int right = nums.length - 1;

    while (left <= right)
    {
        if(nums[left] == val && nums[right] != val)
        {
            int temp = nums[left];
            nums[left] = nums[right];   //覆盖删除
            nums[right] = temp; //交换的目的是让right指针能够移动
        }

        //更新指针
        if (nums[left] != val)
            left++;
        if (nums[right] == val)
            right--;
    }

    return left;
}

在这里插入图片描述

对撞指针+覆盖

public int removeElement(int[] nums, int val)
{
    int left = 0;
    int right = nums.length - 1;

    while (left <= right)
    {
        if (nums[left] == val)
        {
            nums[left] = nums[right];
            right--;
        }
        else
            left++;
    }

    return right + 1;
}

在这里插入图片描述

删除有序数组中的重复项

题目描述

26. 删除有序数组中的重复项 - 力扣（LeetCode）

给你一个 非严格递增排列 的数组 nums ，请你** 原地** 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

  • 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
  • 返回 k 。

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示：

  • 1 <= nums.length <= 3 * 104
  • -104 <= nums[i] <= 104
  • nums 已按 非严格递增 排列

快慢指针

public int removeDuplicates(int[] nums)
{
    int slow = 0;

    for(int fast = 0; fast < nums.length; fast++)
    {
        //fast往下走，直到指向第一个与slow不同的元素
        if(nums[fast] != nums[slow])
        {
            slow++; //slow后移一位，存储新的不重复元素
            nums[slow] = nums[fast];
        }
    }

    return slow + 1;    //返回nums中唯一元素的个数。
}

在这里插入图片描述

进阶：重复元素保留k个

  • 前 k 位直接保留
  • **fast 不断向后遍历， nums[fast] 能够保留的前提是与nums[slow]**的前面第 k 个元素不同
  • 保留后 slow 指向新的写入位置
public int removeDuplicates(int[] nums)
{
    int slow = 0;
    int k = 2;  //重复元素保留k个

    for(int fast = 0; fast < nums.length; fast++)
    {
        if(slow < k  || nums[slow - k] != nums[fast])
        {
            nums[slow] = nums[fast];
            slow++;
        }
    }

    return slow;    //返回nums中唯一元素的个数。
}

按奇偶排序数组

题目描述

905. 按奇偶排序数组 - 力扣（LeetCode）

给你一个整数数组 nums，将 nums 中的的所有偶数元素移动到数组的前面，后跟所有奇数元素。

返回满足此条件的 任一数组 作为答案。

示例 1：

输入：nums = [3,1,2,4]
输出：[2,4,3,1]
解释：[4,2,3,1]、[2,4,1,3] 和 [4,2,1,3] 也会被视作正确答案。

示例 2：

输入：nums = [0]
输出：[0]

对撞指针+交换

public int[] sortArrayByParity(int[] nums)
{
    int left = 0;
    int right = nums.length - 1;

    while (left < right)
    {
        //左奇右偶时两边交换，把奇数调到后面，偶数调到前面
        if(nums[left] % 2 == 1  && nums[right] % 2 == 0)
        {
            int t = nums[left];
            nums[left] = nums[right];
            nums[right] = t;
        }

        if(nums[left] % 2 == 0) left++; //跳过左边的偶数
        if(nums[right] % 2 == 1) right--; //跳过右边的奇数
    }

    return nums;
}

数组轮转

题目描述

189. 轮转数组 - 力扣（LeetCode）

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

提示：

  • 1 <= nums.length <= 105
  • -231 <= nums[i] <= 231 - 1
  • 0 <= k <= 105

进阶：

  • 尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
  • 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

三次翻转

public void rotate(int[] nums, int k)
{
    //举例nums:[1,2,3,4,5,6,7]
    k = k % nums.length;
	
    reverse(nums,0, nums.length - 1);	//nums:[7,6,5,4,3,2,1]
    reverse(nums,0,k-1);	//nums:[5,6,7,4,3,2,1]
    reverse(nums,k, nums.length - 1);	//nums:[5,6,7,1,2,3,4]
}

//反转指定区间
public void reverse(int[] nums, int left, int right)
{
    while (left < right)
    {
        int t = nums[left];
        nums[left] = nums[right];
        nums[right] = t;

        left++;
        right--;
    }
}

数组的区间专题

汇总区间

题目描述

228. 汇总区间 - 力扣（LeetCode）

给定一个 无重复元素 的 有序 整数数组 nums 。

返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表* 。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。

列表中的每个区间范围 [a,b] 应该按如下格式输出：

  • "a->b" ，如果 a != b
  • "a" ，如果 a == b

示例 1：

输入：nums = [0,1,2,4,5,7]
输出：["0->2","4->5","7"]
解释：区间范围是：
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"

示例 2：

输入：nums = [0,2,3,4,6,8,9]
输出：["0","2->4","6","8->9"]
解释：区间范围是：
[0,0] --> "0"
[2,4] --> "2->4"
[6,6] --> "6"
[8,9] --> "8->9"

提示：

  • 0 <= nums.length <= 20
  • -231 <= nums[i] <= 231 - 1
  • nums 中的所有值都 互不相同
  • nums 按升序排列
解
  1. slow 指向每个区间的起始位置， fast 从 slow 位置开始向后遍历，直到不满足连续递增或 fast 达到数组边界。当前区间结束
  2. 将 slow 指向更新为 fast + 1，作为下一个区间的开始位置，fast继续向后遍历找下一个区间的结束位置，如此循环，直到 nums 遍历完毕

append(char c)：将指定的字符添加到当前StringBuilder对象的末尾。如果参数是数字，则自动转为字符

public List<String> summaryRanges(int[] nums)
{
    ArrayList<String> ans = new ArrayList<>();

    int slow = 0;
    int fast = 0;

    for (; fast < nums.length; fast++)
    {
        if(fast == nums.length - 1 || nums[fast]+1 != nums[fast + 1])
        {
            StringBuilder sb = new StringBuilder();
            sb.append(nums[slow]);

            if(nums[slow] != nums[fast])
                sb.append("->").append(nums[fast]);

            ans.add(sb.toString());

            slow = fast + 1;
        }
    }

    return ans;
}

缺失的区间

题目描述

163. 缺失的区间 - 力扣（LeetCode）

给你一个闭区间 [lower, upper] 和一个 按从小到大排序 的整数数组 nums ，其中元素的范围在闭区间 [lower, upper] 当中。

如果一个数字 x 在 [lower, upper] 区间内，并且 x 不在 nums 中，则认为 x 缺失。

返回 准确涵盖所有缺失数字 的 最小排序 区间列表。也就是说，nums 的任何元素都不在任何区间内，并且每个缺失的数字都在其中一个区间内。

示例 1：

输入: nums = [0, 1, 3, 50, 75], lower = 0 , upper = 99
输出: [[2,2],[4,49],[51,74],[76,99]]
解释：返回的区间是：
[2,2]
[4,49]
[51,74]
[76,99]

示例 2：

输入： nums = [-1], lower = -1, upper = -1
输出： []
解释： 没有缺失的区间，因为没有缺失的数字。

提示：

  • -109 <= lower <= upper <= 109
  • 0 <= nums.length <= 100
  • lower <= nums[i] <= upper
  • nums 中的所有值 互不相同
解
public List<List<Integer>> findMissingRanges(int[] nums, int lower, int upper)
{
    List<List<Integer>> missingRanges = new ArrayList<>();

    //[lower, upper]缺失
    if (nums.length == 0)
    {
        missingRanges.add(generateRange(lower, upper));
        return missingRanges;
    }

    //[lower, nums[0] - 1]缺失
    if (nums[0] > lower)
    {
        missingRanges.add(generateRange(lower, nums[0] - 1));
    }

    //i = 0起，[nums[i] + 1, nums[i + 1] - 1]缺失
    for (int i = 0; i < nums.length - 1; i++)
    {
        if(nums[i + 1] - nums[i] > 1)	//非连续递增
        {
            missingRanges.add(generateRange(nums[i] + 1, nums[i + 1] - 1));
        }
    }

    //[nums[length - 1] + 1, upper]缺失
    if (nums[nums.length - 1] < upper)
    {
        missingRanges.add(generateRange(nums[nums.length - 1] + 1, upper));
    }

    return missingRanges;	//返回所有缺失区间
}

//生成区间
public List<Integer> generateRange(int start, int end)
{
    ArrayList<Integer> range = new ArrayList<>();
    range.add(start);
    range.add(end);

    return range;
}

字符串替换空格

题目描述

（剑指offer）请实现一个函数，将一个字符串中的每个空格替换成**“%20”。例如，“We Are Happy.”** 经过替换之后为**“We%20Are%20Happy.”**

解

public class replaceSpaces
{
    public static void main(String[] args)
    {
        String str1 = replaceSpace_immutable("We Are Happy.");
        System.out.println(str1);    //We%20Are%20Happy.(正确)

        StringBuffer sb = new StringBuffer("We Are Happy.");
        String str2 = replaceSpace_variable(sb);
        System.out.println(str2);   //We%20Are%20Happy.(正确)

    }

    //存储字符串的空间不可变，或者存储空间不算大
    public static String replaceSpace_immutable(String str)
    {
        String res = "";

        for (int i = 0; i < str.length(); i++)
        {
            char c = str.charAt(i);

            if (c == ' ')
                res = res + "%20";
            else
                res = "%s%s".formatted(res, c); //效果相同
        }

        return res;
    }

    //存储字符串的空间可变，或者存储空间很大
    public static String replaceSpace_variable(StringBuffer str)
    {
        int blank = 0;  //str中的空格数
        //计算空格数
        for (int i = 0; i < str.length(); i++)
            if (str.charAt(i) == ' ')
                blank++;

        int fast = str.length() - 1;    //fast指向原长度的末尾

        //设置新的长度(StringBuffer才有的方法，String没有)
        str.setLength(str.length() + 2 * blank);

        int slow = str.length() - 1;    //slow指向新长度的末尾

        while (fast >=0 && fast < slow)
        {
            char c = str.charAt(fast);

            if (c == ' ')
            {
                str.setCharAt(slow,'0');	//复制
                slow--;
                str.setCharAt(slow,'2');
                slow--;
                str.setCharAt(slow,'%');
            }
            else
                str.setCharAt(slow, c);

            fast--;
            slow--;
        }

        return str.toString();
    }
}

replaceSpace_variable图解

在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/283512.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【C#】知识点实践序列之Lock的输出多线程信息

【C#】知识点实践序列之Lock的输出多线程信息

大家好&#xff0c;我是全栈小5&#xff0c;欢迎来到《小5讲堂之知识点实践序列》文章。 2023年第2篇文章&#xff0c;此篇文章是C#知识点实践序列之Lock知识点&#xff0c;博主能力有限&#xff0c;理解水平有限&#xff0c;若有不对之处望指正&#xff01; 本篇在Lock锁定代码…
阅读更多...
开关电源反馈环路重要参数设计，PC817和TL431实例计算和取值详解

开关电源反馈环路重要参数设计，PC817和TL431实例计算和取值详解

author&#xff1a;小高霸气 data:2021.04.16 下面介绍开关电源重要的反馈电路PC817和TL431设计和应用。 在开关电源当中&#xff0c;对稳压反馈电路的设计通常会使用TL431和PC817来配合使用。在TOP 及3842等单端反激电路中的反馈电路很多都采用TL431和PC817作为参考、隔离、取…
阅读更多...
Vue中目录以及文件内容简单分析

Vue中目录以及文件内容简单分析

src文件下目录分析&#xff1a; App.vue文件中内容&#xff1a; vue文件中基本的三个结构&#xff0c;template&#xff08;结构&#xff09;、script&#xff08;行为&#xff09; 、style&#xff08;样式&#xff09;。 <template><!-- html结构 --><div cl…
阅读更多...
记一次Oracle Cloud计算实例ssh恢复过程

记一次Oracle Cloud计算实例ssh恢复过程

#ssh秘钥丢失# &#xff0c; #Oracle Cloud# 。 电脑上的ssh秘钥文件不知道什么时候丢失了&#xff0c;直到用的时候才发现没有了&#xff0c;这下可好&#xff0c;Oracle Cloud的计算实例连不上了&#xff0c;这个实例只能通过ssh连接上去&#xff1a; 以下是解决步骤&#x…
阅读更多...
Linux常用命令大全总结及讲解（超详细版）

Linux常用命令大全总结及讲解（超详细版）

前言&#xff1a; Linux 是一个基于Linux 内核的开源类Unix 操作系统&#xff0c;Linus Torvalds于 1991 年 9 月 17 日首次发布的操作系统内核。Linux 通常打包为Linux 发行版。 Linux 最初是为基于Intel x86架构的个人计算机开发的&#xff0c;但此后被移植到的平台比任何其…
阅读更多...
Ubuntu系统上TensorBoard使用方式

Ubuntu系统上TensorBoard使用方式

Ubuntu系统上TensorBoard使用方式 Tensorboard 启动TensorBoard 后台开启TensorBoard访问权限 执行命令&#xff1a;nohup tensorboard --logdirlogs/ >>tensorboard.log & 查看访问链接和登录token 执行命令&#xff1a;cat tensorboard.log&#xff0c;打开ten…
阅读更多...
typore自定义删除线快捷键

typore自定义删除线快捷键

打开高级设置 设置快捷键 重新打开typore
阅读更多...
在高并发场景下，缓存“雪崩”了怎么办

在高并发场景下，缓存“雪崩”了怎么办

1. 缓存雪崩的常见原因 缓存“雪崩”是指&#xff0c;因为部分缓存节点不可用&#xff0c;而导致整个缓存系统&#xff08;甚至是整个服务系统&#xff09;不可用。缓存“雪崩”主要分为以下两种情况&#xff1a; 因缓存不支持 rehash 而导致的缓存“雪崩”缓存支持 rehash 时…
阅读更多...
【Java】ThreadLocal原理与使用场景

【Java】ThreadLocal原理与使用场景

ThreadLocal原理&#xff1a; 字段&#xff1a; //ThreadLocal对象的哈希码 private final int threadLocalHashCode nextHashCode();//生成ThreadLocal对象的哈希码时&#xff0c;需要用到该对象&#xff0c;从0开始 private static AtomicInteger nextHashCode new Atomic…
阅读更多...
使用docker build构建image

使用docker build构建image

文章目录 环境步骤准备例1&#xff1a;基本用法例2&#xff1a;缓存layer例3&#xff1a;Multi-stage例4&#xff1a;Mountcache mountbind mount 例5&#xff1a;参数例6&#xff1a;Export文件例7&#xff1a;测试 参考 环境 RHEL 9.3Docker Community 24.0.7 步骤 在Dock…
阅读更多...
Pix2Pix如何工作？

Pix2Pix如何工作？

一、说明 在本指南中&#xff0c;我们将重点介绍 Pix2Pix [1]&#xff0c;它是用于配对图像翻译的著名且成功的深度学习模型之一。在地理空间科学中&#xff0c;这种方法可以帮助传统上不可能的广泛应用&#xff0c;在这些应用中&#xff0c;我们可能希望从一个图像域转到另一个…
阅读更多...
认识Linux基本指令之 “touch mkdir rm”

认识Linux基本指令之 “touch mkdir rm”

01.touch指令 语法:touch [选项]... 文件... 功能&#xff1a;touch命令参数可更改文档或目录的日期时间&#xff0c;包括存取时间和更改时间&#xff0c;或者新建一个不存在的文件 常用选项&#xff1a; -a 或--timeatime或--timeaccess或--timeuse只更改存取时间。 -c…
阅读更多...
JAVA：利用JUnit进行高效的单元测试

JAVA：利用JUnit进行高效的单元测试

1、简述 在软件开发中&#xff0c;单元测试是确保代码质量和可维护性的关键步骤。JUnit作为Java领域最流行的单元测试框架之一&#xff0c;提供了简单而强大的测试工具&#xff0c;可以帮助开发者在项目开发过程中及时发现和修复代码中的问题。本文将介绍JUnit的基本用法以及一…
阅读更多...
3D视觉-3D测量技术对比

3D视觉-3D测量技术对比

从前面四种主流的 3D 测量技术来看&#xff0c;其优点和缺点都很明显&#xff0c;没有单独一种技术可以适用于所有的三维测量场景&#xff0c;从实际应用来看&#xff0c;双目与结构光在人脸识别&#xff0c;拆码垛定位&#xff0c;静态尺寸测量等应用上最为广泛。激光三角法因…
阅读更多...
【CISSP学习笔记】6. 安全开发

【CISSP学习笔记】6. 安全开发

该知识领域涉及如下考点&#xff0c;具体内容分布于如下各个子章节&#xff1a; 理解安全并将其融入软件开发生命周期 (SDLC) 中在软件开发环境中识别和应用安全控制评估软件安全的有效性评估获得软件对安全的影响定义并应用安全编码准则和标准 6.1. 系统开发控制 6.1.1. 软…
阅读更多...
数据转换的三剑客：Pandas 中 apply、map 和 applymap 方法的应用指南

数据转换的三剑客：Pandas 中 apply、map 和 applymap 方法的应用指南

数据转换的三剑客&#xff1a;Pandas 中 apply、map 和 applymap 方法的应用指南 ​ 在 Pandas 中&#xff0c;apply、map 和 applymap 是常用的数据转换和处理方法&#xff0c;它们为数据分析和数据处理提供了灵活的功能。这些方法可以根据具体的需求选择合适的方法进行操作。…
阅读更多...
如何使用ModuleShifting测试Module Stomping和Module Overloading注入技术

如何使用ModuleShifting测试Module Stomping和Module Overloading注入技术

关于ModuleShifting ModuleShifting是一款针对Module Stomping和Module Overloading注入技术的安全测试工具&#xff0c;该工具基于Python ctypes实现其功能&#xff0c;因此可以通过Python解释器或Pyramid在内存中完整执行&#xff0c;这样就可以避免使用编译加载器了。 需要…
阅读更多...
普中STM32-PZ6806L开发板(HAL库函数实现-按键扫描)

普中STM32-PZ6806L开发板(HAL库函数实现-按键扫描)

简介 实现按键扫描, 实现四个按键按下控制灯的亮灭 电路原理图 按键电路原理图 按键与主芯片引脚原理图 其他知识 原理图分析 Key_UP按下会有高电平输入, 所以电路设置应该是默认低电平, 初始化为下拉输入 Key_Left/Right/Down按下会有低电平&#xff0c; 初始化为下拉输…
阅读更多...
鸿蒙开发 - 认证账号

鸿蒙开发 - 认证账号

注册成功后&#xff0c;进行账号认证 认证成功后就可以进行开发了
阅读更多...
2023年“中银杯”四川省职业院校技能大赛“云计算应用”赛项样题卷②

2023年“中银杯”四川省职业院校技能大赛“云计算应用”赛项样题卷②

2023年“中银杯”四川省职业院校技能大赛“云计算应用”赛项&#xff08;高职组&#xff09; 样题&#xff08;第2套&#xff09; 目录 2023年“中银杯”四川省职业院校技能大赛“云计算应用”赛项&#xff08;高职组&#xff09; 样题&#xff08;第2套&#xff09; 模块…
阅读更多...
最新文章

Copyright @ 2022~2023