在这里插入图片描述

@[TOC]

序号为LeetCode的题序，语言选择的是JavaScript

# 数字类

# 7. 整数反转（简单）

https://leetcode-cn.com/problems/reverse-integer/ (opens new window)

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

# 【解法一】反转字符串

这题一拿到手，最先也是最容易想到的就是将数字传转换成字符串然后进行反转数字 ——> 字符串 ——> 数组 ——> 反转 ——> 字符串 ——> 数字在这里插入图片描述注意分清楚正负号，还有题目的条件，即可得到答案

var reverse = function(x) {
  let res = 0;
  if (x >= 0) {
    res = +String(x).split("").reverse().join("");
  } else {
    x = -x;
    res = -String(x).split("").reverse().join("");
  }
  if(res > 2**31 - 1 || res < -(2**31)) return 0;
  return res;
};

在这里插入图片描述

再想着用数学的方式来试试，不需要开辟新的空间来进行反转

# 【解法二】商与余数

整数除以10 余数为其个位数商为去除个位数的剩余数字 (需要取整) 在这里插入图片描述

整体思路就是遍历（x / 10商）数字x，每次拿数字的个位（x % 10 余数），直到拿完。每次遍历都将x的个位拼接到result的新腾出的个位上（result = result * 10 + (x % 10);）

/**
 * @param {number} x
 * @return {number}
 */
var reverse = function (x) {
  let result = 0;
  while (x) {
    result = result * 10 + (x % 10);
    if (result > 2 ** 31 - 1 || result < -(2 ** 31)) return 0;
    x = ~~(x / 10);
  }
  return result;
};

在这里插入图片描述

# 【技巧】`~~`取整（舍去小数位）

~按位取反

对于整数相当于取反减一

~0 === -1
~1 === -2
~-1 === 0
~-2 === 1

对于小数相当于舍去小数位再取反减一

~0.3 === -1
~1.7 === -2
~-0.3 === -1
~-1.2 === 0
~-2.9 === 1

~~按位取反再取反

对于整数还是自身

~~1 === 1
~~-1 === -1
~~0 === 0

对于小数，等于舍去小数位相当于正数向下取整，负数向上取整

~~1.1 === 1
~~1.9 === 1
~~-1.1 === -1
~~-1.9 === -1

# 【技巧】`Math.floor()` 向下取整

Math.floor() 是向下取整

Math.floor(1.1) === 1
Math.floor(1.9) === 1
Math.floor(-1.1) === -2
Math.floor(-1.9) === -2

# 13. 罗马数字转整数（简单）

https://leetcode-cn.com/problems/roman-to-integer/ (opens new window)

# 【解法一】Map

创建map映射
遍历字符串，在map中根据key取value （map.get(s[i])）

正常情况下小的数在大的数的右边直接累加

要先排除特殊情况小的数在大的数的左边，那就给它前面加一个负号

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function (s) {
  let map = new Map();
  map
    .set("I", 1)
    .set("V", 5)
    .set("X", 10)
    .set("L", 50)
    .set("C", 100)
    .set("D", 500)
    .set("M", 1000);

  let result = 0;
  for (let i = 0; i < s.length; i++) {
    let value = map.get(s[i]);
    if (i < s.length - 1 && value < map.get(s[i + 1])) {
      result -= value;
    } else {
      result += value;
    }
  }
  return result;
};

在这里插入图片描述

# 【解法二】switch

# 【技巧】巧用`switch`语句

有限种确定情况，完全可以用switch语句

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function (s) {
  let result = 0;
  for (let i = 0; i < s.length; i++) {
    let value = getValue(s[i]);
    if (i < s.length - 1 && value < getValue(s[i + 1])) {
      result -= value;
    } else {
      result += value;
    }
  }
  return result;
};

function getValue(s) {
  switch (s) {
    case "I":
      return 1;
    case "V":
      return 5;
    case "X":
      return 10;
    case "L":
      return 50;
    case "C":
      return 100;
    case "D":
      return 500;
    case "M":
      return 1000;
    default:
      return 0;
  }
}

# 50. Pow(x, n) （中等）

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，$x^n$）。

# 【解法一】快速幂前处理

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function(x, n) {
    let result = 1

    if(n < 0){
        x = parseFloat(1/x)
        n = -n
    }

    while (n > 0) {
        if ((n & 1) === 1) result *= x;
        x *= x
        n >>>= 1;
    }
    
    return result
};

# 【解法二】快速幂后处理

也可以这样最后处理

var myPow = function(x, n) {
    let result = 1

    let flag = false
    if(n < 0){
        flag = true
        n = -n
    }

    while (n > 0) {
        if ((n & 1) === 1) result *= x
        x *= x
        n >>>= 1
    }
    if(flag){
        result = parseFloat(1/result)
    }
    return result
};

在这里插入图片描述

# 数组类

# 1. 两数之和（简单）

https://leetcode-cn.com/problems/two-sum/ (opens new window)

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。

# 【解法一】两层循环 - 暴力查找

拿到题最容易想到的就是两层循环遍历，固定一个元素，查找另一个元素在这里插入图片描述

