LeetCode 上几道经典的排列组合题

LeetCode 上有几道题都和排列组合有关,非常经典,值得放在一起总结一下。这几道题分别是:

  • Permutations。给定一组各不相同的数字,求这些数字的所有排列。
  • Permutations II。给定一组数字,这些数字中可能有重复的,求这些数字的所有不重复的排列。
  • Next Permutation。给定一组数字的全排列中的一个排列,求这个排列的下一个排列。
  • Permutation Sequence。给定一组数字和一个数字 K,求这组数字的全排列中,按照字典序顺序排序的第 K 个排列。

继续阅读“LeetCode 上几道经典的排列组合题”

LeetCode-494-Target Sum

这个题也是一道动态规划题目。题意是:给出一系列数和一个目标数,使用+-来使这些数字的和等于给定的目标数,求总共可行的方法数。

例子:输入[1, 1, 1, 1, 1]target = 3,那么:

所以最后的输出结果是:5 继续阅读“LeetCode-494-Target Sum”

LeetCode-120-Triangle

这道题的题意是:给定一个数组形成的三角形,在从三角形的顶部出发的路径中,求节点数值相加结果为最小的和。

例子:输入

那么从顶部到底部最小的一条路径和为:2+3+5+1=11

思路:这是一道逆序的二维动态规划题,和之前看过的一道题–《龙与地下城》非常相似,都是逆序地从下往上求 DP数组。代码很简单,就不多做分析了,相信大家一看就能看懂。

代码如下:

LeetCode-746-Min Cost Climbing Stairs

链接在此。

解题思路:输入的 cost 向量的长度 len即为台阶的级数。我们可以生成一个长度为len+1的向量 dp,dp[i]表示跳到第 i 个位置(从0开始计数)需要的费用。例如 dp[0]表示跳到第0个位置的cost,为0;dp[1]表示跳到第1个位置的 cost,因为起始 index 可以为1,所以 dp[1] = 0;dp[2]表示跳到第2个位置的 cost,因为一次可以跳一步或者两步,因此 dp[2]的值有两种可能:

* 从第0个位置跳过来,所以 dp[2] = dp[0] + cost[0];
* 从第1个位置跳过来,所以 dp[2] = dp[1] + cost[1];
因此我们应该取这两种情况中较小的那一个:dp[2] = min(dp[2-2] + cost[2-2], dp[2-1]+cost[2-1]);

下面我们来推导状态转移方程:
dp[i]表示跳到第 i 个位置,它的值有两种可能:
* 从第 i-2 个位置跳过来,因此dp[i] = dp[i-2]+cost[i-2]
* 从第 i-1 个位置跳过来,因此dp[i] = dp[i-1]+cost[i-1]

因此,dp[i] = min(dp[i-1]+cost[i-1], dp[i-2] + cost[i-2])。这即为本题的状态转移方程。根据该方程,我们不难写出下面的代码:

二叉树的 Morris 遍历

转载自:Morris Traversal方法遍历二叉树(非递归,不用栈,O(1)空间),有所修改。

Morris 遍历是由 Joseph Morris 于1979年发明的,这种遍历方法与递归以及非递归遍历方法相比,其时间复杂度为 O(n),而空间复杂度只要 O(1)。在某些场合下,其空间复杂度为常数的特性非常有用,因此我们有必要了解和掌握它是如何实现的。 继续阅读“二叉树的 Morris 遍历”