leetcode刷题总结

二叉树

深度优先搜索

广度优先搜索

完全二叉树的节点个数

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

难度：简单

思路：递归

1. 如果当前节点存在则加1
2. 然后对当前节点的左右节点执行当前函数

function countNodes(root) {
  if (!root) return 0;

  return 1 + countNodes(root.left) + countNodes(root.right);
}

二叉树的最大深度

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

难度：简单

思路：递归

1. 当前节点存在则加1
2. 再加上左右节点中的最大值

function maxDepth(root) {
  if (!root) return 0;

  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

二叉搜索树的最近公共祖先

题目链接

重点关注

难度：简单

思路：两侧遍历，参考题解

1. 二叉搜索树的值是数值，并且当前节点的值大于左子树的值小于右子树的值（重要）
2. 遍历两次二叉树，分别找出根节点到这两个节点的路径，路径中需要包括目标节点
3. 两个路径从后向前数，最近的相同节点就是最近的公共节点

/***
 * 执行用时：76ms，98%
 * 内存消耗：50MB，超5%
 */
function lowestCommonAncestor(root, p, q) {
  // 返回根节点到数值为num的节点的路径
  function getRoute(root, num) {
    const route = [];
    let currNode = root;

    while (currNode) {
      route.push(currNode);

      // 判断目标值在当前节点的哪个方向，根据二叉搜索树的定义得出
      if (num > currNode.val) {
        // 如果num大于当前节点的值，则表示目标节点在右子树这一侧
        currNode = currNode.right;
      } else if (num < currNode.val) {
        // 如果num小于当前节点的值，则表示目标节点在左子数这一侧
        currNode = currNode.left;
      } else {
        // 找到目标值，则返回路径
        return route;
      }
    }
  }

  // 获取两个节点的路径
  const pRoute = getRoute(root, p.val);
  const qRoute = getRoute(root, q.val);

  // 根据路径找出最近的公共祖先节点，从后向前找
  for (let i = pRoute.length - 1; i >= 0; i--) {
    if (qRoute.includes(pRoute[i])) {
      return pRoute[i];
    }
  }
}

思路：一次遍历，参考题解

1. 跟两次遍历方法类似，只不过这次是同时对 p 和 q 进行比较
2. 如果当前节点大于 p 和 q，则 p 和 q 在左子树
3. 如果当前节点小于 p 和 q，则 p 和 q 在右子树
4. 如果不满足 2 和 3 条件，则表示 p 和 q 分别在左子树和右子树，即再次分叉，即当前节点是最近的公共节点
5. 此方法省去了存储路径的空间

/***
 * 执行用时：72ms，99%
 * 内存消耗：47MB，超57%
 */
function lowestCommonAncestor(root, p, q) {
  let currNode = root;

  while (currNode) {
    const value = currNode.val;

    // p和q在左子树
    if (value > p.val && value > q.val) {
      currNode = currNode.left;
    } else if (value < p.val && value < q.val) {
      // p和q在右子树
      currNode = currNode.right;
    } else {
      // p和q在当前节点的两侧，即当前节点是最近的公共节点
      return currNode;
    }
  }

  return currNode;
}

链表

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

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。

难度：简单

思路

1. 链表是按升序进行排列的，因此值相同的节点会排列在一起
2. 将具有相同值的第一个节点记做uniqueNode，将当前节点记做currNode
3. 遍历链表，当uniqueNode的值和currNode的值不相等的时候，让uniqueNode.next = currNode
4. 这样即可将与uniqueNode.val相同的值跳过、去重
5. 需要注意的是最后需要单独让uniqueNode.next = null

function deleteDuplicates(head) {
  if (head === null) return head;

  let currNode = head;
  let uniqueNode = head;

  while (currNode) {
    if (uniqueNode.val !== currNode.val) {
      uniqueNode.next = currNode;
      uniqueNode = currNode;
    }

    currNode = currNode.next;
  }

  uniqueNode.next = null;

  return head;
}

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

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。

重点关注

难度：中等

思路

1. 由题意可知，head节点也可能会被删除，因此需要创建一个dummy节点指向head节点，作用就是删除head节点
2. 判断当前节点currNode的后两个节点的值是否相等。如果相等则表示重复，通过while循环将其删除。如果不相等，则直接将currNode节点向后移动一位即可
3. 最后返回dummy.next即可

function deleteDuplicates(head) {
  if (!head) return head;
  const dummy = new ListNode(0, head);
  let currNode = dummy;

  while (currNode.next && currNode.next.next) {
    const val = currNode.next.val;

    if (currNode.next.next.val === val) {
      while (currNode.next && currNode.next.val === val) {
        currNode.next = currNode.next.next;
      }
    } else {
      currNode = currNode.next;
    }
  }

  return dummy.next;
}

从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）

难度：简单

思路：栈

1. 创建一个栈
2. 遍历链表，将节点push入栈
3. 遍历结束后在将栈中的节点pop出来

function reversePrint(head) {
  const stack = [];
  const result = [];
  let currNode = head;

  while (currNode) {
    stack.push(currNode.val);
    currNode = currNode.next;
  }

  while (stack.length) {
    result.push(stack.pop());
  }

  return result;
}

动态规划

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

重点关注

难度：简单

思路

1. 有动态转移方程f(n) = f(n - 1) + f(n - 2)
2. 因此只需要计算f(n - 1)和f(n - 2)即可

function climbStairs(n) {
  const dp = [0, 1, 2];

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

  return dp[n];
}

最大子数组和(关注)

题目链接

难度：简单

思路：两层循环，肯定超时，不写了

思路：

1. 用 f(i)表示以第 i 个数结尾的[最大子数组和]，最终只需要求出最大的 f(i)即可
2. 重点：关键在于如何求 f(i)，f(i) = Math.max(f(i - 1) + nums[i], nums[i])

/**
 * 执行用时：76ms，超99%
 * 内存消耗：49MB，超18%
 */
function maxSubArray(nums) {
  const dp = [...nums];

  for (let i = 1; i < nums.length; i++) {
    dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
  }

  return Math.max(...dp);
}

递归

比赛中的配对次数

题目链接

难度：简单

思路：递归

1. 每次都执行相同的操作，故使用递归
2. 确认递归的出口条件，当决出获胜队伍后return，即当剩余队伍数为 1
3. 接下来就是判断奇偶，再根据题意去计算即可

/**
 * 执行用时：52ms，超100%
 * 内存消耗：41MB，超5%
 */
function numberOfMatches(n) {
  // 递归出口条件，n等于1表示决出了获胜队伍
  if (n === 1) return 0;

  // 比赛次数
  let count = 0;
  // 是不是奇数，&是与位运算符
  const isOdd = n & 1;

  if (isOdd) {
    // 奇数
    count = (n - 1) / 2;
  } else {
    // 偶数
    count = n / 2;
  }

  return count + numberOfMatches(count + isOdd);
}

思路：遍历

1. 创建一个变量存储当前比赛次数，取代递归函数的return
2. 结束条件是一致的

/**
 * 执行用时：60ms，超97%
 * 内存消耗：41MB，超5%
 */
function numberOfMatches(n) {
  let total = 0;
  let count = 0;

  while (n > 1) {
    const isOdd = n & 1;
    if (isOdd) {
      // 奇数
      count = (n - 1) / 2;
    } else {
      // 偶数
      count = n / 2;
    }

    n = count + isOdd;
    total += count;
  }

  return total;
}

二分查找

二分查找

给定一个  n  个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索  nums  中的 target，如果目标值存在返回下标，否则返回 -1

难度：简单

思路

function search(nums, target) {
  let start = 0;
  let end = nums.length - 1;
  let index = 0;
  let middle = 0;

  while (start <= end) {
    index = Math.floor((start + end) / 2);
    middle = nums[index];

    if (middle > target) {
      end = index - 1;
    } else if (middle < target) {
      start = index + 1;
    } else {
      return index;
    }
  }

  return -1;
}

sqrt(x)

计算 x 算数平方根的整数部分值，0 <= x < 2³¹ - 1

难度：简单

思路

1. 如果 x 的算数平方根整数部分为 k，那么根据数学知识可以得到k² <= x 并且(k + 1)² > x，
2. 上述两个条件可以作为二分查找的上下界
3. 首指针start = 0，尾指针end = x，因为k <= x

function mySqrt(x) {
  // 定义首尾指针
  let start = 0;
  let end = x;
  let k = 0;

  // x可能等于0
  while (start <= end) {
    k = Math.floor((start + end) / 2);

    if (k ** 2 > x) {
      // k的平方 > x
      end = k - 1;
    } else if ((k + 1) ** 2 <= x) {
      // (k + 1)的平方 <= x
      start = k + 1;
    } else {
      return k;
    }
  }
}

字符串

一年中的第几天

给你一个字符串 date ，按 YYYY-MM-DD 格式表示一个 现行公元纪年法 日期。请你计算并返回该日期是当年的第几天

题目链接

难度：简单

思路：使用Date计算日期的毫秒值

1. 将年的值year从日期date中截取出来
2. 获取year-1-1的毫秒值
3. 获取date的毫秒值
4. 两者相减，再除一天的毫秒值，最后加 1

function dayOfYear(date) {
  const year = date.split("-")[0];
  const now = new Date(date);
  const beginning = new Date(`${year}-1-1`);
  return (now - beginning) / (24 * 60 * 60 * 1000) + 1;
}

替换所有的问号

题目链接

难度：简单

思路：枚举 + 随机值

1. 因为字符串不可修改只能被赋值，所以将字符串转成数组
2. 遍历数组，判断当前项是不是问号，如果是则使用string.charCodeAt()方法获取前后字符的ASCII码值
3. 小写字母的ASCII码范围为97 - 122
4. 封装一个函数返回这个范围的ASCII码随机值所对应的字符，并且这个随机值不能等于传入的参数，如果等于则再次执行改函数

/**
 * 执行用时：76ms，超80%
 * 内存消耗：39MB，超63%
 */
function modifyString(s) {
  const arr = s.split("");
  let preStrCode = "";
  let nextStrCode = "";

  // 返回UTF-16代码单元序列不等于pre和next的a-z随机字符
  function random(pre, next) {
    const val = Math.floor(Math.random() * (122 - 97 + 1) + 97);

    if (val !== pre && val !== next) {
      // 将 UTF-16 代码单元序列转成字符串
      return String.fromCharCode(val);
    }

    return random(pre, next);
  }

  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === "?") {
      // 将字符转成UTF-16 代码单元序列
      preStrCode = arr[i - 1] ? arr[i - 1].charCodeAt() : "";

      if (arr[i + 1] && arr[i + 1] !== "?") {
        nextStrCode = arr[i + 1].charCodeAt();
      } else {
        nextStrCode = "";
      }

      arr[i] = random(preStrCode, nextStrCode);
    }
  }

  return arr.join("");
}

