Giter Club home page Giter Club logo

javascript-leetcode's Introduction

前端食堂的 LeetCode 题解仓库

2021 年计划,这个仓库写满 100 篇前端面试高频 LeetCode 题解(JavaScript)。

题目序号为 LeetCode 对应题目的序号,题解内有链接跳转到对应题目。

如果你是初学者,可能你需要一份数据结构与算法的入门资料,我之前写过一些文章,如下:

感谢 Star🌟

进度

已经完成 100 道。

数组

链表

队列

贪心

回溯

字符串

排序

DFS

LRU

位运算

二分查找

动态规划

交流

加我微信: hungryturbo 备注「加群」即可。

javascript-leetcode's People

Contributors

geekhyt avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar

javascript-leetcode's Issues

24. 两两交换链表中的节点

原题链接

链表基础知识

数组想必大家都很熟悉,几乎我们每天都会操作它,我们可以对比数组来学习链表。

首先要明确的是,链表和数组的底层存储结构不同,数组要求存储在一块连续的内存中,而链表是通过指针将一组零散的内存块串联起来。可见链表对内存的要求降低了,但是随机访问的性能就没有数组好了,需要 O(n) 的时间复杂度。

下图中展示了单链表及单链表的添加和删除操作,其实链表操作的本质就是处理链表结点之间的指针

list

在删除链表结点的操作中,我们只需要将需要删除结点的前驱结点的 next 指针,指向其后继即可。这样,当前被删除的结点就被丢弃在内存中,等待着它的是被垃圾回收器清除。

为了更便于你理解,链表可以类比现实生活中的火车,火车的每节车厢就是链表的一个个结点。车厢之间相互连接,可以添加或者移除掉。春运时,客运量比较大,列车一般会加挂车厢。

链表的结点结构由数据域和指针域组成,在 JavaScript 中,以嵌套的对象形式实现。

{
    // 数据域
    val: 1,
    // 指针域
    next: {
        val:2,
        next: ...
    }
}  

回到本题,先明确想要交换节点共需要有三个指针进行改变。

1.所以我们需要在链表头部添加一个哨兵节点
2.循环中首先操作三个指针完成节点交换
3.指针右移,进行下一对节点的交换

两两交换链表中的节点

迭代 + 哨兵节点

const swapPairs = (head) => {
  const dummy = new ListNode(0);
  dummy.next = head; // 头部添加哨兵节点
  let prev = dummy;

  while (head && head.next) {
    const next = head.next; // 保存 head.next
    head.next = next.next;
    next.next = head;
    prev.next = next;
    // 下面两个操作将指针更新
    prev = head;      
    head = head.next;
  }
  return dummy.next;
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

递归

如果你对递归还觉得掌握的不够透彻,可以移步我的这篇专栏 你真的懂递归吗?

回到本题的递归解法:

1.写递归解法的话,老套路,先明确终止条件,链表中没有节点或只有一个节点时无法进行交换。
2.接下来递归的进行两两交换节点并更新指针关系。
3.返回新链表的头节点 newHead。

const swapPairs = function (head) {
    // 递归终止条件
    if (head === null || head.next === null) {
        return head;
    }
    // 获得第 2 个节点
    let newHead = head.next;
    // 将第 1 个节点指向第 3 个节点,并从第 3 个节点开始递归
    head.next = swapPairs(newHead.next);
    // 将第 2 个节点指向第 1 个节点
    newHead.next = head;
    return newHead;
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

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

原题链接

快慢指针

先明确,删除倒数第 n 个结点,我们需要找到倒数第 n+1 个结点,删除其后继结点即可。

1.添加 prev 哨兵结点,处理边界问题。
2.借助快慢指针,快指针先走 n+1 步,然后快慢指针同步往前走,直到 fast.next 为 null。
3.删除倒数第 n 个结点,返回 prev.next。

const removeNthFromEnd = function(head, n) {
    let prev = new ListNode(0), fast = prev, slow = prev;
    prev.next = head;
    while (n--) {
        fast = fast.next;
    }
    while (fast && fast.next) {
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;
    return prev.next;
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

300. 最长递增子序列

原题链接

什么是上升子序列?

首先,我们需要对基本的概念进行了解和区分:

  • 子串:一定是连续的
  • 子序列:子序列不要求连续 例如:[6, 9, 12] 是 [1, 3, 6, 8, 9, 10, 12] 的一个子序列
  • 上升/递增子序列:一定是严格上升/递增的子序列

注意:子序列中元素的相对顺序必须保持在原始数组中的相对顺序

题解

动态规划

关于动态规划的**,还不了解的同学们可以移步我的这篇专栏入个门,「算法**」分治、动态规划、回溯、贪心一锅炖

我们可以将状态 dp[i] 定义为以 nums[i] 这个数结尾(一定包括 nums[i])的最长递增子序列的长度,并将 dp[i] 初始化为 1,因为每个元素都是一个单独的子序列。

定义状态转移方程:

  • 当我们遍历 nums[i] 时,需要同时对比已经遍历过的 nums[j]
  • 如果 nums[i] > nums[j]nums[i] 就可以加入到序列 nums[j] 的最后,长度就是 dp[j] + 1
    注:(0 <= j < i) (nums[j] < nums[i])
const lengthOfLIS = function(nums) {
    let n = nums.length
    if (n == 0) {
        return 0
    }
    let dp = new Array(n).fill(1)
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1)
            }
        }
    }
    return Math.max(...dp) 
}
  • 时间复杂度:O(n^2)
  • 空间复杂度:O(n)

这里我画了一张图,便于你理解。

进阶:你能将算法的时间复杂度降低到 O(n log(n)) 吗?

贪心 + 二分查找

关于贪心和二分查找还不了解的同学们可以移步我的这两篇专栏入个门。

这里再结合本题理解一下贪心**,同样是长度为 2 的序列,[1,2] 一定比 [1,4] 好,因为它更有潜力。换句话说,我们想要组成最长的递增子序列,就要让这个子序列中上升的尽可能的慢,这样才能更长。

我们可以创建一个 tails 数组,用来保存最长递增子序列,如果当前遍历的 nums[i] 大于 tails 的最后一个元素(也就是 tails 中的最大值)时,我们将其追加到后面即可。否则的话,我们就查找 tails 中第一个大于 nums[i] 的数并替换它。因为是单调递增的序列,我们可以使用二分查找,将时间复杂度降低到 O(logn)

const lengthOfLIS = function(nums) {
    let len = nums.length
    if (len <= 1) {
        return len
    }
    let tails = [nums[0]]
    for (let i = 0; i < len; i++) {
        // 当前遍历元素 nums[i] 大于 前一个递增子序列的 尾元素时,追加到后面即可
        if (nums[i] > tails[tails.length - 1]) {
            tails.push(nums[i])
        } else {
            // 否则,查找递增子序列中第一个大于当前值的元素,用当前遍历元素 nums[i] 替换它
            // 递增序列,可以使用二分查找
            let left = 0
            let right = tails.length - 1
            while (left < right) {
                let mid = (left + right) >> 1;
                if (tails[mid] < nums[i]) {
                    left = mid + 1
                } else {
                    right = mid
                }
            }
            tails[left] = nums[i]
        }
    }
    return tails.length
}
  • 时间复杂度:O(nlogn)
  • 空间复杂度:O(n)

这里我画了一张图,便于你理解。

注意:这种方式被替换后组成的新数组不一定是解法一中正确结果的数组,但长度是一样的,不影响我们对此题求解。

比如这种情况:[1,4,5,2,3,7,0]

  • tails = [1]
  • tails = [1,4]
  • tails = [1,4,5]
  • tails = [1,2,5]
  • tails = [1,2,3]
  • tails = [1,2,3,7]
  • tails = [0,2,3,7]

我们可以看到最后 tails 的长度是正确的,但是里面的值不正确,因为最后一步的替换破坏了子序列的性质。

Vue3 DOM Diff 核心算法

搞清楚了最长递增子序列这道算法题,我们再来看 Vue3 的 DOM Diff 核心算法就简单的多了。

我知道你已经迫不及待了,但是这里还是要插一句,如果你还不了解 React 以及 Vue2 的 DOM Diff 算法可以移步这个链接进行学习,循序渐进的学习可以让你更好的理解。

回来后我们思考一个问题:Diff 算法的目的是什么?

为了减少 DOM 操作的性能开销,我们要尽可能的复用 DOM 元素。所以我们需要判断出是否有节点需要移动,应该如何移动以及找出那些需要被添加或删除的节点。

好了,进入正题,Vue3 DOM Diff 核心算法。

首先我们要搞清楚,核心算法的的位置。核心算法其实是当新旧 children 都是多个子节点的时候才会触发。

下面这段代码就是 Vue3 的 DOM Diff 核心算法,我加上了在源码中的路径,方便你查找。

// packages/runtime-core/src/renderer.ts
function getSequence(arr: number[]): number[] {
  const p = arr.slice()
  const result = [0]
  let i, j, u, v, c
  const len = arr.length
  for (i = 0; i < len; i++) {
    const arrI = arr[i]
    if (arrI !== 0) {
      j = result[result.length - 1]
      if (arr[j] < arrI) {
        p[i] = j
        result.push(i)
        continue
      }
      u = 0
      v = result.length - 1
      while (u < v) {
        c = ((u + v) / 2) | 0
        if (arr[result[c]] < arrI) {
          u = c + 1
        } else {
          v = c
        }
      }
      if (arrI < arr[result[u]]) {
        if (u > 0) {
          p[i] = result[u - 1]
        }
        result[u] = i
      }
    }
  }
  u = result.length
  v = result[u - 1]
  while (u-- > 0) {
    result[u] = v
    v = p[v]
  }
  return result
}

getSequence 的作用就是找到那些不需要移动的元素,在遍历的过程中,我们可以直接跳过不进行其他操作。

其实这个算法的核心**就是我们上面讲到的求解最长递增子序列的第二种解法,贪心 + 二分查找法。这也是为什么不着急说它的原因,因为如果你看懂了上面的 LeetCode 题解,你就已经掌握了 Vue3DOM Diff 核心算法的**啦。

