LeetCode刷题笔记
发表更新学习笔记2 小时读完 (大约15702个字)0次访问

LeetCode刷题笔记

  • 最近在学习JavaScript，刷题也用顺便巩固，两全其美。

简单题

罗马数字转整数

  • 思路
    • 通常情况下，罗马数字中小的数字在大的数字的右边。若输入的字符串满足该情况，那么可以将每个字符视作一个单独的值，累加每个字符对应的数值即可。
    • 若存在小的数字在大的数字的左边的情况，根据规则需要减去小的数字。对于这种情况，我们也可以将每个字符视作一个单独的值，若一个数字右侧的数字比它大，则将该数字的符号取反。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    // 声明对象，存储罗马数字对应的整数值
    let romanOBJ={
        'M' : 1000,
        'D' : 500,
        'C' : 100,
        'L' : 50,
        'X' : 10,
        'V' : 5,
        'I' : 1,
    };

    let result = 0;

    // 遍历源字符串
    for (let i = 0; i < s.length; ++i) {
        const value = romanOBJ[s[i]];
        // 值小的罗马数字在前则减，否则加
        if (i <  s.length-1 && value < romanOBJ[s[i + 1]]) {
            result -= value;
        } else {
            result += value;
        }
    }
    return result;
};

最长公共前缀

  • 描述
    • 编写一个函数来查找字符串数组中的最长公共前缀。
    • 如果不存在公共前缀，返回空字符串""。
  • 思路
    • 纵向扫描
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function (strs) {
    let i = 0, j = 0;
    // 需要一个标指记录内层循环是正常结束还是不匹配后的break出来的
    let flag = false;
    // 找出最短的字符串长度 以此为行最大扫描长度
    let n = strs.reduce((max, current) => 
    max < current.length ? current.length : max, 0);
    if (n === 0) {
        return "";
    }
    for (j = 0; j < n; j++) {
        for (i = 0; i < strs.length - 1; i++) {
            if (strs[i][j] === strs[i + 1][j]) {  // 匹配成功继续下一轮循环
                continue;
            } else {  // 匹配失败结束循环（此时j的值是最近一次成功的下标）
                flag = true;
                break;
            }
        }
        if (flag) {   // flag === true说明匹配结束，否则进行下一个字符的匹配
            return strs[0].slice(0, j);
        }
    }
    // 这里的返回表示全部匹配成功（几个字符串完全一样）
    return strs[0].slice(0, n + 1);
};
  • 改进版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var longestCommonPrefix = function(strs) {
    if (strs.length == 0) return "";
    // 行列下标范围
    const rows = strs.length;
    const cols = strs[0].length; 

    for (let i = 0; i < cols; i++) {
        const firstChar = strs[0][i];   // 首行 i 列字符（以首行字符串为基准比较）
        for (let j = 1; j < rows; j++) {
            // 如果第 j 行字符串的长度 === i（此时j行的字符串最短，即最长公共前缀）
            // 或 字符不匹配（说明最长前缀已经找到）
            // 此时 i 即最长前缀下标结束位置
            if (strs[j].length == i || strs[j][i] != firstChar) {
                return strs[0].substr(0, i);
            }
        }
    }
    // 若前面循环没有 return 说明第一行字符串肯定是最长公共前缀
    return strs[0];
};

有效的括号

  • 描述
    • 给定一个只包括'('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
    • 有效字符串需满足：
      • 左括号必须用相同类型的右括号闭合。
      • 左括号必须以正确的顺序闭合。
  • 思路
    • 栈
    • 遍历字符串，遇左括号入栈，遇右括号进行匹配校验，匹配成功出栈，失败返回false。
    • 遍历完毕，栈为空（说明全部匹配）则返回true，栈不空（说明有括号”落单“）返回false。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
  let stack = [];
  let i = 0;
  while (i < s.length) {
    if (s[i] === '(' || s[i] === '[' || s[i] === '{') {
      stack.push(s[i]);
      i++;
    } else {
      if (s[i] === ')') {
        // 注意这里当栈中无元素时，前面表达式值为undefined也不与 '(' 相等
        // 正好考虑到了这种情况（其他语言可能出现语法错误 最好加上一个stack不为空的判断条件）
        // 即 stack.length!==0 && stack[stk.length-1]==='('
        if (stack.slice(-1)[0] === '(') { // 也可以用stack[stack.length - 1]
          stack.pop();
          i++;
        } else {
          return false;
        }
      } else if (s[i] === ']') {
        if (stack.slice(-1)[0] === '[') {
          stack.pop();
          i++;
        } else {
          return false;
        }
      } else if (s[i] === '}') {
        if (stack.slice(-1)[0] === '{') {
          stack.pop();
          i++;
        } else {
          return false;
        }
      }
    }
  }
  if (stack.length === 0) {
    return true;
  } else {
    return false;
  }
};
  • 改进（哈希）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var isValid = function(s) {
    let m =s.length
    if(m%2!==0) return false  // 奇数个括号肯定不匹配
    let map =new Map([
        ['{','}'],
        ['(',')'],
        ['[',']']
    ])
    let stk=[]
    for(ch of s){
        if(map.has(ch)){  // 左括号进栈
            stk.push(ch)
        }else{  // 右括号进行匹配校验
        // stk.length === 0 说明栈中无左括号，也是不匹配的一种情况
        //（其实可以不写，因为stk为空的话那么前面的表达式值为 undefined）
            if(map.get(stk[stk.length-1])!==ch || stk.length===0) return false
            else stk.pop()
        }
    }
    if(stk.length==0) return true
    else return false
};

移除元素

  • 描述
    • 给你一个数组nums和一个值val，你需要原地移除所有数值等于val的元素，并返回移除后数组的新长度。
    • 不要使用额外的数组空间，你必须仅使用O(1)额外空间并 原地 修改输入数组。
    • 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
  • 思路
    • 遍历 + splice()，此法有点流氓，我猜不是题目考察本意。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    let i = 0;
    // 必须用 nums.length而不能提前赋值个变量
    // 因为删除过程中长度是变化的
    while(i < nums.length){
        if(val === nums[i]){
            nums.splice(i,1);
            i--;  // 删除之后指针回溯一位
        }
        i++;
    }
    return nums.length;
};
  • 官方解法
  • 思路（双指针）
    • 右指针right指向当前将要处理的元素，左指针left指向下一个将要赋值的位置。
    • 如果右指针指向的元素不等于val，它一定是输出数组的一个元素，我们就将右指针指向的元素复制到左指针位置，然后将左右指针同时右移；
    • 如果右指针指向的元素等于val，它不能在输出数组里，此时左指针不动，右指针右移一位。
    • 最后返回left即是数组应当输出得到长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
var removeElement = function(nums, val) {
    let left = 0;
    let right = 0;
    while(right < nums.length){
        if(nums[right] === val){
            right++;
        }else{
            nums[left] = nums[right];
            left++;
            right++;
        }
    }
    return left;
};

搜索插入位置

  • 描述
    • 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
    • 请必须使用时间复杂度为$O(log_n)$的算法。
  • 思路
    • 有序且要求时间复杂度 -> 二分查找。
    • 需要注意的是，查找失败时应该返回的下标是right + 1 或 left（循环结束条件为left <= right时）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    while(left <= right){
        let mid = Math.floor((left+right)/2);
        if(nums[mid] === target){
            return mid;
        }else if(nums[mid] < target){
            left = mid + 1;
        }else{
            right = mid -1;
        }
    }
    return right + 1;
    /* 根据if的判断条件，left左边的值一直保持小于target，right右边的值一直保持大于等于target，而且left最终一定等于right+1;
    这么一来，循环结束后，在left和right之间画一条竖线，恰好可以把数组分为两部分：
    left左边的部分和right右边的部分，而且left左边的部分全部小于target，并以right结尾；
    right右边的部分全部大于等于target，并以left为首。所以最终答案一定在left的位置。
    */
};

最大子数组和

  • 描述
    • 给你一个整数数组nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
    • 子数组是数组中的一个连续部分。
  • 思路（贪心）
    • 从左向右迭代，一个个数字加过去如果tempSum < 0, 那说明加上它只会变得越来越小, 所以我们将tempSum置零后重新开始找子序串。
    • 在迭代的过程中要注意，我们需要用maxSum来不断维持当前的最大子序和, 因为maxSum的值是在不断更新的, 所以我们要及时记录下它的最大值。
    • 有一个注意点是: 当数组全是负数的时候其实是没有问题的。因为在tempSum不断遍历的过程中, 早已将最大值不断传给maxSum，即使tempSum一直是负数被不断置零也不用担心，maxSum还是会记录下最大的那个负数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let maxSum = -Infinity;
    let tempSum = 0;
    for(let i = 0; i < nums.length; i++){
        tempSum += nums[i];
        maxSum = Math.max(tempSum, maxSum);
        if(tempSum < 0){
            tempSum = 0;
        }
    }
    return maxSum;
};
  • 思路（动态规划）
    • 略

