3. 无重复字符的最长子串 - 力扣（LeetCode）

滑动窗口实现

function lengthOfLongestSubstring(s) {
	// 记录最大长度
  let maxLen = 0;
  // 当前窗口中的元素
  const temp = [];
  for (let right = 0; right < s.length; ++right) {
    // 只要当前窗口中有最新的元素就出队一个元素
    while (temp.includes(s[right])) {
      temp.shift();
    }
    // 入队最新的元素
    temp.push(s[right]);
    // 如果最大长度小于当前元素的长度就覆盖
    if (maxLen < temp.length) {
      maxLen = temp.length;
    }
  }
  return maxLen;
}

比较版本号

165. 比较版本号 - 力扣（LeetCode）

切割字符串并转换成数字类型 还可以使用生成器返回迭代器的方式优化性能

/**
 * @param {string} version1
 * @param {string} version2
 * @return {number}
 */
function compareVersion(version1, version2) {
  const arr1 = version1.split(".");
  const arr2 = version2.split(".");
  while (arr1.length && arr2.length) {
    const v1 = parseInt(arr1.shift());
    const v2 = parseInt(arr2.shift());
    if (v1 > v2) return 1;
    if (v1 < v2) return -1;
  }
  if (arr1.length) {
    return arr1.every((v) => v == 0) ? 0 : 1;
  }
  if (arr2.length) {
    return arr2.every((v) => v == 0) ? 0 : -1;
  }
  return 0;
}

合并两个有序数组

88. 合并两个有序数组 - 力扣（LeetCode）

三指针从后往前遍历，避免数据覆盖。

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
function merge(nums1, m, nums2, n) {
  let i = m - 1;
  let j = n - 1;
  let k = m + n - 1;

  while (i >= 0 && j >= 0) {
    nums1[k--] = nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
  }
  while (i >= 0) {
    nums1[k--] = nums1[i--];
  }
  while (j >= 0) {
    nums1[k--] = nums2[j--];
  }
}

字符串相加

415. 字符串相加 - 力扣（LeetCode） 从后往前遍历字符串，将字符转换成数字相加 也可以在位数不足的前面补上0

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var addStrings = function (num1, num2) {
  let result = "";
  let i = Math.max(num1.length, num2.length);
  let j = 1;
  let carry = 0;
  while (j <= i) {
    const n1 = num1[num1.length - j] ? parseInt(num1[num1.length - j]) : 0;
    const n2 = num2[num2.length - j] ? parseInt(num2[num2.length - j]) : 0;
    const sum = n1 + n2 + carry;
    const res = sum % 10;
    carry = Math.floor(sum / 10);
    result = res + result;

    ++j;
  }
  if (carry) {
    result = carry + result;
  }
  return result;
};

有效括号

20. 有效的括号 - 力扣（LeetCode）

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
  const stack = [];
  for (let i = 0; i < s.length; ++i) {
    if (["(", "[", "{"].includes(s[i])) {
      stack.push(s[i]);
    } else if (["}", "]", ")"].includes(s[i])) {
      if (stack.length === 0) {
        return false;
      } else {
        const top = stack.pop();
        if (
          (top === "(" && s[i] === ")") ||
          (top === "[" && s[i] === "]") ||
          (top === "{" && s[i] === "}")
        ) {
          continue;
        }
        return false;
      }
    }
  }
  return stack.length === 0;
};

两数之和

1. 两数之和 - 力扣（LeetCode）

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

全排列

46. 全排列 - 力扣（LeetCode）

回溯：有状态的递归

使用回溯法 递归进行深搜，遍历数字数组，如果当前元素存在于状态数组中表示当前元素已经在结果数组中了就跳过，如果不在就添加入状态数组中，继续递归，当递归出来后将当前元素从状态数组中取出（修改状态）

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
  const result = [];
  function bfs(arr) {
    if (arr.length === nums.length) {
	    // 防止引用传递
      result.push(JSON.parse(JSON.stringify(arr)));
      return;
    } else {
      for (let i = 0; i < nums.length; ++i) {
        if (arr.includes(nums[i])) {
          continue;
        } else {
          arr.push(nums[i]);
          bfs(arr);
          arr.pop();
        }
      }
    }
  }
  bfs([]);
  return result;
};

反转链表

206. 反转链表 - 力扣（LeetCode）

双指针，在反转时需要构造一个temp做中转

class ListNode {
  constructor(val, next) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
  }
}

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
function reverseList(head) {
  let cur = head;
  let pre = null;

  while (cur) {
    const temp = cur.next;
    cur.next = pre;
    pre = cur;
    cur = temp;
  }
  return pre;
}