i遍历一遍数组； j从i+1开始遍历剩余部分，看是否能找到等于 target-nums[i] 的元素，找到返回下标

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  for (let i = 0; i < nums.length - 1; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[j] === target - nums[i]) {
        return [i, j];
      }
    }
  }
  return [];
};

在这里插入图片描述

# 【解法二】一层循环 - Map

复习一下ES6的Map

# 【技巧】map

map会维护插入时的顺序

// 定义空map
let map = new Map();
// 添加元素
map.set("key1","value1").set("key2", "value2");
// 查询元素
map.has("key1"); // true
map.get("key1"); // "value1"
map.size === 2;

构建映射【值：下标】

遍历nums构建map，之后只需在map中查找元素，而不需要每次都遍历剩余数组了

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let map = new Map();
    for(let i = 0; i < nums.length; i++){
	    let value = target - nums[i]
	    if(map.has(value)){
	        return [map.get(value), i]
	    }else {
	    	// 找不到就插入到 map中
	        map.set(nums[i], i)
	    }
    }
    return [];
};

在这里插入图片描述

# 【坑】注意题目条件不可以取两次自己的下标

注意这里有一个坑，往map中存数据（set）操作要在判断语句之后！因为不可以重复取两次自己，所以要在之前存入的元素中查找！！！

# 11. 盛最多水的容器（中等）

https://leetcode-cn.com/problems/container-with-most-water/ (opens new window)

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

在这里插入图片描述

# 【解法】双指针

初始时，两个指针分别指向数组的两端，得到当前可以容纳的水的容量每次移动一个指针，就是指向的值小的那个指针这道题操作起来其实很简单，然而其中的重点是这种方法的【正确性】，我们在移动指针的时候抛弃了很多的解，但是这些解是可以抛弃的解，不会影响结果的解

将本题的搜索空间用矩阵表示出来就是这样的【白色区域】在这里插入图片描述如果遍历所有的解【所有小方块】，就需要O(N^2)的复杂度通过本题的双指针来缩减搜索空间

双指针最先得到的解是右上方的解在这里插入图片描述假设左边的 0 号柱子较短。0 号柱子目前的水面高度已经到了上限。由于 7 号柱子已经是离 0 号柱子最远的了，水的宽度也最大，如果换其他的柱子和 0 号柱子配对，水的宽度只会更小，高度也不会增加，容纳水的面积只会更小。也就是说，0 号柱子和6,5,4,3,2,1号柱子的配对都可以排除掉了。记录了 (0,7) 这组柱子的结果之后，就可以排除 0 号柱子了。这相当于 i=0 的情况全部被排除。对应于双指针解法的代码，就是 i++；对应于搜索空间，就是削减了一行的搜索空间，如下图所示。在这里插入图片描述

排除掉了搜索空间中的一行之后，我们再看剩余的搜索空间，仍然是倒三角形状。

在这里插入图片描述

最终的动图如图所示在这里插入图片描述图片作者：nettee；链接：https://leetcode-cn.com/problems/container-with-most-water/solution/on-shuang-zhi-zhen-jie-fa-li-jie-zheng-que-xing-tu/

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    let i = 0;
    let j = height.length - 1;
    let maxA = 0;
    
    while(i<j){
        let nowA = Math.min(height[i],height[j]) * (j - i);
        maxA = Math.max(maxA, nowA);
        if(height[i] <= height[j]){
            i++;
        }else{
            j--;
        }
    }
    
    return maxA;
};

在这里插入图片描述

# 26. 删除有序数组中的重复项【简单】

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/ (opens new window)

给你一个有序数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

# 【解法一】快慢指针

快指针表示遍历数组到达的下标位置【遍历数组】慢指针表示下一个不同元素要填入的下标位置【维持条件】

快指针 i 用来遍历一遍数组慢指针 j 用来维护数组【维护数组元素不重复的性质】注意这里的判断条件，满足条件【元素不重复】，慢指针j才走

在这里插入图片描述

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    let j = 0;
    for(let i = 0; i < nums.length; i++){
        if(nums[i] !== nums[j]){
            j++;
            nums[j] = nums[i];
        }
    }
    return j + 1;
};

在这里插入图片描述

# 【解法二】双指针

这里利用了JavaScript的特性，就是数组越界的结果是undefined，不会报错

var removeDuplicates = function (nums) {
  let j = 0;
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== nums[i + 1]) {
      nums[j] = nums[i];
      j++;
    }
  }
  return j;
};

在这里插入图片描述

也可以将遍历初始值+1，这样就不会出现数组越界了

var removeDuplicates = function(nums) {
    let j = 1
    for(let i = 1; i < nums.length; i++){
        if(nums[i] !== nums[i-1]){
            nums[j] = nums[i]
            j++
        }
    }
    return j
};

在这里插入图片描述

# 27. 移除元素【简单】

https://leetcode-cn.com/problems/remove-element/ (opens new window)

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

# 【解法】快慢指针