最后一个单词的长度

  • 描述
    • 给你一个字符串s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中最后一个单词的长度。
    • 单词是指仅由字母组成、不包含任何空格字符的最大子字符串。
  • 思路
    • 反向遍历，忽略尾部的空格，找到最后一个单词。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLastWord = function(s) {
    let n = s.length;
    let lastWLen = 0;
    let flag = false; // 记录是否遍历到非“空格“的标识
    for(let i = n-1; i >= 0; i--){
        if(s[i] === ' ' && !flag){  // 此处匹配的是末尾的“空格”字符
            continue;
        }else if(s[i] === ' ' && flag){ // 此处匹配的是末尾单词前一个空格
            return lastWLen;
        }else{  // 此处匹配的是单词字符
            lastWLen++;
            flag = true;
        }
    }
    return lastWLen;  // 注意：若末尾没有空格应当在此处返回，否则函数将无返回值
};
  • 简化（实际上lastWLen本身就可以作为flag）
1
2
3
4
5
6
7
8
9
10
11
var lengthOfLastWord = function(s) {
    let lastWLen = 0;
    for(let i = s.length - 1;i >= 0; i--) {
        if(s.charAt(i) === ' ' && lastWLen) { // lastWLen !== 0 表示已经遍历到末尾单词前一个空格
            break;
        } else if(s.charAt(i) !== ' ') {
            lastWLen++;
        }
    }
    return lastWLen;
};
  • 思路（内置方法）
1
2
3
4
5
6
7
8
var lengthOfLastWord = function(s) {
    return s.trim().split(' ').reverse()[0].length;
};

var lengthOfLastWord = function(s) {
    let arr = s.trim().split(' ');
    return arr[arr.length-1].length;
};

二进制求和

  • 描述
    • 给你两个二进制字符串，返回它们的和（用二进制表示）。
    • 输入为非空字符串且只包含数字1和0。
  • 思路（模拟）
    • 长度不同则补零
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function(num1, num2) {
    let res = '';
    let i1 = num1.length - 1;
    let i2 = num2.length - 1;
    let carry = 0;
    while (i1 >= 0 || i2 >= 0) {
      // 补零操作
        const x = i1 >= 0 ? num1[i1] - '0' : 0;
        const y = i2 >= 0 ? num2[i2] - '0' : 0;

        const sum = x + y + carry;
        res += (sum % 2);
        carry = Math.floor(sum / 2);

        i1--;
        i2--;
    }
    if (carry) res += carry;
    // res = res + ... 需要反转
    // 可以改成 res = ... + res
    return res.split("").reverse().join("");
};
};

x 的平方根

  • 描述
    • 给你一个非负整数x，计算并返回x的 算术平方根 。
    • 由于返回类型是整数，结果只保留整数部分 ，小数部分将被舍去。
  • 思路
    • 找出刚好小于或等于x的i*i。
    • 穷举
    • 二分查找
      • 查找范围为[0,x]的一个单调递增数组，找出第一个小于等于x的值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    for(let i =0; i <= x; i++){
        let leftNum = i*i;
        let rightNum = (i+1)*(i+1);
        if(leftNum === x){
            return i;
        }else if( leftNum < x && rightNum > x){
            return i;
        }
    }
};

var mySqrt = function(x) {
    for(let i =0; i <= x; i++){
        if(i*i > x){
            return i-1;
        }
    }
    return x; // x === 0 的情况
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var mySqrt = function(x) {
    let left = 0;
    let right = x;
    while(left <= right){
        // const mid = Math.floor((left + right)/2);
        const mid = (left + right) >> 1;  // 移位运算相当于除以 2 取整
        if(mid * mid === x){
            return mid;
        }else if(mid * mid < x){
            left = mid + 1;
        }else{
            right = mid -1;
        }
    }
    // 退出循环后，left 在 right的右边（紧邻）
    // left 指向比目标数大的最小值
    // 而 right 指向比目标值小的最大值
    // 即 left 及 left 之右都是比目标值大的
    // right 及 right 之左都是比目标值小的
    return right;
};

爬楼梯

  • 描述
    • 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
    • 每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？
  • 思路
    • 一般递归（超时）
    • 带记录的递归（保存已计算过的阶）
    • 动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if(n===2){
        return 2;
    }
    if(n===1){
        return 1;
    }
    return climbStairs(n-1) + climbStairs(n-2);
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 带记录的递归
var climbStairs = function (n) {
  let map = new Map();  // 创建 map 记录递归树结点
  return climbStairsMemo(n, map);
};

let climbStairsMemo = (n, map) => {
  if (map.has(n)) { // 如果已经计算过到该阶的方法数量，直接返回即可
    return map.get(n);
  }
  if (n === 2) {  // 到 2 阶有两种方法
    map.set(n, 2);
  } else if (n === 1) { // 到 1阶有一种方法
    map.set(n, 1);
  } else {
    // 递归调用，并记录到第 n 阶的方法种数  Fn = Fn-1 + Fn-2
    map.set(n, climbStairsMemo(n - 1, map) + climbStairsMemo(n - 2, map));
  }
  return map.get(n);
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// 动态规划

var climbStairs = function (n) {
    let dp = [0,1,2];
    if(n < 3){
        return dp[n];
    }
    for(let i = 3; i <= n; i++){
      dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
};

var climbStairs = function (n) {
    let s1 = 1;
    let s2 = 2;
    if(n < 3){
        return n;
    }
    for(let i = 3; i <= n; i++){
        // let sum = s1 + s2;
        // s1 = s2;
        // s2 = sum;
        s2 = s1 + s2;
        s1 = s2 - s1;
    }
    return s2;
};

// 打表
var climbStairs = function (n) {
    let dp = [0,1,2];
    climbStairsDp(dp,n);
    return dp[n];
};

let climbStairsDp = (dp,n) =>{
    for(let i = 3; i <= n; i++){
      dp[i] = dp[i-1] + dp[i-2];
  }
};

删除排序链表中的重复元素

  • 描述
    • 给定一个已排序的链表的头head， 删除所有重复的元素，使每个元素只出现一次。返回已排序的链表。
  • 思路
    • 双指针（其实可以只用一个指针）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
    let p = head;
    let q = head?.next; // 注意 head可能为空需要 ?.否则执行出错
    while(q){
        if(p.val === q.val){
            p.next = q.next;
            q = q.next;
        }else{
            p = p.next;
            q = q.next;
        }
    }
    return head;
};

var deleteDuplicates = function(head) {
    let p = head;
    while(p?.next){ // 若p为空等价于 提前判断 if(!head) return head; 
        if(p.val === p.next.val){
            p.next = p.next.next;
        }else{
            p = p.next;
        }
    }
    return head;
};

合并两个有序数组

  • 描述
    • 给你两个按 非递减顺序 排列的整数数组nums1和nums2，另有两个整数m和n，分别表示nums1和nums2中的元素数目。
    • 请你合并nums2到nums1中，使合并后的数组同样按非递减顺序排列。
    • 注意：最终，合并后数组不应由函数返回，而是存储在数组nums1中。为了应对这种情况，nums1的初始长度为m + n，其中前m个元素表示应合并的元素，后n个元素为0，应忽略。nums2的长度为n。
  • 思路
    • 双指针 + 辅助数组
    • 先合并再排序
    • 逆向双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * @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 tempArr = [];
    let p = 0;
    let q = 0;
    while(p < m && q < n ){
        if(nums1[p] <= nums2[q]){
            tempArr.push(nums1[p]);
            p++;
        }else{
            tempArr.push(nums2[q]);
            q++;
        }
    }
    if(p === m ){
        tempArr.push(...nums2.slice(q));
    }else{
        tempArr.push(...nums1.slice(p,m));
    }
    nums1.length = 0;   // 清空nums1
    nums1.push(...tempArr);
};
1
2
3
4
var merge = function(nums1, m, nums2, n) {
    nums1.splice(m, nums1.length - m, ...nums2);
    nums1.sort((a, b) => a - b);  // 注意sort()用法
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
var merge = function(nums1, m, nums2, n) {
    let p = m - 1;
    let q = n - 1;
    let r = m + n - 1;
    while(p >= 0 && q >= 0){
        if(nums1[p] > nums2[q]){
            nums1[r--] = nums1[p--];
        }else{
            nums1[r--] = nums2[q--];
        }
    }
    // 若nums1先遍历完，即p < 0，说明nums2还有未遍历完，将nums2剩余数复制至nums1
    // 若nums2先遍历完，虽然nums1未遍历完但已经有序且在结果数组（nums1）中，不用调整
    if(p < 0){
        while(r >= 0){
            nums1[r--] = nums2[q--];
        }
    }
};

var merge = function(nums1, m, nums2, n) {
    let p1 = m - 1, p2 = n - 1;
    let tail = m + n - 1;
    var cur;
    while (p1 >= 0 || p2 >= 0) {
        if (p1 === -1) {
            cur = nums2[p2--];
        } else if (p2 === -1) {
            cur = nums1[p1--];
        } else if (nums1[p1] > nums2[p2]) {
            cur = nums1[p1--];
        } else {
            cur = nums2[p2--];
        }
        nums1[tail--] = cur;
    }
};

二叉树的中序遍历

  • 描述
    • 给定一个二叉树的根节点root，返回它的中序遍历。
  • 思路（递归）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    let arr = [];
    inorderTraversalCall(root, arr);
    return arr;
};

let inorderTraversalCall = (root, arr) => {
    if(!root){
        return ;
    }
    inorderTraversalCall(root.left,arr);
    arr.push(root.val);
    inorderTraversalCall(root.right,arr);
}

相同的树

  • 描述
    • 给你两棵二叉树的根节点p和q，编写一个函数来检验这两棵树是否相同。
    • 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
  • 思路
    • DFS
    • BFS
    • 骚操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// DFS
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    if (!p && !q) {
        return true
    } else if (!p || !q) {
        return false
    } else if (p.val !== q.val) {
        return false
    } else {
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
    }
};
1
2
3
4
// 骚操作 判断两个 js 对象是否相等
var isSameTree = function(p, q) {
    return JSON.stringify(p) === JSON.stringify(q)
};