不过,想要搞懂每一行代码的细节,还需放到 Vue3 整个 DOM Diff 的上下文中去才行。而且需要注意的是,上面代码中的 getSequence 方法的返回值与 LeetCode 题中所要求的返回值不同,getSequence 返回的是最长递增子序列的索引。上文我们曾提到过,使用贪心 + 二分查找替换的方式存在一些 Bug,可能会导致结果不正确。Vue3 把这个问题解决掉了,下面我们来一起看一下它是如何解决的。

// packages/runtime-core/src/renderer.ts
function getSequence(arr: number[]): number[] {
  const p = arr.slice() // 拷贝一个数组 p
  const result = [0]
  let i, j, u, v, c
  const len = arr.length
  for (i = 0; i < len; i++) {
    const arrI = arr[i]
    // 排除等于 0 的情况
    if (arrI !== 0) {
      j = result[result.length - 1]
      // 与最后一项进行比较
      if (arr[j] < arrI) { 
        p[i] = j // 最后一项与 p 对应的索引进行对应
        result.push(i)
        continue
      }
      // arrI 比 arr[j] 小,使用二分查找找到后替换它
      // 定义二分查找区间
      u = 0
      v = result.length - 1
      // 开启二分查找
      while (u < v) {
        // 取整得到当前位置
        c = ((u + v) / 2) | 0
        if (arr[result[c]] < arrI) {
          u = c + 1
        } else {
          v = c
        }
      }
      // 比较 => 替换
      if (arrI < arr[result[u]]) {
        if (u > 0) { 
          p[i] = result[u - 1]  // 正确的结果
        }
        result[u] = i // 有可能替换会导致结果不正确,需要一个新数组 p 记录正确的结果
      }
    }
  }
  u = result.length
  v = result[u - 1]
  // 倒叙回溯 用 p 覆盖 result 进而找到最终正确的索引
  while (u-- > 0) {
    result[u] = v
    v = p[v]
  }
  return result
}

Vue3 通过拷贝一个数组,用来存储正确的结果,然后通过回溯赋值的方式解决了贪心 + 二分查找替换方式可能造成的值不正确的问题。

以上就是 Vue3 DOM Diff 的核心算法部分啦,欢迎光临前端食堂,客官您慢走~

归并排序

分治法典型应用,分治算法**很大程度上是基于递归的,也比较适合用递归来实现。

处理过程是由下到上的,先处理子问题,然后再合并。

如果感觉自己对递归掌握的还不是很透彻的同学,可以移步我的这篇专栏你真的懂递归吗?

顾名思义,分而治之。一般分为以下三个过程:

  1. 分解:将原问题分解成一系列子问题。
  2. 解决:递归求解各个子问题,若子问题足够小,则直接求解。
  3. 合并:将子问题的结果合并成原问题。

归并排序就是将待排序数组不断二分为规模更小的子问题处理,再将处理好的子问题合并起来,这样整个数组就都有序了。

const mergeSort = function(arr) {
    const merge = (right, left) => {
    const result = []
    let i = 0, j = 0
    while (i < left.length && j < right.length) {
      if (left[i] < right[j]) {
        result.push(left[i++])
      } else {
        result.push(right[j++])
      }
    }
    while (i < left.length) {
      result.push(left[i++])
    }
    while (j < right.length) {
      result.push(right[j++])
    }
    return result
    }
    const sort = (arr) => {
        if (arr.length === 1) { return arr }
        const mid = Math.floor(arr.length / 2)
        const left = arr.slice(0, mid)
        const right = arr.slice(mid, arr.length)
        return merge(mergeSort(left), mergeSort(right))
    }
    return sort(arr)
}
  • 时间复杂度: O(nlogn)
  • 空间复杂度: O(n)
  • 稳定

22. 括号生成

原题链接

回溯法

题目要求我们生成所有可能的有效的括号组合,数字 n 代表生成括号的对数。

使用回溯法进行解题,从空字符串开始构造,做加法。

  1. 当 l < r 时(构造用的左括号 < 构造用的右括号),不满足条件,直接剪枝。
  2. 当 l < n 时,可以一直插入左括号,最多插入 n 个。
  3. 当 r < l (构造用的右括号 < 构造用的左括号)时,可以插入右括号。
const generateParenthesis = function (n) {
    const res = []
    function generate(l, r, str) {
        // 递归终止条件
        if (l === n && r === n) {
            return res.push(str)
        }
        if (l < r) {
            return
        }
        if (l < n) {
            generate(l + 1, r, str + '(')
        }
        if (r < l) {
            generate(l, r + 1, str + ')')
        }
    }
    generate(0, 0, '')
    return res
}
  • 时间复杂度:O(2^n)
  • 空间复杂度:O(2^n)

一口气团灭 6 道股票算法

  1. 买卖股票的最佳时机
  2. 买卖股票的最佳时机II
  3. 买卖股票的最佳时机III
  4. 买卖股票的最佳时机 IV
  5. 最佳买卖股票时机含冷冻期
  6. 买卖股票的最佳时机含手续费

上面这 6 道题目可以归为一道题目来看,与现实略有不同,题目中添加了一些限制条件,读完题分析后不难发现。

  1. 第一题只交易一次,也就是 k = 1。
  2. 第二题不限制交易次数,也就是 k = +infinity。
  3. 第三题只交易两次,也就是 k = 2。
  4. 第四道限制最多次数为 k。
  5. 第五道和第六道不限次数,相当于在第二题的基础上分别添加了交易冷冻期手续费的额外条件。

我们每天能做的操作无非是以下这三种:

  1. 买入
  2. 卖出
  3. 无操作

不过要注意以下四点限制条件。

  1. 要先买入才能卖出
  2. 题目要求不能同时参与多笔交易,也就是说再次买入前需要卖出手中持有的股票
  3. 无操作基于两种状态,手中持有股票没有持有股票
  4. 交易次数 k 也有限制,只有 k >= 0 时才可以买入

分析好了这些状态,接下来就是翻译成代码了。

首先,我们可以建立一个三维数组来表示上面的这些状态,先来明确一些变量含义。

  • i: 天数 范围是 (0 <= i <= n - 1)
  • k: 最大交易次数
  • 0: 没有持有股票
  • 1: 持有股票
  • n: 股票数组长度
dp[i][k][0]
dp[i][k][1]

// 举个🌰
dp[2][2][1] // 今天是第 2 天,手中持有股票,最多还可以进行 2 次交易

我们最终要求的可获得的最大收益就是 dp[n - 1][k][0],代表最后一天将股票卖出后的最大收益。(这里卖出一定比持有收益更大,所以是 [0],而不是 [1])

接下来,我们尝试列出状态转移方程。

// 今天手中没有持有股票,有两种可能:
// 1. 昨天没有持有,今天选择不操作。 对应: dp[i - 1][k][0]
// 2. 昨天持有,今天卖出了,所以今天没有股票了。对应: dp[i - 1][k][1] + prices[i]
dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])


// 今天手中持有股票,有两种可能:
// 1. 昨天手中持有股票,今天选择不操作。对应: dp[i - 1][k][1]
// 2. 昨天没有持有股票,今天买入了。对应: dp[i - 1][k - 1][0] - prices[i]
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])

很显然,卖出股票利润增加,买入股票利润减少。因为每次交易包含两次成对的操作,买入和卖出。

所以只有买入的时候需要将 k - 1,那么最大利润就是上面这两种可能性中的最大值。

第一题 k = 1

将状态转移方程套入本题的条件,k = 1,列出状态转移方程。

dp[i][1][0] = Math.max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i])
dp[i][1][1] = Math.max(dp[i - 1][1][1], dp[i - 1][0][0] - prices[i])
            = Math.max(dp[i - 1][1][1], -prices[i])
// k = 0 时,dp[i - 1][0][0] = 0

观察发现 k 既然都是 1 且不会改变,也就是说 k 对状态转移已经没有影响了,我们可以进一步化简方程。

dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = Math.max(dp[i - 1][1], -prices[i])

对于第 0 天,我们需要进行初始化:

  • 不持有:dp[0][0] = 0
  • 持有:dp[0][1] = -prices[0] (花了 prices[0] 的钱买入股票)
const maxProfit = function(prices) {
    let n = prices.length
    let dp = Array.from(new Array(n), () => new Array(2))
    dp[0][0] = 0
    dp[0][1] = -prices[0]
    for (let i = 1; i < n; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
        dp[i][1] = Math.max(dp[i - 1][1], -prices[i])
    }
    return dp[n - 1][0]
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

我们发现在转移的时候,dp[i] 只会从 dp[i - 1] 转移得来,因此第一维可以去掉,空间复杂度优化到 O(1)。

const maxProfit = function(prices) {
    let n = prices.length
    let dp = Array.from(new Array(n), () => new Array(2))
    dp[0] = 0
    dp[1] = -prices[0]
    for (let i = 1; i < n; i++) {
        dp[0] = Math.max(dp[0], dp[1] + prices[i])
        dp[1] = Math.max(dp[1], -prices[i])
    }
    return dp[0]
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

我们也可以将变量名变得更加友好一些。

  • profit_out:卖出时的利润
  • profit_in:买入时的利润
const maxProfit = function(prices) {
    let n = prices.length
    let profit_out = 0
    let profit_in = -prices[0]
    for (let i = 1; i < n; i++) {
        profit_out = Math.max(profit_out, profit_in + prices[i])
        profit_in = Math.max(profit_in,  -prices[i])
    }
    return profit_out
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

第二题 k = +infinity

将状态转移方程套入本题的条件,k = +infinity。

dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])
            = Math.max(dp[i - 1][k][1], dp[i - 1][k][0] - prices[i])

我们发现数组中的 k 同样已经不会改变了,也就是说 k 对状态转移已经没有影响了,可以进一步化简方程。

dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i])

对于第 0 天,我们要给出初始值:

  • 不持有:dp[0][0] = 0
  • 持有:dp[0][1] = -prices[0] (花了 prices[0] 的钱买入股票)