与26题的思路一样，快指针i用来遍历一遍nums，慢指针j用来维持数组【不包含val元素】【注意】这题判断语句内部的执行顺序与26题不一样，先进行赋值再自增【注意】由于后自增，所以最后返回值已不需要手动+1

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    let j = 0;
    for(let i = 0; i< nums.length; i++){
        if(nums[i] !== val){
            nums[j] = nums[i];
            j++;
        }
    }
    return j;
};

在这里插入图片描述

# 【解法二】对撞指针

由于题目对元素顺序没有要求，所以可以在碰到需要舍弃的元素（等于val的元素）时，用最后的元素替代即可

定义左右两个对撞指针

var removeElement = function(nums, val) {
  let left = 0;
  let right = nums.length - 1;
  while (left <= right) {
    if (nums[left] === val) {
      nums[left] = nums[right];
      right--;
    } else {
      left++;
    }
  }
  return left;
};

在这里插入图片描述

# 53. 最大子序和【简单】

https://leetcode-cn.com/problems/maximum-subarray/ (opens new window)

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

# 【解法】动态规划

转移方程

$$f(i)=max ( f(i−1)+nums[i], nums[i] ) $$

thisSum 维护一个向右累加子序和如果之前和子序和都没有第i个元素大，就从i开始重新维护一个累加子序和

maxSum 保存遍历过程中的最大子序和

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let thisSum = 0;
    let maxSum = nums[0];
    
    for(let i = 0; i < nums.length; i++){
        if(thisSum + nums[i] < nums[i]){
            thisSum = nums[i];
        }else{
            thisSum += nums[i];
        }
        
        if(thisSum > maxSum){
            maxSum = thisSum;
        }
    }
    
    return maxSum;
};

精简一下代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let thisSum = 0;
    let maxSum = nums[0];
    for(let i = 0; i< nums.length; i++){
        thisSum = Math.max(thisSum + nums[i], nums[i]);
        maxSum = Math.max(maxSum, thisSum);
    }
    return maxSum;
};

在这里插入图片描述

# 54. 螺旋矩阵

https://leetcode-cn.com/problems/spiral-matrix/

给你一个 m 行 n 列的矩阵 matrix ，请按照顺时针螺旋顺序，返回矩阵中的所有元素。

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function(matrix) {
    if(!matrix.length || !matrix[0].length) return []

    const rows = matrix.length
    const columns = matrix[0].length
    const result = []

    let left = 0
    let right = columns -1
    let top = 0
    let bottom = rows - 1

    // 只要指针没有重合到一个点就一直循环
    while(left <= right && top <= bottom){
        // 上边一行 从左到右
        for(let column = left; column <= right; column++){
            result.push(matrix[top][column])
        }
        // 右边一列，从上到下
        for(let row = top + 1; row <= bottom; row++){
            result.push(matrix[row][right])
        }
        // 要保证正在遍历的矩阵
        if(left < right && top < bottom){
            // 下方一行，从右往左
            for(let column = right - 1; column > left; column--){
                result.push(matrix[bottom][column])
            }
            // 左边一列，从下到上
            for(let row = bottom; row > top; row--){
                result.push(matrix[row][left])
            }
        }
        // 去除最外面一层
        [left, right, top, bottom] = [left+1, right-1, top+1, bottom-1]
    }
    return result
};

在这里插入图片描述

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function(matrix) {
    if(!matrix.length || !matrix[0].length) return []

    const rows = matrix.length
    const columns = matrix[0].length
    const result = []

    let left = 0
    let right = columns -1
    let top = 0
    let bottom = rows - 1

    while(true){
        for(let i = left; i <= right; i++){
            result.push(matrix[top][i])
        }
        top++
        if(top > bottom) break

        for(let i = top; i <= bottom; i++){
            result.push(matrix[i][right])
        }
        right--
        if(right < left) break

        for(let i = right; i >= left; i--){
            result.push(matrix[bottom][i])
        }
        bottom--
        if(bottom < top) break

        for(let i = bottom; i >= top; i--){
            result.push(matrix[i][left])
        }
        left++
        if(left>right) break
    }
    return result
};

在这里插入图片描述

# 75. 颜色分类【中等】

https://leetcode-cn.com/problems/sort-colors (opens new window)

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

# 【解法一】两次遍历

一种很朴素的解法遍历两边，正着找0放在最前面，倒着找2放在最后面【双指针】

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function(nums) {
    let first = 0;
    let last = nums.length - 1;
    // 第一次正序遍历，将所有的0 移动到最左边
    for(let i = 0; i < nums.length; i++){
        if(nums[i] === 0){
            swap(nums, i, first);
            first++;
        }
    }
	// 第二次倒序遍历，把所有的2移动到最右边
    for(let i = nums.length - 1; i >= 0; i--){
        if(nums[i] === 2){
            swap(nums, i, last);
            last--;
        }
    }
};

