js算法基础-01

js算法基础, 每个重要逻辑思路，做一下列举

1、双指针

• 有序数组合并：一般思路就是合并、排序，当然效率略低
• 题目1：nums1中取前m个元素，nums2中取前n个元素，组成新的有序数组，最后结果写入nums1
• 思路：双指针，两个数组各自一个指针，该位置就是未参与排序的最小值

// 一般思路
const merge = function (nums1, m, nums2, n) {const mergedArray = [...nums1.slice(0, m), ...nums2.slice(0, n)]; // 合并mergedArray.sort((a, b) => a - b); // 修改原数组，重新排序// 数组内容粘贴，一般出现在修改原数组的时候for (let i = 0; i < merged.length; i++) {nums1[i] = merged[i];}return nums1;
};console.log(merge([1, 2, 3, 0, 0, 0], 3, [2, 5, 6], 3));

// 双指针
const merge = function (nums1, m, nums2, n) {const target1 = nums1.slice(0, m); // 截取后目标数组const target2 = nums2.slice(0, n);let index1 = 0; // 每个数组一个排序位置的指针let index2 = 0;for (let i = 0; i < m + n; i++) {const num_1 = target1[index1]; // 每个数组取出的元素const num_2 = target2[index2];// 边界条件if (index1 >= m) {// 这里表示数组1已经取完了，那么剩下的全部取数组2的元素即可nums1[i] = num_2;index2++;} else if (index2 >= n) {nums1[i] = num_1;index1++;} else if (num_1 < num_2) {// 取最小值nums1[i] = num_1;index1++;} else {nums1[i] = num_2;index2++;}}return nums1;
};
console.log(merge([1, 2, 3, 0, 0, 0], 3, [2, 5, 6], 3));

• 题目2：验证回文，返回是或者否
• 思路1：当需要得到是否的时候，可以正向思考，所有满足即为true，也常见于反向思考，找出一个不符合的即为false，一般看条件苛刻程度，比如预测大部分都符合条件，那么就找出不符合的
• 思路2：for循环里自变量i就是单指针

// 快速
var isPalindrome = function (s) {const str = s.toLowerCase().replace(/[^a-z0-9]/g, "");const strR = str.split("").reverse().join("");return str === strR;
};// 双指针
var isPalindrome = function (s) {const str = s.toLowerCase().replace(/[^a-z0-9]/g, "");for (let i = 0, j = str.length - 1; i < j; i++, j--) {if (str[i] !== str[j]) return false;}return true;
};// for循环，单指针
var isPalindrome = function (s) {const str = s.toLowerCase().replace(/[^a-z0-9]/g, "");for (let i = 0; i < str.length / 2; i++) {if (str[i] !== str[str.length - 1 - i]) {return false;}}return true;
};
console.log(isPalindrome("A man, a plan, a canal: Panama")); // true

2、快慢指针

• 快慢指针：一般会出现在一个数组、一个目标数据中
• 题目：删除有序数组中的重复项
• 思路：由于有序数组中会出现重复的元素，所以慢指针指示写入的位置，快指针跳过重复的元素，直到下一个不同元素出现

var removeDuplicatesArray = [1, 1, 2];
var removeDuplicates = function (nums) {let slow = 0,fast = 1;while (fast < nums.length) {if (nums[slow] !== nums[fast]) {slow++;nums[slow] = nums[fast];}fast++;}return slow + 1;
};
console.log(removeDuplicates([1, 1, 2]), removeDuplicatesArray);

补充while 和 for的差异；可以看到差异很小，while没有初始化变量的位置，没有自增位置，只有终止逻辑；一般来说for更全面，while循环都可以改造成for循环；while适用于略微简化逻辑；

var removeDuplicates2 = function (nums) {let slow = 0,fast = 1;for (fast = 1; fast < nums.length; fast++) {if (nums[slow] !== nums[fast]) {slow++;nums[slow] = nums[fast];}}return slow + 1;
};

3、滑动指针

• 滑动指针：需要对两个指针之间的元素进行计算，比如求和
• 题目1：找出该数组nums中满足其总和大于等于 target 的长度最小的子数组，返回长度，

var minSubArrayLen = function (target, nums) {let length = nums.length,// 左指针缩小范围left = 0,// 右指针扩大范围right = 0,// sum 是动态和，有时比 target 小，有时比 target 大sum = 0,// 加1是为了断定是不是所有的元素都加起来都不够targetminLen = length + 1;for (right = 0; right < length; right++) {sum += nums[right];// 只要sum大于等于target，一直移动左指针，并得到sum和while (sum >= target) {minLen = Math.min(minLen, right - left + 1); // 计算当前窗口的长度sum -= nums[left]; // 减去左指针的值left++; // 左指针右移}}return minLen === length + 1 ? 0 : minLen;
};
console.log(minSubArrayLen(5, [1, 4, 4])); // 2

4、哈希表

• 哈希表：可以统计字符和存储数据
• 题目1：判断 ransomNote 能不能由 magazine 里面的字符构成；每个字符只能使用一次；

var canConstruct = function (ransomNote, magazine) {// 对字符的个数进行统计const magazineObj = {};// 统计for (let i = 0; i < magazine.length; i++) {const char = magazine[i];if (magazineObj[char]) {magazineObj[char]++;} else {magazineObj[char] = 1;}}// 检验for (let i = 0; i < ransomNote.length; i++) {const char = ransomNote[i];// 减到0就说明没了，返回falseif (magazineObj[char]) {magazineObj[char]--;} else {return false;}}return true;
};
console.log(canConstruct("aa", "ab")); // false

