十五周算法訓(xùn)練營(yíng)——快慢指針
今天是十五周算法訓(xùn)練營(yíng)的第八周，主要講快慢指針專題。
移除元素
給你一個(gè)數(shù)組 nums 和一個(gè)值 val，你需要 原地 移除所有數(shù)值等于 val 的元素，并返回移除后數(shù)組的新長(zhǎng)度。
不要使用額外的數(shù)組空間，你必須僅使用 O(1) 額外空間并 原地 修改輸入數(shù)組。
元素的順序可以改變。你不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素。
輸入：nums = [3,2,2,3], val = 3 輸出：2, nums = [2,2] 解釋：函數(shù)應(yīng)該返回新的長(zhǎng)度 2, 并且 nums 中的前兩個(gè)元素均為 2。你不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素。例如，函數(shù)返回的新長(zhǎng)度為 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也會(huì)被視作正確答案。
利用快慢指針解決，如果fast遇到val就跳過(guò)，否則就賦值給slow指針，并讓slow指針前進(jìn)一步。
// 利用快慢指針解決，如果fast遇到val就跳過(guò)，否則就賦值給slow指針，并讓slow指針前進(jìn)一步
function removeElement(nums, val) {
let slow = 0;
let fast = 0;
while (fast < nums.length) {
// 當(dāng)快指針等于對(duì)應(yīng)值時(shí)，則跳過(guò)
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
// 快指針每次都前進(jìn)一步
fast++;
}
return slow;
}
const nums = [3, 2, 2, 3];
console.log(removeElement(nums, 3));移動(dòng)零
給定一個(gè)數(shù)組 nums，編寫一個(gè)函數(shù)將所有 0 移動(dòng)到數(shù)組的末尾，同時(shí)保持非零元素的相對(duì)順序。
「請(qǐng)注意」 ，必須在不復(fù)制數(shù)組的情況下原地對(duì)數(shù)組進(jìn)行操作。
「示例 1:」
輸入: nums = [0,1,0,3,12]
輸出: [1,3,12,0,0]用快慢指針解決，首先去除所有零點(diǎn)，然后慢指針后面的賦值為0
function moveZeroes(nums) {
// 1. 首先去除所有的零點(diǎn)
// 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ù)組中的重復(fù)項(xiàng)
給你一個(gè) 升序排列 的數(shù)組 nums ，請(qǐng)你 原地 刪除重復(fù)出現(xiàn)的元素，使每個(gè)元素 只出現(xiàn)一次 ，返回刪除后數(shù)組的新長(zhǎng)度。元素的 相對(duì)順序 應(yīng)該保持 一致 。
由于在某些語(yǔ)言中不能改變數(shù)組的長(zhǎng)度，所以必須將結(jié)果放在數(shù)組nums的第一部分。更規(guī)范地說(shuō)，如果在刪除重復(fù)項(xiàng)之后有 k 個(gè)元素，那么 nums 的前 k 個(gè)元素應(yīng)該保存最終結(jié)果。
將最終結(jié)果插入 nums 的前 k 個(gè)位置后返回 k 。
不要使用額外的空間，你必須在 原地 修改輸入數(shù)組 并在使用 O(1) 額外空間的條件下完成。
示例 1：
輸入：nums = [1,1,2] 輸出：2, nums = [1,2,_] 解釋：函數(shù)應(yīng)該返回新的長(zhǎng)度 2 ，并且原數(shù)組 nums 的前兩個(gè)元素被修改為 1, 2 。不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素。
利用快慢指針實(shí)現(xiàn)，當(dāng)快慢指針不相等時(shí)，就證明找到了一個(gè)新的元素，此時(shí)將慢指針移動(dòng)一下，將新值賦值給慢指針。
// 利用快慢指針實(shí)現(xiàn)，當(dāng)快慢指針不相等時(shí)，就證明找到了一個(gè)新的元素，此時(shí)將慢指針移動(dòng)一下，將新值賦值給慢指針
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));鏈表的中間結(jié)點(diǎn)
給定一個(gè)頭結(jié)點(diǎn)為 head 的非空單鏈表，返回鏈表的中間結(jié)點(diǎn)。
如果有兩個(gè)中間結(jié)點(diǎn)，則返回第二個(gè)中間結(jié)點(diǎn)。
示例 1：
輸入：[1,2,3,4,5] 輸出：此列表中的結(jié)點(diǎn) 3 (序列化形式：[3,4,5]) 返回的結(jié)點(diǎn)值為 3 。 (測(cè)評(píng)系統(tǒng)對(duì)該結(jié)點(diǎn)序列化表述是 [3,4,5])。 注意，我們返回了一個(gè) ListNode 類型的對(duì)象 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;
}
// 利用快慢指針解決
// 注意鏈表長(zhǎng)度奇偶的問(wèn)題，奇數(shù)返回的就是中間那個(gè)，偶數(shù)返回的則是兩個(gè)中間點(diǎn)中的后一個(gè)
function middleNode(head) {
// 快慢指針初始化
let slow = head;
let fast = head;
// 快指針走到末尾時(shí)停止
while (fast !== null && fast.next !== null) {
// 快指針走兩步、慢指針走一步
fast = fast.next.next;
slow = slow.next;
}
// 慢指針指向中點(diǎn)
return slow;
}刪除鏈表中的倒數(shù)第n個(gè)節(jié)點(diǎn)
給你一個(gè)鏈表，刪除鏈表的倒數(shù)第 n 個(gè)結(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎ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)建一個(gè)空節(jié)點(diǎn)，方便刪除第一個(gè)節(jié)點(diǎn)的情況
const dummy = new ListNode(null, head);
let p1 = dummy;
let p2 = dummy;
// 因?yàn)橐獎(jiǎng)h除倒數(shù)第n個(gè)節(jié)點(diǎn)，則p1則必須先走n + 1步，否則找到的則是倒數(shù)第n個(gè)，不能進(jìn)行刪除
for (let i = 0; i < n + 1; i++) {
p1 = p1.next;
}
// p1和p2一起往后走,知道p1走到終點(diǎn)，這樣p2就是要?jiǎng)h除的點(diǎn)
while (p1 != null) {
p1 = p1.next;
p2 = p2.next;
}
// 刪除倒數(shù)第n個(gè)節(jié)點(diǎ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的兩個(gè)數(shù)字
輸入一個(gè)遞增排序的數(shù)組和一個(gè)數(shù)字s，在數(shù)組中查找兩個(gè)數(shù)，使得它們的和正好是s。如果有多對(duì)數(shù)字的和等于s，則輸出任意一對(duì)即可。
「示例 1：」
輸入：nums = [2,7,11,15], target = 9
輸出：[2,7] 或者 [7,2]// 通過(guò)雙指針解決
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 [];
}