function swap(nums,i,j){
    let temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

也可以按顺序找，0放前面，1放中间，一样一样的【单指针】

var sortColors = function(nums) {
    let first = 0
    for(let i = 0; i < nums.length; i++){
        if(nums[i] === 0){
            swap(nums, i, first);
            first++;
        }
    }
    for(let i = first; i < nums.length; i++){
        if(nums[i] === 1){
            swap(nums, i, first);
            first++;
        }
    }
};

# 【解法二】两层循环冒泡排序

很多原地排序算法都可以【冒泡】【选择】【插入】等

更多关于排序算法可以参考这篇博文【算法】经典排序算法总结-JavaScript描述-图解-复杂度分析 (opens new window)

var sortColors = function(nums) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < nums.length - i -1; j++) {
      if (nums[j] > nums[j + 1]) {
        swap(nums, j, j + 1);
      }
    }
  }
};

# 【解法三】遍历一次 + 循环不变量【重点】

头尾指针i和j，遇到0与nums[i]交换，遇到2与nums[j]交换，遇到1就跳过啥也不做

定义循环不变量

[0, i) === 0
(i, k) === 1
(j, nums.length-1] === 2

终止条件是k===j

var sortColors = function(nums) {
    let i = 0;
    let j = nums.length - 1;
    // 遍历一遍nums，到尾指针的位置
    for(let k = 0; k <= j; k++){
        if(nums[k] === 0){
        	// 遇到 0 和 头指针交换位置
            swap(nums, k, i);
            // 头指针后移
            i++;
        }else if(nums[k] === 2){
        	// 遇到 2 和 尾指针交换位置
            swap(nums, k, j);
            // 尾指针前移
            j--;
            // 循环指针后退一位，处理从后面移动过来的元素
            k--;
        }
    }
};

# 80. 删除有序数组中的重复项 II【中等】

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii (opens new window)

给你一个有序数组 nums ，请你原地删除重复出现的元素，使每个元素最多出现两次，返回删除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

与26题解题思路一致，就是多一个计数器

# 【解法】快慢指针

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
	// j 用来维持一个满足条件的数组
    let j = 0;
    // 定义一个计数变量
    let count = 1;
    // 遍历nums数组
    for(let i = 0; i < nums.length; i++){
    	// 设置计数器
        if(nums[i] === nums[i+1]){
        	// 遇到和后一个元素相同的情况，计数器加1
            count++;
        }else{
        	// 与后一个元素不同，计数器重置为1
            count = 1;
        }
        // j维持一个数组
        if(count <= 2){
        	// 满足条件，j才移动【计数器大于2的时候j不动】
            nums[j] = nums[i];
            j++;
        }					
    }
    return j;
};

换一种数组不越界的写法

var removeDuplicates = function(nums) {
    let j = 1
    let count = 1
    for(let i = 1; i < nums.length; i++){
         if(nums[i] === nums[i-1]){
             count++
         }else{
             count = 1
         }
         if(count <= 2){
             nums[j] = nums[i]
             j++
         }
    }
    return j
};

# 88. 合并两个有序数组【简单】

https://leetcode-cn.com/problems/merge-sorted-array/ (opens new window)

既然是合并【有序】数组就从后面开始维持数组关系

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {

    // 定义两个指针分别指向两个数组的末尾元素
    let i = m - 1;
    let j = n - 1;
    
    // 从后向前遍历temp数组
    for( let k = m+n-1; k >= 0; k--){
        if(nums1[i] >= nums2[j] || j<0){
        	// 两个数组中，谁大谁进，如果另一个数组遍历完了，剩下的都进这个
            nums1[k] = nums1[i]; 
            // 指针前移
            i--;
        } else if (nums1[i] < nums2[j] || i<0){
            nums1[k] = nums2[j];
            j--;
        }
    }
};

在这里插入图片描述

# 118. 杨辉三角

https://leetcode-cn.com/problems/pascals-triangle/ (opens new window)

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。在「杨辉三角」中，每个数是它左上方和右上方的数的和。

# 【解法】双层循环

/**
 * @param {number} numRows
 * @return {number[][]}
 */
function generate(numRows) {
  let result = [];
  for (let i = 0; i < numRows; i++) {
    let row = new Array(i + 1).fill(1);
    for (let j = 1; j < row.length - 1; j++) {
      row[j] = result[i - 1][j - 1] + result[i - 1][j];
    }	
    result.push(row);
  }
  return result;
}

在这里插入图片描述

# 121. 买卖股票的最佳时机

# 【解法一】暴力解法不通过

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let result = 0
    
    for(let i=0; i < prices.length; i++){
        for(let j = i; j < len; j++){
            result = Math.max(prices[j] - prices[i], result)
        }
    }
    
    return result
};

在这里插入图片描述

# 【解法二】类似动态规划

要想得到最大收益，那就要满足两个条件：

买入最低点到卖出最高点
最低点在最高点的左侧

// 当前价格比历史最低还要低，那就在这里买入
if(prices[i] < minPrice){
    minPrice = prices[i]
}
// 当前收益大于历史最大收益，那就在这里卖出
if (prices[i] - minPrice > result){
    result = prices[i] - minPrice
}

