当前位置:   article > 正文

DFS:从递归去理解深度优先搜索

DFS:从递归去理解深度优先搜索

一、深入理解递归

二、递归vs迭代 

 三、深入理解搜索、回溯和剪枝

 四、汉诺塔问题

. - 力扣(LeetCode)

  1. class Solution {
  2. public:
  3. //笔试题,不讲武德,C=A
  4. void move(int n,vector<int>& A, vector<int>& B, vector<int>& C)//实现从a经过b这个辅助盘子移到c
  5. {
  6. //设置函数出口
  7. if(n==1) //此时不能再分割子问题了 直接给C即可
  8. {
  9. C.push_back(A.back());
  10. A.pop_back();
  11. return;
  12. }
  13. //先把a的前n-1个通过c移到b
  14. move(n-1,A,C,B);
  15. //然后将A的最后一个盘子移到C上
  16. C.push_back(A.back());
  17. A.pop_back();
  18. //然后将b上的n-1个盘子通过A移到c
  19. move(n-1,B,A,C);
  20. }
  21. void hanota(vector<int>& A, vector<int>& B, vector<int>& C)
  22. {
  23. int n=A.size();
  24. return move(n,A,B,C);
  25. }
  26. };

五、合并两个有序链表

. - 力扣(LeetCode)

  1. class Solution {
  2. public:
  3. ListNode* mergeTwoLists(ListNode* list1, ListNode* list2)
  4. {
  5. if(list1==nullptr) return list2;
  6. else if(list2==nullptr) return list1;
  7. else if(list1->val<list2->val) {list1->next=mergeTwoLists(list1->next,list2);return list1;}
  8. else {list2->next=mergeTwoLists(list2->next,list1);return list2;}
  9. }
  10. };

六、反转链表

. - 力扣(LeetCode)

  1. class Solution {
  2. public:
  3. ListNode* reverseList(ListNode* head)
  4. {
  5. if(head==nullptr||head->next==nullptr) return head;;
  6. ListNode*ret=reverseList(head->next);
  7. head->next->next=head;
  8. head->next=nullptr;
  9. return ret;
  10. }
  11. };

七、两两交换链表

. - 力扣(LeetCode)

  1. class Solution {
  2. public:
  3. ListNode* swapPairs(ListNode* head)
  4. {
  5. if(head==nullptr||head->next==nullptr) return head;
  6. ListNode*temp=swapPairs(head->next->next);
  7. ListNode*ret=head->next;
  8. ret->next=head;
  9. head->next=temp;
  10. return ret;
  11. }
  12. };

八、快速幂

. - 力扣(LeetCode)

 1、迭代

  1. class Solution {
  2. public:
  3. double myPow(double x, long long n) //修改参数,将传进来的值都转化成;long long 类型,避免溢出
  4. {
  5. if(n==0) return 1;
  6. if(n<0) return myPow(1/x,-n) ;
  7. double ans=1.0;
  8. while(n)
  9. {
  10. if(n&1) ans*=x;//说明最低位为1,要乘以x
  11. x*=x;
  12. n>>=1;
  13. }
  14. return ans;
  15. }
  16. };

2、递归

  1. class Solution {
  2. public:
  3. double myPow(double x, long long n) //修改参数,将传进来的值都转化成;long long 类型,避免溢出
  4. {
  5. if(n==0) return 1;
  6. if(n<0) return 1/myPow(x,-n);
  7. double temp=myPow(x,n/2);//快速计算前一半的结果
  8. return n%2==0?temp*temp:temp*temp*x;
  9. }
  10. };

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/388205
推荐阅读
相关标签
  

闽ICP备14008679号