dfs专题一：递归

dfs简介：

1.汉诺塔问题

link:面试题 08.06. 汉诺塔问题 - 力扣（LeetCode）

code

class Solution {
public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        dfs(A, B, C, A.size());
    }

    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);// 相信dfs一定可以完成任务
        C.push_back(A.back()); A.pop_back();
        dfs(B, A, C, n - 1);
    }
};

2.合并两个升序链表

link:21. 合并两个有序链表 - 力扣（LeetCode）

code

/**
 * 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) {
        return dfs(list1, list2);
    }

    ListNode* dfs(ListNode* list1, ListNode* list2)
    {
        if(!list1) return list2;
        if(!list2) return list1;
        if(list1->val > list2->val) swap(list1, list2);
        {
            list1->next = dfs(list1->next, list2);
            return list1;
        }
    }
};

3.反转链表

link:206. 反转链表 - 力扣（LeetCode）

code

/**
 * 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) {
        return dfs(head);
    }

    ListNode* dfs(ListNode* head)
    {
        if(!head || !head->next) return head;
        ListNode* newhead = dfs(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newhead;
    }
};

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

link:24. 两两交换链表中的节点 - 力扣（LeetCode）

code

/**
 * 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) {
        return dfs(head);
    }

    ListNode* dfs(ListNode* head)
    {
        if(!head || !head->next) return head;
        ListNode* next = head->next;
        head->next = dfs(head->next->next);
        next->next = head;
        return next;
    }
};

5.快速幂Pow(x, n)

link:

典型算法，快速求出pow（x, n) ：不能return pow(x, n - 1) * x;太慢了

code

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