这样写的画，虽然能得到结果，但是我们没有必要每次遍历都计算最大收益值，所以可以改进一下在这里插入图片描述买入和卖出不可能同时操作，所以我们用了一个if-else语句来让减少计算

var maxProfit = function(prices) {
    let result = 0
    let minPrice = Infinity

    for(let i=0; i < prices.length; i++){
        // 当前价格比历史最低还要低，那就在这里买入
        if(prices[i] < minPrice){
            minPrice = prices[i]
        // 当前收益大于历史最大收益，那就在这里卖出
        }else if (prices[i] - minPrice > result){
            result = prices[i] - minPrice
        }
    }

    return result
};

在这里插入图片描述

# 167. 两数之和 II - 输入有序数组【简单】

https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/ (opens new window)

给定一个已按照升序排列的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

不考虑有序数组。就当第1题做

# 【解法一】两层循环-暴力查找

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(numbers, target) {
    for(let i = 0; i < numbers.length; i++){
        for(let j = i+1; j < numbers.length; j++){
            if(numbers[j] === target - numbers[i]){
                return [i + 1, j + 1]
            }
        }
    }
};

在这里插入图片描述

考虑有序数组，可以优化是有序数组，所以可以从两头往中间找

# 【解法二】头尾指针 - 对撞指针

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(numbers, target) {
	// 定义头尾指针
    let i = 0
    let j = numbers.length - 1
    
    while(i<j){
        let sum = numbers[i] + numbers[j]
        
        if(sum === target){
            return [i+1, j+1];
        }else if (sum < target) {
            i++;
        }else{
            j--;
        }
    }
};

在这里插入图片描述

# 215. 数组中的第K个最大元素【中等】

https://leetcode-cn.com/problems/kth-largest-element-in-an-array/ (opens new window)

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

# 【解法】划分 + 二分查找

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function (nums, k) {

  // 头尾指针
  let left = 0;
  let right = nums.length- 1;
  
  // 第k大的元素，应该在降序排列的数组的第k-1的位置
  let target = k - 1;

  while (true) {
    let index = partition(nums, left, right);
    // 类似于二分查找，不断划分数组直到找到第target个
    if (index == target) {
      return nums[index];
    } else if (index > target) {
      right = index - 1;
    } else {
      left = index + 1;
    }
  }
};

// 类似快排中的划分
function partition(nums, left, right) {
  // 保存枢轴元素的值，取左侧元素
  let piovt = nums[left];
  // 记录左指针
  let j = left;
  // 遍历 nums 指定位置 中的元素【从枢轴后面开始遍历】
  for (let i = left + 1; i <= right; i++) {
    if (nums[i] > piovt) {
      // 碰到大于枢轴的元素，左指针右移一位，当前元素与左指针交换位置
      j++;
      swap(nums, j, i);
    }
  }
  // 循环结束后，所有大于枢轴的元素都在左侧
  // 将枢轴元素放到对应的位置
  swap(nums, left, j);
  // 返回枢轴的位置
  return j;
}

function swap(nums, i, j) {
  let temp = nums[i];
  nums[i] = nums[j];
  nums[j] = temp;
}

# 283. 移动零【简单】

https://leetcode-cn.com/problems/move-zeroes/ (opens new window)

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

# 【解法一】快慢指针 + 两次遍历

快指针i遍历数组慢指针j维持非零条件【只有元素不为0，j才右移，这样保证了数组的长度就是所有非0元的个数】

这个和第27题相似

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
    let j = 0;
    for(let i = 0; i < nums.length; i++){
        if(nums[i] !== 0){
        	// 将不为0的元素都保存下来
            nums[j] = nums[i];
            j++;
        }
    }
    // 剩下的位置置0
    for(;j<nums.length;j++){
        nums[j] = 0
    }
};

# 【解法二】快慢指针 + 一次遍历 + 交换元素

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
    let j = 0;
    for(let i = 0; i < nums.length; i++){
        if(nums[i] !== 0){
            swap(nums, i, j);
            j++;
        }
    }
};

function swap(nums, i, j){
    let temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

# 704. 二分查找

# 【解法】头尾指针

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    let i = 0;
    let j = nums.length - 1;
    
    while(i <= j){
        let index = Math.floor(i + (j-i)/2);
        if(nums[index] === target){
            return index;
        }else if (nums[index] < target){
            i = index + 1;
        }else{
            j = index - 1;
        }
    }
    
    return -1;
};

# 278. 第一个错误的版本

# 【解法】二分查找

/**
 * Definition for isBadVersion()
 * 
 * @param {integer} version number
 * @return {boolean} whether the version is bad
 * isBadVersion = function(version) {
 *     ...
 * };
 */

/**
 * @param {function} isBadVersion()
 * @return {function}
 */
var solution = function(isBadVersion) {
    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function(n) {
        let i = 1;
        let j = n;
        while(i < j){
            let mid = Math.floor(i + (j-i)/2);
            if(isBadVersion(mid)){
                j = mid;
            }else{
                i = mid + 1;
            }
        }
        return i;
    };
};

注意这里的边界条件

# 剑指 Offer 09. 用两个栈实现队列

