刷爆leetcode Day11 DFS

1. 汉诺塔（easy)

https://leetcode.cn/problems/hanota-lcci/description/

class Solution {
public:void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {//A柱借助B柱移动到C柱//用递归解决问题，不要过多关注具体细节//首先拆分子问题//其次解决子问题//返回（回溯条件）_hanota(A,B,C,A.size());}void _hanota(vector<int>& A, vector<int>& B, vector<int>& C,int n){if(n==1)//只剩一个盒子这个盒子是最大的{C.push_back(A.back());A.pop_back();return;}//子问题，将n-1个盒子借助C挪到B_hanota(A,C,B,n-1);C.push_back(A.back());A.pop_back();//将n-1个盒子借助借助A挪到C_hanota(B,A,C,n-1);}
};

2. 合并两个有序链表（easy）

https://leetcode.cn/problems/merge-two-sorted-lists/submissions/576440296/

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

3. 反转链表（easy）

https://leetcode.cn/problems/merge-two-sorted-lists/submissions/576419884/

/*** 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)return nullptr;//链表可能为空if(head->next==nullptr)return head;ListNode*NewNode=reverseList(head->next);head->next->next=head;head->next=nullptr; return NewNode;}
};

4. 两两交换链表中的节点（medium）

https://leetcode.cn/problems/swap-nodes-in-pairs/submissions/576438012/

/*** 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*ret=head->next;head->next->next=head;head->next=tmp;return ret;}
};

5. Pow（x,n）-快速幂（medium）

https://leetcode.cn/problems/powx-n/submissions/576439853/

class Solution {
public:double _myPow(double x, int n){if(n==0)return 1.0;double tmp=_myPow(x,n/2);return n%2==0?tmp*tmp:x*tmp*tmp;}double myPow(double x, int n) {return n>=0?_myPow(x,n):1.0/_myPow(x,n);}
};