递归（6题）

你们叫她小龙女么

847人浏览 · 2024-11-14 18:39:35

你们叫她小龙女么 · 2024-11-14 18:39:35 发布

方法论

调试小技巧

写oj题调试的时候，我们可以在相应逻辑处进行一个打印，来查看对应逻辑是否正确。

1.汉诺塔问题

. - 力扣（LeetCode）

我们列出三种情况，即可发现其子问题。

我们从第二组开始看，发现

先把A中最上面一个先放到B中，

然后把A中余下的一个放到C中，

最后把B中的一个放到C中。

再观察第三组。

先把A中最上面两个先放到B中，

然后把A中余下的一个放到C中，

最后把B中的两个放到C中。

把两个放到另一个位置的问题与第二种情况相同。

因此我们的函数头设置为

void dfs(vector<int>& x, vector<int>& y, vector<int>& z,int n)

把x中的n个元素，通过y，放到z中。

在函数体中我们先写出口。即唯一的特例，当要转移的位置中元素只有1时。

然后在函数体中写下解决某一子问题的过程。

先把x中的元素通过z放到y中即步骤1

再把剩下的一个放到z中即步骤2

最后把y中的元素通过x放到z中即步骤3

class Solution {
public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        dfs(A,B,C,A.size());
    }
    void dfs(vector<int>& x, vector<int>& y, vector<int>& z,int n)
    {
        if(n == 1)
        {
            z.push_back(x.back());
            x.pop_back();
            return;
        }
        dfs(x,z,y,n-1);
        z.push_back(x.back());
        x.pop_back();
        dfs(y,x,z,n-1);
    }
};

下面是递归展开图

2.合并两个有序链表

. - 力扣（LeetCode）

一版代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* tail = new ListNode;
        merge(tail,list1,list2);
        return tail->next;
    }
    void merge(ListNode* tail,ListNode* list1, ListNode* list2)
    {
        if(list1 == nullptr)
        {
            tail->next = list2;
            return;
        }
        if(list2 == nullptr)
        {
            tail->next = list1;
            return;
        }
        if(list1->val < list2->val)
        {
            tail->next = list1;
            merge(list1,list1->next,list2);
        }
        else
        {
            tail->next = list2;
            merge(list2,list1,list2->next);
        }
    }
};

定义一个尾节点。

先判断出口条件，当l1为空，那么尾节点接上l2反之接上l1，然后返回。

解决子问题：

如果l1的节点数值更小，那么把l1连到tail后面，且此时l1变为新的tail，l1的next变为新的l1，l2不变。

反之把l2连到tail后面，且此时l2变为新的tail，l2的next变为新的l2，l1不变

解决的子问题是把tail后面接上对应的节点

二版代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1 == nullptr)return list2;
        if(list2 == nullptr)return list1;

        if(list1->val < list2->val)
        {
            list1->next = mergeTwoLists(list1->next,list2);
            return list1;
        }
        else
        {
            list2->next = mergeTwoLists(list1,list2->next);
            return list2;
        }
    }
};

递归的出口，谁为空就返回另一个。

解决的子问题是返回排序结束后的头节点。函数体中只需要考虑一步就可以了。剩下的递归会去做

补充知识

递归和循环都是解决重复问题，在多分枝的时候我们通常选择递归，单分支的时候，我们可以使用循环去做

如图是使用递归来打印一个数组。

我们也可以理解成是一种先序遍历。

如果我们要逆序打印，dfs的工作变为逆序打印，只需要把cout 放在dfs(nums,i+1)后面。就成了后序遍历

3.合并k个有序链表

. - 力扣（LeetCode）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists,0,lists.size()-1);
    }
    ListNode*merge(vector<ListNode*>& lists,int left,int right)
    {
        if(left > right)return nullptr;
        if(left == right)return lists[left];

        //1.平分数组
        int mid = (left + right) / 2;

        //2.递归左右区间
        ListNode* l1 = merge(lists,left,mid);
        ListNode* l2 = merge(lists,mid+1,right);

        return mergeTwoLists(l1,l2);

    }
     ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1 == nullptr)return list2;
        if(list2 == nullptr)return list1;

        if(list1->val < list2->val)
        {
            list1->next = mergeTwoLists(list1->next,list2);
            return list1;
        }
        else
        {
            list2->next = mergeTwoLists(list1,list2->next);
            return list2;
        }
    }
};

是上一题的升级版，在主逻辑使用递归的同时，小步骤中也使用递归。这里附用了第二题的代码。

我们把存储链表的数组分成两半，让他们两半各自合并成一个链表，然后合并。

这两半的任意一半要合成一个链表，又要把这个范围内的链表分成两半，让它们先各自合并成一个链表，然后合并，就出现了子问题

merge函数的作用就是合并一个范围内的链表。我们只需要相信merge可以帮助我们完成这个工作即可

合并之后由mergeTwoLists合并两个链表，得到结果。

4.反转链表

. - 力扣（LeetCode）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == nullptr || head->next == nullptr)return head;
        ListNode* tmp = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return tmp;
    }
};

这题我们依然用宏观视角。

如果我们一开始直接反转第一第二个链表的话，就会找不到第三个链表，因此我们使用reverseList函数来反转后面的链表，我不关心你是怎么样实现的，但是我相信你能把链表逆置后再把新的头节点返回给我。接着反转第一和第二个节点，临界条件是head或者head->next为空

5.两两交换链表中的节点

. - 力扣（LeetCode）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head == nullptr)return nullptr;
        if(head->next == nullptr)return head;
        ListNode* tmp = swapPairs(head->next->next);
        ListNode* next = head->next;
        next->next = head;
        head->next = tmp;
        return next;
    }
};

这道题目较为容易，我们要两两交换，只需要考虑一次两两交换节点即可，交换之后将第二个节点与后面的节点相连，我相信我这个函数可以帮我做到将后面的节点两两交换，最后用一个变量接收返回值。因为需要用到第三个节点，因此需要判断前两个节点的存在与否

6.pow(x,n)

. - 力扣（LeetCode）

class Solution {
public:
    double myPow(double x, int n) {
        if(n < 1)
        {
            x = 1.0/x;
            n = -(long long)n;
        }
       return mypow(x,n);
    }
    double mypow(double x,int n)
    {
        if(n == 0)return 1.0;
        double tmp = mypow(x,n/2);
        if(n % 2)return tmp*tmp*x;
        else return tmp*tmp;
    }
};

这题因为要处理n < 1的问题我们可以将函数分离，在一个函数里处理好，另一个函数专注处理一般情况，使得函数的功能实现更为集中。

每次计算某个数时，我们都想着求底数相同指数是它的一半的数是多少。