中等题

无重复字符的最长子串

  • 描述
    • 给定一个字符串s，请你找出其中不含有重复字符的最长子串的长度。
  • 思路（双指针 + Set）
    • 一个指针遍历，另一个指针记录回溯位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let p = 0;
    let q = p + 1 ;
    let maxCount = 0;
    let set = new Set();
    while(p < s.length){
        if(set.has(s[p])){
            maxCount = Math.max(maxCount, set.size);
            set.clear();
            p = q;
            q++;
        }else{
            set.add(s[p]);
            p++;
        }
    }
    // 这一步不能少，因为存在 1.整个字符串无重复 2.最尾端的无重复子串最长 的情况
    // 以上两种情况 set.has(s[p])为 false 因此不会进入 if 因此不会被记录需要在此进行记录
    maxCount = Math.max(maxCount, set.size);  // 当然也可将其放入循环尾部，并删除上面的赋值操作
    return maxCount;
};
  • 思路（滑动窗口）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var lengthOfLongestSubstring = function (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;
};

最长回文子串

  • 描述
    • 给你一个字符串s，找到s中最长的回文子串。]
  • 思路
    • 首先，找到源串中的所有回文串，然后，截取最长的即可。
    • 如何找：
      • 找到源串中头尾相同的子串。
      • 用判断回文串的方法（双指针）判断该子串和是否为回文串。
      • 若是，则与之前找到的回文串比较长度，更长则更新maxStr和maxLen。
      • 否则，换下一子串继续第二步。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
  // 设置两指针用来分别指向相同的两元素
  let p;
  let q;
  let maxStr = s[0];  // 记录最长回文串
  let maxLen = 1; // 记录最长回文串长度
  // 遍历寻找两个相同元素
  for (let i = 0; i < s.length; i++) {
    for (let j = i + 1; j < s.length; j++) {
      if (s[i] === s[j]) {
        // recp、recq 记录两个相同元素下标方便以后截取
        let recp = p = i;
        let recq = q = j;
        let tempLen = q - p + 1;  // 暂时记录 p、q之间的串长度（可能不是回文串）
        while (p < q) { // 判断是否为回文串
          if (s[++p] === s[--q]) {
            continue;
          } else {
            tempLen = 0;  // 不是回文串则将长度置 0（maxLen一定 > 0，因此此串（非回文串）不会被记录）
            break;
          }
        }
        if (maxLen < tempLen) { // maxLen < tempLen 说明上一次while处理结果一定是回文串，且是比之前长的回文串
          maxStr = s.slice(recp, recq + 1);
          maxLen = tempLen;
        }
      }
    }
  }
  return maxStr;

Z 字形变换

  • 描述
    • 将一个给定字符串s根据给定的行数numRows，以从上往下、从左到右进行Z字形排列。
  • 思路
    • 模拟
    • 数学规律
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var convert = function (s, numRows) {
  if (numRows == 1) return s;   // 注意一行时有点特殊（没有拐角）
  let resStr = '';
  let flag = 1;   // 1表示向下，-1表示向上 
  let arr = Array.from(new Array(numRows), () => new Array());
  let curRow = 0;
  for (let i = 0; i < s.length; i++) {
    if (curRow > numRows - 1) {
      flag = -1;
      curRow -= 2;
    } else if (curRow < 0) {
      flag = 1;
      curRow += 2;
    }
    if (curRow <= numRows - 1 && flag === 1) {
      arr[curRow++].push(s[i]);
    } else if (curRow >= 0 && flag === -1) {
      arr[curRow--].push(s[i]);
    }
  }
  for (let item of arr) {
    resStr += item.join('');
  }
  return resStr;
};
  • 改进（模拟）
    • 妙用flag
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var convert = function (s, numRows) {
  // flag作为每一次扫描到顶（底）的标指（-1为顶 1为底）
  // 同时作为下标递增（减）的计算参数
  let flag = -1;
  let i = 0;
  let resStrArr = new Array(numRows).fill('');
  if (numRows === 1) {
    return s;
  }
  for (let c of s) {
    resStrArr[i] += c;
    if (i === 0 || i === numRows - 1) {
      flag = -flag;
    }
    i += flag;
  }
  return resStrArr.join('');
};

盛最多水的容器

  • 描述
    • 给定一个长度为n的整数数组height。有n条垂线，第i条线的两个端点是(i, 0)和(i, height[i])。
    • 找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。
  • 思路
    • 暴力搜索（超时）
    • 双指针
      • 每次移动指向高度较小的指针，面积才有可能大于之前的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
  let maxArea = 0;
  for(let i = 0; i < height.length - 1; i++){
      for(let j = i +1; j < height.length; j++){
          if(height[i] > height[j]){
              maxArea = Math.max(height[j]*(j-i), maxArea);
          }else{
              maxArea = Math.max(height[i]*(j-i), maxArea);
          }
      }
  }
  return maxArea;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    let maxArea = 0;
    let left = 0;
    let right = height.length - 1;
    while(left < right){
        if(height[left] < height[right]){
            maxArea = Math.max(maxArea, height[left]*(right-left));
            left++;
        }else{
            maxArea = Math.max(maxArea, height[right]*(right-left));
            right--;
        }
    }
    return maxArea;
};

整数转罗马数字

  • 描述
    • 给你一个整数，将其转为罗马数字。
  • 思路
    • 模拟（模拟）
    • 根据罗马数字的唯一表示法，为了表示一个给定的整数num，我们寻找不超过num的最大符号值，将num减去该符号值，然后继续寻找不超过num的最大符号值，将该符号拼接在上一个找到的符号之后，循环直至num为0。最后得到的字符串即为num的罗马数字表示。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {number} num
 * @return {string}
 */
var intToRoman = function(num) {
  // let romanOBJ =
  // {1000: 'M', 900: 'CM', 500: 'D', 400: 'CD', 100: 'C',
  // 90: 'XC', 50: 'L', 40: 'XL', 10: 'X', 9: 'IX', 5:'V', 4:'IV', 1:'I'};
  // js中一般对象属性（键）在不同环境下顺序不同，不一定是按照定义顺序输出（一般升序）
  // 且属性会自动转化为字符串，因此使用数组

  let romanArr = [[1000, "M"], [900, "CM"], [500, "D"], [400, "CD"], [100, "C"], [90, "XC"], [50, "L"], [40, "XL"], [10, "X"], [9, "IX"], [5, "V"], [4, "IV"], [1, "I"]];
  let resStr = '';
  for(let [val,roman] of romanArr){
      while(num >= val){
          resStr += roman;
          num -= val;
      }
  }
  return resStr;
};

三数之和

  • 描述
    • 给你一个包含n个整数的数组nums，判断nums中是否存在三个元素a，b，c ，使得a + b + c = 0 ？请你找出所有和为0且不重复的三元组。
  • 思路
    • 暴力搜索
      • 略
    • 排序 + 双指针
      • 将排好序的数组，依次以某一元素为基准（并去除重复），剩下的元素进行two sum操作（也要去重）。
      • 有序的tow sum：相加之和小于目标值，左指针left++，相加之和大于于目标值右指针right--。
      • 其实相当于三指针，只是指针i是依次从左向右移动而已。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
  if (nums.length < 3) {
    return [];
  }
  nums.sort((a,b) => a-b);
  // 最小值大于 0 或者 最大值小于 0，说明没有无效答案
  if (nums[0] > 0 || nums[nums.length - 1] < 0) {
    return [];
  }
  const n = nums.length;
  const res = [];
  for (let i = 0; i < n; i++) {
    // 如果当前值大于 0，和右侧的值再怎么加也不会等于 0，所以直接退出
    if (nums[i] > 0) {
      return res;
    }
    // 当前循环的值和上次循环的一样，就跳过，避免重复值
    if (i > 0 && nums[i] === nums[i - 1]) {
      continue;
    }
    // 双指针(two sum)
    let l = i + 1;
    let r = n - 1;
    while(l < r) {
      const temp = nums[i] + nums[l] + nums[r];
      if (temp > 0) {
        r--;
      }
      if (temp < 0) {
        l++;
      }
      if (temp === 0) {
        res.push([nums[i], nums[l], nums[r]]);
        // 跳过重复值
        while(l < r && nums[l] === nums[l + 1]) {
          l++;
        }
        // 同上
        while(l < r && nums[r] === nums[r - 1]) {
          r--;
        }
        l++;
        r--;
      }
    }
  }
  return res;
};