const maxProfit = function(prices) {
    let n = prices.length
    let dp = Array.from(new Array(n), () => new Array(2))
    dp[0][0] = 0 
    dp[0][1] = -prices[0]
    for (let i = 1; i < n; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i])
    }
    return dp[n - 1][0]
}

同样在转移的时候,dp[i] 只会从 dp[i - 1] 转移得来,因此第一维可以去掉,空间复杂度优化到 O(1)。

const maxProfit = function(prices) {
    let n = prices.length
    let dp = Array.from(new Array(n), () => new Array(2))
    dp[0] = 0
    dp[1] = -prices[0]
    for (let i = 1; i < n; i++) {
        let tmp = dp[0] // 中间变量可省略,因为当天买入卖出不影响结果
        dp[0] = Math.max(dp[0], dp[1] + prices[i])
        dp[1] = Math.max(dp[1], tmp - prices[i])
    }
    return dp[0]
}

同上题一样,我们可以将变量名变得更加友好一些。

const maxProfit = function(prices) {
    let n = prices.length
    let profit_out = 0
    let profit_in = -prices[0]
    for (let i = 1; i < n; i++) {
        profit_out = Math.max(profit_out, profit_in + prices[i])
        profit_in = Math.max(profit_in, profit_out - prices[i])
    }
    return profit_out
}

第三题 k = 2

前面两种情况,无论是 k = 1,还是 k = +infinity 的情况下,k 对状态转移方程是没有影响的。

不过当 k = 2 时,k 就对状态转移方程有影响了。列出状态转移方程:

dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])

这个时候 k 无法化简,我们需要使用两次循环对 k 进行穷举。

for (let i = 0; i < n; i++) {
    for (let k = maxK; k >= 1; k--) {
        dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
        dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])
    }
}

不过因为 k 的取值范围比较小,我们也可以直接将它们全部列举出来。

dp[i][2][0] = Math.max(dp[i - 1][2][0], dp[i - 1][2][1] + prices[i])
dp[i][2][1] = Math.max(dp[i - 1][2][1], dp[i - 1][1][0] - prices[i])
dp[i][1][0] = Math.max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i])
dp[i][1][1] = Math.max(dp[i - 1][1][1], dp[i - 1][0][0] - prices[i])
            = Math.max(dp[i - 1][1][1], -prices[i])

有了上面两道题的铺垫,我们后面几道题就直接写出降维后的解法。

const maxProfit = function(prices) {
    let n = prices.length
    let dp_i10 = 0
    let dp_i11 = -prices[0]
    let dp_i20 = 0
    let dp_i21 = -prices[0]
    for (let i = 1; i < n; i++) {
        dp_i20 = Math.max(dp_i20, dp_i21 + prices[i])
        dp_i21 = Math.max(dp_i21, dp_i10 - prices[i])
        dp_i10 = Math.max(dp_i10, dp_i11 + prices[i])
        dp_i11 = Math.max(dp_i11, -prices[i])
    }
    return dp_i20
}

同上面一样,我们可以将变量名变得更加友好一些。

const maxProfit = function(prices) {
    let profit_1_in = -prices[0], profit_1_out = 0
    let profit_2_in = -prices[0], profit_2_out = 0
    let n = prices.length
    for (let i = 1; i < n; i++) {
        profit_2_out = Math.max(profit_2_out, profit_2_in + prices[i])
        profit_2_in = Math.max(profit_2_in, profit_1_out - prices[i])
        profit_1_out = Math.max(profit_1_out, profit_1_in + prices[i])
        profit_1_in = Math.max(profit_1_in, -prices[i])
    }
    return profit_2_out
}

第四题 k 是任意数

一个有收益的交易至少需要两天(在前一天买入,在后一天卖出,前提是买入价格低于卖出价格)。

如果股票价格数组的长度为 n,则有收益的交易的数量最多为 n / 2(整数除法)。因此 k 的临界值是 n / 2。

如果给定的 k 不小于临界值,即 k >= n / 2,则可以将 k 扩展为正无穷,也就是第二题的情况,如下函数 maxProfit2。

const maxProfit = function(k, prices) {
    let n = prices.length
    const maxProfit2 = function(prices) {
        let profit_out = 0
        let profit_in = -prices[0]
        for (let i = 1; i < n; i++) {
            profit_out = Math.max(profit_out, profit_in + prices[i])
            profit_in = Math.max(profit_in, profit_out - prices[i])
        }
        return profit_out
    }
    if (k > n / 2) {
        return maxProfit2(prices)
    }
    let profit = new Array(k)
    // 初始化买入卖出时的利润,将每次交易买入、卖出时的利润放在一个对象中,实现降维
    for (let j = 0; j <= k; j++) {
        profit[j] = {
            profit_in: -prices[0],
            profit_out: 0
        }
    }
    for (let i = 0; i < n; i++) {
        for (let j = 1; j <= k; j++) {
            profit[j] = {
                profit_out: Math.max(profit[j].profit_out, profit[j].profit_in + prices[i]), 
                profit_in: Math.max(profit[j].profit_in, profit[j-1].profit_out - prices[i])
            }
        }
    }
    return profit[k].profit_out
}

第五题 k 为正无穷但有冷却时间

每次卖出之后都要等一天才能继续交易,也就是第 i 天选择买的时候,要从 i - 2 状态转移。

列出状态转移方程。

dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 2][k - 1][0] - prices[i])
            = Math.max(dp[i - 1][k][1], dp[i - 2][k][0] - prices[i])

k 同样对状态转移已经没有影响了,可以进一步化简方程。

dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 2][0] - prices[i])
const maxProfit = function(prices) {
    let n = prices.length
    let dp_i0 = 0
    let dp_i1 = -prices[0];
    let dp_pre = 0 // 代表 dp[i-2][0]
    for (let i = 0; i < n; i++) {
        let tmp = dp_i0
        dp_i0 = Math.max(dp_i0, dp_i1 + prices[i])
        dp_i1 = Math.max(dp_i1, dp_pre - prices[i])
        dp_pre = tmp
    }
    return dp_i0
}

同上面一样,我们可以将变量名变得更加友好一些。

const maxProfit = function(prices) {
    let n = prices.length
    let profit_in = -prices[0]
    let profit_out = 0
    let profit_freeze = 0
    for (let i = 1; i < n; i++) {
        let temp = profit_out
        profit_out = Math.max(profit_out, profit_in + prices[i])
        profit_in = Math.max(profit_in, profit_freeze - prices[i])
        profit_freeze = temp
    }
    return profit_out
}

第六题 k 为正无穷但有手续费

在第二题的基础上,添加了手续费。

每次交易要支付手续费,只要把手续费从利润中减去即可,可以列出如下两种方程。

第一种方程:在每次买入股票时扣除手续费

dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i] - fee)

第二种方程:在每次卖出股票时扣除手续费

dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee)
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
const maxProfit = function(prices, fee) {
    let n = prices.length
    let dp = Array.from(new Array(n), () => new Array(2))
    dp[0] = 0
    dp[1] = -prices[0]
    for (let i = 1; i < n; i++) {
        let tmp = dp[0]
        dp[0] = Math.max(dp[0], dp[1] + prices[i] - fee)
        dp[1] = Math.max(dp[1], tmp - prices[i])
    }
    return dp[0]
}

同上面一样,我们可以将变量名变得更加友好一些。

const maxProfit = function(prices, fee) {
    let profit_out = 0
    let profit_in = -prices[0]
    for (let i = 1; i < prices.length; i++) {
        profit_out = Math.max(profit_out, profit_in + prices[i] - fee)
        profit_in = Math.max(profit_in, profit_out - prices[i])
    }
    return profit_out
}

站在巨人的肩膀上

78. 子集

原题链接

回溯

你爱,或者不爱我。爱就在那里,不增不减。

  1. 对于数组中的每个元素都有两种选择:选或者不选。
  2. 对于当前迭代的元素,选择它就将其 push 后,基于选择后的状态从 start + 1 递归。
  3. 然后使用 pop 将其状态恢复,不选择当前迭代的元素从 start + 1 递归。
const subsets = function(nums) => {
    const res = []
    const dfs = function(start, cur) {
        if (start === nums.length) {
            res.push(cur.slice())
            return
        }
        cur.push(nums[start]) // 选择
        dfs(start + 1, cur)
        cur.pop()
        dfs(start + 1, cur) // 不选择
    }
    dfs(0, [])
    return res
}
  • 时间复杂度: O(n * 2^n),共 2^n 个状态,需要 O(n) 的时间来构造子集。
  • 空间复杂度: O(n)

40. 组合总和 II

原题链接

回溯

本题在 39.组合总和 题的基础上加了1个限制条件:元素不可以重复使用了。

解题思路还是和 39 题一样,只需要在代码中改动如下几点即可:

  1. 题目要求元素不能重复,需要去重,去重就要排序,因为排序后去重更方便。
  2. 在枚举过程中,遇到重复项直接跳过。
  3. 递归时改成 i + 1,避免与当前 i 重复。
const combinationSum2 = (candidates, target) => {
    candidates.sort((a, b) => a - b)
    const res = []
    // start: 起点索引 arr: 当前集合 cur: 当前所求之和
    const dfs = (start, arr, cur) => {
        if (cur > target) return
        if (cur === target) {
            res.push(arr.slice())
            return
        }
        for (let i = start; i < candidates.length; i++) {
            if (i - 1 >= start && candidates[i - 1] === candidates[i]) continue
            arr.push(candidates[i])
            dfs(i + 1, arr, cur + candidates[i])
            arr.pop()
        }
    }
    dfs(0, [], 0)
    return res
}

125. 验证回文串

原题链接

双指针

先明确题意,题目要求只考虑字母和数字字符,并且可以忽略大小写。

1.首先用正则去掉字符串中不是字母和数字的元素,并且都转换成小写。
2.借助双指针 left, right 进行夹逼比较。
3.如果 s[left] 和 s[right] 每一项都相等,则是回文串,否则就不是回文串。

const isPalindrome = function (s) {
    s = s.replace(/[^0-9a-zA-Z]/g, '').toLowerCase()
    let n = s.length, left = 0, right = n - 1;
    while (left < right) {
        if (s[left] !== s[right]) {
            return false
        }
        left++
        right--
    }
    return true
}
  • 时间复杂度: O(∣s∣), 其中 ∣s∣ 是字符串 s 的长度
  • 空间复杂度: O(1)

