十五周算法訓練營——快慢指針
今天是十五周算法訓練營的第八周，主要講快慢指針專題。
移除元素
給你一個數(shù)組 nums 和一個值 val，你需要 原地 移除所有數(shù)值等于 val 的元素，并返回移除后數(shù)組的新長度。
不要使用額外的數(shù)組空間，你必須僅使用 O(1) 額外空間并 原地 修改輸入數(shù)組。
元素的順序可以改變。你不需要考慮數(shù)組中超出新長度后面的元素。
輸入：nums = [3,2,2,3], val = 3 輸出：2, nums = [2,2] 解釋：函數(shù)應該返回新的長度 2, 并且 nums 中的前兩個元素均為 2。你不需要考慮數(shù)組中超出新長度后面的元素。例如，函數(shù)返回的新長度為 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));移動零
給定一個數(shù)組 nums，編寫一個函數(shù)將所有 0 移動到數(shù)組的末尾，同時保持非零元素的相對順序。
「請注意」 ，必須在不復制數(shù)組的情況下原地對數(shù)組進行操作。
「示例 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));刪除數(shù)組中的重復項
給你一個 升序排列 的數(shù)組 nums ，請你 原地 刪除重復出現(xiàn)的元素，使每個元素 只出現(xiàn)一次 ，返回刪除后數(shù)組的新長度。元素的 相對順序 應該保持 一致 。
由于在某些語言中不能改變數(shù)組的長度，所以必須將結果放在數(shù)組nums的第一部分。更規(guī)范地說，如果在刪除重復項之后有 k 個元素，那么 nums 的前 k 個元素應該保存最終結果。
將最終結果插入 nums 的前 k 個位置后返回 k 。
不要使用額外的空間，你必須在 原地 修改輸入數(shù)組 并在使用 O(1) 額外空間的條件下完成。
示例 1：
輸入：nums = [1,1,2] 輸出：2, nums = [1,2,_] 解釋：函數(shù)應該返回新的長度 2 ，并且原數(shù)組 nums 的前兩個元素被修改為 1, 2 。不需要考慮數(shù)組中超出新長度后面的元素。
利用快慢指針實現(xiàn)，當快慢指針不相等時，就證明找到了一個新的元素，此時將慢指針移動一下，將新值賦值給慢指針。
// 利用快慢指針實現(xiàn)，當快慢指針不相等時，就證明找到了一個新的元素，此時將慢指針移動一下，將新值賦值給慢指針
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 。 (測評系統(tǒng)對該結點序列化表述是 [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;
}
// 利用快慢指針解決
// 注意鏈表長度奇偶的問題，奇數(shù)返回的就是中間那個，偶數(shù)返回的則是兩個中間點中的后一個
function middleNode(head) {
// 快慢指針初始化
let slow = head;
let fast = head;
// 快指針走到末尾時停止
while (fast !== null && fast.next !== null) {
// 快指針走兩步、慢指針走一步
fast = fast.next.next;
slow = slow.next;
}
// 慢指針指向中點
return slow;
}刪除鏈表中的倒數(shù)第n個節(jié)點
給你一個鏈表，刪除鏈表的倒數(shù)第 n 個結點，并且返回鏈表的頭結點。
示例 1：
輸入：head = [1,2,3,4,5], n = 2 輸出：[1,2,3,5]
- 用雙指針p1、p2,然后p1先走n+1步
function ListNode(val, next) {
this.val = val;
this.next = next === undefined ? null : next;
}
function removeNthFromEnd(head, n) {
// 創(chuàng)建一個空節(jié)點，方便刪除第一個節(jié)點的情況
const dummy = new ListNode(null, head);
let p1 = dummy;
let p2 = dummy;
// 因為要刪除倒數(shù)第n個節(jié)點，則p1則必須先走n + 1步，否則找到的則是倒數(shù)第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;
}
// 刪除倒數(shù)第n個節(jié)點
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的兩個數(shù)字
輸入一個遞增排序的數(shù)組和一個數(shù)字s，在數(shù)組中查找兩個數(shù)，使得它們的和正好是s。如果有多對數(shù)字的和等于s，則輸出任意一對即可。
「示例 1：」
輸入：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 [];
}