最大子数组和

53. 最大子数组和 - 力扣（LeetCode） 每次遍历查看上次的和是否大于0，如果大于0表示此前的和相加是有益的，就相加，否则就将和赋值为当前值，再与保存的最大和比较

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

二叉树的层序遍历

102. 二叉树的层序遍历 - 力扣（LeetCode） 每次遍历传递当前层级数，层级数的索引就是自己在二维结果数组中对应的数组

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function (root) {
  function helper(node, level) {
    if (!node) return;
    if (!res[level]) {
      res[level] = [];
    }
    res[level].push(node.val);
    helper(node.left, level + 1);
    helper(node.right, level + 1);
  }
  const res = [];
  helper(root, 0);
  return res;
};

三数之和

15. 三数之和 - 力扣（LeetCode） 一次遍历+双指针 先排序整个数组，让数组有序，每次遍历在当前值的前一个位置设置一个指针，在数组末尾设置第二个指针，如果值相加大于则右指针前移再比较，如果大于则左指针后移，如果等于则直接添加到结果数组中并两个指针都相向移动一次，再再次循环中循环左指针的值是否小

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  const result = [];
  nums = nums.sort((a, b) => a - b);

  for (let i = 0; i < nums.length; ++i) {
    if (nums[i] === nums[i - 1]) {
      continue;
    } else {
      let l = i + 1,
        r = nums.length - 1;

      while (l < r) {
        if (nums[i] + nums[l] + nums[r] === 0) {
          result.push([nums[i], nums[l], nums[r]]);
          ++l;
          --r;
          while (l < r && nums[l] === nums[l - 1]) {
            ++l;
          }
        } else if (nums[i] + nums[l] + nums[r] < 0) {
          ++l;
        } else {
          --r;
        }
      }
    }
  }
  return result;
};

买卖股票的最佳时机

121. 买卖股票的最佳时机 - 力扣（LeetCode） 记录买入价值，和当前利润 遍历数组，如果当前值比此前的买入价值小则将当前值记录为买入价值，否则的话就尝试卖出，取当前卖出利润和此前的利润的最大值

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  let buy_price = prices[0];
  let max_profit = 0;
  for (let i = 0; i < prices.length; ++i) {
    if (buy_price > prices[i]) {
      buy_price = prices[i];
    } else {
      max_profit = Math.max(max_profit, prices[i] - buy_price);
    }
  }
  return max_profit;
};

环形链表

141. 环形链表 - 力扣（LeetCode）

快慢指针，快指针一次走两步，慢指针一次走异步，如果快指针遇到null则无环，如果遇到慢指针则有环

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function (head) {
  let fast = head,
    slow = head;

  while (fast && fast.next) {
    fast = fast.next.next;
    slow = slow.next;
    if (fast === slow) {
      return true;
    }
  }
  return false;
};

路径求和

112. 路径总和 - 力扣（LeetCode）

回溯：带状态的递归 每次递归传递上次的目标值减去当前值，也就是后续节点要达到的目标总值，遇到叶子节点则返回判断

/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {boolean}
 */
var hasPathSum = function (root, targetSum) {
  if (!root) {
    return false;
  } else if (!root.left && !root.right) {
    return root.val === targetSum;
  } else {
    return (
      hasPathSum(root.left, targetSum - root.val) ||
      hasPathSum(root.right, targetSum - root.val)
    );
  }
};

爬楼梯

70. 爬楼梯 - 力扣（LeetCode） 类似斐波那契数列，单独递归会栈溢出，需要存储之前的状态 如果台阶等于1只有一种方式，如果等于2则有两种方式，因此初始的f(1)和f(2)的值就可求出 后续的每个台阶所包含的方法就是前一次和前两次所能达到方法的和，也就是满足：f(n)=f(n-1)+f(n-2)

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
  if (n <= 2) return n;
  let prev1 = 1;
  let prev2 = 2;
  for (let i = 3; i <= n; ++i) {
    const cur = prev1 + prev2;
    prev1 = prev2;
    prev2 = cur;
  }
  return prev2;
};

合并两个有序链表

21. 合并两个有序链表 - 力扣（LeetCode）

构建一个虚拟头节点指向新链表，并在两个链表中各设置一个指针，将相对较小的添加到新链表队尾，最后返回虚拟头节点的下一个节点

/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function (list1, list2) {
  const head = new ListNode(0);
  let cur = head;
  while (list1 && list2) {
    if (list1.val < list2.val) {
      cur.next = list1;
      list1 = list1.next;
    } else {
      cur.next = list2;
      list2 = list2.next;
    }
    cur = cur.next;
  }
  cur.next = list1 || list2;
  return head.next;
};

