Javascript算法——双指针法移除元素、数组去重、比较含退格字符、有序数组平方
数组移除元素（保证数组仍连续）
暴力求解法（两层for循环）,length单词拼写错误❌二次嵌套for的length设置
/**
* @param {number[]} nums
* @param {number} val
* @return {number}
*/
var removeElement = function(nums, val) {
let length=nums.length;
for(i=0;i<length;i++){
const currVal=nums[i];
if(currVal===val){
for(k=i;k<length-1;k++){
nums[k]=nums[k+1]
}
i--;//往前移了一个，有要从此位置开始遍历检测
length--;
}
}
return length;
};双指针法（一层for循环）
没碰到要删除的值一样快，碰上要删除的值”慢指针就落后（不++）“
return位置❌ ,核心基础
/**
* @param {number[]} nums
* @param {number} val
* @return {number}
*/
var removeElement = function(nums, val) {
let slow=0;
for(fast=0;fast<nums.length;fast++){
if(nums[fast]!==val){
nums[slow++]=nums[fast];
}
}
return slow;
};数组去重
function removeDuplicatesWithTwoPointers(arr) {
// 首先对数组进行排序（如果数组未排序）
arr.sort((a, b) => a - b);
// 初始化两个指针（索引）
let left = 0;
// 遍历数组，从第二个元素开始（索引1）
for (let right = 1; right < arr.length; right++) {
// 如果当前元素与左指针指向的元素不同，则将其保留在数组中
// 并移动左指针到该位置
if (arr[right] !== arr[left]) {
//先移动指针，后替换值
left++;
// 可选：如果你想要在原地修改数组，可以使用splice来替换元素
// arr.splice(left, 0, arr[right]); // 这行代码实际上是不必要的，因为我们可以直接赋值
arr[left] = arr[right]; // 直接赋值即可，因为我们已经移动了left指针
}
// 如果相同，则忽略当前元素（右指针继续移动）
}
// 截断数组，只保留去重后的部分
arr.length = left + 1;
return arr;
}
// 示例
const originalArray = [4, 4, 2, 5, 1, 2, 3, 3];
const uniqueArray = removeDuplicatesWithTwoPointers(originalArray);
console.log(uniqueArray); // 输出: [1, 2, 3, 4, 5]
------------------------------------------------------------------
/**
* @param {number[]} nums
* @return {number}
*/
var removeDuplicates = function(nums) {
let pre=0;
for(i=1;i<nums.length;i++){
if(nums[pre]!==nums[i]){
pre++;
nums[pre]=nums[i];
}
}
return pre+1;
};移动零
在移除元素的基础上加了一个zeroCounts而已
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var moveZeroes = function(nums) {
let zeroCounts=0;
let currentIndex=0;
for(let i=0;i<nums.length;i++){
if(nums[i]!=0){
nums[currentIndex]=nums[i];
currentIndex++
}else{
zeroCounts++;
}
}
for(j=0;j<zeroCounts;j++){
nums[currentIndex+j]=0;
}
return nums;
};比较含退格的字符串
使用栈的思路
-
定义函数：
首先，你需要定义一个函数，比如叫backspaceCompare，它接收两个字符串s和t作为参数。 -
处理字符串：
对于每个字符串（s和t），你需要编写一个辅助函数（比如叫processString）来模拟退格字符的行为。这个函数将遍历字符串，并使用一个栈（或数组，因为在这里栈的功能可以通过数组轻松模拟）来存储非退格字符。遍历完成后，栈中剩余的字符就是模拟退格字符后的字符串。
- 遍历字符串时，如果当前字符不是
#，则将其压入栈中。 - 如果当前字符是
#，则从栈中弹出一个字符（如果栈不为空）。
- 遍历字符串时，如果当前字符不是
-
比较结果：
使用上述辅助函数分别处理s和t，得到两个处理后的字符串。然后，比较这两个字符串是否相等。 -
返回结果：
根据比较的结果，返回true或false。
/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
var backspaceCompare = function(s, t) {
let sArr=process(s);
let tArr=process(t);
return sArr.toString()===tArr.toString()
};
function process(str){
let arr=[];
for(let i=0;i<str.length;i++){
if(arr[i]!=='#'){
arr.push(arr[i]);
}else{
arr.pop();
}
}
return arr;
}双向指针
/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
var backspaceCompare = function(s, t) {
//#数量
let sSkipNum=0;
let tSkipNum=0;
let i=s.length-1;
let j=t.length-1;
while(true){
while(i>=0){
if(s[i]==="#"){
sSkipNum++;
i--;
}else{
//有#号抵消一个数，移动指针[key]
if(sSkipNum>0){
sSkipNum--;
i--;
}else{
break;
}
}
}
while(j>=0){
if(t[j]==="#"){
tSkipNum++;
j--;
}else{
if(tSkipNum>0){
tSkipNum--;
j--;
}else{
break;
}
}
}
//有一方处理完就退出
if(i<0||j<0)break;
//字符不同
if(s[i]!==t[j]){return false;}
//移动指针，继续比较
i--;
j--;
}
if(i==-1&&j==-1){
//同时处理完，且字符已经相等了
return true;
}else{
return false;
}
};
有序数组平方
定义左右指针和一个索引（从大递减），比较两个数的平方，移动指针更新索引
function sortedSquares(nums) {
const n = nums.length;
const result = new Array(n); // 创建一个与输入数组相同大小的结果数组
let left = 0; // 左指针
let right = n - 1; // 右指针
let index = n - 1; // 结果数组的索引，从后往前填充
while (left <= right) {
const leftSquare = nums[left] * nums[left];
const rightSquare = nums[right] * nums[right];
if (leftSquare > rightSquare) {
result[index] = leftSquare;
left++;
} else {
result[index] = rightSquare;
right--;
}
index--;
}
return result;
}
// 示例用法
const nums = [-4, -1, 0, 3, 10];
const squaredNums = sortedSquares(nums);
console.log(squaredNums); // 输出: [0, 1, 9, 16, 100]在JavaScript算法中，双向指针（也称为双指针或对指针）技术是一种常用的技巧，特别适用于处理需要同时从数组或字符串的两端或中间向某个方向移动指针的问题。这种方法通常能够减少空间复杂度，并且有时也能降低时间复杂度。以下是一些常见的应用场景：
- 数组或字符串中的两数之和：
- 给定一个已排序的数组（或字符串）和一个目标和，使用双向指针从两端向中间遍历，找到两个数（或字符）使它们的和等于目标和。这种方法的时间复杂度为O(n)。
- 回文检测：
- 判断一个字符串是否是回文。可以使用两个指针，一个从字符串的开头开始，另一个从字符串的末尾开始，然后向中间移动，比较对应位置的字符是否相同。
- 容器中的水量：
- 给定n个非负整数表示每个柱子的高度，计算在这些柱子之间能够接到的雨水总量。这个问题可以通过使用双向指针和栈来解决。
- 合并两个有序数组：
- 将两个有序数组合并成一个有序数组。可以使用两个指针分别指向两个数组的开头，然后比较当前指针所指的元素，将较小的元素添加到结果数组中，并移动相应的指针。
- 最长公共子序列（LCS）：
- 虽然通常使用动态规划来解决LCS问题，但双向指针也可以用于一些特定形式的LCS问题，特别是在与字符串匹配相关的问题中。
- 滑动窗口：
- 双向指针技术可以与滑动窗口技术结合使用，以解决一些需要维护一个固定大小的窗口并计算窗口内元素的问题。
- 移除元素使数组有序：
- 给定一个数组，其中每个元素都是某个范围内的整数。要求移除尽可能少的元素，使得剩余的元素按非递减顺序排列。这个问题可以通过使用双向指针和贪心策略来解决。
- 链表中的两数相加：
- 给定两个表示非负整数的链表，每个节点包含一个数字。这些数字以逆序的方式存储，并且每个节点只能存储一个数字。将这两个数相加并以链表的形式返回它们的和。这个问题可以通过使用双向指针（或更准确地说是两个游标）来遍历两个链表并构建结果链表。
请注意，双向指针的应用场景不仅限于上述例子，它可以根据问题的具体需求进行灵活应用。在解决问题时，重要的是要识别出是否可以通过同时从两个方向遍历数据来简化问题或提高效率。