前端算法总结

• 基础–时间复杂度&空间复杂度
  • 什么是复杂度分析 ？
  • 为什么要进行复杂度分析 ？
  • 如何进行复杂度分析 ？
• 双指针
  • 最接近的三数之和
  • 通过删除字母匹配到字典里最长单词
• 滑动窗口
  • 滑动窗口的最大值
• 二叉树
  • 二叉树的最近公共祖先
• 堆
  • 最小的k个数
  • 前 K 个高频元素 – 桶排序
  • 数组中的第K个最大元素 – 快速选择（quickselect）算法
• 图
  • 找到小镇的法官
  • 课程表问题
• 动态规划
  • 爬楼梯问题 – dp[n] = dp[n?1] + dp[n?2]
  • 使用最小花费爬楼梯 – dp[i] = mindp[i-2], dp[i-1] + cost[i]

基础–时间复杂度&空间复杂度

复杂度分析是整个算法学习的精髓，只要掌握了它，数据结构和算法的内容基本上就掌握了一半了。

什么是复杂度分析 ？

数据结构和算法解决是 “如何让计算机更快时间、更省空间的解决问题”。因此需从执行时间和占用空间两个维度来评估数据结构和算法的性能。分别用时间复杂度和空间复杂度两个概念来描述性能问题，二者统称为复杂度。
复杂度描述的是算法执行时间（或占用空间）与数据规模的增长关系。

为什么要进行复杂度分析 ？

和性能测试相比，复杂度分析有不依赖执行环境、成本低、效率高、易操作、指导性强的特点。掌握复杂度分析，将能编写出性能更优的代码，有利于降低系统开发和维护成本。

如何进行复杂度分析 ？

大 O 表示法

算法的执行时间与每行代码的执行次数成正比，用 T(n) = O(f(n)) 表示，其中 T(n) 表示算法执行总时间，f(n) 表示每行代码执行总次数，而 n 往往表示数据的规模。这就是大 O 时间复杂度表示法。

更多详细内容，请微信搜索“前端爱好者“， 戳我 查看 。

双指针

最接近的三数之和

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。

找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

通过删除字母匹配到字典里最长单词

给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。

如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。

滑动窗口

滑动窗口的最大值

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

二叉树

二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

堆

最小的k个数

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

前 K 个高频元素 – 桶排序

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

数组中的第K个最大元素 – 快速选择（quickselect）算法

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

图

找到小镇的法官

在一个小镇里，按从 1 到 N 标记了 N 个人。传言称，这些人中有一个是小镇上的秘密法官。
如果小镇的法官真的存在，那么：

1. 小镇的法官不相信任何人。
2. 每个人（除了小镇法官外）都信任小镇的法官。
3. 只有一个人同时满足属性 1 和属性 2 。
   给定数组 trust ，该数组由信任对 trust[i] = [a, b] 组成，表示标记为 a 的人信任标记为 b 的人。

如果小镇存在秘密法官并且可以确定他的身份，请返回该法官的标记。否则，返回 -1 。

课程表问题

你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。

在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]
给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？

动态规划

爬楼梯问题 – dp[n] = dp[n?1] + dp[n?2]

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

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

使用最小花费爬楼梯 – dp[i] = min(dp[i-2], dp[i-1]) + cost[i]

数组的每个索引作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i] (索引从0开始)。

每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。

您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。