算法学习-递归

leet_code 的递归算法的学习

344.反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

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

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符

示例 1：

1
2
输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：

1
2
输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
function reverseString(s: string[]): void {
  const fn = (start: number, end: number, s: string[]) => {
    if (start > end) {
      return;
    }
    let tmp = s[start];
    s[start] = s[end];
    s[end] = tmp;
    fn(start + 1, end - 1, s);
  }

  fn(0, s.length - 1, s);
};

通过首尾替换的方式修改数组的值，左边的值 ++ ，右边的值--，直到 left > right （索引）跳出递归

509.斐波那契数

斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。

代码

递归

1
2
3
4
5
6
7
8
9
10
11
let cache = new Map();
function fib(N: number): number {
  if (N == 0) return 0
  if (N == 1) return 1
  if (cache.has(N)) {
    return cache.get(N)
  }
  let ret = fib(N - 1) + fib(N - 2)
  cache.set(N, ret);
  return ret;
}

数组

1
2
3
4
5
6
7
function fibArr(n: number): number {
  let arr = [0, 1];
  for (let i = 2; i <= n; i++) {
    arr[i] = arr[i - 1] + arr[i - 2];
  }
  return arr[n];
}

206.反转链表

反转一个单链表。

示例:

1
2
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

1
2
3
4
5
6
7
8
9
function reverseList(head: ListNode | null): ListNode | null {
  if (head === null || head.next === null) {
    return head;
  }
  const node = reverseList(head.next);
  head.next.next = head;
  head.next = null;
  return node;
}

104.二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。示例：给定二叉树 3,9,20,null,null,15,7，

返回它的最大深度 3 。

1
2
3
4
5
function maxDepth(root: TreeNode | null): number {
  return root
    ? Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
    : 0
};

50. Pow(x, n)

实现 pow(x, n) ，即计算 x 的 n 次幂函数。 示例 1:

1
2
输入: 2.00000, 10
输出: 1024.00000

示例 2:

1
2
输入: 2.10000, 3
输出: 9.26100

示例 3:

1
2
3
输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25

说明:

-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 −231, 231 − 1 。

1. for循环累乘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function myPow(x: number, n: number): number {
  let newN = n;
  let newX = x;
  if (newN < 0) {
    newX = 1 / x;
    newN = -n
  }
  let aws = 1;
  console.info(newX);
  for (let i = 0; i < newN; i++) {
    aws *= newX;
  }
  return aws;
}

2. 递归

1
2
3
pow(2, 10) === pow(2, 5) * pow(2, 5) === pow(2, pow(2, 5))

pow(2, 9) === pow(2, 4) * pow(2, 4) * 2 === pow(2, pow(2, 4)) * 2

我们可以知道 在次方为偶数的情况下: 一个值（2）的 10次方相当于是，两个该值的一半(10 / 2) 的乘积 在次方为奇数的情况下: 一个值（2）的 9次方相当于是，两个该值的一半【向下取整的次方】(Math.floor(9 / 2)) * 2 的乘积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function myPow(x: number, n: number): number {
  const fastPow = (x: number, n: number): number => {
    if (n === 0) {
      return 1;
    }

    const half = fastPow(x, Math.floor(n / 2));
    if (n % 2 === 1) {
      // 基数
      return half * half * x;
    } else {
      return half * half;
    }
  }

  const ret = fastPow(x, Math.abs(n));
  // n < 0 负次方则将总的乘积求导数
  return n > 0 ? ret : 1 / ret;
};

21.合并两个有序链表

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

示例 1：

合并两个有序链表

1
2
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

1
2
输入：l1 = [], l2 = []
输出：[]

示例 3：

1
2
输入：l1 = [], l2 = [0]
输出：[0]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  // 如果 l1 到头了，直接拼l2的值
  if (l1 === null) {
    return l2;
  }

  // 如果 l2 到头了，拼接l1的值
  if (l2 === null) {
    return l1;
  }

  // l1.val > l2.val 则将l1 和 l2 的下一个做比较，l2的next值就是比较之后的值
  if (l1.val > l2.val) {
    l2.next = mergeTwoLists(l1, l2.next);
    return l2;
  } else {
    // 同理
    l1.next = mergeTwoLists(l1.next, l2);
    return l1;
  }
};

779.第K个语法符号

在第一行我们写上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。

给定行数 N 和序数 K，返回第 N 行中第 K个字符。（K从1开始） 例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
输入: N = 1, K = 1
输出: 0

输入: N = 2, K = 1
输出: 0

输入: N = 2, K = 2
输出: 1

输入: N = 4, K = 5
输出: 1

解释:
第一行: 0
第二行: 01
第三行: 0110
第四行: 01101001

注意： 1. N 的范围 1, 30. 2. K 的范围 1, 2^(N-1).

1
2
3
4
5
6
7
8
9
10
11
12
function kthGrammar(N: number, K: number): number {
  if (N === 1) return 0;
  // 如果 K 是奇数，则 N,K 对应的值为父级（N-1，((K + 1)) / 2）的位置的值
  if (K % 2) {
    return kthGrammar(N-1, (K + 1) / 2);
  } else {
    // 偶数 
    // 上一行为0 下一行为1
    // 上一行为1 下一行为0
    return kthGrammar(N-1, K / 2) === 0 ? 1 : 0;
  }
};

95.不同的二叉搜索树 II

给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
输入：3
输出：
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
解释：
以上的输出对应以下 5 种不同结构的二叉搜索树：

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

提示：

0 <= n <= 8

二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function generateTrees(n: number): Array<TreeNode | null> {
  // 0 直接返回
  if (n === 0) return [];

  // 递归函数 初始值 以及最大值
  const getBSTnum = (start: number, n: number) => {
    if (start > n) return [null];
    if (start === n) return [new TreeNode(start)];

    const res = [];
    for (let i = start; i <= n; i++) {
      let leftBST = getBSTnum(start, i - 1);
      let rightBST = getBSTnum(i + 1, n);

      for (let leftV of leftBST) {
        for (let rightV of rightBST) {
          const root = new TreeNode(i);
          root.left = leftV;
          root.right = rightV;
          res.push(root);
        }
      }
    }
    return res;
  };
  return getBSTnum(1, n);
};

总结

递归算法的时间复杂度通常是递归调用的数量和计算的时间复杂度的乘积
递归算法的空间复杂度, 虑造成空间消耗的两个部分：
- 递归相关空间 (不断执行递归，堆栈数据得不到释放，规模过大可能会导致堆栈溢出)
- 非递归相关空间（与递归过程没有直接关系的内存空间，通常包括为全局变量分配的空间（通常在堆中））

记忆化技术优化递归性能

https://leetcode-cn.com/leetbook/read/recursion/xk5vw2/

✏️ 如有问题，欢迎指正

上一篇 : 2020总结下一篇 : 提升页面性能的n种方法