【刷题25】深搜——递归专题

一、汉诺塔问题

题目：

思路：如下图

• 出口条件：n=1，A盘给C盘
• A盘上面的借助C盘给B盘
• A盘给C盘
• B盘借助A盘给C盘

注意：为啥是push_back

代码：

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

二、合并两个有序链表

题目：

思路：

• l1为空返回l2，l2为空返回l1
• 比大小，小的节点的next->dfs，然后返回该节点

代码：

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        return dfs(list1, list2);
    }
    ListNode* dfs(ListNode* list1, ListNode* list2)
    {
        if(list1==nullptr) return list2;
        if(list2==nullptr) return list1;
        if(list1->val < list2->val)
        {
            list1->next = dfs(list1->next, list2);
            return list1;
        }
        else 
        {
            list2->next = dfs(list1, list2->next);
            return list2;
        }
        return nullptr;
    }
};

三、反转链表

题目：

思路：

• 没有节点或者只有一个节点返回head
• 后序遍历，直到当前节点的下一个节点为空返回
• 重复的动作：当前节点的下一个节点的next指向自己，然后自己指向空

注意：newhead其实指向的是val为2的节点2，图的意思是表示newhead在val为1的节点这层

代码：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == nullptr || head->next == nullptr)
        {
            return head;
        }
        ListNode* newhead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newhead;
    }
};

四、两两交换链表中的节点

题目：

思路：

代码：

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head == nullptr || head->next == nullptr)
        {
            return head;
        }
        ListNode* tmp = swapPairs(head->next->next);
        ListNode* ret = head->next;
        head->next->next = head;
        head->next = tmp;
        return ret;
    }
};

五、Pow(x,n)

题目：

思路：

• 出口条件：n等于0，返回1
• dfs，每次n/2，用ret来接收递归调用的返回值
• 如果 n %2 有余数，返回 ret 乘 ret 乘 x ； 否则返回ret 乘 ret
• 如果n是负数，x要倒置，n变成正数，其他和前面一样
• 注意：n的类型转成long long

代码：

class Solution {
public:
    double myPow(double x, long long n) {
        if(n < 0) 
        {
            x = 1.0 /x;
            n = abs(n);
        }
        return pow(x, n);
    }
    double pow(double x, long long n)
    {
        if(n == 0) return 1.0;
        
        double ret = pow(x, n/2);
        long y = n % 2;
        if(y == 1) return ret * ret * x;
        else return ret * ret;
    }
};