HOME

你有一个三角形形状的 2D 数组，你需要找到从最顶层走到最底层的最短路径。

限制是每一步你只能下一层，且每一步你只能选择下一层的同下标位置或者下标 +1 位置。

Given a triangle array, return the minimum path sum from top to bottom.

For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.

看看例子才能更好理解题目，这题看上去需要计算所有可能才能知道答案，或许是 DP 的用武之地。

杨辉三角问题。在杨辉三角中每个元素 i 的值由上一行同位置 i 的值加上上一行前一个位置 i-1 的值决定。

你需要实现一个程序接受一个行数，返回到这行位置的杨辉三角数组。枚举问题，DP 解决。

将二叉树结构数据扁平化为链表，采用前序遍历（pre-order traversal）顺序。

题目要求修改二叉树结构去构成数组，在这个限制下我们要对前序遍历做一些修改才能解决这道题。

你有一个链表的 head 元素，链表数组按照升序排列，现在你需要实现一个程序将其转换为高度平衡的二叉查找树。

对这道题来说，高度平衡的二叉树定义为所有节点的子节点深度相差不大于 1。

题目的难点在于你不知道链表的长度。我们从几个思路讨论如何解决这道题。

求二叉树的最大深度。二叉树的深度指的是其节点的最大层数。

这是一道简单题，但是可以视作是 Top-Down 和 Bottom-Up 方法的教学题。

我们应用 DFS 来处理之道题，来看看自上而下与自下而上方法的区别。

遍历树的方式除了通常的前序遍历、中序遍历和后序遍历之外，还有本题的层序遍历。

层序遍历的顺序是从左到右依次遍历同层级到节点，然后在进入下一层级重复这个过程，直到不再存在下一层级。这是一个典型的宽度优先搜索（BFS）算法。

字符串问题。定义字符串交错指的是俩个字符串的字符交错出现构成一个新的字符串。比如对字符串 s 和 t 来说：

• s = s1 + s2 + ... + sn
• t = t1 + t2 + ... + tm
• |n - m| <= 1
• The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + s1 + t2 + s2 + t3 + s3 + ...

现在你需要实现一个程序接受三个字符串 s1、 s2、 s3，判断 s3 是否是 s1 和 s2 字符串交错组成。

遍历树的方法通常有三种，分别是前序遍历 pre-order traversal、中序遍历 in-order traversal 和后序遍历 post-order traversal。这道题是中序遍历。

难度上来说，前序最简单，中序和后序遍历会复杂一点。

链表问题。实现一个程序根据 2 个下标位置对链表对于位置的元素进行翻转。

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

链表问题。链表分区，给你一个链表和整数 x，你需要在保证相对顺序的情况下，将小于 x 的值排在链表前面，大于等于 x 的值排在后面。

Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.