最接近的三数之和

  • 描述
    • 给你一个长度为n的整数数组nums和一个目标值target。请你从nums中选出三个整数，使它们的和与target最接近。
    • 返回这三个数的和。
  • 思路
    • 排序 + 双指针
      • 三之和稍微变化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function(nums, target) {
    nums.sort((a,b) => a-b);
    let res = Infinity; // 结果，且过程中保存上一次的最接近值
    for(let i = 0; i < nums.length; i++){
        let left = i+1;
        let right = nums.length - 1;
        while(left < right){
            let sum = nums[i] + nums[left] + nums[right]; // 当前sum
            if(sum < target){
                left++;
            }else if(sum > target){
                right--;
            }else{  // 有a+b+c=0则直接返回target
                return target;
            }
            // 如果上一次的最接近值与目标值之差的绝对值 ＞ 当前值与目标值之差的绝对值
            // 则更新最接近值
            if(Math.abs(res - target) > Math.abs(sum - target)){
                res = sum;
            }
        }
    }
    return res;
};

电话号码的字母组合

  • 描述
    • 给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。
    • 给出数字到字母的映射如下（与电话按键相同）。
    • 注意1不对应任何字母。
  • 思路
    • 递推组合（广度优先-非标准）
      • 例如：输入"23456"，可先将2和3进行组合，然后保存这个中间结果res。
      • 然后，再将res与4进行组合，再保存至res…
      • 直到把最后一个6组合完毕，则res即最终结果。
    • 递归回溯（深度优先）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
var letterCombinations = function (digits) {
  // 为空特殊处理
  if (digits.length === 0) return [];
  let numMap = new Map([
    ['0', ''],
    ['1', ''],
    ['2', 'abc'],
    ['3', 'def'],
    ['4', 'ghi'],
    ['5', 'jkl'],
    ['6', 'mno'],
    ['7', 'pqrs'],
    ['8', 'tuv'],
    ['9', 'wxyz']
  ])
  let res = [];
  dfs("", digits);
  return res;

  function dfs(str, digit) {
    // 如果字符串为空了，将拼接好的字符加入数组
    if (digit.length === 0) res.push(str);
    else {
      // 拿到字符串第一个字符，拿到其对应的数字
      let numstr = numMap.get(digit[0]);
      // 对可能性进行组合
      for (let i = 0; i < numstr.length; i++) {
        str += numstr[i];
        // 递归组好的 str和下一段字符串
        dfs(str, digit.slice(1))
        // 回溯
        str = str.slice(0, -1);
      }
    }
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
  if(digits === ""){  // 注意考虑为空情况 *****
      return [];
  }
  let arr =  [['a','b','c'],['d','e','f'],['g','h','i'],['j','k','l'],
  ['m','n','o'],['p','q','r','s'],['t','u','v'],['w','x','y','z']];
  // 存储两组字符组第 n 次组合后的结果（初始值为第一个要参与组合的字符组-可看作第 0 次组合结果）
  // 此数组会递推参与组合，每一次保存当前一次组合产生的结果。
  let res = [...arr[+digits[0] - 2]]; // 第 0 个数字对应的符号组（可看作第 0 次组合结果）
  let i = 1; // 数字下标
  while(i < digits.length){ // 当数字遍历完后退出循环
      let row = +digits[i] - 2; // arr 中行号从0开始，而数字从2开始才有效，因此取出数字后 -2确定行号
      let n = res.length;   // 组合前 res 的长度（进入循环长度会随着 push 而增加）
      for(let j = 0; j < n; j++){ // 上一次组合结果构成的数组与新字符组进行组合
          for(let k = 0; k < arr[row].length; k++){
              let combination = res[j] + arr[row][k];
              res.push(combination);
          }
      }
      res.splice(0,n);  // 删除上一次组合的结果，留下最新组合结果
      i++;
  }
  return res;
};

四数之和

  • 描述
    • 给你一个由n个整数组成的数组nums，和一个目标值target。请你找出并返回满足下述全部条件且不重复的四元组[nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）
  • 思路（降维）
    • 将四数之和降为两数之和，套两层循环即可（三数之和套一层）
    • 注意：
      • 判断重复
      • target !== 0时，不能使用 nums[0](nums[n-1]) <(>) target直接返回。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function (nums, target) {
  let n = nums.length;
  if (n < 4) {
    return [];
  }
  nums.sort((a, b) => a - b);
  let res = [];
  for (let i = 0; i < n - 3; i++) { // i 后至少要有 3 位
    while (i - 1 !== -1 && nums[i] === nums[i - 1]) {
      i++;
    }
    for (let j = i + 1; j < n - 2; j++) { // j 后至少要有 2 位
      while (j - 1 !== i && nums[j] === nums[j - 1]) {
        j++;
      }
      let l = j + 1;
      let r = n - 1;
      while (l < r) {
        let temp = nums[i] + nums[j] + nums[l] + nums[r];
        if (temp < target) {
          l++;
        } else if (temp > target) {
          r--;
        } else if (temp === target) {
          res.push([nums[i], nums[j], nums[l], nums[r]]);
          l++;
          r--;
        }
        while (l - 1 !== j && nums[l] === nums[l - 1]) {
          l++;
        }
        while (r + 1 !== n && nums[r] === nums[r + 1]) {
          r--;
        }
      }
    }
  }
  return res;
};
  • 优化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
var fourSum = function (nums, target) {
  let n = nums.length;
  if (n < 4) {
    return [];
  }
  nums.sort((a, b) => a - b);
  let res = [];
  for (let i = 0; i < n - 3; i++) {
    while (i - 1 !== -1 && nums[i] === nums[i - 1]) {
      i++;
    }
    for (let j = i + 1; j < n -2; j++) {
      while (j - 1 !== i && nums[j] === nums[j - 1]) {
        j++;
      }
      let l = j + 1;
      let r = n - 1;
      while (l < r) {
        let temp = nums[i] + nums[j] + nums[l] + nums[r];
        if (temp < target) {
          l++;
          continue; // (*)
        } else if (temp > target) {
          r--;
          continue; // (*)
        } else if (temp === target) {
          res.push([nums[i], nums[j], nums[l], nums[r]]);
          l++;
          r--;
        }
        while (l < r && nums[l] === nums[l - 1]) { // (*)
          l++;
        }
        while (l < r && nums[r] === nums[r + 1]) { // (*)
          r--;
        }
      }
    }
  }
  return res;
};
  • 代码随想录
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var fourSum = function(nums, target) {
    const len = nums.length;
    if(len < 4) return [];
    nums.sort((a, b) => a - b);
    const res = [];
    for(let i = 0; i < len - 3; i++) {
        // 去重i
        if(i > 0 && nums[i] === nums[i - 1]) continue;
        for(let j = i + 1; j < len - 2; j++) {
            // 去重j
            if(j > i + 1 && nums[j] === nums[j - 1]) continue;
            let l = j + 1, r = len - 1;
            while(l < r) {
                const sum = nums[i] + nums[j] + nums[l] + nums[r];
                if(sum < target) { l++; continue}
                if(sum > target) { r--; continue}
                res.push([nums[i], nums[j], nums[l], nums[r]]);
                while(l < r && nums[l] === nums[++l]);
                while(l < r && nums[r] === nums[--r]);
            }
        } 
    }
    return res;
};

括号生成

  • 描述
    • 数字n代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
  • 思路
    • 首先，可以知道的是，在“拼凑”每一组有效括号的过程中，一定满足：
      • 左括号数小于等于括号的对数（(左括号 + 右括号)/2）
      • 右括号小于等于左括号数（当然也小于等于括号对数）
    • 题目要求生成n对的合法括号序列组合，因此可以考虑使用深度优先搜索，将搜索顺序定义为枚举序列的每一位填什么，那么最终的答案一定是由n个左括号和n个右括号组成。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var generateParenthesis = function (n) {
  let l = 0;    // 左括号已使用数
  let r = 0;    // 右括号已使用数
  let str = ''; // 每一次成功匹配的括号组（遍历到叶子结点）
  let res = []; // 结果字符串数组
  dfs(n, l, r, str, res);
  return res;
};

let dfs = (n, l, r, str, res) => {
  if (l == n && r == n) { // 递归出口
    // 可以返回空，重点是将当前成功匹配的括号组字符串加入结果数组
    return res.push(str);
  }
  if (l < n) {  // 剪枝 已加入的左括号数小于括号总数的一半
    dfs(n, l + 1, r, str + '(', res);
  }
  if (r < l) {  // 剪枝 已加入的右括号数小于左括号数（比左括号限制条件强）
    dfs(n, l, r + 1, str + ')', res);
  }
};

两两交换链表中的节点

  • 描述
    • 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题。

  • 思路

    • 迭代
    • 递归

  • 迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
    if(!head || !head.next){
        return head;
    }
    let prehead = new ListNode();
    prehead.next = head;
    let t = prehead;
    let p = head;
    let q = head.next;
    while(q){
        t.next = q;
        p.next = q.next;
        q.next = p;
        t = p;
        p = p.next;
        q = p?.next;
    }
    return prehead.next;
};

var swapPairs = function(head) {
    let prehead = new ListNode();
    prehead.next = head;
    let t = prehead;
    while(t.next!==null && t.next.next !==null){
        const p = t.next;
        const q = t.next.next;
        t.next = q;
        p.next = q.next;
        q.next = p;
        t = p;
    }
    return prehead.next;
};
  • 递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
```

## 初级算法

### [删除有序数组中的重复项](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/)

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

```js
/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
   nums.forEach((value, index, list) => {
       for(let i = index+1; value === list[i]; ){  // 注意此处 i 无需自增，因为删除数组元素后，i 已指向“下一个元素”
           nums.splice(i,1);   // 从 i 开始删除 1 个元素（不能用 delete list[i]，会保留位置）     
       }
   })
   return nums.length;
};
  • 官方解法
    • 思路
      • 由于给定的数组nums是有序的,因此对于任意$i<j$，如果$nums[i]=nums[j]$,则对任意$i≤k≤j$必有$nums[i]=nums[k]=nums[j]$，即相等的元素在数组中的下标一定是连续的。利用数组有序的点,可以通过双指针的方法刪除重复元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var removeDuplicates = function(nums) {
    const n = nums.length;
    if (n === 0) {
        return 0;
    }
    // 快慢指针 （ slow 指向预备改变的位置）
    let fast = 1, slow = 1;
    while (fast < n) {
        // 如果 nums[fast] !== nums[fast - 1]
        // 说明 nums[fast] 和之前的元素都不同
        if (nums[fast] !== nums[fast - 1]) {
            nums[slow] = nums[fast];
            ++slow;
        }
        // nums[slow]改变后 或 遇到相同元素后 fast 都得加 1
        ++fast;
    }
    // 遍历结束之后，从 nums[0] 到 nums[slow−1] 的每个元素都不相同且包含原数组中的每个不同的元素。
    return slow;
};