简化路径

题目链接

难度：中等

思路：栈

1. 首先创建一个栈stack用来存储目录和文件名，表示当前的目录结构
2. 再将路径字符串path以/为标识进行分割，得到一个由目录、文件、..组成的数组
3. 遍历这个数组，判断当前项是不是目录或者文件（由字母、数字、_组成），如果是将其push入栈，如果是..表示回到上一层目录，则将stack的栈顶元素pop出来
4. 最后将stack以/为标识进行拼接，得到的就是简化后的路径

/**
 * 执行用时：72ms，超82%
 * 内存消耗：39MB，超80%
 */
function simplifyPath(path) {
  const stack = [];
  const pathArr = path.split("/");
  // 文件名可以由字母、数组、_组成，并且长度至少为1
  const pathReg = /[\w\_]+/;

  pathArr.forEach((item) => {
    // 判断'/'之间的值是不是一个目录或者文件，超过3个点的也算目录或文件
    if (pathReg.test(item) || /[\.]{3,}/.test(item)) {
      stack.push(item);
    } else if (item === "..") {
      stack.pop();
    }
  });

  return "/" + stack.join("/");
}

一次编辑

题目链接

难度：中等

思路：普通

1. 题目要求编辑次数小于等于1，因此可以得出两个字符串的长度差不能大于 1
2. 如果两个字符串的长度相等，

