5/9刷题_牛客博客

1.实现 int sqrt(int x) 函数。
思路一：袖珍计算器算法
图片说明
计算完结果后，因为浮点数可能存在误差，因此我们要计算ans和ans+1哪个是更符合要求的。

class Solution {
public:
    int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        int ans = exp(0.5 * log(x));
        return ((long long)(ans + 1) * (ans + 1) <= x ? ans + 1 : ans);
    }
};

思路二：二分查找

class Solution {
public:
    int mySqrt(int x) {
        if(x==0) return 0;
        int left=0;
        int right=x;
        int res=-1;
        while(left<=right)
        {
            int mid=(right+left)/2;
            if((long long)mid*mid<=x)
            {
                res=mid;
                left=mid+1;//因为要寻找最大的平方小于x的数，因此出现小于x的，就把左指针移到mid之后
            }
            else
            {
                right=mid-1;//如mid的平方大于x，就将右指针移到mid之前
            }
        }
        return res;
    }
};

思路三：牛顿法

class Solution {
public:
    int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        double C = x, x0 = x;
        while (true) {
            double xi = 0.5 * (x0 + C / x0);
            if (fabs(x0 - xi) < 1e-7) {
                break;
            }
            x0 = xi;
        }
        return int(x0);
    }
};

2.二叉树中和为某一个值的路径
输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
思路：利用递归，首先放入根节点，如果根节点的值等于期望值且没有左右子树，就形成一条路径，如不形成，就分别递归遍历左右子树，注意当递归完成时，若没找到符合条件的路径，要把数组尾部元素弹出，表示搜索往回退一步。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {   
public:
    vector<vector<int>> result;
    vector<int> buf;
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        if(root==nullptr) return result;
        buf.push_back(root->val);
        if(expectNumber==root->val&&root->left==nullptr&&root->right==nullptr)//因为路径要到叶子节点
        {
            result.push_back(buf);//路径的和符合期望值，就放入一条路径
        }
        FindPath(root->left,expectNumber-root->val);//递归左子树
        FindPath(root->right,expectNumber-root->val);//递归右子树
        buf.pop_back();
        return result;
    }

3.复杂链表的复制
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead)
    {
         /*
        *解题思路：
        *1、遍历链表，复制每个结点，如复制结点A得到A1，将结点A1插到结点A后面；
        *2、重新遍历链表，复制老结点的随机指针给新结点，如A1.random = A.random.next;
        *3、拆分链表，将链表拆分为原链表和复制后的链表
         */
        //复制
        if(!pHead) return nullptr;
        RandomListNode *cur=pHead;
        while(cur!=NULL)
        {
            RandomListNode *p=new RandomListNode(cur->label);
            p->next=cur->next;
            cur->next=p;
            cur=p->next;
        }
        //重新遍历
        cur=pHead; 
        RandomListNode *p;
        while(cur!=NULL)
        {
            p=cur->next;
            if(cur->random!=NULL)
           {
            p->random=cur->random->next;
           }  
           cur=p->next;
        }
        //拆分
        RandomListNode *clone=pHead->next;
        RandomListNode *tmp;
        cur=pHead;
        while(cur->next!=NULL)
        {
            tmp=cur->next;
            cur->next=tmp->next;
            cur=tmp;            
        }
        return clone;   
    }
};

4.二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        TreeNode *Last=nullptr;//双向链表的尾结点
        helper(pRootOfTree,&Last);
        TreeNode *Head=Last;
        while(Head!=nullptr&&Head->left!=nullptr)
        {
            Head=Head->left;//返回头结点
        }
        return Head;
    }
    void helper(TreeNode* pNode,TreeNode** Last)//中序遍历
    {
        if(pNode==nullptr) return;
        TreeNode *cur=pNode;
        if(cur->left!=nullptr)
            helper(cur->left,Last);//遍历左子树
        cur->left=*Last;//根节点左指针指向左子树最大的数或空
        if(*Last!=nullptr)
            (*Last)->right=cur;//如果不为空，此节点的右指针指向根节点
        *Last=cur;
       if(cur->right)
            helper(cur->right,Last);//遍历右子树
    }
};