买卖股票的最佳时机 II

  • 思路（贪心）
    • 股票买卖策略
      • 单独交易日：设今天价格$p_1$、明天价格$p_2$，则今天买入、明天卖出可赚取金额$p_2-p_1$(负值代表亏损）。
      • 连续上涨交易日：
        • 设此上张交易日股票价格分別为$p_1,p_2,…,p_n$，则第一天买最后一天卖收益最大，即$p_n-p_1$。
        • 等价于每天都买卖。
      • 连续下降交易日：则不买卖收益最大,即不会亏钱。
    • 故只需将相邻两天价格差为正的差价加起来，即为最大收益。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let n = prices.length;
    let i = 0, max = 0;

    while(i<n-1){
        if(prices[i]<prices[i+1]){
            max += prices[i+1]-prices[i];
        }
        i++;
    }
    return max;
};

轮转数组

  • 描述
    • 给你一个数组，将数组中的元素向右轮转k个位置，其中k是非负数。
  • 思路
    • 切片连接
1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function(nums, k) {
    // 注意此处 的 -k%nums.length 
    // 当 k > nums.length 时，需要取模
    let arr = nums.splice(-k%nums.length, nums.length+1);
    for(let i = arr.length-1; i >= 0;i--){
        nums.unshift(arr[i]);
    }
};
  • 改进版本
1
2
3
4
5
6
var rotate = function (nums, k) {
    k = k % nums.length;
    // arr.splice()返回被删除的数组
    let temp = nums.splice(-k);
    nums.splice(0, 0, ...temp) // ...ES6扩展运算符
};

存在重复元素

  • 描述

    • 给你一个整数数组nums。如果任一值在数组中出现至少两次，返回true；如果数组中每个元素互不相同，返回false。

  • 思路（超时）

    • 遍历数组后删除对应元素
    • 使用includes()判断是否任然存在该元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function (nums) {
  let flag = false;
  nums.forEach((item, index, array) => {
    let temp = item;
    // array.splice(index, 1);  
    // 不能使用splice删除，因为不会保留位置
    // 而index是根据原数组得来的，会导致删除的元素不对
    delete array[index];
    if (array.includes(temp)) {
      flag = true;
    }
  })
  return flag;
};
  • 思路（排序）
    • 在对数字从小到大排序之后，数组的重复元素一定出现在相邻位置中。
1
2
3
4
5
6
7
8
9
10
var containsDuplicate = function(nums) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    for (let i = 0; i < n - 1; i++) {
        if (nums[i] === nums[i + 1]) {
            return true;
        }
    }
    return false;
};
  • 思路（哈希表）
    • 对于数组中每个元素，将它插入到哈希表中。如果插入一个元素时发现该元素已经存在于哈希表中，则说明存在重复的元素。
1
2
3
4
5
6
7
8
9
10
var containsDuplicate = function(nums) {
    const set = new Set();
    for (const x of nums) {
        if (set.has(x)) {
            return true;
        }
        set.add(x);
    }
    return false;
};

只出现一次的数字

  • 描述
    • 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
    • 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
  • 思路（空间复杂度：$O(n)$）
    • 使用集合存储数字。遍历数组中的每个数字，如果集合中没有该数字，则将该数字加入集合，如果集合中已经有该数字，则将该数字从集合中删除，最后剩下的数字就是只出现一次的数字。
    • 使用哈希表存储每个数字和该数字出现的次数。遍历数组即可得到每个数字出现的次数，并更新哈希表，最后遍历哈希表，得到只出现一次的数字。
    • 使用集合存储数组中出现的所有数字，并计算数组中的元素之和。由于集合保证元素无重复，因此计算集合中的所有元素之和的两倍，即为每个元素出现两次的情况下的元素之和。由于数组中只有一个元素出现一次，其余元素都出现两次，因此用集合中的元素之和的两倍减去数组中的元素之和，剩下的数就是数组中只出现一次的数字。
  • 思路（位运算）
    • 任何数和$0$做异或运算，结果仍然是原来的数，即$a⊕0=a$。
    • 任何数和其自身做异或运算，结果是$0$，即$a⊕a=0$。
    • 异或运算满足交换律和结合律
    • $a⊕b⊕a=b⊕(a⊕a)$
    • $b⊕(a⊕a)=b⊕0=b$
    • 数组中的全部元素的异或运算结果即为数组中只出现一次的数字。
1
2
3
4
5
6
7
8
/**
 * @param {number[]} nums
 * @return {number}
 */
 // 位运算
var singleNumber = function(nums) {
  return nums.reduce((prev, curr) => prev ^ curr);
};
1
2
3
4
5
6
7
8
9
10
11
12
13
// 哈希
var singleNumber = function(nums) {
  const map = {}
  nums.forEach(val => {
    // 存在则 +1 不存在则 1
    map[val] = map[val] + 1 || 1;
  })
  for(let key in map) {
    if(map[key] === 1) {
      return key;
    }
  }
};

两个数组的交集 II

  • 描述
    • 给你两个整数数组nums1和nums2，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。
  • 思路
    • 分别以两个数组对的数组元素为键，出现次数为值，创建哈希表。然后遍历两个哈希表找出共同元素，插入n次入数组（n为较小值）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */

 // value：数组元素（作为键）；count：出现次数（作为值）；
var intersect = function(nums1, nums2) {
    let map1 = new Map();
    let map2 = new Map();
    let arr = [];
    nums1.forEach(value => {
        // map1[value] = map1.get((value)) + 1 || 1;  建议使用 set
        map1.set(value,map1.get((value)) + 1 || 1);
    })
    nums2.forEach(value => {
        map2.set(value,map2.get((value)) + 1 || 1);
    })
    for(let key1 of map1.keys()){
        for(let key2 of map2.keys()){
            if(key1===key2){
                let count1 = map1.get(key1);
                let count2 = map2.get(key2);
                if(count1 >= count2){
                    for(let i = 1; i<= count2; i++){
                        arr.push(key2);
                    }
                }else{
                    for(let i = 1; i<= count1; i++){
                        arr.push(key1);
                    }
                }
            }
        }
    }
    return arr;
};
  • 官方解法
  • 思路（一个哈希表）
    • 首先遍历第一个数组，并在哈希表中记录第一个数组中的每个数字以及对应出现的次数，然后遍历第二个数组，对于第二个数组中的每个数字，如果在哈希表中存在这个数字，则将该数字添加到答案，并减少哈希表中该数字出现的次数。
    • 为了降低空间复杂度，首先遍历较短的数组并在哈希表中记录每个数字以及对应出现的次数，然后遍历较长的数组得到交集。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