仅仅翻转字母

题目链接

难度：简单

思路：双指针

1. 字符串只能被赋值，不能被修改，因此先将字符串转为数组
2. 创建两个指针，分别是 start 和 end。当两个指针所指的元素都是字母时进行交换，否则移动指针

/**
 * 执行用时：72ms，超65%
 * 内存消耗：38MB，43%
 */
function reverseOnlyLetters(s) {
  const arr = s.split("");
  const length = arr.length;
  const lettersReg = /[a-zA-Z]/;
  let start = 0;
  let end = length - 1;
  let startIsLetter = true;
  let endIsLetter = true;

  while (start < end) {
    startIsLetter = lettersReg.test(arr[start]);
    endIsLetter = lettersReg.test(arr[end]);

    // 两个指针所指元素都是字母，交换
    if (startIsLetter && endIsLetter) {
      [arr[start], arr[end]] = [arr[end], arr[start]];
      start++;
      end--;
    } else {
      // 两个指针所指元素存在不是字母的情况
      if (!startIsLetter) {
        start++;
      }

      if (!endIsLetter) {
        end--;
      }
    }
  }

  return arr.join("");
}

思路：字母栈，参考题解

1. 创建一个栈用来存储所有的字母
2. 遍历 s 字符串，将遇到的字母 push 入栈
3. 再次遍历 s 字符串，当遇到字母时，将栈顶元素 pop 出来，替代当前字母，这样就实现了字母的翻转

/**
 * 执行用时：64ms，超94%
 * 内存消耗：38MB，76%
 */
function reverseOnlyLetters(s) {
  const arr = s.split("");
  const length = arr.length;
  const lettersReg = /[a-zA-Z]/;
  const stack = [];

  // 收集所有字母，将字母push入栈
  for (let i = 0; i < length; i++) {
    if (lettersReg.test(arr[i])) {
      stack.push(arr[i]);
    }
  }

  for (let i = 0; i < length; i++) {
    if (lettersReg.test(arr[i])) {
      arr[i] = stack.pop();
    }
  }

  return arr.join("");
}

删除回文子序列

题目链接

难度：简单

思路：直接判断，参考题解

1. 根据题意，子序列可以不是连续的
2. 字符串中只有两种字符 a 和 b，因此最多需要删两次，最少删一次，因为字符串本身就是回文的
   3. 理解错题意了，以为是删除连续子序列