• 题目2：两数之和，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标；这里规定只有一对满足条件
• 思路：两个值，刚好可以用哈希key：value完成记录；（还有三数之和等）

var twoSum = function (nums, target) {const numsObj = {};// 统计for (let i = 0; i < nums.length; i++) {const item = nums[i];// 注意 索引0是存在配对数的，要判断undefined才准确if (numsObj[item] !== undefined) {return [numsObj[item], i];} else {numsObj[target - item] = i; // 记录配对数 对应的索引}}return [];
};console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]

5、汇总区间

汇总区间

• 题目1：给定一个 无重复元素 的 有序 整数数组 nums，返回区间汇总

var summaryRanges = function (nums) {// 区间起点指针let index = 0,result = []; // 结果数组for (let i = 0; i < nums.length; i++) {const item = nums[i];// 判断 是否 连续；不连续就要添加区间if (item !== nums[i + 1] - 1) {// 是否是单个数字；然后添加区间result.push(index === i ? `${item}` : `${nums[index]}->${item}`);index = i + 1; // 记录下一个开始的索引}}return result;
};console.log(summaryRanges([0, 1, 2, 4, 5, 7])); // ["0->2", "4->5", "7"]

6、栈

• 栈：储存了顺序结构
• 题目1：判断字符串是不是有效括号

// 方式1，所有括号都有配对的另一半，把配对子都放进去；
// 如果栈最后一个配对上了。说明他是偏向内部的完整括号，那么删除，也不再增加配对子；
// 栈为空，添加配对子；没有匹配上，添加配对子；
var isValid = function (s) {// 偶数位if (s.length % 2 !== 0 || s.length === 0) return false;const configObj = {"(": ")","{": "}","[": "]"};const stack = [];for (let i = 0; i < s.length; i++) {const char = s[i];const target = configObj[char];if (stack.length > 0) {// 检测是否配对if (stack[stack.length - 1] === char) {stack.pop();} else {// 存配对子stack.push(target);}} else {// 存配对子stack.push(target);}}return stack.length === 0;
};
console.log(isValid("([]{})")); // true
// console.log(isValid("([)")); // false

方式2，只关注左侧括号，只存储左侧括号对应的配对子

// 碰到左侧括号就放入配对子，
// 否则检查最后一个元素是否配对，
// 配对上了就删除最后一个元素
var isValid = function (s) {// 偶数位if (s.length % 2 !== 0 || s.length === 0) return false;const configObj = {"(": ")","{": "}","[": "]"};const stack = [];for (let i = 0; i < s.length; i++) {const char = s[i];const target = configObj[char];if (target) {// 放入配对子stack.push(target);} else {//  右侧括号 对应if (stack[stack.length - 1] !== char) {return false;}// 配对上了 必须删除一个stack.pop();}}return stack.length === 0;
};
console.log(isValid("([]{})")); // true
// console.log(isValid("([)")); // false

7、进制求和

• 进制求和：模仿进制
• 题目1：二进制求和

var addBinary = function (a, b) {const maxLength = Math.max(a.length, b.length);let carry = 0; // 进位let result = ""; // 结果for (let i = 0; i < maxLength; i++) {const num1 = a[a.length - 1 - i] || 0; // 取最后一位，不存在则补0const num2 = b[b.length - 1 - i] || 0;const count = parseInt(num1) + parseInt(num2) + carry; // 加法result = (count % 2) + result; // 取最后一位carry = count >= 2 ? 1 : 0; // 进位}return carry === 1 ? 1 + result : result;
};console.log(addBinary("11", "1")); // "100"

8、数学

• 题目1：数字加一，[1, 2, 9]=>[1, 3, 0]
• 熟练使用自增和自减

var plusOne = function (digits) {const length = digits.length;let carry = 1;for (let i = length - 1; i >= 0; i--) {const num = digits[i];// 处理的位置// 进制为10 检查是否进制// 不进制，原位置加数if (num + carry === 10) {digits[i] = 0;carry = 1;} else {digits[i] = num + carry;carry = 0;break; // 找到第一个不为9的就退出, 不用再加}}// 如果超出进制，在最前面再加一if (carry === 1) {digits.unshift(1);}return digits;
};
console.log(plusOne([1, 2, 9])); // [1, 2, 4]

进制时，循环索引可以自增，也可以自减；都可以定位到最后一位

const arr = [1, 2, 9];
// 自增
for (let i = 0; i < arr.length; i++) {// 处理的位置const index = length - 1 - i;const num = digits[index];
}
// 自减
for (let i = arr.length - 1; i >= 0; i--) {const num = arr[i];
}

9、动态规划

• 题目1：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

var climbStairs = function (n) {if (n === 1) return 1;if (n === 2) return 2;let prev1 = 1;let prev2 = 2; // 两种方案 1+1，2let result = 0;// 由于最后一步只能爬1或2，// 所以只需要计算前两步的和，相当于分类讨论;// 比如假设最后一步是1，那就是在n-1的位置，爬1个台阶，// 最后一步是2，那么就在n-2的位置，爬2个台阶；// f(n) = f(n-1) + f(n-2)// 如果可以爬1\2\3，则f(n) = f(n-1) + f(n-2) + f(n-3)for (let i = 3; i <= n; i++) {result = prev1 + prev2;prev1 = prev2;prev2 = result;}return result;
};console.log(climbStairs(5)); // 8