var intersect = function(nums1, nums2) {
// 长短交换判定
    if (nums1.length > nums2.length) {
            return intersect(nums2, nums1);
    }
    const hashmap = new Map()
// 将较短的nums1中的元素与个数存入hashmap
    for (let num of nums1) {
        let count = hashmap.get(num) || 0;
        hashmap.set(num, count+1);
    }
    let res = [], index = 0;
// 遍历nums2，遇到重复则count--并更新hashmap
// 遇到重复说明两个数组都有该元素
// cout==0说明先存进 hashmap 中的数组的对应某元素已经全部加入新数组中
    for (let num of nums2) {
        let count = hashmap.get(num) || 0;
        if (count > 0) {
            res[index++] = num;
            count--;
// 更新 hashmap，以count状态作为判断条件
            if (count > 0) {
                hashmap.set(num, count);
            } else {
                hashmap.delete(num);
            }
        }
    }
    return res;
};
  • 思路（排序+双指针）
    • 首先对两个数组进行排序，然后使用两个指针遍历两个数组。
    • 初始时，两个指针分别指向两个数组的头部。每次比较两个指针指向的两个数组中的数字，如果两个数字不相等，则将指向较小数字的指针右移一位，如果两个数字相等，将该数字添加到答案，并将两个指针都右移一位。当至少有一个指针超出数组范围时，遍历结束。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var intersect = function(nums1, nums2) {
//将两个数组从小到大排序
    nums1.sort((a,b) => a-b);
    nums2.sort((a,b) => a-b);
    let res = [];
    let key1 = 0, key2 = 0, index = 0;
//在两个指针不达边界的前提下不断推进
    while(key1 < nums1.length && key2 < nums2.length){
//判断nums1[key1]与nums2[key2]的大小，分出大于小于等于三种情况
        if(nums1[key1] < nums2[key2]) key1++;
        else if(nums1[key1] > nums2[key2]) key2++;
        else{
            res[index++] = nums1[key1];
            key1++;
            key2++;
        }
    }
    return res;
};

加一

  • 描述
    • 给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
    • 最高位数字存放在数组的首位，数组中每个元素只存储单个数字。
    • 你可以假设除了整数0之外，这个整数不会以零开头。
  • 思路（js方法）
    • 数组 -> 大整数 -> +1 -> 数组（->表示转换类型）
    • 基于js是一门非常高级的语言，已经封装好了很多方法，直接调用方法完成，虽然方便但忽略了算法。
1
2
3
4
5
6
7
8
9
10
11
12
/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function(digits) {
    // 将数组转化成 字符串 => 大整数（否则可能会超出范围）
    let num = BigInt(digits.join(''));
    num++;
    // num = num.toString()
    // let arr = Array.from(num);
    return  num.toString().split('');
};
  • 官方解法
  • 思路（找出最长的后缀9）
    • 如果digits的末尾没有9，例如[1,2,3]，那么我们直接将末尾的数加一，得到[1,2,4]并返回；
    • 如果digits的末尾有若干个9，例如[1,2,3,9,9]，那么我们只需要找出从末尾开始的第一个不为9的元素，即3，将该元素加一，得到[1,2,4,9,9]。随后将末尾的9全部置零，得到[1,2,4,0,0]并返回。
    • 如果digits的所有元素都是9，例如[9,9,9,9,9]，那么答案为[1,0,0,0,0,0]。我们只需要构造一个长度比digits多1的新数组，将首元素置为1，其余元素置为0即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var plusOne = function(digits) {
    const n = digits.length;
    // 找出第一个不为 9 的元素，将其加 1 并将后续所有元素置零
    // 包括了第一二种情况
    for (let i = n - 1; i >= 0; --i) {
        if (digits[i] !== 9) {
            ++digits[i];
            for (let j = i + 1; j < n; ++j) {
                digits[j] = 0;
            }
            return digits;
        }
    }

    // digits 中所有的元素均为 9（第三种情况）
    const ans = new Array(n + 1).fill(0);
    ans[0] = 1;
    return ans;
};

移动零

  • 描述
    • 给定一个数组nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序。
    • 请注意 ，必须在不复制数组的情况下原地对数组进行操作。
  • 思路
    • 考虑到js对数组封装的方法丰富，就不使用找零移动法了
    • 将数组中为0的元素删除，并计数count，删除全部0后，在数组末尾插入count个0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
  let n = nums.length;
  let count = 0;
  for(let i = 0; i < n; i++){
      if(nums[i]===0){
          nums.splice(i,1);
          count++;
          n--;  // 删除元素后长度 n 应减 1
          i--;  // 删除元素后当前下标实际指向的是下一个元素应减 1
      }
  }
  while(count){
      nums.push(0);
      count--;
  }
};

// 错误代码
  nums.forEach((value,index,arr) => {
      if(value === 0){
          arr.splice(index,1);
          // forEach()中的 index 虽然在函数体中改变，但不会有效果
          index--;
          count++;
      }
  })
  • 官方解法
    • 思路（双指针 类似冒泡排序）
      • 使用双指针，左指针指向当前已经处理好的序列的尾部，右指针指向待处理序列的头部。
      • 右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移。
      • 注意到以下性质：
        • 左指针左边均为非零数
        • 右指针左边直到左指针处均为零。
        • 因此每次交换，都是将左指针的零与右指针的非零数交换，且非零数的相对顺序并未改变。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 还是写复杂了呀
var moveZeroes = function (nums) {
  let n = nums.length;
  for (let i = 0; i < n; i++) {
    if (nums[i] === 0) {  // 找到第一个为 0 的元素
      let j = 0;  // 写在 for循环外 因为for循环外 要用
      for (j = i + 1; j < n; j++) {
        if (nums[j] !== 0) {  // 如果 j 指向非 0 则交换
          nums[i] = nums[j];
          nums[j] = 0;
          break;
        }
      }
      // 当 j 指向最后一个元素（此时数组已经任务）
      // 可以结束最外层循环
      if (j > n-1)
        break;
      }
    }
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 这个好点
// 两个指针都从左侧出发，左指针遇 0 等待，与下一个非零数交换
var moveZeroes = function(nums) {
    let n = nums.length;
    let left = 0, right = 0;
    for(let i = 0; i < n; i++){
        if(nums[i]!==0){
            // 注意 这里必须使用 temp 变量而不能直接使用 0 赋值
            // 原因是：开始时 l r 指向同一个元素且可能不为 0
            // 注意与上面写的区别
            let temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
        }
        right++;
    }
}

有效的数独

  • 描述
    • 请你判断一个9 x 9的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
      • 数字1-9在每一行只能出现一次。
      • 数字1-9在每一列只能出现一次。
      • 数字1-9在每一个以粗实线分隔的3x3宫内只能出现一次。
      • 空白格用’.’表示。
  • 思路（三次遍历）
    • 利用哈希唯一性，按规则扫描表格内的数，插入哈希表，若已存则在返回false；若扫描完成未发现重复则返回true。
    • 分别按行、列、3 × 3块扫描。
    • 其中块扫描按块进行列扫面，即先扫描左边3 × 9组成的3个列块，然后向右依次扫描。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
 * @param {character[][]} board
 * @return {boolean}
 */
var isValidSudoku = function (board) {
  let hash = new Map();
  let len = 9;
  let llen = 3; // 每一个小块边长 3 
  // 判断行
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len; j++) {
      // "."代表空，不作为重复条件判定
      if (hash.has(board[i][j]) && board[i][j] !== '.') {
        return false;
      } else {
        hash.set(board[i][j], 0); // 这里的value 0 没啥用
      }
    }
    hash.clear();
  }
  // 判断列
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len; j++) {
      if (hash.has(board[j][i]) && board[j][i] !== '.') {
        return false;
      } else {
        hash.set(board[j][i], 0);
      }
    }
    hash.clear();
  }
  // 判断3*3
  // iStart、jStart分别代表行、列开始的下标
  let iStart = 0, jStart = 0;
  // jStart < 9 扫描结束（已经扫到最右下角的块）
  while (jStart < 9) {
    // 扫描每一 3 × 3块
    for (let i = iStart; i < llen + iStart; i++) {
      for (let j = jStart; j < llen + jStart; j++) {
        if (hash.has(board[i][j]) && board[i][j] !== '.') {
          return false;
        } else {
          hash.set(board[i][j], 0);
        }
      }
    }
    hash.clear(); // 某一块扫描完成，清除哈希表
    iStart += 3;  // 修改iStart 至下一块 行开始位置
    if (iStart >= 9) {  // iStart >= 9 说明某一“块列”扫描完成
      iStart = 0;     // 重置 iStart 至下一列”块列“ 的行开始位置
      jStart += 3;    // 修改 jStart 至下一列“块列” 的列开始位置
    }
  }
  return true;
};
  • 官方解法
  • 思路（一次遍历）
    • 创建二维数组rows和columns分别记录数独的每一行和每一列中的每个数字的出现次数，创建三维数组 subbozes记录数独的每一个小九官格中的每个数字的出现次数。
    • 其中$rows[i][index]、\textit{columns}[j][\textit{index}]$
    • $columns[j][index]$和$subboxes[⌊\frac{i}{3}⌋][⌊\frac{j}{3}⌋][index]$
    • 分别表示数独的第i行第j列的单元格所在的行、列和小九宫格中,数字index+1出现的次数,其中0≤index<9,对应的数字index+1满足1≤inde+1≤9
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var isValidSudoku = function(board) {
  // arr.map()：对数组的每个元素都调用函数，并返回结果数组
  const rows = new Array(9).fill(0).map(() => new Array(9).fill(0));
  const columns = new Array(9).fill(0).map(() => new Array(9).fill(0));
  const subboxes = new Array(3).fill(0).map(() => new Array(3).fill(0).map(() => new Array(9).fill(0)));
  for (let i = 0; i < 9; i++) {
      for (let j = 0; j < 9; j++) {
          const c = board[i][j];
          if (c !== '.') {
              const index = c.charCodeAt() - '0'.charCodeAt() - 1;
              rows[i][index]++;
              columns[j][index]++;
              // i：0-2；j：0-2代表一个 3×3 单元格
              subboxes[Math.floor(i / 3)][Math.floor(j / 3)][index]++;
              if (rows[i][index] > 1 || columns[j][index] > 1 || subboxes[Math.floor(i / 3)][Math.floor(j / 3)][index] > 1) {
                  return false;
              }
          }
      }
  }
  return true;
};

