算法面试题---利用双指针移除元素
2021/4/19 12:25:15
本文主要是介绍算法面试题---利用双指针移除元素,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
前言
当我们遇到移除元素的题目时,通常可以考虑使用双指针的方式来解,下面从leetcode上面总结了几道相关的题目,都是基础入门级别的,非常适合用来入门双指针相关操作的题目。
1、移除元素
给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。
不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
解题思路
定义快慢指针,快指针遇到目标值,就跳过继续往下找,而慢指针始终指向待替换的位置。
public int removeElement(int[] nums, int val) { int len = nums.length; if (len == 0) { return 0; } int slow = 0; int fast = 0; while (fast < len) { if (nums[fast] != val) { nums[slow] = nums[fast]; slow++; } fast++; } return slow; }
2、删除有序数组中的重复项
给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。
不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
解题思路
和上一题思路差不多,定义快慢指针,慢指针始终指向待替换值的下标,快指针每次和慢指针的前一个下标进行比较,如果相等则跳过,否则快指针用当前值替换慢指针指向的当前值。
public int removeDuplicates(int[] nums) { int len = nums.length; if (len == 0) { return 0; } int slow = 1; int fast = 1; while (fast < len) { if (nums[slow - 1] != nums[fast]) { nums[slow] = nums[fast]; slow++; } fast++; } return slow; }
3、移动零
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
解题思路
还是通过快慢指针的套路,最后处理一下慢指针之后的数全为0即可。
public void moveZeroes(int[] nums) { int len = nums.length; if (len < 2) { return; } int slow = 0; int fast = 0; while (fast < len) { if (nums[fast] != 0) { nums[slow] = nums[fast]; slow++; } fast++; } while (slow < len) { nums[slow] = 0; slow++; } }
4、移除链表元素
给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。
解题思路
这是一道操作链表的题目,同样可以利用双指针的思路,先从头部节点开始找,找到值不为value的节点,跳出循环,之后的过程就还是定义两个指针,cur就相当于慢指针,next就相当于快指针,如果快指针指向的节点就是要删除的,则先跳过,否则让cur来到next位置。
public ListNode removeElements(ListNode head, int val) { while (head != null) { if (head.val != val) { break; } head = head.next; } ListNode cur = head; while (cur != null) { ListNode next = cur.next; if (next != null && next.val == val) { cur.next = next.next; } else { cur = next; } } return head; }
这篇关于算法面试题---利用双指针移除元素的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01为什么公共事业机构会偏爱 TiDB :TiDB 数据库在某省妇幼健康管理系统的应用
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署