跳到主要内容

力扣 200-299

200.岛屿数量（dfs）​

/**
 * @param {character[][]} grid
 * @return {number}
 */
// count = 0
// 遍历二维数组，如果当前位置为陆地，count++,开始变0操作
// 变0函数（i，j,grid)，如果不符合范围或不为0了，直接return
// 否则变为0，且向四个方向变0
const numIslands = (grid) => {
  let count = 0;
  let m = grid.length;
  let n = grid[0].length;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      //循环网格
      if (grid[i][j] === "1") {
        //如果为陆地，count++，
        count++;
        turnZero(i, j, grid);
      }
    }
  }
  function turnZero(i, j) {
    //沉没四周的陆地
    if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] === "0") return; //检查坐标的合法性
    grid[i][j] = "0"; //让四周的陆地变为海水, 整个grid作为参数传递
    turnZero(i, j + 1);
    turnZero(i, j - 1);
    turnZero(i + 1, j);
    turnZero(i - 1, j);
  }
  return count;
};

202.快乐数（类似快慢指针，链表环）​

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。 如果这个过程 结果为 1，那么这个数就是快乐数。 如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

/**
 * @param {number} n
 * @return {boolean}
 */
var isHappy = function (n) {
  let slow = n;
  // 有可能第一步就判断出是快乐数
  let fast = getNext(n);

  // 无限循环就是环
  while (fast !== 1) {
    slow = getNext(slow);
    fast = getNext(getNext(fast));
    if (slow === fast) {
      return false;
    }
  }

  return fast === 1;
};

let getNext = function (n) {
  let sum = 0;
  while (n > 0) {
    sum += Math.pow(n % 10, 2);
    n = Math.floor(n / 10);
  }
  return sum;
};

204.计数质数​

给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。

/**
 * @param {number} n
 * @return {number}
 */
var countPrimes = function (n) {
  const isPrime = new Array(n).fill(1);
  let ans = 0;
  for (let i = 2; i < n; ++i) {
    if (isPrime[i]) {
      ans += 1;
      // i=2,可以确定4,6,8不是
      // i=3,可以确定9,12,15不是
      for (let j = i * i; j < n; j += i) {
        // j=i2 i2+i i2+2i
        isPrime[j] = 0;
      }
    }
  }
  return ans;
};

206.反转链表/翻转链表/链表反转​

