今天是十五周算法训练营的第八周,主要讲快慢指针专题。周算指针
给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的练营元素,并返回移除后数组的快慢新长度。
不要使用额外的周算指针数组空间,你必须仅使用 O(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],也会被视作正确答案。
利用快慢指针解决,如果fast遇到val就跳过,否则就赋值给slow指针,并让slow指针前进一步。
// 利用快慢指针解决,如果fast遇到val就跳过,否则就赋值给slow指针,并让slow指针前进一步function removeElement(nums, val) { let slow = 0; let fast = 0; while (fast < nums.length) { // 当快指针等于对应值时,则跳过 if (nums[fast] != val) { nums[slow] = nums[fast]; slow++; } // 快指针每次都前进一步 fast++; } return slow;}const nums = [3, 2, 2, 3];console.log(removeElement(nums, 3));
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
「请注意」 ,必须在不复制数组的情况下原地对数组进行操作。
「示例 1:」
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]用快慢指针解决,首先去除所有零点,然后慢指针后面的赋值为0
function moveZeroes(nums) { // 1. 首先去除所有的零点 // 2. 将去除元素后,慢指针后面的赋值为0 let slow = 0; let fast = 0; while (fast < nums.length) { if (nums[fast] !== 0) { nums[slow] = nums[fast]; slow++; } fast++; } for (let i = slow; i < nums.length; i++) { nums[i] = 0; } return nums;}const nums = [0,1,0,3,12];console.log(moveZeroes(nums));
给你一个 升序排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
由于在某些语言中不能改变数组的长度,所以必须将结果放在数组nums的第一部分。更规范地说,如果在删除重复项之后有 k 个元素,那么 nums 的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 1:
输入:nums = [1,1,2] 输出:2, nums = [1,2,_] 解释:函数应该返回新的长度 2 ,并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
利用快慢指针实现,当快慢指针不相等时,就证明找到了一个新的元素,此时将慢指针移动一下,将新值赋值给慢指针。
// 利用快慢指针实现,当快慢指针不相等时,就证明找到了一个新的元素,此时将慢指针移动一下,将新值赋值给慢指针function removeDuplicates(nums) { let slow = 0; let fast = 0; while (fast < nums.length) { if (nums[slow] !== nums[fast]) { slow++; nums[slow] = nums[fast]; } fast++; } return slow + 1;}const nums = [1,1,2];console.log(removeDuplicates(nums));
给定一个头结点为 head 的非空单链表,返回链表的中间结点。
如果有两个中间结点,则返回第二个中间结点。
示例 1:
输入:[1,2,3,4,5] 输出:此列表中的结点 3 (序列化形式:[3,4,5]) 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。 注意,我们返回了一个 ListNode 类型的对象 ans,这样: ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
function listNode(val, next) { this.val = val; this.next = next === undefined ? null : next;}// 利用快慢指针解决// 注意链表长度奇偶的问题,奇数返回的就是中间那个,偶数返回的则是两个中间点中的后一个function middleNode(head) { // 快慢指针初始化 let slow = head; let fast = head; // 快指针走到末尾时停止 while (fast !== null && fast.next !== null) { // 快指针走两步、慢指针走一步 fast = fast.next.next; slow = slow.next; } // 慢指针指向中点 return slow;}
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
示例 1:
输入:head = [1,2,3,4,5], n = 2 输出:[1,2,3,5]
function ListNode(val, next) { this.val = val; this.next = next === undefined ? null : next;}function removeNthFromEnd(head, n) { // 创建一个空节点,方便删除第一个节点的情况 const dummy = new ListNode(null, head); let p1 = dummy; let p2 = dummy; // 因为要删除倒数第n个节点,则p1则必须先走n + 1步,否则找到的则是倒数第n个,不能进行删除 for (let i = 0; i < n + 1; i++) { p1 = p1.next; } // p1和p2一起往后走,知道p1走到终点,这样p2就是要删除的点 while (p1 != null) { p1 = p1.next; p2 = p2.next; } // 删除倒数第n个节点 p2.next = p2.next.next; return dummy.next;}const listNode = new ListNode(1, null);listNode.next = new ListNode(2, null);listNode.next.next = new ListNode(3, null);listNode.next.next.next = new ListNode(4, null);listNode.next.next.next.next = new ListNode(5, null);console.log(JSON.stringify(removeNthFromEnd(listNode, 2)));
输入一个递增排序的数组和一个数字s,在数组中查找两个数,使得它们的和正好是s。如果有多对数字的和等于s,则输出任意一对即可。
输入:nums = [2,7,11,15], target = 9输出:[2,7] 或者 [7,2]
// 通过双指针解决function twoSum(nums, target) { let left = 0; let right = nums.length - 1; while (left < right) { const sum = nums[left] + nums[right]; if (sum === target) { return [nums[left], nums[right]]; } else if (sum > target) { right--; } else { left++; } } return [];}
责任编辑:姜华 来源: 前端点线面 Nums快慢指针(责任编辑:娱乐)
南京银行(601009.SH)拟发行不超400亿元金融债券 一次或分次申报
iPhone8的全新功能:可以甩三星Galaxy S8几条街
中欧班列(西安)2021年累计运输车数突破3万车 同比增长24.36%