let CQueue = function(){
    this.stackA = []
    this.stackB = []
}

CQueue.prototype.appendTail = function(value){
    this.stackA.push(value)
}

CQueue.prototype.deleteHead = function(){
    if(this.stackB.length > 0){
        return this.stackB.pop()
    }else {
        while(this.stackA.length > 0){
            this.stackB.push(this.stackA.pop())
        }
        if(this.stackB.length > 0){
            return this.stackB.pop()
        }else{
            return -1
        }
    }
}

# 989. 数组形式的整数加法

对于非负整数 X 而言，X 的数组形式是每位数字按从左到右的顺序形成的数组。例如，如果 X = 1231，那么其数组形式为 [1,2,3,1]。给定非负整数 X 的数组形式 A，返回整数 X+K 的数组形式。

/**
 * @param {number[]} num
 * @param {number} k
 * @return {number[]}
 */
var addToArrayForm = function(num, k) {
    let result = []
    let len = num.length
    let add = 0
    for(let i = len - 1; i >= 0; i--){
        
        let sum = num[i] + k % 10 + add

        add = Math.floor(sum / 10)
        sum = sum % 10
        result[i] = sum
        k = Math.floor(k/10)
        
    }
    if(add === 1){
        result.unshift(1)
    }
    if(k > 0){
        if(add ===1){
            result.shift()  
            k = k + 1
        }
        while(k > 0){
            result.unshift(k%10)
            k = Math.floor(k / 10)
        }
    }

    return result
};

在这里插入图片描述

push+reverse的操作要比unshift效率高~

var addToArrayForm = function(num, k) {
    let result = []
    let len = num.length
    
    for(let i = len - 1; i >= 0; i--){
        let sum = num[i] + k % 10
        k = Math.floor(k/10)
        if(sum >= 10){
            k++
            sum -= 10
        }
        result.push(sum)
    }

    while(k > 0){
        result.push(k % 10)
        k = Math.floor(k/10)
    }

    result.reverse()

    return result
};

在这里插入图片描述

直接将数组中的数字加到k上来，然后将k的个位加到结果数组中

var addToArrayForm = function(num, k) {
    let result = []
    let len = num.length
    for(let i = len - 1; i >= 0 || k > 0; i--, k = Math.floor(k/10)){
        if(i >= 0){
            k += num[i]
        }
        result.push(k % 10)
    }
    result.reverse()
    return result
};

在这里插入图片描述

# 1480. 一维数组的动态和

给你一个数组 nums 。数组「动态和」的计算公式为：runningSum[i] = sum(nums[0]…nums[i]) 。请返回 nums 的动态和。

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var runningSum = function(nums) {
    let result = []
    let n = 0
    for(let i = 0; i < nums.length; i++){
        result.push(nums[i] + n)
        n = result[i]
    }
    return result
};

在这里插入图片描述可以直接原地修改数组

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var runningSum = function(nums) {
    for(let i = 1; i < nums.length; i++){
        nums[i] = nums[i] + nums[i-1]
    }
    return nums
};

在这里插入图片描述

# 1588. 所有奇数长度子数组的和

https://leetcode-cn.com/problems/sum-of-all-odd-length-subarrays/

给你一个正整数数组 arr ，请你计算所有可能的奇数长度子数组的和。子数组定义为原数组中的一个连续子序列。请你返回 arr 中所有奇数长度子数组的和。

/**
 * @param {number[]} arr
 * @return {number}
 */
var sumOddLengthSubarrays = function(arr) {
    let result = 0
    for(let i = 0; i < arr.length; i++){
        let sum = 0
        for(let j = i; j < arr.length; j++){
            sum += arr[j]
            if((j - i)%2 === 0){
                result += sum
            }
        }
    }

    return result
};

在这里插入图片描述

# 字符串类

# 3. 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

# 【解法一】暴力遍历 + Set

最快想到的就是暴力遍历，以每个字符串为开头遍历一遍也就是总共要遍历两遍

function lengthOfLongestSubstring(s) {
  let len = s.length;
  let result = 0;

  for (let i = 0; i < len; i++) {
    let set = new Set();
    let maxLen = 0;
    // 从i的位置遍历得到最长子串的长度
    let j = i;
    while (j < len && !set.has(s[j])) {
      set.add(s[j]);
      maxLen++;
      j++;
    }
    // 取历史最大值
    result = Math.max(result, maxLen);
  }
  return result;
}

在这里插入图片描述

# 【解法二】滑动窗口

这是官方题解的答案，其实不是特别清晰

function lengthOfLongestSubstring(s) {
  let len = s.length;
  let result = 0;
  let set = new Set();
  // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
  let j = -1;
  
  for (let i = 0; i < len; i++) {
    if (i !== 0) {
      // 左指针向右移动一格，移除一个字符
      set.delete(s[i - 1]);
    }
    while (j + 1 < len && !set.has(s[j + 1])) {
      // 不断地移动右指针
      set.add(s[j + 1]);
      j++;
    }
    // 第 i 到 j 个字符是一个极长的无重复字符子串
    result = Math.max(result, j - i + 1);
  }
  return result;
}

