当前位置：首页 > news >正文

学习记录：js算法（十三）：移动零、验证回文串

news 来源：原创 2024/9/21 0:32:50

文章目录

- 移动零
- - 我的思路
  - 网上思路
- 验证回文串
- - 我的思路
  - 网上思路
- 总结

移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意： 必须在不复制数组的情况下原地对数组进行操作。

示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]示例 2:
输入: nums = [0]
输出: [0]

我的思路
万变不离其宗：循环
网上思路
双指针

我的思路

var moveZeroes = function (nums) {let len = nums.length - 1for (let i = 0; i < len; i++) {for (let j = 0; j < len - i; j++) {if (nums[j] === 0) {nums[j] = nums[j + 1]nums[j + 1] = 0}}}
};

讲解
改变冒泡排序，这种不需要讲解了吧，唯一需要说明的是：let len = nums.length - 1，为什么要 减去1 呢？是因为在第二个循环中，j+1 会找到数组的最后一位，如果长度是 nums.length 的话，会找不到 j+1 。

网上思路

var moveZeroes = function (nums) {let lastNonZeroIndex = 0; // 指向下一个非零元素的位置// 遍历数组for (let i = 0; i < nums.length; i++) {if (nums[i] !== 0) {// 如果当前元素不是 0，将其放到 lastNonZeroIndex 位置nums[lastNonZeroIndex] = nums[i];lastNonZeroIndex++; // 移动指针}}// 将剩余的元素设置为 0for (let i = lastNonZeroIndex; i < nums.length; i++) {nums[i] = 0;}
};

讲解
其实很好理解

初始化一个指针 **lastNonZeroIndex：指向数组第一个元素 **
如果当前元素不是 0，将其放到 lastNonZeroIndex 指向的位置，然后 lastNonZeroIndex++，目的是： 移动指针，为下一个非零元素准备位置。
这时 lastNonZeroIndex：指向下一个非零的元素。

验证回文串

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个回文串。
字母和数字都属于字母数字字符。
给你一个字符串 s，如果它是回文串，返回 true ；否则，返回 false 。

示例

我的思路
简单，使用正则完成条件后，只需要将字符串转成数组后在翻转，然后将翻转的数组转成字符串之后，再比较。
网上思路
双指针

我的思路

var isPalindrome = function (s) {let str = s.toLowerCase().replace(/[^a-z0-9]/g, '')return str === str.split("").reverse().join("") ? true : false
};

讲解

s.toLowerCase(): 将字符串转换为小写，这样在比较时就不需要考虑大小写的差异。
正则表达式中：
/[^a-z0-9]/g ：这个正则表达式的含义是匹配所有非字母（a-z）和非数字（0-9）的字符。
g ：这个标志表示全局匹配，即替换字符串中所有符合条件的字符。
‘’ ：将匹配到的字符替换为空字符串，从而移除它们。

然后字符串转数组，数组翻转后再转字符串，最后对比即可。

网上思路

var isPalindrome = function (s) {// 使用正则表达式清洗字符串const str = s.toLowerCase().replace(/[^a-z0-9]/g, '');let left = 0;let right = str.length - 1;// 使用双指针比较while (left < right) {if (str[left] !== str[right]) {return false; // 不是回文}left++;right--;}return true; // 是回文
};