旋转图像

  • 描述
    • 给定一个n×n的二维矩阵matrix表示一个图像。请你将图像顺时针旋转90度。
    • 你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
  • 思路
    • 找出旋转前后下标变化规律
    • 关键等式：
    • matrixNew[col][n−row−1]=matrix[row][col]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var rotate = function(matrix) {
    let len = matrix.length;
    for(let i =0; i < Math.floor(len/2); i++){
        for(let j = 0; j < Math.floor((len+1)/2); j++){
            let temp = matrix[i][j];
            matrix[i][j] = matrix[len-j-1][i];
            matrix[len-j-1][i] = matrix[len-i-1][len-j-1];
            matrix[len-i-1][len-j-1] = matrix[j][len-i-1];
            matrix[j][len-i-1] = temp;
        }
    }
};

反转字符串

  • 描述
    • 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
    • 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
  • 思路
    • 调用内建方法reverse()
    • 双指针
    • 解构语法
    • 位运算
1
2
3
4
5
6
7
8
9
10
11
/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
var reverseString = function(s) {
    let left = 0;
    let right = s.length - 1;
    while(left < right){
        [s[left++],s[right--]] = [s[right],s[left]];
    }
};

整数反转

  • 描述
    • 你一个32位的有符号整数x，返回将x中的数字部分反转后的结果。
    • 如果反转后整数超过32位的有符号整数的范围[−2^31, 2^31 − 1] ，就返回0。
    • 假设环境不允许存储64位整数（有符号或无符号）。
  • 思路
    • 先将输入整数的位数计算出来，以便计算每一位应对应的权重（转化后在什么位上）。
    • 通过整除、取余获取尾部数字，乘以转化后对应的位的权重，然后相加。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * @param {number} x
 * @return {number}
 */
var reverse = function (x) {
  let flag = false;
  if (x < 0) {
    flag = true;
  }
  let result = 0;
  // 这里将它转化成绝对值 
  // 因为 对于负数 floor()向下取整时：floor(-1.2) === 2 而非 1
  let temp = x = Math.abs(x);
  let count = 0;
  while (temp) {
    temp = Math.floor(temp / 10);
    count++;
  }
  while (count) {
    result += x % 10 * 10 ** (count - 1);
    x = Math.floor(x / 10);
    count--;
  }
  if (result < (-2) ** 31 || result > 2 ** 31 - 1) {
    return 0;
  }
  return flag ? -result : result;
};
  • 官方解法
1
2
3
4
5
6
7
8
9
10
11
12
13
var reverse = function(x) {
    let rev = 0;
    while (x !== 0) {
        const digit = x % 10;
        // 向 0 取整
        x = ~~(x / 10); // ~~ 正数时是Math.floor()的替代品
        rev = rev * 10 + digit;
        if (rev < Math.pow(-2, 31) || rev > Math.pow(2, 31) - 1) {
            return 0;
        }
    }
    return rev;
};

字符串中的第一个唯一字符

  • 描述
    • 给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
  • 思路
    • 遍历字符串利用hashmap以字符为key、{index:null,count:null}为value，存储字符的下标index和出现次数count。
    • 遍历哈希表找到第一个count === 1的映射，并返回其下标。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * @param {string} s
 * @return {number}
 */
var firstUniqChar = function (s) {
  let char = s.split('');
  let map = new Map();
  char.forEach((c, index) => {
    if (map.has(c)) {
      map.get(c).count++;
    } else {
      map.set(c, { index: index, count: 1 });
    }
  })
  for (let item of map.values()) {
    if (item.count === 1) {
      return item.index;
    }
  }
  return -1;  // 字符串没有不重复的

  // 不能用 forEach()遍历，因为难以跳出整个循环
  // map.forEach((obj) => {
  //   if(obj.count === 1){
  //     result = obj.index;
  //     return false;  // 仅跳出本次循环 而非整个 forEach
  //   }
  // })
};
  • 官方解法
  • 思路
    • 我们可以对字符串进行两次遍历。
    • 在第一次遍历时，我们使用哈希映射统计出字符串中每个字符出现的次数。
    • 在第二次遍历时，我们只要遍历到了一个只出现一次的字符，那么就返回它的索引，否则在遍历结束后返回-1。
1
2
3
4
5
6
7
8
9
10
var firstUniqChar = function(s) {
  //_.countBy方法创建一个由键组成的对象，这些键是通过运行iteratee的collection的每个元素的结果生成的。每个 key 的对应值是iteratee返回 key 的次数。
    const frequency = _.countBy(s);
    for (const [i, ch] of Array.from(s).entries()) {  // arr.entries()返回[key,value]
        if (frequency[ch] === 1) {
            return i;
        }
    }
    return -1;
};

有效的字母异位词

  • 描述
    • 给定两个字符串s和t，编写一个函数来判断t是否是s的字母异位词。
    • 注意：若s和t中每个字符出现的次数都相同，则称s和t互为字母异位词。
  • 思路
    • 首先判断字符串长度是否相等，不相等直接return false。
    • 利用hashmap，扫描字符串字符存入map并记录出现次数。
    • 扫描第二个字符串判断map中是否已经存在：
      • 若存在则次数减1，若次数减至< 0则return false；
      • 若不存在return false（不存在说明第二个串用了第一个没有使用的字符） 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {
    let map = new Map();
    if(s.length !== t.length){
        return false;
    }
    for(let item of s){
        if(map.has(item)){
            map.set(item, map.get(item)+1);
        }else{
            map.set(item,1);
        }
    }
    for(let item of t){
        if(map.has(item)){
             map.set(item, map.get(item)-1);
            if(map.get(item) < 0){
                return false;
            }
        }else{
           return false;
        }
    }
    return true;
};
  • 官方解法
  • 思路
    • 排序
    • 判断字符串是否相等
1
2
3
var isAnagram = function(s, t) {
    return s.length == t.length && [...s].sort().join('') === [...t].sort().join('');
};