在这里插入图片描述

# 【解法三】双指针 - 滑动窗口（这种写法通俗易懂）

其实可以通过观察可以优化，我们制作一个窗口，让窗口中的字符串满足题目要求（无重复）怎么让他满足要求呢？那就要滑动窗口了，循环去掉左边第一个元素，直到窗口中元素无重复，此时再扩大窗口

滑动窗口有两个关键点：扩张 + 收缩首先（右指针）扩张到滑动窗口不满足条件的时候暂停，（左指针）开始收缩窗口，让窗口满足条件后再进行扩张（右指针）

function lengthOfLongestSubstring(s) {
  let len = s.length;
  let result = 0;

  let set = new Set();
  // 左指针用来收缩窗口
  let left = 0;
  // 右指针用来扩张窗口
  let right = 0;

  while (left < len) {
    // 如果不重复，就不断扩张窗口，元素添加到set中
    while (right < len && !set.has(s[right])) {
      set.add(s[right]);
      right++;
    }
    // 到这里说明有元素重复了，先记录子串长度，然后收缩窗口
    result = Math.max(result, right - left);
    // 收缩窗口
    set.delete(s[left]);
    left++;
  }
  return result;
}

在这里插入图片描述

# 14. 最长公共前缀

https://leetcode-cn.com/problems/longest-common-prefix/

# 【解法一】横向扫描

在这里插入图片描述

var longestCommonPrefix = function (strs) {
  let result = strs[0];
  for (let i = 1; i < strs.length; i++) {
    result = LCP(result, strs[i]);
    if (result === "") {
      return result;
    }
  }
  return result;
};

function LCP(str1, str2) {
  let i = 0;
  for (i = 0; i < str1.length && i < str2.length; i++) {
    if (str1[i] !== str2[i]) {
      break;
    }
  }
  return str1.substr(0, i);
}

# 【解法二】纵向扫描

在这里插入图片描述

在这里插入代码片

# 【解法三】分治法

在这里插入图片描述

在这里插入代码片

# 20. 有效的括号

都是一个思想，形式不同罢了

# 【解法一】暴力栈

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    let stack = [];
    for(let i = 0; i< s.length; i++){
        if(s[i] === '(' || s[i] === '{' || s[i] === '['){
            stack.push(s[i]);
        }else if (s[i] === ')'){
            if(stack.pop() !== '('){
                return false;
            }
        }else if(s[i] === ']'){
            if(stack.pop() !== '['){
                return false;
            }
        }else if(s[i] === '}'){
            if(stack.pop() !== '{'){
                return false;
            }
        }
    }
    if(stack.length === 0){
        return true;
    }else{
        return false;
    }
};

# 【解法二】用map

# 【解法三】用swtich语句

# 165. 比较版本号

/**
 * @param {string} version1
 * @param {string} version2
 * @return {number}
 */
var compareVersion = function(version1, version2) {
    let v1 = version1.split('.')
    let v2 = version2.split('.')
    let len = Math.max(v1.length, v2.length)
    for(let i = 0; i < len; i++){
        if(v1[i] === undefined) v1[i] = 0
        if(v2[i] === undefined) v2[i] = 0
        if(+v1[i] > +v2[i]) return 1
        if(+v1[i] < +v2[i]) return -1
    }
    return 0
};

在这里插入图片描述

# 345. 反转字符串中的元音字母

https://leetcode-cn.com/problems/reverse-vowels-of-a-string/ (opens new window)

编写一个函数，以字符串作为输入，反转该字符串中的元音字母。

/**
 * @param {string} s
 * @return {string}
 */
var reverseVowels = function (s) {
  let arr = Array.from(s);
  let i = 0;
  let j = arr.length - 1;
  while (i < j) {
    if (!isVowel(arr[i])) {
      i++;
      continue;
    }
    if (!isVowel(arr[j])) {
      j--;
      continue;
    }
    swap(arr, i, j);
    i++;
    j--;
  }
  return arr.join("");
};

function swap(nums, i, j) {
  let temp = nums[i];
  nums[i] = nums[j];
  nums[j] = temp;
}

function isVowel(char) {
  return (
    char === "a" ||
    char === "e" ||
    char === "i" ||
    char === "o" ||
    char === "u" ||
    char === "A" ||
    char === "E" ||
    char === "I" ||
    char === "O" ||
    char === "U"
  );
}

利用set

/**
 * @param {string} s
 * @return {string}
 */
var reverseVowels = function(s) {
    let arr = Array.from(s)
    let set = new Set(['a','e','i','o','u','A','E','I','O','U'])
    let i = 0
    let j = arr.length - 1
    while(i < j){
        if(!set.has(arr[i])){
            i++;
            continue;
        }
        if(!set.has(arr[j])){
            j--;
            continue;
        }
        swap(arr, i, j);
        i++;
        j--;
    }
    return arr.join('')
};

function swap(nums, i, j) {
  let temp = nums[i];
  nums[i] = nums[j];
  nums[j] = temp;
}