const reverseList = function (head) {
  if (!head || !head.next) {
    return head;
  }
  let curr = head;
  let prev = null;
  // n 2 3 4 n
  // 2 n 3 4 n
  // 3 2 n 4 n
  // 4 3 2 n n
  // n 4 3 2 n
  while (curr) {
    let next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
};

// 递归法
var reverseList = function (head) {
  if (!head || !head.next) {
    return head;
  }
  const newHead = reverseList(head.next);
  head.next.next = head;
  head.next = null;
  return newHead;
};

208.实现 Trie(前缀树)​

前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false
const Trie = function () {
  this.root = new TrieNode();
};

const TrieNode = function () {
  //  当前节点的子节点
  this.next = {};
  //  当前是否是结束节点
  this.isEnd = false;
};

// 插入
Trie.prototype.insert = function (word) {
  if (!word) return false;
  // 每次都从root开始搜索
  let node = this.root;
  // 遍历word
  for (let i = 0; i < word.length; i++) {
    // 没有则创建
    node.next[word[i]] = node.next[word[i]] || new TrieNode();
    // 进入到下一个
    node = node.next[word[i]];
  }
  node.isEnd = true;
  return true;
};

// 搜索
Trie.prototype.search = function (word) {
  if (!word) return false;
  let node = this.root;
  for (let i = 0; i < word.length; i++) {
    if (node.next[word[i]]) {
      node = node.next[word[i]];
    } else {
      return false;
    }
  }
  // 树里有appleTree,搜索apple应该返回false，因为e不是end
  return node.isEnd;
};

// 前缀匹配
Trie.prototype.startsWith = function (prefix) {
  if (!prefix) return false;
  let node = this.root;
  for (let i = 0; i < prefix.length; i++) {
    if (node.next[prefix[i]]) {
      node = node.next[prefix[i]];
    } else {
      return false;
    }
  }
  return true;
};

209.长度最小的子数组（滑动窗口）​

出该数组中满足其总和大于等于 target 的长度最小的 连续 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

var minSubArrayLen = function (target, nums) {
  let l = 0;
  let r = 0;
  let sum = 0;
  let min = Infinity;
  sum = 0;
  while (l <= r && r < nums.length) {
    sum += nums[r];
    r++;
    while (sum >= target) {
      min = Math.min(min, r - l);
      sum -= nums[l];
      l++;
    }
  }

  return min === Infinity ? 0 : min;
};

213.打家劫舍 II​

地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function (nums) {
  let n = nums.length;
  if (n == 1) {
    return nums[0];
  }
  let dp = new Array(n).fill(0);
  dp[0] = nums[0];
  // [2,3] 初始值
  dp[1] = nums[0] > nums[1] ? nums[0] : nums[1];
  // 第一种情况：只遍历1~n-1的房屋，最后一个房屋不遍历
  for (let i = 2; i < n - 1; i++) {
    dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
  }
  let max1 = dp[n - 2];
  // 第二种情况：只遍历2~n的房屋，第一个房屋不遍历.
  dp[1] = nums[1];
  dp[2] = nums[1] > nums[2] ? nums[1] : nums[2];
  for (let i = 3; i < n; i++) {
    dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
  }
  let max2 = dp[n - 1];
  max1 = max1 > max2 ? max1 : max2;
  return max1;
};

214.*最短回文串（kmp）​

给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为 回文串 。找到并返回可以用这种方式转换的最短回文串。

/**
 * @param {string} s
 * @return {string}
 */
const shortestPalindrome = (s) => {
  const rev_s = s.split('').reverse().join('');
  const str = s + "#" + rev_s;
  const next = new Array(str.length).fill(0);
  const kmp = (next, str) => {
    next[0] = 0;
    let len = 0;
    let i = 1;
    // 扩展前缀
    for (let i = 1, j = 0; i < str.length; i++) {
        while (j > 0 && str[i] !== str[j]) {
            j = next[j - 1];
        }
        if (str[i] == str[j]) {
            j++;
        }
        next[i] = j;
    }
  kmp(next, str);
  const maxLen = next[str.length - 1]; // 最长回文前缀的长度
  const add = s.substring(maxLen).split('').reverse().join('');
  return add + s;
};

215.topK(快排)​

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

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

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

O(n)

1.构建一个最小堆，并依次把数组的值插入堆中 2.当堆的容量超过 k 时，就删除堆顶 3.插入结束后，堆顶就是第 k 个最大元素

时间复杂度：O（nlogk） 空间复杂度：O（k）

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
// 整个流程就是上浮下沉
var findKthLargest = function (nums, k) {
  let heapSize = nums.length;
  buildMaxHeap(nums, heapSize); //构建大顶堆 大小为heapSize
  //大顶堆 前k-1个堆顶元素不断和数组的末尾元素交换 然后重新heapify堆顶元素
  //这个操作就是之前小顶堆出堆顶的操作，只不过现在是原地排序
  for (let i = nums.length - 1; i >= nums.length - k + 1; i--) {
    [nums[i], nums[0]] = [nums[0], nums[i]];
    //交换堆顶和数组末尾元素
    --heapSize; //堆大小减1
    maxHeapify(nums, 0, heapSize); //重新heapify
  }
  return nums[0]; //返回堆顶元素，就是第k大的元素

  function buildMaxHeap(nums, heapSize) {
    for (let i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {
      //从第一个非叶子节点开始构建
      maxHeapify(nums, i, heapSize);
    }
  }
  // 从左向右，自上而下的调整节点
  function maxHeapify(heap, i, len) {
    let max = i;
    let left = 2 * i + 1;
    let right = 2 * i + 2;
    max = left < len && heap[left] > heap[max] ? left : max;
    max = right < len && heap[right] > heap[max] ? right : max;
    if (max !== i) {
      [heap[i], heap[max]] = [heap[max], heap[i]];
      maxHeapify(heap, max, len);
    }
  }
};

2.死的人

时间复杂度 O（n） 空间复杂度常数

我们仅仅需要在每执行一次快排的时候，比较基准值位置是否在 n-k 位置上，

// 升序，用 n-k 如果小于 n-k ，则第 k 个最大值在基准值的右边，我们只需递归快排基准值右边的子序列即可； 如果大于 n-k ，则第 k 个最大值在基准值的左边，我们只需递归快排基准值左边的子序列即可； 如果等于 n-k ，则第 k 个最大值就是基准值

let findKthLargest = function (nums, k) {
  // 因为是升序，所以把k处理成length-k
  return quickSelect(nums, nums.length - k);
};

let quickSelect = (arr, k) => {
  return quick(arr, 0, arr.length - 1, k);
};

let quick = (arr, left, right, k) => {
  let index;
  if (left < right) {
    // 划分数组
    index = partition(arr, left, right);
    // Top k, 最后缩到一位时，必然能确定第topk的位置，
    // partition后 该位置左边全是小于它的，右边全是大于它的！
    if (k === index) {
      return arr[index];
    } else if (k < index) {
      // Top k 在左边
      return quick(arr, left, index - 1, k);
    } else {
      // Top k 在右边
      return quick(arr, index + 1, right, k);
    }
  }
  return arr[left];
};

let partition = (arr, l, r) => {
  // 取中间项为基准，因为有random，所以加一
  const pivot = arr[Math.floor(Math.random() * (r - l + 1)) + l],
  // 开始调整
  while (l < r) {
    // 左指针右移
    while (arr[l] < pivot) l++;
    // 右指针左移
    while (arr[r] > pivot) r--;
    if (arr[l] === arr[r] && l < r) {
      l++;
    }
    // 交换
    if (l < r) {
      [array[l], array[r]] = [array[r], array[l]];
    };
  }
  return l;
};

221.最大正方形(dp,min)​

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

100 010

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalSquare = function (matrix) {
  // 用ma[i][j]表示以该点为右下角正方形的最大边长
  // 且ma[i][j]=min(ma[i-1][j], ma[i][j-1], ma[i-1][j-1]) + 1;
  // 只能找min,短板效应确定可以加的
  const long = matrix.length;
  if (long < 1) {
    return 0;
  }
  const width = matrix[0].length;
  let max = 0;
  for (let i = 0; i < long; i++) {
    for (let j = 0; j < width; j++) {
      if (matrix[i][j] === "1") {
        matrix[i][j] =
          i !== 0 && j !== 0
            ? Math.min(
                matrix[i - 1][j],
                matrix[i][j - 1],
                matrix[i - 1][j - 1]
              ) + 1
            : 1;
        max = Math.max(max, matrix[i][j]);
      } else {
        matrix[i][j] = 0;
      }
    }
  }
  return max * max;
};

226.翻转二叉树（后序）​

var invertTree = function (root) {
  if (!root) {
    return null;
  }
  const left = invertTree(root.left);
  const right = invertTree(root.right);
  root.left = right;
  root.right = left;
  return root;
};

227.基本计算器 II(栈)​

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。

你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。

注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

// 设一个stack数组，n为0，用来记位数，sign用来存上一次的符号，默认是+，因为刚开始数字没有上一个符号
// 遍历数组，如果当前位为' ',continue
// 如果当前位处于0-9，n= n*10+parseInt(s[i]) continue
// 否则当前位为符号，更新符号前，把旧符号和数字合成，入栈，四种情况+n,-n,stk.pop()*n,~~stk.pop()/n
// 更新sign为当前位，n为0
// 最后返回stk.reduce(+,0)

var calculate = function (s) {
  let stack = [],
    n = 0,
    sign = "+"; // stack用来存数值，sign用来存上一个符号
  for (let i = 0; i <= s.length; i++) {
    if (s[i] === " ") continue;
    if (s[i] <= "9" && s[i] >= "0") {
      n = n * 10 + parseInt(s[i]);
      continue;
    }
    switch (sign) {
      case "+":
        stack.push(n);
        break;
      case "-":
        stack.push(-n);
        break;
      case "*":
        stack.push(stack.pop() * n);
        break;
      case "/":
        stack.push(~~(stack.pop() / n));
        break; // ~~用来去掉小数部分
    }
    sign = s[i];
    n = 0;
  }
  return stack.reduce((pre, cur) => pre + cur, 0); // 赋予初始值，第一次pre为0，cur为arr[0]
};

234.回文链表(链表反转+中间节点)​

给你一个单链表的头节点 head ，请你判断该链表是否为 回文链表。如果是，返回 true ；否则，返回 false 。

var isPalindrome = function (head) {
  // 1. 找到中间节点
  let tail = middleNode(head).next;

  // 2. 反转后半段链表
  tail = reverseList(tail);

  // 3. 判断前半段和反转的后半段链表，值是否相等
  while (tail) {
    if (tail.val !== head.val) {
      return false;
    }
    tail = tail.next;
    head = head.next;
  }

  return true;
};

// 找到中间节点
var middleNode = function (head) {
  let slow = head;
  let fast = head;
  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
};

// 反转链表
var reverseList = function (head) {
  let prev = null;
  let curr = head;
  while (curr) {
    let next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
};

230.二叉搜索树中第 K 小的元素​

const kthSmallest = function (root, k) {
  let res = null;
  let inOrderTraverseNode = function (node) {
    if (node !== null && k > 0) {
      // 先遍历左⼦树
      inOrderTraverseNode(node.left);
      k--;
      // 然后根节点
      if (k === 0) {
        res = node.val;
        return;
      }
      // 再遍历右⼦树
      inOrderTraverseNode(node.right);
    }
  };
  inOrderTraverseNode(root);
  return res;
};

236.二叉树的最近公共祖先（dfs）​

（一个节点也可以是它自己的祖先）。

//  递归函数(root,p节点,q节点)
// 特殊!root,return false
// 后序遍历，lson = 递归函数（root.left,p,q) rson同理
// 判断正确性直接ans=root：1.lson&&rson 2.（root节点值等于p值或q值）且lson或rson即至少一个
// 判断正确性失败，return lson||rson||root节点值等于p值或q值
// 启动函数
var lowestCommonAncestor = function (root, p, q) {
  const dfs = (root, p, q) => {
    if (!root) return false;
    const lson = dfs(root.left, p, q);
    const rson = dfs(root.right, p, q);
    // 满足终极条件，直接设答案为root
    // 1.左子树中有节点，右子树中有节点
    // 2.或左/右节点刚好为公共祖先，且至少有一个子树节点
    if (
      (lson && rson) ||
      ((root.val === p.val || root.val === q.val) && (lson || rson))
    ) {
      ans = root;
      return;
    }
    // 穿透性
    return lson || rson || root.val === p.val || root.val === q.val;
  };
  let ans;
  dfs(root, p, q);
  return ans;
};

239.滑动窗口最大值​

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function (nums, k) {
  // deque 存有nums中数字的下标
  // [3]
  // [5]
  const deque = [];
  const res = [];
  for (let i = 0; i < nums.length; i++) {
    //1.保留的下标已经过于远，舍掉
    if (i - deque[0] >= k) {
      deque.shift();
    }
    // 2.留下窗口内大于当前的值的，且下标满足在窗口内；反正上一步会清不在窗口里的
    while (nums[deque[deque.length - 1]] <= nums[i]) {
      deque.pop();
    }
    // 3.这次的i可能会在下次留最大值时清除掉，不清除也没关系
    // 因为加result只会看deque的第一位，只要保证第一位肯定是窗口内最大值即可
    deque.push(i);
    // 4.当下标=k-1,证明窗口已经至少看了0..k个数，可以开始加入res
    if (i >= k - 1) {
      res.push(nums[deque[0]]);
    }
  }
  // n-k个滑动窗口，存在数组里
  return res;
};

240.搜索二维矩阵 II（左下角开始右找上找）​

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。 每列的元素从上到下升序排列。

1234 5678

不存在 1239 5678

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */

var searchMatrix = function (matrix, target) {
  const m = matrix.length,
    n = matrix[0].length;
  //从矩阵最左下角开始搜起
  for (let i = m - 1, j = 0; i >= 0 && j < n; ) {
    if (matrix[i][j] == target) return true;
    // 向右找
    else if (matrix[i][j] < target) j += 1;
    // 向父亲找
    else i -= 1;
  }
  return false;
};

260.只出现一次的数字 III​

给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。

var singleNumber = function (nums) {
  let xorsum = 0;

  for (const num of nums) {
    xorsum ^= num;
  }
  let type1 = 0,
    type2 = 0;
  const lsb = xorsum & -xorsum;
  for (const num of nums) {
    if (num & lsb) {
      type1 ^= num;
    } else {
      type2 ^= num;
    }
  }
  return [type1, type2];
};
var singleNumber = function (nums) {
  const freq = new Map();
  for (const num of nums) {
    freq.set(num, (freq.get(num) || 0) + 1);
  }
  const ans = [];
  for (const [num, occ] of freq.entries()) {
    if (occ === 1) {
      ans.push(num);
    }
  }
  return ans;
};

283.移动零(双指针)​

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */

//  设左指针位于0，右指针位于0，
// 右指针遍历数组
// 如果右指针不等于0，则左右指针值互换，左指针走动
// 记得右指针走动
var moveZeroes = function (nums) {
  // 2,2,0,0,2
  // 2,2,2,0,0
  let len = nums.length;
  let left = 0;
  right = 0;
  while (right < len) {
    if (nums[right] !== 0) {
      [nums[left], nums[right]] = [nums[right], nums[left]];
      left++;
    }
    right++;
  }
};

297.二叉树序列化和反序列化​

// 序列化，递归（root,str)
// 如果root为null，str加None,
// 否则先序遍历储存，str + root.val
// 然后将新的str传给序列化（root.left,str)
// 返回新新的str传给序列化（root.right,str)

// 反序列化，由于是先序遍历，先split,如果数组第一位是none，*记得shift!否则root.right时拿到的数组还是null开头,返回null
// 创建root节点 root = new TreeNode(parseInt(dataList[0]))
// dataList移出根节点
// root.left = 递归的的建立root(新dataList)

// 我们序列化成这样形式，便于反序列化
// 1,2,3,None,None,4,5,
var serialize = function (root) {
  let str = "";
  const stringify = (root) => {
    if (root === null) {
      str += "None,";
    } else {
      str += root.val + ",";
      stringify(root.left, str);
      stringify(root.right, str);
    }
  };
  stringify(root);
  return str;
};

var deserialize = function (data) {
  const dataList = data.split(",");

  return parse(dataList);
};

const parse = (dataList) => {
  if (dataList[0] === "None") {
    dataList.shift();
    return null;
  }

  const root = new TreeNode(parseInt(dataList[0]));
  dataList.shift();
  root.left = parse(dataList);
  root.right = parse(dataList);

  return root;
};