验证回文串

  • 描述
    • 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
    • 说明：本题中，我们将空字符串定义为有效的回文串。
  • 思路
    • 双指针
    • 正则表达式（两年前学过忘记了，用得很笨拙）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function (s) {
  // 为什么要转化成数组？
  // 因为js中字符串不可更改
  // 即 s[0]=s[0].toLowerCase()无效
  let strArr = s.split('');
  let l = 0;
  let r = strArr.length - 1;
  // 正则：数字和字母
  let re = /[0-9A-Za-z]/g;  // 等同于/\w/g
  // 正则：大写字母
  let reUp = /[A-Z]/g;
  while (l < r) {
    // 如果不是数字或字母 指针移动
    if (!strArr[l].match(re)) {
      l++;
      continue; // 指针移动后得先再判断 l < r?和再次判断是否为数字或字母
    }
    if (!strArr[r].match(re)) {
      r--;
      continue;
    }
    // 如果是大写字母 转换成小写
    if (strArr[l].match(reUp)) {
      strArr[l] = strArr[l].toLowerCase();
    }
    if (strArr[r].match(reUp)) {
      strArr[r] = strArr[r].toLowerCase();
    }
    if (strArr[l] === strArr[r]) {
      l++;
      r--;
    } else {
      return false;
    }
  }
  return true;
};
  • 其他解法
  • 思路
    • 和我一样，但是正则比我用的好
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var isPalindrome = function(s) {
    // s = s.replace(/[^\w]/g, '').toLowerCase()
    // 题目要求只考虑字母和数字字符，所以上面的写法也没啥问题
    s = s.replace(/[^0-9a-zA-Z]/g, '').toLowerCase()  // 还没学js正则的api 上面我写的像坨xx
    let left = 0;
    let right = s.length - 1;

    while(left < right) {
        if(s[left] != s[right]) {
           return false 
        }
        left++
        right--
    }
    return true
};

实现 strStr()

  • 描述
    • 实现strStr()函数。
    • 给你两个字符串haystack和needle，请你在haystack字符串中找出needle字符串出现的第一个位置（下标从0开始）。如果不存在，则返回-1 。
    • 说明：
      • 当needle是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
      • 对于本题而言，当needle是空字符串时我们应当返回0。这与C语言的strstr()以及Java的indexOf()定义相符。
  • 思路（暴力搜索）
    • 双指针
    • 分别指向源串和子串，比较、回溯（源串回溯至第一个匹配位置的下一位，模式串回溯至0）
    • 模式串指针指向最后一位字符的下一位，则代表匹配成功。
    • 源串指针指向最后一位字符的下一位，且此时模式串没有指向最后一位字符的下一位则匹配失败。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function (haystack, needle) {
  let hLen = haystack.length;
  let nLen = needle.length;
  if (nLen > hLen) {  // 模式串长度大于源串必定找不到
    return -1;
  }
  if (needle === "") {  // 别忘记这个特殊模式串
    return 0;
  }
  let p = 0, q = 0;
  while (p < hLen) {
    if (haystack[p] === needle[q]) {  // 字符匹配指针移动
      p++;
      q++;
      if (q > nLen - 1) { // 模式串指针已经移动到“溢出”字符串？
        return p - nLen;  // 代表匹配成功，返回源串下标（注意下标的计算）
      }
    } else {  // 否则回溯
      p = p - q + 1;  // p指针回溯（注意计算）
      q = 0;  // q指针回溯
    }
  }
  return -1;
};
  • 其他思路
    • KMP（略）
    • 滑动窗口（略）

删除链表中的节点

  • 描述
    • 请编写一个函数，用于删除单链表中某个特定节点。在设计函数时需要注意，你无法访问链表的头节点head，只能直接访问要被删除的节点 。
    • 题目数据保证需要删除的节点不是末尾节点。
  • 思路
    • 复制下一个结点的值 -> 删除下一个节点。
    • (我觉得我又行了!）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */
var deleteNode = function(node) {
    node.val = node.next.val;
    node.next = node.next.next;
};

反转链表

  • 描述
    • 给你单链表的头节点head，请你反转链表，并返回反转后的链表。
  • 思路
    • 略
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    let p = null;
    let q = head;
    let r = head?.next; // head可能为空
    while(q){
        q.next = p;
        p = q;
        q = r;
        r = r?.next;  // 遍历到最后时，尾部节点 r 可能为空
    }
    return p;
};

// 这种解法排除了可能为空而无法调用.next而报错的情况
// var reverseList = function(head) {
//     let prev = null;
//     let curr = head;
//     while (curr) {
//         const next = curr.next;
//         curr.next = prev;
//         prev = curr;
//         curr = next;
//     }
//     return prev;
// };

删除链表的倒数第 N 个结点

  • 描述
    • 给你一个链表，删除链表的倒数第n个结点，并且返回链表的头结点。
  • 思路
    • 计算链表长度
    • 首先从头节点开始对链表进行一次遍历，得到链表的长度L。随后我们再从头节点开始对链表进行一次遍历，当遍历到第L-n+1个节点时，它就是我们需要删除的节点。
    • 注意
      • 没有头结点的链表注意表头元素的删除方法需要单独编写
      • 若使用复制删除法，则尾部结点的删除方法也需要单独编写
    • 其他
      • 双指针
        • 由于我们需要找到倒数第n个节点，因此我们可以使用两个指针first和second同时对链表进行遍历，并且first比second超前n个节点。当first遍历到链表的末尾时，second就恰好处于倒数第n个节点。
      • 栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function (head, n) {
  let sumCount = 0;  // 总结点数 链表长度
  let p = head;
  while (p) {
    sumCount++;
    p = p.next;
  }
  let index = sumCount - n + 1;  // 删除第index个结点（从1开始）
  let count = 1;  // 当前遍历到第 count 个结点
  p = head;
  if (index === 1) {    // 由于没有头结点，删除首节点时需要单独操作
    // 直接让head指向下一个结点
    head = p.next;
  } else if (index === sumCount) {   // 删除尾结点需要单独操作
    // 当count===index 使 p 指向index -1，被删除的结点前一个元素
    while (count < index - 1) {
      p = p.next;
      count++;
    }
    p.next = null;
  } else {
    // 当count===index 使 p 指向index，即，将被删除的结点
    while (count < index) {  // 除以上情况外，进行常规删除操作
      p = p.next;
      count++;
    }
    // 删除操作（赋值替换）
    p.val = p.next.val;
    p.next = p.next.next;
  }
  return head;
};

合并两个有序链表

  • 描述
    • 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
  • 思路
    • 迭代
    • 递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function(list1, list2) {
    let p = list1;
    let q = list2;
    let r = head = new ListNode(undefined,undefined);
    while(p && q){    // 如果任意链表遍历至完成（指向null）跳出循环
        if(p.val < q.val){
            let temp = new ListNode(p.val,null);
            r.next = temp;
            r = r.next;
            p = p.next;
        }else{
            let temp = new ListNode(q.val,null);
            r.next = temp;
            r = r.next;
            q = q.next;
        }
    }
    // 若p(q)空，则将q(p)直接接入新链表即可
    if(!p){
        r.next = q;
    }else if(!q){
        r.next = p;
    }
    return head.next;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
var mergeTwoLists = function(l1, l2) {
    if (l1 === null) {
        return l2;
    } else if (l2 === null) {
        return l1;
    } else if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
};

回文链表

  • 描述
    • 给你一个单链表的头节点head，请你判断该链表是否为回文链表。如果是，返回true；否则，返回false。
  • 思路
    • 将值复制到数组中后用双指针法
    • 递归
    • 快慢指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function(head) {
    const vals = [];
    while (head !== null) {
        vals.push(head.val);
        head = head.next;
    }
    for (let i = 0, j = vals.length - 1; i < j; ++i, --j) {
        if (vals[i] !== vals[j]) {
            return false;
        }
    }
    return true;
};

环形链表

  • 描述
    • 给你一个链表的头节点head，判断链表中是否有环。
  • 思路
    • 利用数据结构集合（或哈希表）的唯一性，也可以用数组的includes()方法
      • 遍历链表加入集合，重复则true，反之true。
    • 快慢指针
      • 定义两个指针，一快一满。慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针在位置head，而快指针在位置head.next。
      • 这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    let p = head;
    let set = new Set();
    while(p){
        if(set.has(p)){
            return true;
        }else{
            set.add(p);
        }
        p = p.next;
    }
    return false;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const hasCycle = function(head) {
  if(head === null || head.next === null) {
    return false;
  }
  let slow = head;
  let fast = head.next;
  while (slow) {
    if(slow === fast) {
      return true
    }
    slow = slow?.next || null;
    fast = fast?.next?.next || null;
  }
  return false;
};

LeetCode刷题笔记

http://tianyuzhou.github.io/2022/01/24/LeetCode刷题笔记/

作者

TIANYUZHOU

发布于

2022-01-24

更新于

2022-02-20

许可协议

#

喜欢这篇文章？打赏一下作者吧

评论

关注我

链接

分类

最新文章

归档

标签

80×86汇编语言2
C++内联函数1
HTML5+CSS+JS初步1
LeetCode1
Python学习1
Python应用(爬虫)1
Python应用(爬虫-XPath)1
Python自动打卡1
VS Code小坑1
分区、分段、段页式1
图库1
我的歌单-周杰伦1
我的歌单-林俊杰1
我的歌单-赵海洋1
我的歌单-陈奕迅1
拓展1
操作系统1
操作系统-课后习题1
数据库2
数据挖掘1
旅行1
模型迁移1
第一篇文章1
算法分析与设计1
网易云插件小坑1
视频作品1
计算机组成与系统结构1
计算机网络7

订阅更新

×