/**
 * 执行用时：64ms，超86%
 * 内存消耗：37MB，超30%
 */
function removePalindromeSub(s) {
  const length = s.length;

  for (let i = 0; i < Math.floor(length / 2); i++) {
    // 只要不是回文，就需要删两次
    if (s[i] !== s[length - 1 - i]) {
      return 2;
    }
  }

  return 1;
}

有效的括号

题目链接

难度：简单

思路：栈

1. 创建栈
2. 遍历字符串，将所有的左括号push入栈
3. 当遍历到右括号时，判断当前括号是否和栈顶元素配对，如果配对则继续遍历，不过不是直接 return false

/**
 * 执行用时：64ms，超94%
 * 内存消耗：38MB，超56%
 */
function isValid(s) {
  const stack = [];
  // 括号匹配map
  const map = {
    "(": ")",
    "{": "}",
    "[": "]",
  };

  for (let i = 0; i < s.length; i++) {
    // 如果是左括号，push入栈
    if (map[s[i]]) {
      stack.push(s[i]);
      // 判断栈顶元素对应的右括号是否和s[i]相等
    } else if (map[stack.pop()] !== s[i]) return false;
  }

  // 栈中元素数小于等于0表示，全部匹配成功
  return stack.length <= 0;
}

句子中的有效单词数

题目链接

难度：简单

思路：正则

1. 首先需要以空格为分隔符分隔句子，得到tokens数组
2. 遍历tokens数组，使用正则判断token是否符合条件的难点在于token中是否存在连字符
3. 因此创建两个正则表达式，分别匹配有连字符和无连字符的token

/**
 * 执行用时：68ms，超96%
 * 内存消耗：39MB，超96%
 */
function countValidWords(sentence) {
  let count = 0;
  // 将句子分解成多个token
  const tokens = sentence.split(" ");
  // 匹配存在连字符的token
  const tokenReg1 = /^[a-z]+\-[a-z]+(!|\.|,)?$/;
  // 匹配不存在连字符的token
  const tokenReg2 = /^[a-z]*(!|\.|,)?$/;

  // 遍历tokens，找出有效token
  tokens.forEach((token) => {
    // 过滤掉空字符
    if (!token) return;
    // 判断token中是否有连字符-
    if (token.includes("-")) {
      tokenReg1.test(token) && count++;
    } else {
      tokenReg2.test(token) && count++;
    }
  });

  return count;
}

数组

适龄的朋友

题目链接

难度：中等

思路：暴力法

1. 从题中可以知道年龄低的用户不能向比自己年龄大的用户发起请求
2. 对ages进行降序排序，保证发起请求的人比被请求的人年龄大或者相等
3. 最后再判断被请求用户是否满足ages[y] > 0.5 * ages[x] + 7即可
4. 需要注意的是年龄相同的用户可以相互通信，需要特殊处理

/**
 * 执行用时：1460ms，超33%
 * 内存消耗：45.6MB，超25%
 */
function numFriendRequests(ages) {
  let sum = 0;

  // 将年龄从大到小排序
  ages.sort((i, j) => j - i);

  for (let x = 0; x < ages.length; x++) {
    let index = x;

    // 向与自己年龄相等的人发起请求
    if (
      ages[index] === ages[index - 1] &&
      ages[index] > 0.5 * ages[index] + 7
    ) {
      while (index > 0 && ages[index] === ages[index - 1]) {
        sum++;
        index--;
      }
    }

    // 向比自己年龄小的人发起请求
    for (let y = x + 1; y < ages.length; y++) {
      // 因为从大到小排序，当前项不满足，之后的肯定也不满足
      if (ages[y] <= 0.5 * ages[x] + 7) break;
      sum++;
    }
  }

  return sum;
}

统计特殊四元组

题目链接

难度：简单

思路：暴力法，直接枚举

/**
 * 执行用时：72ms，超97%
 * 内存消耗：38MB，超78%
 */
function countQuadruplets(nums) {
  let count = 0;

  // -3是为了减少没必要的循环
  for (let a = 0; a < nums.length - 3; a++) {
    for (let b = a + 1; b < nums.length; b++) {
      for (let c = b + 1; c < nums.length; c++) {
        const target = nums[a] + nums[b] + nums[c];
        for (let d = c + 1; d < nums.length; d++) {
          // 可能存在重复元素
          if (nums[d] === target) {
            count++;
          }
        }
      }
    }
  }

  return count;
}

思路：hashMap

1. [3, n]这个区间的值都可以当作nums[d]
2. 从后向前遍历数组，记录相同值的个数
3. nums[1] + nums[b] + nums[c] = nums[d]的个数即为nums[d]出现的次数

/**
 * 执行用时：80ms，超90%
 * 内存消耗：39.6MB，超29%
 */