70. 爬楼梯

原题链接

虽然动态规划的最终版本 (降维再去维) 大都不是递归,但解题的过程还是离不开递归的。

如果你觉得你对递归理解的还不够透彻,请移步我的这篇专栏你真的懂递归吗?

新手可能会觉得动态规划**接受起来比较难,确实,动态规划求解问题的过程不太符合人类常规的思维方式,我们需要切换成机器思维。

使用动态规划**解题,首先要明确动态规划的三要素。

动态规划三要素

  • 重叠子问题
  • 最优子结构
  • 状态转移方程

重叠子问题

切换机器思维,自底向上思考。

爬第 n 阶楼梯的方法数量,等于两部分之和:

  • 爬上 n-1 阶楼梯的方法数量
  • 爬上 n-2 阶楼梯的方法数量

最优子结构

子问题的最优解能够推出原问题的优解。

状态转移方程

dp[n] = dp[n-1] + dp[n-2]

具备三要素,确认边界条件,初始化状态,开始切菜:

  • dp[0] = 1
  • dp[1] = 1
const climbStairs = function(n) {
    const dp = []
    dp[0] = 1
    dp[1] = 1
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

优化

在此基础上,我们还可以通过压缩空间来对算法进行优化。因为 dp[i] 只与 dp[i-1]dp[i-2] 有关,没有必要存储所有出现过的 dp 项,只用两个临时变量去存储这两个状态即可。

const climbStairs = function(n) {
    let a1 = 1
    let a2 = 1
    for (let i = 2; i <= n; i++) {
        [a1, a2] = [a2, a1 + a2]
    }
    return a2
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

415. 字符串相加

原题链接

  1. 模拟加法,先补 0 对齐。
  2. 从右往左做加法,计算当前位 +num1[i] + +num2[i] + carry,使用 + 号将字符转换成数字。
  3. 当前位:模10的结果 + res字符串。
  4. carry 代表是否进位。
  5. 如果 carry 等于 1,需要在 res 前添加 '1'。
const addStrings = (num1, num2) => {
  while (num1.length > num2.length) num2 = '0' + num2
  while (num1.length < num2.length) num1 = '0' + num1
  let res = '', carry = 0;
  for (let i = num1.length - 1; i >= 0; i--) {
    const sum = +num1[i] + +num2[i] + carry 
    res = sum % 10 + res                       
    carry = sum > 9 ? 1 : 0
  }
  return carry === 1 ? '1' + res : res
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

1.两数之和

原题链接

1.暴力法

符合第一直觉的暴力法,潜意识里要学会将两数之和转换为两数之差

然后问题就变得像切菜一样简单了,双层循环找出当前数组中符合条件的两个元素,并将它们的索引下标组合成数组返回即所求。

const twoSum = function(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] === target - nums[j]) {
                return [i, j]
            }
        }
    }
}
  • 时间复杂度:O(n^2)
  • 空间复杂度:O(1)

写出这种方法是不会让面试官满意的,所以接下来我们要想办法进行优化。

2.借用 Map

算法优化的核心方针基本上都是用空间换时间。

我们可以借用 Map 存储遍历过的元素及其索引,每遍历一个元素时,去 Map 中查看是否存在满足要求的元素。

如果存在的话将其对应的索引从 Map 中取出和当前索引值组合为数组返回即为所求,如果不存在则将当前值作为键,当前索引作为值存入。

题目要求返回的是数组下标,所以 Map 中的键名是数组元素,键值是索引。

const twoSum = function(nums, target) {
    const map = new Map()
    for (let i = 0; i < nums.length; i++) {
        const diff = target - nums[i]
        if (map.has(diff)) {
            return [map.get(diff), i]
        }
        map.set(nums[i], i)
    }
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

21. 合并两个有序链表

原题链接

说起递归,大家可以看下我之前整理的这篇文章,你真的懂递归吗?

题目描述

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例:

输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4

思路

1.使用递归来解题
2.将两个链表头部较小的一个与剩下的元素合并
3.当两条链表中的一条为空时终止递归

关键点

  • 掌握链表数据结构
  • 考虑边界情况

复杂度分析

n+m是两条链表的长度

  • 时间复杂度:O(m+n)
  • 空间复杂度:O(m+n)
const mergeTwoLists = function (l1, l2) {
    if (l1 === null) {
        return l2
    }
    if (l2 === null) {
        return l1
    }
    if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2)
        return l1
    } else {
        l2.next = mergeTwoLists(l1, l2.next)
        return l2
    }
}

876. 链表的中间结点

原题链接

快慢指针

老套路,借助快慢指针,fast 一次走两步,slow 一次走一步,当 fast 到达链表末尾时,slow 就处于链表的中间点了。

