HOME

求二叉树最深层的所有节点的值之和。二叉树层序遍历的应用场景。

虽然题目的 tag 包含 DFS，但是感觉用 DFS 思路比 BFS 还要复杂并且低效，所以这题我们只讨论 BFS 思路。

图论问题。一共有 n 台服务器，我们将存在于任意 2 台服务器之间链接定义为边，可以构成一张无向图。

给定一个 connections 数组定义这个服务器网络的所有链接（边），在这个网络上任何节点都可以直接或间接的相互访问。

关键链接指的是这个网络中的某一个节点如果被移除，将导致一部分服务器无法访问到另一部分。

要求找到所有关键链接。

矩阵求和问题。给定一个矩阵 matrix 和一个目标值 target，求和为 target 的子矩阵的数量。

这是典型的前缀和应用场景，我们分别用两种思路应用前缀和来解决这个问题。

给定一个由英文小写字母组成的字符串数组 words，你需要从中挑选单词构成满足下面定义的词汇链（word chain），找到能构成的最长词汇链，返回其长度。

• 词汇链（word chain）指一个字符串数组中，每个字符串都是后一个字符串的前置（predecessor），如果数组只有一个字符串，这个词汇链长度为 1；
• 前置（predecessor）指一个字符串 A 满足仅向其中添加一个字符可以构成字符串 B 的条件，此时字符串 A 称之为字符串 B 的前置。
  • 比如 "abc" 是 "abac" 的前置, 而 "cba" 不是 "bcad" 的前置。

我们用 DFS 和 DP 两个思路解决这个问题。

给定一个由英文小写字母组成的字符串 s，要求去重并返回结果。去重的条件是 2 个字符必须接邻且相等。

这道题的难点在于去重之后的字符串可能会产生新的重复。使用 Stack 可以方便的解决这道题。

给定一个二进制数组 nums（元素的值为 0 或 1），求最长的连续的 1 的长度。

有趣的地方在于你有 k 次机会将 0 翻转为 1，你需要找出最合适的时机使用这些机会。

“连续”是这道题的关键字，看上去我们可以使用滑动窗口来解决这道题。

给定 3 个整数 x， y， bound，求所有小于等于 bound 的强整数（Powerful Integers）。

强整数（Powerful Integers）指一个数可以用 x^i + y^j 的形式表现，其中 i 和 j 均大于等于 0。

答案无所谓排序，但是不能有重复的值。需要用到一些数学方法来解决这道题。

在二叉树上安装摄像头，每个摄像头可以监控 +1 的距离，也就是它的父节点、子节点和自身。求最少需要安装多少摄像头才能监控整棵树。

这道题我们讨论贪心算法和 DP 的应用。

NOT SOLVED YET!!

计算完每个字符串的 overlap 之后，这个问题变成了有向加权图的最短路径问题，这是一个典型的 TSP 问题，NP-Hard 难度。

由于暂时还是我的只是盲区，先做记录，等学到图论和 TSP 解法的时候再来看看这道题。

嗯…暂且打表吧…