function countQuadruplets(nums) {
  const map = new Map();
  let count = 0;

  for (let c = nums.length - 2; c >= 2; c--) {
    // 更新值为nums[c+1]的个数
    map.set(nums[c + 1], (map.get(nums[c + 1]) || 0) + 1);

    for (let a = 0; a < c; a++) {
      for (b = a + 1; b < c; b++) {
        const sum = nums[a] + nums[b] + nums[c];
        count += map.get(sum) || 0;
      }
    }
  }

  return count;
}

一手顺子

题目链接

难度：中等

思路：排序 + splice

1. 因为题目要求每一组都是有序的，因此先对数组进行排序
2. 每一组的长度为groupSize，我们可以从下标为 0 的元素开始将连续的值组合在一起，如果不存在下一个连续的值，则表示当前hand数组不满足顺子条件
3. 匹配到满足条件的值后，将其从数组中删掉，防止相同元素出现在不同的组中

/**
 * 执行用时：684ms，超55%
 * 内存消耗：42MB，超100%
 */
function isNStraightHand(hand, groupSize) {
  // 不能等分直接false
  if (hand.length % groupSize !== 0) return false;
  hand.sort((i, j) => i - j);

  while (hand.length) {
    let size = groupSize - 1;
    let val = hand[0];
    let index;

    // shift和splice方法的作用是将已经使用过的元素从数组中删掉
    hand.shift();

    while (size) {
      index = hand.indexOf(val + 1);

      // 找不到下一个元素return false
      if (index === -1) return false;

      hand.splice(index, 1);
      // 连续元素，所以加一
      val++;
      size--;
    }
  }
  return true;
}

思路：排序 + hashMap

1. 首先排序，原因与方法一一样
2. 方法一使用了splice方法导致时间复杂度增加，想办法使用O(1)的复杂度代替splice方法，这里使用map实现
3. 方法一使用splice是为了将已经使用过的元素从数组中删除，避免重复使用。可以使用map记录相同元素的个数来实现相同的功能，每当元素被使用一次后，元素的可用次数减一，当下一个连续的元素的个数为 0 时，表示hand数组不满足顺子的条件

/**
 * 执行用时：104ms，超92%
 * 内存消耗：46MB，超44%
 */
function isNStraightHand(hand, groupSize) {
  const length = hand.length;

  // 不能等分直接false
  if (length % groupSize !== 0) return false;
  const map = new Map();

  // 排序
  hand.sort((i, j) => i - j);

  // 统计相同元素出现次数
  for (let i = 0; i < length; i++) {
    const count = map.get(hand[i]);
    map.set(hand[i], (count || 0) + 1);
  }

  for (let i = 0; i < length; i++) {
    let size = groupSize;
    let val = hand[i];
    let count;

    // 首先判断当前元素的个数是否为0,如果是0表示在之前的匹配中将次数用完了
    if (!map.get(val)) continue;

    while (size) {
      count = map.get(val);
      // 如果元素不存在或者个数为0,表示匹配失败
      if (!count) return false;
      // 值为val的元素个数减一
      map.set(val, count - 1);
      val++;
      size--;
    }
  }

  return true;
}

一维数组转二维数组

题目链接

难度：简单

思路：两层循环

/**
 * 执行用时：224ms，超50%
 * 内存消耗：60MB，超6%
 */
function construct2DArray(original, m, n) {
  const result = [];

  if (original.length / n !== m) {
    return result;
  }

  for (let i = 0; i < m; i++) {
    const arr = [];
    for (let j = 0; j < n; j++) {
      arr.push(original[i * n + j]);
    }
    result.push(arr);
  }

  return result;
}

思路：一层循环

1. 两种方法的时间复杂度是一样的
2. 第一种方法的时间复杂度是O(mn)
3. 第二种方法的时间复杂度是O(original.length)，然而original.length === m * n

/**
 * 执行用时：196ms，超95%
 * 内存消耗：60MB，超6%
 */
function construct2DArray(original, m, n) {
  const result = [];
  const length = original.length;

  if (length / n !== m) {
    return result;
  }

  let arr = [];

  for (let i = 0; i < length; i++) {
    arr.push(original[i]);
    if (arr.length === n) {
      result.push(arr);
      arr = [];
    }
  }

  return result;
}

至少是其他数字两倍的最大数

题目链接

难度：简单

思路

1. 整体思路就是找出nums中的最大值max，再找出第二大值secondMax
2. 判断max >= secondMax * 2是否成立，成立则存在满足条件的最大数
3. 对secondMax满足以上条件，则对其他数一定满足以上条件
4. 找max和secondMax值的方式还有很多，例如使用排序

/**
 * 执行用时：640ms，超96%
 * 内存消耗：38MB，超86%
 */