const middleNode = function(head) {
    let fast = head, slow = head;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

101. 对称二叉树

原题链接

递归

先明确,所谓“对称”,也就是两个树的根节点相同

  • 第一个树的左子树与第二个树的右子树镜像对称。
  • 第一个树的右子树与第二个树的左子树镜像对称。
const isSymmetric = function(root) {
    if (root === null) return true
    return isEqual(root.left, root.right) // 比较左右子树是否对称
};

const isEqual = function(left, right) {
    // 递归终止条件
    if (left === null && right === null) return true // 对称
    if (left === null || right === null) return false // 不对称
    // 比较左右子树的 root 值以及左右子树是否对称
    return left.val === right.val
        && isEqual(left.left, right.right)
        && isEqual(left.right, right.left)
}
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

20. 有效的括号

原题链接

先明确题意,所谓“有效的括号”,不仅要保证左括号的数量和右括号的数量相等,还要保证括号的位置。

显然,有效括号的部分子表达式中也是有效的括号。

我们可以借助栈来解题,栈满足后进先出,这样在遍历的过程中,每次与栈顶的元素相匹配,能够保证是最近出现的元素。

  1. 排除掉奇数个括号或是右括号开头的情况。
  2. 如果是 '(' 、'{'、'[' 等左括号则直接入栈。
  3. 否则就是右括号,将其与栈顶元素匹配,匹配失败则是无效的括号返回 false,成功则继续遍历。
  4. 当遍历完成时,栈如果为空则是有效的括号返回 true,若栈不为空则意味着还有无法匹配的括号,返回 false。
const isValid = function(s) {
    // 奇数个括号或右括号开头的情况无效
    if (s.length % 2 !== 0 || [')', ']', '}'].indexOf(s[0]) !== -1) return false
    const map = {
        '(': ')',
        '[': ']',
        '{': '}'
    }
    const stack = []
    for (let i = 0; i < s.length; i++) {
        if (s[i] === '(' || s[i] === '{' || s[i] === '[') {
            stack.push(s[i])
        } else if(s[i] !== map[stack.pop()]){
            return false
        }
    }
    return stack.length === 0
}
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

104. 二叉树的最大深度

原题链接

DFS 深度优先搜索

树的深度 = 左右子树的最大深度 + 1

const maxDepth = function(root) {
    if (!root) { // 递归终止条件
        return 0
    } else {
        const left = maxDepth(root.left)
        const right = maxDepth(root.right)
        return Math.max(left, right) + 1
    }
};
  • 时间复杂度: O(n)
  • 最坏空间复杂度: O(height), height 表示二叉树的高度

BFS 广度优先搜索

层序遍历时记录树的深度。

二叉树的层序遍历可参考轻松拿下二叉树的层序遍历

const maxDepth = function(root) {
    let depth = 0
    if (root === null) {
        return depth
    }
    const queue = [root]
    while (queue.length) {
        let len = queue.length
        while (len--) {
            const cur = queue.shift()
            cur.left && queue.push(cur.left)
            cur.right && queue.push(cur.right)
        }
        depth++
    }
    return depth
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

226. 翻转二叉树

原题链接

Google:我们 90% 的工程师都用你写的软件(Homebrew),但你没法在白板上翻转二叉树,所以翻滚吧,蛋炒饭。

22131612272051_ pic

原推截图,至今仍在。 Max Howell 当年吐槽之后 LeetCode 马上加入了这道题。

会了这道题,是不是我们也可以超越世界级大牛了?(狗头保命)

书归正传

首先明确,所谓二叉树的翻转需要满足以下两点:

1.它的左右子树要交换位置。
2.并且左右子树内部的所有子树或是结点都要进行交换位置。

递归

1.从根节点开始,递归的对树进行遍历。
2.从叶子结点开始进行翻转。
3.左右子树都已经翻转后,交换两棵子树的位置即可完成全部的翻转。

const invertTree = function(root) {
    if (root === null) return null // 递归终止条件
    invertTree(root.left)
    invertTree(root.right)
    const temp = root.left
    root.left = root.right
    root.right = temp
    return root
}
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

当然你也可以将上面的 2,3 两个步骤颠倒执行,也就是先交换两棵子树的位置,再对其内部进行翻转。

const invertTree = function(root) {
    if (root === null) return null // 递归终止条件
    const temp = root.left
    root.left = root.right
    root.right = temp
    invertTree(root.left)
    invertTree(root.right)
    return root
}

BFS

层序遍历遍历二叉树,当根结点出列时,翻转它的左右子树。然后将其左右子节点入列,以便下一层时翻转。

二叉树的层序遍历可参考轻松拿下二叉树的层序遍历

const invertTree = (root) => {
  if (root === null) return null;
  const queue = [root];
  while (queue.length) {
    const cur = queue.shift();
    [cur.left, cur.right] = [cur.right, cur.left];
    if (cur.left) queue.push(cur.left);
    if (cur.right) queue.push(cur.right);
  }
  return root;
}

46. 全排列

原题链接

回溯法

题目要求我们返回所有可能的全排列,我们就要考虑到所有的情况,可以使用回溯法解题。

回溯法的本质是枚举,并且还可以通过剪枝少走一些冤枉路。

回溯:一条路走到黑,手握后悔药,可以无数次重来。(英雄联盟艾克大招无冷却)。

关键点:在递归之前做选择,在递归之后撤销选择。

  1. 借助 deepStack 栈暂存每一种枚举的可能情况。
  2. 开启遍历枚举,已经选择过的数字不能再做选择。
  3. 在递归之前做选择,在递归之后需要撤销选择,恢复状态。
  4. 完成所有遍历时,将 deepStack 存入结果集 res。
const permute = function(nums) {
    const len = nums.length, res = [], deepStack = []
    const backtrack = (deepStack) => {
        // 递归终止条件
        if (deepStack.length == len) {
            return res.push(deepStack)
        }
        for (let i = 0; i < len; i++) {
            // 已经选择过的数字不能再做选择
            if (!deepStack.includes(nums[i])) {
                deepStack.push(nums[i]) // 做选择
                backtrack(deepStack.slice())
                deepStack.pop() // 撤销选择
            }
        }
    }
    backtrack(deepStack)
    return res
}
  • 时间复杂度: O(n * n!)
  • 空间复杂度: O(n * n!)

860. 柠檬水找零

原题链接

贪心

这道题的场景和几年前的我们现实生活中很像,毕竟 2021 年的现在大家都用手机支付了,不过也刚好怀旧一波。

先明确,题目要求我们一开始是没有钱的,全靠老天爷赏饭吃。江山父老能容我 不使人间造孽钱

所以,分为 3 种情况来进行分析:

  1. 顾客支付了 5 美元: 直接收下,不用找。
  2. 顾客支付了 10 美元: 需要找回 5 元。
  3. 顾客支付了 20 美元:需要找回 15元。有两种组合情况,一种是有一张 10 元和一张 5 元,或者三张 5 元。
  4. 我们要保证有 10 元先找 10 元,多保留 5 元,这样支付的灵活度更高 (贪心)。
const lemonadeChange = function(bills) {
    let five = 0, ten = 0
    const len = bills.length
    for (let i = 0; i < len; i++) {
        if (bills[i] == 5) {
            five++
        } else if (bills[i] == 10) {
            if (five == 0) {
                return false
            }
            five--
            ten++
        } else if (bills[i] == 20) {
            if (ten > 0 && five > 0) {
                ten--
                five--
            } else if (five >= 3) {
                five -= 3
            } else {
                return false
            }
        }
    }
    return true
}
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

145. 二叉树的后序遍历

原题链接

172e5c5eb83e4be9

后序遍历:先打印当前节点的左子树,再打印当前节点的右子树,最后打印当前节点 (CDBFGEA)。

const postorderTraversal = function(root) {
    const result = [];
    function pushRoot(node) {
        if (node !== null) {
            if (node.left !== null) {
                pushRoot(node.left);
            }
            if (node.right !== null) {
                pushRoot(node.right);
            } 
            result.push(node.val);
        }
    }
    pushRoot(root);
    return result;
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

66. 加一

原题链接

加一,其实就是小学数学题,很简单,我们逐步来分析。

数字 9 加 1 会进位,其他的数字不会。

所以,情况无非下面这几种:

  1. 1 + 1 = 2 末位无进位,则末位加 1 即可。
  2. 299 + 1 = 300 末位有进位,首位加 1。
  3. 999 + 1 = 1000 末位有进位,最终导致前方多出一位,循环之外单独处理。
const plusOne = function(digits) {
    for (let i = digits.length - 1; i >= 0; i--) {
        if (digits[i] === 9) {
            digits[i] = 0
        } else {
            digits[i]++
            return digits
        }
    }
    digits.unshift(1)
    return digits
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

102. 二叉树的层序遍历

原题链接

172e5c5eb722deb3

DFS 深度优先遍历

按照树的深度将每层对应的节点添加到对应层的数组中即可。

const levelOrder = function(root) {
    if (!root) return []
    const res = []
    dfs(root, 0, res)
    return res
};

const dfs = function(root, depth, res) {
    if (!root) return // 递归终止条件
    if (!res[depth]) res[depth] = []
    res[depth].push(root.val) // 存入每层的节点值
    dfs(root.left, depth + 1, res) // drill down
    dfs(root.right, depth + 1, res)
}

BFS 广度优先遍历

根据层次返回其对应的结果集合。

1.边界处理,初始化队列 queue 和存放结果的数组 res。
2.外层循环遍历层级结构,内层循环遍历每一层的子节点。
3.遍历时需要记录当前层的遍历次数 len 以及当前层的节点数组 arr。
4.取得 node 依次出队,并依次存入当前层的节点数组中。
5.若存在左右子节点,则依次入队,并更新 len。
6.遍历完后返回结果 res。

const levelOrder = function(root) {
    if (!root) return []
    const queue = [root]
    const res = []
    while (queue.length > 0) {
      const arr = []
      let len = queue.length
      while (len) {
        let node = queue.shift()
        arr.push(node.val)
        if (node.left) queue.push(node.left)
        if (node.right) queue.push(node.right)
        len--
      }
      res.push(arr)
    }
    return res
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

堆排序

堆排序相比其他几种排序代码会有些复杂,不过没关系,我们先来看一些前置知识,可以帮助我们更好的理解堆排序。

堆排序顾名思义就是要利用堆这种数据结构进行排序。堆是一种特殊的树,满足以下两点就是堆:

  1. 堆是一个完全二叉树
  2. 堆中每一个节点的值都必须大于等于(或小于等于)其子树中的每个节点的值

每个节点的值都大于等于子树中每个节点值的堆,叫做大顶堆,每个节点的值都小于等于子树中每个节点值的堆,叫做小顶堆

也就是说,大顶堆中,根节点是堆中最大的元素。小顶堆中,根节点是堆中最小的元素

如果你对树这种数据结构还不是很了解,可以移步我的这篇专栏“树”业有专攻

堆如果用一个数组表示的话,给定一个节点的下标 i (i从1开始),那么它的父节点一定为 A[i / 2],左子节点为 A[2i],右子节点为 A[2i + 1]。

堆排序包含两个过程,建堆和排序。首先构建一个大顶堆,也就是将最大值存储在根节点(i = 1),每次取大顶堆的根节点与堆的最后一个节点进行交换,此时最大值放入了有效序列的最后一位,并且有效序列减 1,有效堆依然保持完全二叉树的结构,然后进行堆化成为新的大顶堆。重复此操作,直到有效堆的长度为 0,排序完成。

const heapSort = function(arr) {
    buildHeap(arr, arr.length - 1)
    let heapSize = arr.length - 1 // 初始化堆的有效序列长度
    for (let i = arr.length - 1; i > 1; i--) {
        swap(arr, 1, i) // 交换堆顶元素与最后一个有效子元素
        heapSize-- // 有效序列长度减 1
        heapify(arr, heapSize, 1) // 堆化有效序列
    }
    return arr
}

// 构建大顶堆
const buildHeap = function(items, heapSize) {
    // 从后往前并不是从序列的最后一个元素开始,而是从最后一个非叶子节点开始,这是因为,叶子节点没有子节点,不需要自上而下式堆化。
    // 最后一个子节点的父节点为 n/2 ,所以从 n/2 位置节点开始堆化
    for (let i = Math.floor(heapSize / 2); i >= 1; i--) {
        heapify(items, heapSize, i)
    }
}
// 堆化
const heapify = function(arr, heapSize, i) {
    while (true) {
        let maxIndex = i
        if (2 * i <= heapSize && arr[i] < arr[i * 2]) {
            maxIndex = i * 2
        }
        if (2 * i + 1 <= heapSize && arr[maxIndex] < arr[i * 2 + 1]) {
            maxIndex = i * 2 + 1
        }
        if (maxIndex === i) break
        swap(arr, i, maxIndex)
        i = maxIndex
    }
}

// 交换工具函数
const swap = function(arr, i, j) {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}
  • 时间复杂度: O(nlogn)
  • 空间复杂度: O(1)
  • 不稳定

选择排序

选择排序可视化视频

选择排序和插入排序有些类似,也分已排序序列和未排序序列。

但是选择排序是将最小的元素存放在数组起始位置,再从剩下的未排序的序列中寻找最小的元素,然后将其放到已排序的序列后面。以此类推,直到排序完成。

const selectSort = function(arr) {
    const len = arr.length
    let temp, minIndex
    for (let i = 0; i < len - 1; i++) {
        minIndex = i
        for (let j = i + 1; j < len; j++) {
            if (arr[j] <= arr[minIndex]) {
                minIndex = j
            }
        }
        temp = arr[i]
        arr[i] = arr[minIndex]
        arr[minIndex] = temp
    }
    return arr
}
  • 时间复杂度: O(n^2)
  • 空间复杂度: O(1)
  • 不稳定

198. 打家劫舍

原题链接

先明确题意,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警,所以我们得隔着偷。

最优子结构

从 n 个房子中能偷到的最大金额,f(n)。

  1. 偷前 n - 1 间房子,最后一间房子不偷
  2. 偷前 n - 2 间房子和最后一间房子

状态转移方程

Math.max(dp[i - 1], dp[i - 2] + nums[i - 1])

处理边界条件

  • n = 0,没有房子,所以 dp[0] = 0
  • n = 1,只有一个房子,偷就完了,dp[1] = nums[0]
const rob = function(nums) {
    const n = nums.length
    if (n === 0) return 0
    const dp = new Array(n)
    dp[0] = 0
    dp[1] = nums[0]
    for (let i = 2; i <= n; i++) {
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1])
    }
    return dp[n]
}

降维,空间优化

其实,我们实际上只用到了 f(n - 1) 和 f(n - 2) 的结果,并不需要始终持有整个DP数组,每一步只需要前两个最大值,所以两个变量就足够用了。

const rob = function(nums) {
    const n = nums.length
    if (n === 0) return 0
    let prev = 0
    let curr = 0
    for (let i = 0; i < n; i++) {
        let tmp = curr
        curr = Math.max(curr, prev + nums[i])
        prev = tmp
    }
    return curr
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

206. 反转链表

原题链接

迭代

1.初始化哨兵节点 prev 为 null,及当前节点 curr 指向头节点。
2.开始迭代,记录 next 指针留备后用,反转指针。
3.推进指针继续迭代,最后返回新的链表头节点 prev。

const reverseList = function(head) {
    let prev = null;
    let curr = head;
    while (curr !== null) {
        // 记录 next 节点
        let next = curr.next;
        // 反转指针
        curr.next = prev;
        // 推进指针
        prev = curr;
        curr = next;
    }
    // 返回翻转后的头节点
    return prev;
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

递归

const reverseList = function(head) {
    if (!head || !head.next) return head;
    // 记录当前节点的下一个节点
    let next = head.next;
    let reverseHead = reverseList(next);
    // 操作指针进行反转
    head.next = null;
    next.next = head;
    return reverseHead;
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

455. 分发饼干

原题链接

贪心算法+双指针

  1. 给一个孩子的饼干应当尽量小并且能满足孩子,大的留来满足胃口大的孩子。
  2. 因为胃口小的孩子最容易得到满足,所以优先满足胃口小的孩子需求。
  3. 按照从小到大的顺序使用饼干尝试是否可满足某个孩子。
  4. 当饼干 j >= 胃口 i 时,饼干满足胃口,更新满足的孩子数并移动指针 gi++ sj++ res++
  5. 当饼干 j < 胃口 i 时,饼干不能满足胃口,需要换大的 sj++

关键点

将需求因子 g 和 s 分别从小到大进行排序,使用贪心**,配合双指针,每个饼干只尝试一次,成功则换下一个孩子来尝试。

const findContentChildren = function (g, s) {
    g = g.sort((a, b) => a - b)
    s = s.sort((a, b) => a - b)
    let gi = 0 // 胃口值
    let sj = 0 // 饼干尺寸
    let res = 0
    while (gi < g.length && sj < s.length) {
        if (s[sj] >= g[gi]) {
            gi++
            sj++
            res++
        } else {
            sj++
        }
    }
    return res
}
  • 时间复杂度:O(nlogn)
  • 空间复杂度:O(1)

84. 柱状图中最大的矩形

原题链接

虽然这是一道难度为困难的题,不过大家不要被它所迷惑,其实它不是很难。

解决这道题,最直观的办法就是暴力求解。我们可以先来分析一波:

读题的第一遍,实际上就是要求在宽度为 1 的 n 个柱子能勾勒出来的矩形的最大面积。

这不就是个幼儿园的数学问题吗?

面积 = 底 * 高

撸它!

暴力法

方法一:双重循环遍历出所有的可能性,在遍历的过程中我们还可以求出最小的高度。

const largestRectangleArea = function(heights) {
  let maxArea = 0
  let len = heights.length
  for (let i = 0; i < len; i++) {
    let minHeight = heights[i]
    for (let j = i; j < len; j++) {
      minHeight = Math.min(minHeight, heights[j])
      maxArea = Math.max(maxArea, minHeight * (j - i + 1))
    }
  }
}

方法二:确定一根柱子后,分别向前后两个方向遍历。

const largestRectangleArea = function(heights) {
  let maxArea = 0
  let len = heights.length
  for (let i = 0; i < len; i++) {
    let left = i
    let right = i
    while (left >= 0 && heights[left] >= heights[i]) {
      left--
    }
    while (right < len && heights[right] >= heights[i]) {
      right++
    }
    maxArea = Math.max(maxArea, (right - left - 1) * heights[i])
  }
  return maxArea
}

但是这两种方法的时间复杂度都是 O(n^2),空间复杂度是 O(1)。时间复杂度太高了,我们需要想办法进行优化。

使用单调递增栈

stack0.jpg

我们来思考一个问题,我们究竟想要求的最大面积是什么?

不妨拿起笔画画图,我这里帮你画好了,观察上图,便可以得出:

其实就是以 i 为中心,分别向左、向右找到第一个小于 heighs[i] 的两个边界,也就是以当前这根 i 柱子所能勾勒出的最大面积。

那么,我们为什么要借助单调递增栈这种数据结构呢?

单调递增,也就是我们可以通过 O(1) 的时间复杂度确定柱体 i 的左边界!

又是以空间换时间的套路!

如何确定右边界?

只需遍历一次柱体数组,将大于等于当前柱体的柱子们推入栈中,而当遍历到的柱子高度小于栈顶的柱子高度时,这时我们找到了右边界,可以将栈顶的柱子,弹出栈,来计算矩形面积了!

处理特殊边界情况?

引入前后边界,在柱体数组前后各放入一根高度为 0 的柱子。这样便无需考虑栈空以及栈中还有剩余柱子的情况啦!

ok,上代码!

const largestRectangleArea = function(heights) {
  let maxArea = 0
  let stack = []
  heights.push(0)
  heights.unshift(0)
  // heights = [0, ...heights, 0] 你也可以这样写
  for (let i = 0; i < heights.length; i++) {
    while (stack.length > 0 && heights[stack[stack.length - 1]] > heights[i]) {
      maxArea = Math.max(maxArea, heights[stack.pop()] * (i - stack[stack.length - 1] - 1))
    }
    stack.push(i)
  }
  return maxArea
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

47. 全排列 II

原题链接

回溯

本题与 46. 全排列解题思路一样。

不同之处:序列 nums 是可以重复的,要求按任意顺序返回所有不重复的全排列。

  1. 去重就要排序,排序后可以使相同的数字相邻,便于去重。
  2. 使用 used 数组记录使用过的数字,true 代表使用过,false 代表未使用过。
  3. 在迭代的过程中需要考虑好情况,充分剪枝。
  4. 在选择时记录 used[i] 状态,撤销时也要重置 used[i] 状态。
const permuteUnique = function(nums) {
    const len = nums.length, res = [], used = []
    nums.sort((a, b) => a - b)
    const backtrack = (deepStack) => {
        if (deepStack.length === len) {
            res.push(deepStack.slice())
            return
        }
        for (let i = 0; i < len; i++) {
            // 当前选项与上一项相同、且上一项存在、且没有被使用过,则忽略
            if (nums[i - 1] === nums[i] && i - 1 >= 0 && !used[i - 1]) continue 
            if (used[i]) continue // 使用过便不再使用
            deepStack.push(nums[i])
            used[i] = true
            backtrack(deepStack)
            deepStack.pop()
            used[i] = false
        }
    }
    backtrack([])
    return res
}
  • 时间复杂度: O(n * n!)
  • 空间复杂度: O(n)

144. 二叉树的前序遍历

原题链接

172e5c5eb83e4be9

前序遍历:先打印当前节点,再打印当前节点的左子树,最后打印当前节点的右子树 (ABCDEFG)

const preorderTraversal = function(root) {
    const result = [];
    function pushRoot(node){
        if (node !== null) {
            result.push(node.val);
            if (node.left !== null){ 
                pushRoot(node.left);
            }
            if (node.right !== null) {
                pushRoot(node.right);
            } 
        }
    }
    pushRoot(root);
    return result;
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

141. 环形链表

原题链接

链表的基础知识可以移步这个题解,这里不再赘述。

快慢指针

1.使用快慢不同的两个指针遍历,快指针一次走两步,慢指针一次走一步。
2.如果没有环,快指针会先到达尾部,返回 false。
3.如果有环,则一定会相遇。

const hasCycle = function(head) {
    if (!head || !head.next) return false;
    let fast = head.next;
    let slow = head;
    while (fast !== slow) {
        if (!fast || !fast.next) {
            return false;
        }
        fast = fast.next.next;
        slow = slow.next;
    }
    return true;
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

标记法

遍历链表,通过 flag 标记判断是否有环,如果标记存在则有环。(走过的地方插个旗子做标记)

const hasCycle = function(head) {
    while (head) {
        if (head.flag) {
            return true;
        } else {
            head.flag = true;
            head = head.next;
        }
    }
    return false;
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

344. 反转字符串

原题链接

先明确题目要求:

不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

const reverseString = function(s) {
    s.reverse()
}

这道题可不是为了考察我们是否知道 reverse() 这个 API,我们来看不借助内置方法如何解题。

双指针

  1. 借助双指针left、right分别指向头尾。
  2. 两个指针不断夹逼,进行交换位置完成反转。
const reverseString = function (s) {
    let left = 0, right = s.length - 1;
    while (left < right) {
        [s[left], s[right]] = [s[right], s[left]]
        left++
        right--
    }
}
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

11.盛水最多的容器

原题链接

虽然是中等难度,但这道题解起来还是比较简单的,老规矩,我们看下符合第一直觉的暴力法:

暴力法

幼儿园数学题:矩形面积 = 长 * 宽

放到我们这道题中,矩形的长和宽就分别对应:

  • 长:两条垂直线的距离
  • 宽:两条垂直线中较短的一条的长度

双重 for 循环遍历所有可能,记录最大值。

const maxArea = function(height) {
    let max = 0 // 最大容纳水量
    for (let i = 0; i < height.length; i++) {
        for (let j = i + 1; j < height.length; j++) {
            // 当前容纳水量
            let cur = (j - i) * Math.min(height[i], height[j])
            if (cur > max) {
                max = cur
            }
        }
    }
    return max
}
  • 时间复杂度:O(n^2)
  • 空间复杂度:O(1)

暴力法时间复杂度 O(n^2) 太高了,我们还是要想办法进行优化。

双指针

我们可以借用双指针来减少搜索空间,转换为双指针的视角后,回顾矩形的面积对应关系如下:

(矩形面积)容纳的水量 = (两条垂直线的距离)指针之间的距离 * (两个指针指向的数字中的较小值)两条垂直线中较短的一条的长度

设置两个指针,分别指向头和尾(i指向头,j指向尾),不断向中间逼近,在逼近的过程中为了找到更长的垂直线:

  • 如果左边低,将i右移
  • 如果右边低,将j左移

有点贪心**那味儿了,因为更长的垂直线能组成更大的面积,所以我们放弃了较短的那一条的可能性。

但是这么做,我们有没有更能漏掉一个更大的面积的可能性呢?

先告诉你答案是不会漏掉。

关于该算法的正确性证明已经有很多同学们给出了答案,感兴趣的请戳下面链接。

const maxArea = function(height) {
    let max = 0 // 最大容纳水量
    let left = 0 // 左指针
    let right = height.length - 1 // 右指针
    
    while (left < right) {
        // 当前容纳水量
        let cur = (right - left) * Math.min(height[left], height[right]);
        max = Math.max(cur, max)
        height[left] < height[right] ? left ++ : right --
    }

    return max
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

26. 删除排序数组中的重复项

原题链接

双指针

题目要求原地删除重复出现的元素,不要使用额外的数组空间,返回移除后数组的新长度。

先明确,这道题给我们提供的是排好序的数组,所以重复的元素必然相邻。

所以实际上我们只需要将不重复的元素移到数组的左侧,并返回其对应的长度即可。

1.借助双指针,i 从索引 0 开始,j 从索引 1 开始。
2.当前项 nums[j] 与前一位置 nums[j - 1] 相等时,j++ 跳过重复项。
3.当二者不相等时,意味着不是重复项,此时需要将 i 指针右移, 并将 nums[j] 复制到此时的 nums[i] 位置上,然后将指针 j 右移。
4.重复上述过程,直到循环完成,最终返回 i + 1,因为题目要求返回长度,i 是索引位置,加 1 即所求。

const removeDuplicates = function(nums) {
    const n = nums.length
    let i = 0
    if (n === 0) return 0
    for (let j = 1; j < n; j++) {
        if (nums[j] !== nums[j - 1]) {
            i++
            nums[i] = nums[j]
        }
    }
    return i + 1
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

快速排序

快速排序可视化视频

快速排序也是分治法的应用,处理过程是由上到下的,先分区,然后再处理子问题。

快速排序通过遍历数组,将待排序元素分隔成独立的两部分,一部分记录的元素均比另一部分的元素小,则可以分别对这两部分记录的元素继续进行排序,直到排序完成。

这就需要从数组中挑选出一个元素作为 基准(pivot),然后重新排序数列,将元素比基准值小的放到基准前面,比基准值大的放到基准后面。

然后将小于基准值的子数组(left)和大于基准值的子数组(right)递归地调用 quick 方法,直到排序完成。

const quickSort = function(arr) {
    const quick = function(arr) {
        if (arr.length <= 1) return arr
        const len = arr.length
        const index = Math.floor(len >> 1)
        const pivot = arr.splice(index, 1)[0]
        const left = []
        const right = []
        for (let i = 0; i < len; i++) {
            if (arr[i] > pivot) {
                right.push(arr[i])
            } else if (arr[i] <= pivot) {
                left.push(arr[i])
            }
        }
        return quick(left).concat([pivot], quick(right))
    }
    const result = quick(arr)
    return result
}
  • 时间复杂度: O(nlogn)
  • 空间复杂度: O(nlogn)
  • 不稳定

94. 二叉树的中序遍历

原题链接

周树人先生曾经说过:学好树,数据结构与算法你就掌握了一半!

食堂老板(童欧巴):就算我们作为互联网浪潮中的叶子结点,也需要有蚍蜉撼树的精神,就算蚍蜉撼树是自不量力。因为就算终其一生只是个普通人,但你总不能为了成为一个普通人而终其一生吧。

今日菜谱,蚂蚁上树,下面介绍一下演员。

树的相关名词科普

  • 根节点
  • 叶子节点
  • 父节点
  • 子节点
  • 兄弟节点
  • 高度
  • 深度

172e5c5eb722deb3

A 是 根节点。C、D、F、G 是 叶子节点。A 是 B 和 E 的 父节点。B 和 E 是 A 的 子节点。B、E 之间是 兄弟节点

高度、深度、层 如上图所示。

为了方便理解记忆,高度 就是抬头看,深度 就是低头看。

与 高度、深度 不同,层 类比盗梦空间里的楼,楼都是从 1 层开始计算,盗梦空间中的楼颠倒过来,从上往下。

172e5c5eb83e4be9

中序遍历:先打印当前节点的左子树,再打印当前节点,最后打印当前节点的右子树 (CBDAFEG)

const inorderTraversal = function(root) {
    const result = [];
    function pushRoot(root) {
        if (root !== null) {
            if (root.left !== null) {
                pushRoot(root.left);
            }
            result.push(root.val);
            if (root.right !== null) { 
                pushRoot(root.right);
            }
        }
    }
    pushRoot(root);
    return result;
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

53. 最大子序和

原题链接

动态规划

遍历数组,以当前遍历到的每一个点为终点来计算当前子序列的最大和,每一个点的结果都是基于前一个点的最大子序列和计算得出的。

状态转移方程

res[i] = Math.max(res[i - 1] + cur[i], cur[i])

  • cur: 当前最大连续子序和
  • res: 最终结果
const maxSubArray = function(nums) {
    const len = nums.length
    const dp = new Array(len).fill(1)
    dp[0] = nums[0]
    let res = dp[0]
    for (let i = 1; i < len; i++) {
        if (dp[i - 1] > 0) {
            dp[i] = dp[i - 1] + nums[i]
        } else {
            dp[i] = nums[i]
        }
        res = Math.max(res, dp[i])
    }
    return res
}
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

状态压缩

每一个点的结果只和前一个点有关,我们仅用一个变量来维护即可,可以将空间复杂度降低到 O(1)。

对数组进行遍历,如果 cur 大于 0,则 cur 加上当前遍历的数字 num。

否则 cur 只会对当前结果起到负作用,并不是我们想要的,需要舍弃,更新当前遍历数字 num 为 cur。

每次遍历最后需要比较 res 和 cur 的大小,将最大值给到 res。

遍历结束后返回结果。

const maxSubArray = function(nums) {
    let res = nums[0]
    let cur = 0
    for (const num of nums) {
        if (cur > 0) {
            cur += num
        } else {
            cur = num
        }
        res = Math.max(res, cur)
    }
    return res
}
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

77. 组合

原题链接

回溯

使用回溯法进行解题,在回溯的常规操作下注意以下两点:

  1. 每次递归当选满 k 个数时,将其推入最终集合。
  2. 回溯的过程中为了避免产生重复的组合,需要剪枝,通过指定下次递归的选择范围是 i + 1 来进行剪枝。
const combine = function(n, k) {
    const res = []
    const helper = function(start, cur) {
        if (cur.length === k) {
            res.push(cur.slice())
            return
        }
        for (let i = start; i <= n; i++) {
            cur.push(i)
            helper(i + 1, cur)
            cur.pop()
        }
    }
    helper(1, [])
    return res
}

17. 电话号码的字母组合

原题链接

回溯法

使用回溯法进行求解,回溯是一种通过穷举所有可能情况来找到所有解的算法。

如果一个候选解最后被发现并不是可行解,回溯算法会舍弃它,并在前面的一些步骤做出一些修改,并重新尝试找到可行解。

究其本质,其实就是枚举。

如果没有更多的数字需要被输入,说明当前的组合已经产生。

如果还有数字需要被输入:

  • 遍历下一个数字所对应的所有映射的字母。
  • 将当前的字母添加到组合最后,也就是 str + tmp[r]
const letterCombinations = function (digits) {
    if (!digits) {
        return []
    }
    const len = digits.length
    const map = new Map()
    map.set('2', 'abc')
    map.set('3', 'def')
    map.set('4', 'ghi')
    map.set('5', 'jkl')
    map.set('6', 'mno')
    map.set('7', 'pqrs')
    map.set('8', 'tuv')
    map.set('9', 'wxyz')
    const result = []

    function generate(i, str) {
        if (i === len) {
            result.push(str)
            return
        }
        const tmp = map.get(digits[i])
        for (let r = 0; r < tmp.length; r++) {
            generate(i + 1, str + tmp[r])
        }
    }
    generate(0, '')
    return result
}

N+M是输入数字的总数

  • 时间复杂度:O(3^N * 4^M)
  • 空间复杂度:O(3^N * 4^M)

39. 组合总和

原题链接

回溯

先明确,元素可以重复使用,但是组合不能重复。

  1. 使用回溯法,不符合条件的情况进行剪枝。
  2. cur === target 时,拷贝 arr 推进结果集。
  3. 从 start 开始遍历可选数组,选择当前数字后递归时注意要基于当前状态 i 继续选择,因为元素是可以重复进入集合的。
  4. 撤销选择,恢复状态。
const combinationSum = (candidates, target) => {
    const res = []
    // start: 起点索引 arr: 当前集合 cur: 当前所求之和
    const dfs = (start, arr, cur) => {
        if (cur > target) return
        if (cur === target) {
            res.push(arr.slice())
            return
        }
        for (let i = start; i < candidates.length; i++) {
            arr.push(candidates[i])
            dfs(i, arr, cur + candidates[i])
            arr.pop()
        }
    }
    dfs(0, [], 0)
    return res
}

15.三数之和

原题链接

先明确,题目不仅是要求 a + b + c = 0,而且需要三个元素都不重复。

所以我们可以先将数组从小到大排序,排序后,去除重复项会更加简单。

1.外层循环指针 i 遍历数组,题目要求三数之和为 0,考虑此次循环中的数若大于 0,另外两个数肯定也大于 0,则当前位置下无解。
2.去重,如果当前元素和前一个元素相同时,直接跳过即可。
3.内层循环借助双指针夹逼求解,两个指针收缩时也要去除重复的位置。
4.三数之和为 0 时,将当前三个指针位置的数字推入数组即所求。若当前和小于 0 则将左指针向右移动,若当前和大于 0 则将右指针向左移动。

const threeSum = function(nums) {
    const result = []
    const len = nums.length
    if (len < 3) {
        return result
    }
    nums.sort((a, b) => a - b)
    for (let i = 0; i < len - 2; i++) {
        if (nums[i] > 0) {
            break
        }
        if (i > 0 && nums[i] === nums[i - 1]) {
            continue
        }
        let L = i + 1
        let R = len - 1
        while (L < R) {
            let sum = nums[i] + nums[L] + nums[R]
            if (sum === 0) {
                result.push([nums[i], nums[L], nums[R]])
                while(nums[L] === nums[L + 1]){
                    L++
                }
                while(nums[R] === nums[R - 1]){
                    R--
                }
                L++
                R--
            } else if (sum < 0) {
                L++
            } else {
                R--
            }
        }
    }
    return result
}
  • 时间复杂度:O(n^2)
  • 空间复杂度:O(1)

155. 最小栈

原题链接

辅助栈

  1. stack 支持常规的 push、pop、top 操作。
  2. 定义一个辅助栈 resStack ,将最小值一直保持在栈顶,来支持常数时间复杂度获取。
const MinStack = function() {
    this.stack = [];
    this.resStack = [Infinity];
};

MinStack.prototype.push = function(x) {
    this.stack.push(x);
    this.resStack.push(Math.min(this.resStack[this.resStack.length - 1], x));
};

MinStack.prototype.pop = function() {
    this.stack.pop();
    this.resStack.pop();
};

MinStack.prototype.top = function() {
    return this.stack[this.stack.length - 1];
};

MinStack.prototype.getMin = function() {
    return this.resStack[this.resStack.length - 1];
};
  • 时间复杂度: O(1)
  • 空间复杂度: O(n)

冒泡排序

冒泡排序可视化视频

冒泡排序,简单粗暴,一句话解释:

冒泡排序在每次冒泡操作时会比较相邻的两个元素,看是否满足大小关系要求,不满足就将它俩互换。一直迭代到不再需要交换,也就是排序完成。

const bubbleSort = function(arr) {
  const len = arr.length
  if (len < 2) return arr
  for (let i = 0; i < len; i++) {
      for (let j = 0; j < len - i - 1; j++) {
          if (arr[j] > arr[j + 1]) {
              const temp = arr[j]
              arr[j] = arr[j + 1]
              arr[j + 1] = temp
          }
      }
  }
  return arr
}
  • 时间复杂度: O(n^2)
  • 空间复杂度: O(1)
  • 稳定

注意:这里的稳定是指,冒泡排序是稳定的排序算法。

什么是稳定的排序算法呢?

排序算法的稳定性

仅仅用执行效率内存消耗来判断排序算法的优劣是不够的,针对排序算法,还有一个重要的度量指标,稳定性

意思是说,如果待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序不变。

举个🌰:

比如我们有一组数据:1,9,2,5,8,9。按照大小排序之后就是 1,2,5,8,9,9。

这组数据中有两个 9,经过某种排序算法排序后,如果两个 9 的前后顺序没有改变,我们就把这种排序算法称为 稳定的排序算法
否则,就是不稳定的排序算法

冒泡排序优化

上面的代码还可以进行优化,当某次冒泡操作已经没有数据交换时,说明已经达到完全有序,不需要再继续执行后续的冒泡操作了。

const bubbleSort = function(arr) {
  const len = arr.length
  let flag = false
  if (len < 2) return arr
  for (let i = 0; i < len; i++) {
      flag = false // 提前退出冒泡循环的标志
      for (let j = 0; j < len - i - 1; j++) {
          if (arr[j] > arr[j + 1]) {
              const temp = arr[j]
              arr[j] = arr[j + 1]
              arr[j + 1] = temp
              flag = true // 表示有数据交换
          }
      }
      if (!flag) break // 没有数据交换,提前退出
  }
  return arr
}

5.最长回文子串

原题连接

如果一个字符串 aba 是一个回文串,那么在它的左右分别添加一个相同的字符 a,那么它一定还是一个回文串 aabaa。

我们可以用 dp[i][j] 表示 s 中从 i 到 j (包括 i 和 j) 是否可以形成回文串,将上面这段话翻译成代码,列出状态转移方程。

  • dp[i][j] === true 是回文串
  • dp[i][j] === false 不是回文串

状态转移方程

s[i] === s[j] && dp[i][j] = dp[i + 1][j - 1]

边界处理

需要考虑 j - i < 2 的情况,此时子串长度为 0 或 1。

例如:a,aa,对称点分别是字符本身和两个字符中间的虚拟点。

双重循环,不断向外延伸尝试得到可能的最大回文串长度。第一层倒着循环,是因为 dp[i] 依赖于 dp[i + 1]。

const longestPalindrome = function (s) {
    const len = s.length
    const dp = Array.from(new Array(len), () => new Array(len).fill(0))
    let res = ''
    for (let i = len - 1; i >= 0; i--) {
        for (let j = i; j < len; j++) {
            dp[i][j] = s[i] === s[j] && (j - i < 2 || dp[i + 1][j - 1])
            if (dp[i][j] && j - i + 1 > res.length) { // 符合条件时截取得到最长的回文串
                res = s.slice(i, j + 1)
            }
        }
    }
    return res
}
  • 时间复杂度:O(n^2)
  • 空间复杂度:O(n^2)

插入排序

插入排序顾名思义,对于未排序的数据,在已排序的序列中从后往前扫描,找到相应的位置进行插入,保持已排序序列中元素一直有序。

从 i 等于 1 开始遍历,拿到当前元素 curr,与前面的元素进行比较。

如果前面的元素大于当前元素,就把前面的元素和当前元素进行交换,不断循环直到未排序序列中元素为空,排序完成。

const insertSort = function(arr) {
    const len = arr.length
    let curr, prev
    for (let i = 1; i < len; i++) {
        curr = arr[i]
        prev = i - 1
        while (prev >= 0 && arr[prev] > curr) {
            arr[prev + 1] = arr[prev]
            prev--
        }
        arr[prev + 1] = curr
    }
    return arr
}
  • 时间复杂度: O(n^2)
  • 空间复杂度: O(1)
  • 稳定

32. 最长有效括号

原题链接

子问题

dp[i]: 表示以 s[i] 结尾的最长有效括号长度。

状态转移方程

分情况讨论出所有可能:

最长有效括号

s[i] 可能为 '(' 或者 ')'

  1. s[i] === '(' 时,不可能组成有效的括号,所以 dp[i] = 0。
  2. s[i] === ')' 时,需要查看 s[i - 1]。
    • s[i - 1] === '(' 时,s[i - 1] 和 s[i] 可以组成一对有效括号,需要查看 s[i - 2]。
      • s[i - 2] 不存在,则有效长度为 2。 dp[i] = 2
      • s[i - 2] 存在,则需要在 2 的基础上加上以 s[i - 2] 为结尾的最长有效长度。dp[i] = dp[i - 2] + 2
    • s[i - 1] === ')' 时,此时 s[i - 1] 和 s[i] 合起来是 '))',需要查看 s[i - dp[i - 1] - 1]。
      • s[i - dp[i - 1] - 1] 不存在或为 ')',则 s[i] 找不到匹配,所以 dp[i] = 0。
      • s[i - dp[i - 1] - 1] 是 '(',与 s[i] 匹配。此时需要查看 s[i - dp[i - 1] - 2]是否存在。
        • s[i - dp[i - 1] - 2] 不存在,dp[i] = dp[i - 1] + 2
        • s[i - dp[i - 1] - 2] 存在,dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2

用代码表示出来即可:

const longestValidParentheses = function(s) {
  let res = 0
  const len = s.length
  const dp = new Array(len).fill(0)
  for (let i = 1; i < len; i++) {
    if (s[i] == ')') {
      if (s[i - 1] == '(') {
        if (i - 2 >= 0) {
          dp[i] = dp[i - 2] + 2
        } else {
          dp[i] = 2
        }
      } else if (s[i - dp[i - 1] - 1] == '(') {
        if (i - dp[i - 1] - 2 >= 0) {
          dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]
        } else {
          dp[i] = dp[i - 1] + 2
        }
      }
    }
    res = Math.max(res, dp[i])
  }
  return res
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

55. 跳跃游戏

原题链接

先明确,题目给出的非负整数数组中的每个位置的数字都对应着其最大的跳跃能力,要求我们判断能否到达最后一个下标。

到达或是超过都是可以满足要求的,因为每个位置的数字代表的是其最大的跳跃能力,而不是固定的跳跃能力(大富翁游戏)。

所以只需要判断能否到达终点即可:

  1. 定义能够跳的最远位置 canJumpMax,初始化为 0。
  2. 遍历数组,如果当前值大于 canJumpMax 则不能跳到末尾返回 false。
  3. 每个位置都可以作为起跳点,将 canJumpMax 不断更新,i + nums[i] 也就是当前位置能够跳到的最远位置。
  4. 如果可以跳到最后即成功返回 true。
const camJump = function(nums) {
    let canJumpMax = 0
    let len = nums.length
    for (let i = 0; i < len; i++) {
        if (i > canJumpMax) {
            return false
        }
        canJumpMax = Math.max(canJumpMax, i + nums[i])
    }
    return true
}
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

100. 相同的树

原题链接

深度优先搜索 DFS

1.如果两个二叉树都为空,则它们相同返回 true。
2.如果两个二叉树中有一个为空,则它们不同返回 false。
3.如果两个二叉树都不为空,首先判断根节点是否相同,不同则返回 false。
4.如果两个二叉树的根节点相同,则分别递归判断其左右子树是否相同。

const isSameTree = function(p, q) {
    if (p === null && q === null) return true;
    if (p === null || q === null) return false;
    if (p.val !== q.val) return false;
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};
  • 时间复杂度: O(min(m, n))
  • 空间复杂度: O(min(m, n))

283. 移动零

原题链接

双指针

题目要求将所有 0 移动到数组的末尾,同时还要保持非零元素的相对顺序。

在此基础上附加了两个条件:

1.必须在原数组上操作,不能拷贝额外的数组。
2.尽量减少操作次数。

我们可以借助双指针来进行求解,求解过程如下:

1.初始化双指针 i 、j 指向数组头部索引 0。
2.将 i 指针不断向右移动,j 指针负责提供交换的位置,当遇到非 0 数字时,将两个指针位置的数字交换,同时继续向右边移动两个指针。这样交换可以保证题目要求的非 0 数字相对顺序不变。
3.当遇到 0 时,向右移动 i 指针,j 指针不动。
4.循环完成时即可将所有的 0 移动到数组的末尾。

const moveZeroes = function (nums) {
    let i = 0, j = 0;
    while (i < nums.length) {
        if (nums[i] != 0) {
            [nums[i], nums[j]] = [nums[j], nums[i]];
            i++;
            j++;
        } else {
            i++;
        }
    }
}
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.