数组中的第k个最大元素

215. 数组中的第K个最大元素 - 力扣（LeetCode） 将数组排序后取第k个值（索引为k-1）

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
function findKthLargest(nums, k) {
  const temp = nums.sort((a, b) => b - a);
  return temp[k - 1];
}

排序数组

912. 排序数组 - 力扣（LeetCode） 归并排序符合O(nlogn)

// 归并排序
function mergeSort(arr) {
  function _mergeSort(left, right) {
    if (left >= right) return;
    let mid = Math.floor((left + right) / 2);
    _mergeSort(left, mid);
    _mergeSort(mid + 1, right);

    let i = left,
      j = mid + 1;
    const temp = [];
    while (i <= mid && j <= right) {
      if (arr[i] <= arr[j]) {
        temp.push(arr[i++]);
      } else {
        temp.push(arr[j++]);
      }
    }
    while (i <= mid) {
      temp.push(arr[i++]);
    }
    while (j <= right) {
      temp.push(arr[j++]);
    }
    for (let k = 0; k < temp.length; ++k) {
      arr[left + k] = temp[k];
    }
  }
  _mergeSort(0, arr.length - 1);
}

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function (nums) {
  mergeSort(nums);
  return nums;
};

LRU

146. LRU 缓存 - 力扣（LeetCode）

使用map做缓存，调用get时如果元素存在就删除后再添加进去

class LRU {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
  }

  get(key) {
    if (this.cache.has(key)) {
      const value = this.cache.get(key);
      this.cache.delete(key);
      this.cache.set(key, value);
      return value;
    } else {
      return -1;
    }
  }

  put(key, value) {
    if (this.cache.has(key)) {
      this.cache.delete(key);
    } else {
      if (this.cache.size >= this.capacity) {
        const oldestKey = this.cache.keys().next().value;
        this.cache.delete(oldestKey);
      }
    }
    this.cache.set(key, value);
  }
}

最长回文子串

5. 最长回文子串 - 力扣（LeetCode）

每次遍历一个字符就从当前字符开始分别向左右设置一个指针，根据判断是否相等 每次遍历要执行两种情况：i和i+1，因为回文子串有两种：bab、baab

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
  let max = "";

  for (let i = 0; i < s.length; ++i) {
    let str = helper(i, i);
    if (str.length > max.length) {
      max = str;
    }
    str = helper(i, i + 1);
    if (str.length > max.length) {
      max = str;
    }
  }

  function helper(l, r) {
    while (l >= 0 && r < s.length && s[l] === s[r]) {
      --l;
      ++r;
    }
    return s.slice(l + 1, r);
  }
};

岛屿数量

200. 岛屿数量 - 力扣（LeetCode） 双层遍历二维数组，如果遇到值为1的则先加上岛屿数量，接着深搜向四周扩散，如果遇到值为1的则将值置为0表示已经遍历过了，并继续向四周扩散，如果越界或者遇到0则返回。 必须向四周扩散，不能只向右或下，因为深搜是从后往前跳出执行栈的，如果只向左或向右会人为地跳过相连的1，后面再计算岛屿数时污染数据

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function (grid) {
  let res = 0;
  for (let i = 0; i < grid.length; ++i) {
    for (let j = 0; j < grid[i].length; ++j) {
      if (grid[i][j] === "1") {
        ++res;
        dfs(grid, i, j);
      }
    }
  }
  return res;
};

function dfs(grid, x, y) {
  if (
    x < 0 ||
    y < 0 ||
    x >= grid.length ||
    y >= grid[x].length ||
    grid[x][y] === "0"
  ) {
    return;
  } else {
    grid[x][y] = "0";
    // 向左扩散
    dfs(grid, x, y - 1);
    // 向上扩散
    dfs(grid, x - 1, y);
    // 向右扩散
    dfs(grid, x, y + 1);
    // 向下扩散
    dfs(grid, x + 1, y);
  }
}

螺旋矩阵

54. 螺旋矩阵 - 力扣（LeetCode）

在上下左右各设置一个边界，以一定顺序按边界执行，每次循环遍历这个边界上的值，循环结束后缩小边界，直到某个边界与它对应的边界接触后就跳出循环

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function (matrix) {
  let left = 0, top = 0, bottom = matrix.length - 1, right = matrix[0].length - 1
  const res = []
  while (true) {
    for (let i = left; i <= right; ++i) {
      res.push(matrix[top][i])
    }
    if (++top > bottom) break

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

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

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

贡献者

PinkDopeyBug

版权所有

版权归属：wynnsimon

许可证：署名 4.0 国际 (CC-BY-4.0)