function dominantIndex(nums) {
  let max = -1;
  let secondMax = -1;
  let index = -1;

  for (let i = 0; i < nums.length; i++) {
    if (nums[i] > max) {
      // 更新最大值和第二大值
      secondMax = max;
      max = nums[i];
      index = i;
    } else if (nums[i] > secondMax) {
      // 更新第二大值
      secondMax = nums[i];
    }
  }

  return max >= secondMax * 2 ? index : -1;
}

最小时间差

题目链接

难度：中等

思路：暴力法，两层循环

1. 当前时间和之后的所有时间进行比较，找出最小差

/**
 * 执行用时：超时
 */
function findMinDifference(timePoints) {
  const length = timePoints.length;
  const formatTime = (time) => {
    const [hour, minute] = time.split(":");
    return +hour * 60 + +minute;
  };
  const wholeTime = formatTime("24:00");
  let min = Infinity;

  for (let i = 0; i < length - 1; i++) {
    const currTime = formatTime(timePoints[i]);
    for (let j = i + 1; j < length; j++) {
      const nextTime = formatTime(timePoints[j]);
      const minus = Math.abs(currTime - nextTime);
      // 更新最小值
      min = Math.min(Math.min(wholeTime - minus, minus), min);
    }
  }

  return min;
}

思路：排序 + 一次循环

1. 从小到大对时间进行排序
2. 排序后最小时间差可以通过相邻时间比较和首尾时间比较得到

/**
 * 执行用时：92ms，超50%
 * 内存消耗：40MB，超62%
 */
function findMinDifference(timePoints) {
  // 将时间字符串转为分钟
  const formatTime = (time) => {
    const [hour, minute] = time.split(":");
    return +hour * 60 + +minute;
  };
  let min = Infinity;

  // 对时间字符串从小到大排序
  timePoints.sort();

  const firstTime = formatTime(timePoints[0]);
  let preTime = firstTime;

  // 遍历数组
  for (let i = 1; i < timePoints.length; i++) {
    const currTime = formatTime(timePoints[i]);
    // 比较相邻时间差
    min = Math.min(currTime - preTime, min);
    preTime = currTime;
  }

  // 比较首尾时间差
  const minus = Math.abs(firstTime - preTime);
  min = Math.min(min, Math.min(1440 - minus, minus));

  return min;
}

存在重复元素 II

题目链接

重点关注

难度：简单

思路：暴力法

1. 让下标为i的元素和i + 1到i + k这个范围内的所有元素进行比较，判断是否满足题目的条件

/**
 * 执行用时：5268ms，超12%
 * 内存消耗：44MB，超90%
 */
function containsNearbyDuplicate(nums, k) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j <= i + k; j++) {
      if (nums[i] === nums[j]) {
        return true;
      }
    }
  }

  return false;
}

思路：哈希表

1. 创建 HashMap，用来存储元素对应的下标
2. 遍历数组，判断当前元素在 map 中是否存在，如果存在取出上一个相同元素的下标，判断与当前下标的差是否小于等于 k。如果不存在则存入 map
3. 利用 hashMap 减少一次循环

/**
 * 执行用时：96ms，超93%
 * 内存消耗：58MB，超23%
 */
function containsNearbyDuplicate(nums, k) {
  const map = new Map();

  for (let i = 0; i < nums.length; i++) {
    const index = map.get(nums[i]);
    if (typeof index !== "undefined") {
      if (Math.abs(index - i) <= k) return true;
    }

    map.set(nums[i], i);
  }

  return false;
}

单调数列

题目链接

难度：简单

思路：一次遍历

1. 假设 nums 是单调数列
2. 根据首尾元素判断数组单调的方向
3. 遍历数组，判断数组是否满足该方向上的单调

/**
 * 执行用时：96ms，超84%
 * 内存消耗：49MS，超78%
 */
function isMonotomic(nums) {
  const length = nums.length;

  if (nums[0] >= nums[length - 1]) {
    // 单调递减中遇到前者小于后者时，表示不是单调的
    for (let i = 0; i < length; i++) {
      if (nums[i] < nums[i + 1]) return false;
    }
  } else {
    // 单调递增中遇到前者大于后者，表示不是单调的
    for (let i = 0; i < length; i++) {
      if (nums[i] > nums[i + 1]) return false;
    }
  }

  return true;
}

思路：一次遍历，参考题解

1. 定义变量 dec 和 inc 表示是否为递减或者递增数列，默认为 true
2. 遍历数组，如果当前项大于下一项，让 inc 为 false; 如果当前项小于下一项，dec 为 false
3. 最后只要有一个变量为 true 则表示是单调数列

/**
 * 执行用时：100ms，超69%
 * 内存消耗：49MS，超69%
 */
function isMonotomic(nums) {
  let dec = true;
  let inc = true;

  for (let i = 0; i < nums.length - 1; i++) {
    if (nums[i] > nums[i + 1]) {
      inc = false;
    }

    if (nums[i] < nums[i + 1]) {
      dec = false;
    }
  }

  return dec || inc;
}