# 415. 字符串相加

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var addStrings = function(num1, num2) {
    let add = 0
    let i = num1.length - 1
    let j = num2.length - 1
    let result = []
    while(i >= 0 || j >= 0 || add !== 0){
        let x = num1[i] ? +num1[i] : 0
        let y = num2[j] ? +num2[j] : 0 
        let res = x + y + add
        result.push(res % 10)
        add = ~~(res / 10)
        i--
        j--
    }
    return result.reverse().join('')
};

在这里插入图片描述注意，这里不适用unshift 而是使用 push + reverse 是效率的考量才这样的

# 剑指 Offer 50. 第一个只出现一次的字符

https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

/**
 * @param {string} s
 * @return {character}
 */
var firstUniqChar = function(s) {
    let map = new Map()
    for(let i = 0; i < s.length; i++){
        if(map.has(s[i])){
            map.set(s[i], -1)
        }else{
            map.set(s[i], 1)
        }
    }
    for(let m of map){
        if(m[1] === 1){
            return m[0]
        }
    }
    return " "
};

在这里插入图片描述

# 1221. 分割平衡字符串

在一个平衡字符串中，'L' 和 'R' 字符的数量是相同的。给你一个平衡字符串 s，请你将它分割成尽可能多的平衡字符串。注意：分割得到的每个字符串都必须是平衡字符串。返回可以通过分割得到的平衡字符串的最大数量。

/**
 * @param {string} s
 * @return {number}
 */
var balancedStringSplit = function(s) {
     let balance = 0
     let result = 0
     for(let i = 0; i < s.length; i++){
         let char = s[i]
         if(char === 'L'){
             balance++
         }else{
             balance--
         }
         if(balance === 0){
             result++
         }
     }
     return result
};

在这里插入图片描述

斐波那契链表

YK菌

# 数字类

# 7. 整数反转（简单）

# 【解法一】反转字符串

# 【解法二】商与余数

# 【技巧】~~取整（舍去小数位）

# 【技巧】Math.floor() 向下取整

# 13. 罗马数字转整数（简单）

# 【解法一】Map

# 【解法二】switch

# 【技巧】巧用switch语句

# 50. Pow(x, n) （中等）

# 【解法一】快速幂前处理

# 【解法二】快速幂后处理

# 数组类

# 1. 两数之和（简单）

# 【解法一】两层循环 - 暴力查找

# 【解法二】一层循环 - Map

# 【技巧】map

# 【坑】注意题目条件 不可以取两次自己的下标

# 11. 盛最多水的容器（中等）

# 【解法】双指针

# 26. 删除有序数组中的重复项【简单】

# 【解法一】快慢指针

# 【解法二】双指针

# 27. 移除元素【简单】

# 【解法】快慢指针

# 【解法二】对撞指针

# 53. 最大子序和【简单】

# 【解法】动态规划

# 54. 螺旋矩阵

# 75. 颜色分类【中等】

# 【解法一】两次遍历

# 【解法二】两层循环 冒泡排序

# 【解法三】遍历一次 + 循环不变量【重点】

# 80. 删除有序数组中的重复项 II【中等】

# 【解法】快慢指针

# 88. 合并两个有序数组【简单】

# 118. 杨辉三角

# 【解法】双层循环

# 121. 买卖股票的最佳时机

# 【解法一】暴力解法 不通过

# 【解法二】类似动态规划

# 167. 两数之和 II - 输入有序数组【简单】

# 【解法一】两层循环-暴力查找

# 【解法二】头尾指针 - 对撞指针

# 215. 数组中的第K个最大元素【中等】

# 【解法】划分 + 二分查找

# 283. 移动零【简单】

# 【解法一】快慢指针 + 两次遍历

# 【解法二】快慢指针 + 一次遍历 + 交换元素

# 704. 二分查找

# 【解法】头尾指针

# 278. 第一个错误的版本

# 【解法】二分查找

# 剑指 Offer 09. 用两个栈实现队列

# 989. 数组形式的整数加法

# 1480. 一维数组的动态和

# 1588. 所有奇数长度子数组的和

# 字符串类

# 3. 无重复字符的最长子串

# 【解法一】暴力遍历 + Set

# 【解法二】滑动窗口

# 【解法三】双指针 - 滑动窗口（这种写法通俗易懂）

# 14. 最长公共前缀

# 【解法一】横向扫描

# 【解法二】纵向扫描

# 【解法三】分治法

# 20. 有效的括号

# 【解法一】暴力 栈

# 【解法二】用map

# 【解法三】用swtich语句

# 165. 比较版本号

# 345. 反转字符串中的元音字母

# 415. 字符串相加

# 剑指 Offer 50. 第一个只出现一次的字符

# 1221. 分割平衡字符串

# 【技巧】`~~`取整（舍去小数位）

# 【技巧】`Math.floor()` 向下取整

# 【技巧】巧用`switch`语句

# 【坑】注意题目条件不可以取两次自己的下标

# 【解法二】两层循环冒泡排序

# 【解法一】暴力解法不通过

# 【解法一】暴力栈