【刷题篇】回溯算法(一)

文章目录

1、汉诺塔
2、合并两个有序链表
3、反转链表
4、两两交换链表中的节点
5、Pow(x, n)
6、计算布尔二叉树的值

1、汉诺塔

在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。
请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。
你需要原地修改栈。

在这里插入图片描述

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.push_back(a.back());
    //     a.pop_back();
    //     dfs(b,a,c,n-1);
    // }
    void hanota(vector<int>& a, vector<int>& b, vector<int>& c) {
        //dfs(a,b,c,a.size());
        c=a;
    }
};

2、合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

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

3、反转链表

class Solution {
public://使用头插//三个指针也可以
    ListNode* reverseList(ListNode* head) {
        // if(head==nullptr)
        //     return nullptr;
        // ListNode* cur=head;
        // ListNode* newhead=new ListNode(0);
        // ListNode* pre=newhead;
        // while(cur)
        // {
        //     ListNode* next=cur->next;
        //     cur->next=pre->next;
        //     pre->next=cur;
        //     cur=next;
        // }
        // cur=newhead->next;
        // delete newhead;
        // return cur;
        if(head==nullptr||head->next==nullptr)
            return head;
        ListNode* newnode=reverseList(head->next);
        head->next->next=head;
        head->next=nullptr;
        return newnode;
    }
};

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

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

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

5、Pow(x, n)

实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。

class Solution {
public://2^9  2^4*2^4*2  2^2*2^2   2*2
    double myPow(double x, int n) {
        return n<0?1.0/pow(x,-n):pow(x,n);//因为n是小于零的话，传的值就需要变号
    }
    double pow(double x,int n)
    {
        if(n==0)
            return 1;
        double tmp=pow(x,n/2);
        if(n%2==0)
            return tmp*tmp;
        else
            return tmp*tmp*x;
    }
};

6、计算布尔二叉树的值

给你一棵完整二叉树的根，这棵树有以下特征：
叶子节点要么值为 0 要么值为 1 ，其中 0 表示 False ，1 表示 True 。
非叶子节点要么值为 2 要么值为 3 ，其中 2 表示逻辑或 OR ，3 表示逻辑与 AND 。
计算一个节点的值方式如下：
如果节点是个叶子节点，那么节点的值为它本身，即 True 或者 False 。
否则，计算两个孩子的节点值，然后将该节点的运算符对两个孩子值进行运算。
返回根节点 root 的布尔运算值。
完整二叉树是每个节点有 0 个或者 2 个孩子的二叉树。
叶子节点是没有孩子的节点。

class Solution {
public:
    bool evaluateTree(TreeNode* root)
    {
        if(root->left==nullptr&&root->val==0)
            return false;
        if(root->left==nullptr&&root->val==1)
            return true;
        bool left=evaluateTree(root->left);
        bool right=evaluateTree(root->right);
        return root->val==2?left|right:left&right;//还要考虑其他的情况除了2，3所以不能写死就判断2，3
    }
};