排序数组

题目链接

难度：中等

思路：递归快排

1. 在数组中取一个中间值，然后遍历数组
2. 将大于这个中间值的值放在右侧，小于的放在左侧
3. 然后在对左右两侧的值进行相同的操作

/**
 * 执行用时：184ms，超62%
 * 内存消耗：58MB，超5%
 */
function sortArray(nums) {
  // 重要：递归出口条件
  if (nums.length <= 1) {
    return nums;
  }

  const index = Math.floor(nums.length / 2);
  const middle = nums[index];
  const left = [];
  const right = [];

  // 遍历数组，将大于和小于middle的值放在两侧
  nums.forEach((num, i) => {
    // middle元素不参与遍历
    if (i === index) return;

    if (num > middle) {
      right.push(num);
    } else if (num <= middle) {
      // 这里必须是小于等于，因为值为middle的元素在数组中可能存在多个
      left.push(num);
    }
  });

  // 最终将所有middle元素连接在一起
  return sortArray(left).concat(middle).concat(sortArray(right));
}

两数之和

题目链接

难度：简单

思路：哈希表

1. 创建哈希 map，key 为数组的某个值，value 是这个值在数组中对应的下标
2. 遍历数组，判断 map 中是否存在 key 为 target - nums[i]的值
3. 存在则找到了和为 target 的值，返回其下标，不存在则将当前值和下标存入 map

/**
 * 执行用时：72ms，超89%
 * 内存消耗：43MB，超5%
 */
function twoSum(nums, target) {
  const map = new Map();

  for (let i = 0; i < nums.length; i++) {
    // 在map中找target - nums[index]
    const value = map.get(target - nums[i]);

    if (typeof value === "undefined") {
      // 不存在则将当前值添加到map中
      map.set(nums[i], i);
    } else {
      return [value, i];
    }
  }
}

游戏中弱角色的数量

题目链接

难度：中等

思路：排序

1. 按照攻击力从大到小进行排序，当遇到攻击力相等的角色时，让防御力大的角色在后面
2. 创建一个变量用来表示当前最大的防御力
3. 遍历数组，因为攻击力是从大到小排序的，因此只需要比较防御力即可
4. 记录目前防御力的最大值，如果当前角色的防御力小于最大值，则表示当前角色是弱角色

/**
 * 执行用时：328ms，超100%
 * 内存消耗：74MB，超7%
 */
function numberOfWeakCharacters(properties) {
  // 排序，如果攻击值相等，则按照防御值进行排序，否则按照攻击值进行排序(从大到小)
  properties.sort((a, b) => (a[0] === b[0] ? a[1] - b[1] : b[0] - a[0]));

  // 记录有多少个弱角色
  let count = 0;
  // 记录最大防御值
  let maxDef = 0;

  for (let p of properties) {
    // 如果当前角色的防御值大于maxDef，更新maxDef
    if (p[1] > maxDef) {
      maxDef = p[1];
    } else if (p[1] < maxDef) {
      // 如果当前角色防御值小于最大值，则当前角色是弱角色，因为其攻击值也小于
      count++;
    }
  }

  return count;
}

买卖股票的最佳时机(关注)

题目链接

难点：简单

思路：一次遍历

1. 要想获得最大利润，肯定是在最低点买入，最高点卖出，关键在于如何找到最低点和最高点(肯定是在最低点后面)
2. 创建min代表当前遇到的最低股票，profit代表当前的最大利润
3. 难点在于需要动态的更新min最小值，但是更新了并不代表最大利润也会更新，这个需要注意

/**
 * 执行用时：76ms，超98%
 * 内存消耗：50MB，超17%
 */
function maxProfit(prices) {
  let min = Infinity;
  // 最大利润
  let profit = 0;

  for (let i = 0; i < prices.length - 1; i++) {
    // 如果当前股价小于当前的最小值，则更新最小值
    if (prices[i] < min) {
      min = prices[i];
    }

    // 如果当前股价大于下一天的股价，则直接跳过，不用比较
    if (prices[i] > prices[i + 1]) {
      continue;
    }

    // 如果最小值小于当前值，比较两者的差和当前的最大值哪个大
    if (min < prices[i + 1]) {
      profit = Math.max(prices[i + 1] - min, profit);
    }
  }

  return profit;
}

二进制

位运算符

• &，与运算符：运算符两侧的值都是 1 才返回 1，否则返回 0
• |，或运算符：运算符两侧只要有一个 1 就返回 1，两个全是 0 返回 0
• ~，非运算符：按位取反
• ^，按位异或运算符：不同值异或返回 1,相同值异或返回 0
• <<，左移运算符：将二进制值向左移动，右侧补 0
• >>，有符号右移：将二进制向右移动，左侧的值补符号位
• >>>，无符号右移：将二进制向右移动，左侧补 0

二进制中 1 的个数

题目链接

难度：简单

