【算法】【学习笔记】递归

递归要注意边界条件和返回值。
❔题目

1. 合并两个有序链表

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

首先可以看出边界条件是list1为null时，返回list2；list2为null时，返回list1。
然后对当前值举行判断，当list1的值大于list2时，让list1.next继续和list2举行合并，而不是两个一起切换为next，这样子就乱套了。
实现

1. function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
2.     if(list1 === null){
3.         return list2;
4.     }
5.     if(list2 === null){
6.         return list1;
7.     }
8.    
9.     if(list1.val <= list2.val){
10.         list1.next = mergeTwoLists(list1.next, list2);
11.         return list1;
12.     }else{
13.         list2.next = mergeTwoLists(list1, list2.next);
14.         return list2;
15.     }
16. };

复制代码

复杂度分析

• 时间复杂度： \(O(m+n)\)
  m、n 分别为两个链表的长度，最多处理两个链表中的每个节点一次。
  
• 空间复杂度： \(O(m+n)\)
  使用递归实现，递归调用栈最多到达 \(O(m+n)\) 层。
  

2. 找出第 N 个二进制字符串中的第 K 位

给你两个正整数 n 和 k，二进制字符串  \(S_n\) 的形成规则如下：

• \(S_1\) = "0"
  
• 当 i > 1 时，\(S_i\) = \(S_{i-1}\) + "1" + reverse(invert(\(S_{i-1}\)))
  其中 + 表示串联操作，reverse(x) 返回反转 x 后得到的字符串，而 invert(x) 则会翻转 x 中的每一位（0 变为 1，而 1 变为 0）。
  

例如，符合上述描述的序列的前 4 个字符串依次是：

• S1 = "0"
  
• S2 = "011"
  
• S3 = "0111001"
  
• S4 = "011100110110001"
  请你返回 \(S_n\) 的 第 k 位字符 ，题目数据保证 k 一定在 \(S_n\) 长度范围以内。
  

解题思路

这个题目必要用到分治的头脑，假如直接递归构造S，会导致 \(2^n\) 的时间复杂度。
根据规律可以知道，中间的数必定为1。假如k在中间的左边，那么递归调查左半边，假如在右边，则递归调查右半边，并由于是右半边，右半边经过了 翻转 和 取反：

• 反转位置映射：\(S_n\) 中的第 \(k\) 位，对应 \(S_{n-1}\) 中的第 \(2^n - k\) 位。
  
• 取反值映射：找到 \(S_{n-1}\) 第 \(2^n - k\) 位的值后，将其 0 变 1，1 变 0 即可。
  

实现

[code]function findKthBit(n: number, k: number): string {    // 递归基：S1 只有一位 '0'    if (n === 1) return "0";    // len = 2^n - 1, mid = 2^(n-1)    const mid = 1