思路：位运算

1. 1 & 1 => 1，1 & 0 = 0，让二进制的每一位&1，即可知道当前位是不是 1
2. >>>无符号右移位操作符可以向右移动二进制

function hammingWeight(n) {
  let count = 0;
  for (let i = 0; i < 32; i++) {
    if ((n >>> i) & 1) {
      count++;
    }
  }
  return count;
}

其他

完美数

题目链接

难度：简单

思路：暴力枚举

/**
 * 执行用时：2680ms，超6%
 * 内存消耗：38MB，超52%
 */
function checkPerfectNumber(num) {
  let sum = 0;

  for (let i = 1; i < num; i++) {
    const val = num / i;

    // 判断val是不是整数
    if (val === Math.floor(val)) {
      sum += i;
    }

    if (sum > num) return false;
  }

  return sum === num;
}

LRU 缓存(关注)

题目链接

难度：中等

思路：哈希表 + 双向链表，参考题解

1. LRU(least recently used)最近最少次使用
2. LRU数据结构涉及到了查询和删除，并且要求O(1)的时间复杂度
3. 查询操作肯定会使用O(1)的哈希表
4. 删除操作有多种方法，但是满足时间复杂度为0(1)的只有双向链表
   • 数组的删除和插入等操作都是O(n)
   • 单向链表的删除操作需要从头节点开始遍历，也是O(n)
   • 双向链表存有上一个节点，因此删除当前节点只需要O(1)
5. key-value存在链表节点中，被使用的key更新到链表头部，那么链表尾部就是最久未使用的值。哈希表存储key-Node来和链表建立引用关系
6. get和put操作都会更新链表的顺序

// 定义双向链表节点
class DoubleListNode {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.pre = null;
    this.next = null;
  }
}

/**
 * 执行用时：620ms，超64%
 * 内存消耗：89MB，超77%
 */
class LRUCache {
  constructor(capacity) {
    // 定义当前容量
    this.capacity = capacity;
    // 定义已使用的容量
    this.usage = 0;
    // 定义哈希表，存储key - ListNode
    this.cache = new Map();
    // 定义双向链表dummy头节点，定义dummy节点的意义在于可以正常操作头节点和尾节点
    this.dummyHead = new DoubleListNode();
    // 定义双向链表dummy尾节点
    this.dummyTail = new DoubleListNode();
    // 构建双向链表，首尾绑定
    this.dummyHead.next = this.dummyTail;
    this.dummyTail.pre = this.dummyHead;
  }

  // 判断key是否存在
  isExist(key) {
    return this.cache.has(key);
  }

  // 获取键为key的值，不存在返回-1
  get(key) {
    const node = this.cache.get(key);
    // key不存在，返回-1
    if (!this.isExist(key)) return -1;
    // key存在，需要更新当前node的位置，更新到头部
    this.moveToHead(node);
    return node.value;
  }

  // 添加key-value，如果key存在则更新value，并将其移动到链表头部（最近使用）
  // 如果key不存在，判断缓存容量是否够用，够用则直接添加
  // 不够用则需要删除链表尾部节点（最久未使用），然后在添加，并移动到链表头部
  put(key, value) {
    // key存在，不需要考虑容量，直接更新
    if (this.isExist(key)) {
      const node = this.cache.get(key);
      node && (node.value = value);
      // 值被更新了(被使用了)，将其移动到链表头部
      this.moveToHead(node);
    } else {
      // key不存在，新建节点，需要考虑容量
      const newNode = new DoubleListNode(key, value);
      if (this.usage >= this.capacity) {
        // 容量不够用，需要删除链表尾节点，即dummyTail节点的前一个
        const deleteNode = this.dummyTail.pre;
        this.removeNode(deleteNode);
        // 删除哈希表中的引用
        this.cache.delete(deleteNode.key);
        // 删除了一个节点，已使用容量减一
        this.usage--;
      }

      // 在链表中添加新节点，添加到头部
      this.addNewNode(newNode);
      // 将新值添加到哈希表中
      this.cache.set(key, newNode);
      // 新增了节点，已使用节点加一
      this.usage++;
    }
  }

  // 把节点移动到链表头部
  moveToHead(node) {
    // 首先将node从链表中删除
    this.removeNode(node);
    // 在将node添加到链表头部
    this.addNewNode(node);
  }

  // 链表添加新节点，直接添加到头部
  addNewNode(node) {
    // 让node.next指向当前的头节点
    node.next = this.dummyHead.next;
    // 让当前头节点的pre指向node
    this.dummyHead.next.pre = node;
    // 让dummyHead.next指向node
    this.dummyHead.next = node;
    node.pre = this.dummyHead;
  }

  // 删除链表节点需要同时修改next和pre，刚开始忘了修改pre了
  removeNode(node) {
    node.next.pre = node.pre;
    node.pre.next = node.next;
  }
}

const LRU = new LRUCache(2);