LeetCode冲刺：Day15

发布于 2022-11-22  85 次阅读

宿舍区又出问题了……

1. 第 N 个神奇数字

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

穷举不可行，因为数字太大了。

参考这篇

转换思路，神奇数字存在一个上限，即，两个数字中最小的那个乘以n。而对于一个给定的x，我们可以计算小于等于x的神奇数字有几个，依据公式，$\frac{x}{a}+\frac{x}{b}-\frac{x}{lcm(a,b)}$，其中每个分式都是向下取整。有了上下限和判断法则，于是可以利用二分搜索答案。

代码

class Solution {
private:
    const long MOD=1e9 + 7;
    int gcd(int a,int b) {
        if (a<b) {
            a^=b;
            b^=a;
            a^=b;
        }
        if (b==0) return a;
        else return gcd(b,a%b);
    }
    int lcm(int a,int b) {
        return (a*b)/gcd(a,b);
    }
public:
    int nthMagicalNumber(int n, int a, int b) {
        long lcmNum=lcm(a,b);
        long left=0,right=(long)min(a,b)*n;
        while (left+1<right) {
            long mid=left+(right-left)/2;
            if (mid/a+mid/b-mid/lcmNum>=n) {
                right =mid;
            } else left=mid;
        }
        return right%MOD;
    }
};

2. 完全二叉树的节点个数

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

O(n)做法遍历一遍即可。

更优化的做法。根据完全二叉树的性质，如果根节点左子树深度大于右子树，说明右子树是满二叉树，这时只用遍历计算左子树结点数，右子树结点数可以由其深度得出；如果左子树深度等于右子树深度，说明左子树是满二叉树，同理可计算。

代码

class Solution {
private:
    int ans=0;
    void dfs(TreeNode* root) {
        if (!root) return;
        ++ans;
        dfs(root->left);
        dfs(root->right);
    }
public:
    int countNodes(TreeNode* root) {
        ans=0;
        dfs(root);
        return ans;
    }
};

3. 二叉树的所有路径

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

要注意的点是，传参时使用值传递而不是引用传递，否则各个分支的追加结点会混在一起。

代码

class Solution {
private:
    void dfs(vector<string>& paths,string path,TreeNode* root) {
        path+="->"+to_string(root->val);
        if (!root->left&&!root->right) {
            paths.push_back(path);
            return;
        }
        if (root->left) dfs(paths,path,root->left);
        if (root->right) dfs(paths,path,root->right);
    }
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> paths;
        if (!root->left&&!root->right) {
            paths.push_back(to_string(root->val));
            return paths;
        }
        if (root->left) dfs(paths,to_string(root->val),root->left);
        if (root->right) dfs(paths,to_string(root->val),root->right);
        return paths;
    }
};

4. 左叶子之和

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

标记一下当前结点是左还是右即可。

代码

class Solution {
private:
    void dfs(int& ans,TreeNode* root,bool flag) {
        if (root->left==nullptr&&root->right==nullptr&&flag) {
            ans+=root->val;
            return;
        } else if (root->left==nullptr&&root->right==nullptr&&!flag) {
            return;
        }
        if (root->left!=nullptr) dfs(ans,root->left,true);
        if (root->right!=nullptr) dfs(ans,root->right,false);
    }
public:
    int sumOfLeftLeaves(TreeNode* root) {
        int ans=0;
        dfs(ans,root,false);
        return ans;
    }
};

5. 找树左下角的值

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

直接层序遍历，每轮完成时，队列首部元素即为该层最左侧元素，随深度增加不断更新即可。

代码

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        int ans=0;
        queue<TreeNode*> que;
        TreeNode* cur=root;
        que.push(cur);
        while(!que.empty()) {
            int size=que.size();
            ans=que.front()->val;
            for (int i=0;i<size;++i) {
                cur=que.front();
                que.pop();
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }
        }
        return ans;
    }
};

6. 从中序与后序遍历序列构造二叉树

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

关键问题在于分割中序数组和后序数组。对于前者，只要找到根节点值（后序末位），其左侧即为左子树，右侧为右子树。对于后者，可以依据已经分割的左右中序数组的大小进行分割。

我自己写的是用for来逐个添加，但后来发现我忘了可以直接构造函数初始化，用begin加上对应数值即可，效率更高。

代码

class Solution {
private:
    TreeNode* construct(vector<int>& inorder, vector<int>& postorder) {
        if (postorder.size()==0) return nullptr;
        TreeNode* root=new TreeNode(postorder[postorder.size()-1]);
        postorder.pop_back();
        if (postorder.size()==0) return root;
        int mid=0;
        for (int i=0;i<inorder.size();++i) {
            if (root->val==inorder[i]) {
                mid=i;
                break;
            }
        }
        vector<int> lInorder(inorder.begin(),inorder.begin()+mid);
        vector<int> rInorder(inorder.begin()+mid+1,inorder.end());

        vector<int> lPostorder(postorder.begin(),postorder.begin()+lInorder.size());
        vector<int> rPostorder(postorder.begin()+lInorder.size(),postorder.end());

        root->right=construct(rInorder,rPostorder);
        root->left=construct(lInorder,lPostorder);

        return root;
    }
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return construct(inorder,postorder);
    }
};

7. 最大二叉树

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

时间复杂度在n的平方。每次找到数组中最大值和对应下标即可，构造当前结点，然后利用下标分割数组，递归构造左右子树。

代码

class Solution {
private:
    TreeNode* construct(vector<int>& nums) {
        if (nums.size()==0) return nullptr;
        int pos=0,maxNum=nums[0];
        for (int i=0;i<nums.size();++i) {
            if (nums[i]>maxNum) {
                maxNum=nums[i];
                pos=i;
            }
        }
        TreeNode* root=new TreeNode(maxNum);
        vector<int> leftNums(nums.begin(),nums.begin()+pos);
        vector<int> rightNums(nums.begin()+pos+1,nums.end());
        root->left=construct(leftNums);
        root->right=construct(rightNums);
        return root;
    }
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return construct(nums);
    }
};

8. 合并二叉树

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

自己写的时候翻了个错，在一个结点为空，另一个不为空的时候，直接返回非空结点即可，不用继续调用递归。

代码

class Solution {
private:
    TreeNode* construct(TreeNode* root1,TreeNode* root2) {
        TreeNode* root;
        if (!root1&&!root2) root=nullptr;
        else if (!root1&&root2) {
            root=root2;
            root->left=construct(nullptr,root2->left);
            root->right=construct(nullptr,root2->right);
        }
        else if (root1&&!root2) {
            root=root1;
            root->left=construct(root1->left,nullptr);
            root->right=construct(root1->right,nullptr);
        }
        else {
            root1->val+=root2->val;
            root=root1;
            root->left=construct(root1->left,root2->left);
            root->right=construct(root1->right,root2->right);
        }
        return root;
    }
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        return construct(root1,root2);
    }
};

9. 二叉搜索树中的搜索

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

没说明是否平衡，保险起见放到数组中做二分。

代码

class Solution {
private:
    void inorder(TreeNode* root,vector<TreeNode*>& tree) {
        if (root==nullptr) return;
        inorder(root->left,tree);
        tree.push_back(root);
        inorder(root->right,tree);
    }
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        vector<TreeNode*> tree;
        inorder(root,tree);
        int left=0,right=tree.size()-1;
        while (left<=right)
        {
            int mid=left+(right-left)/2;
            if (tree[mid]->val==val) return tree[mid];
            else if (tree[mid]->val<val) left=mid+1;
            else right=mid-1;
        }
        return nullptr;
    }
};

10. 验证二叉搜索树

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

想先了下如何遍历树来判断，但找不到好办法。还是把树转换为数组来做。如果整个数组不是严格递增的，就返回false，遍历完成则返回true。

代码

class Solution {
private:
    void inorder(TreeNode* root,vector<int>& nums) {
        if (!root) return;
        inorder(root->left,nums);
        nums.push_back(root->val);
        inorder(root->right,nums);
    }
public:
    bool isValidBST(TreeNode* root) {
        vector<int> nums;
        inorder(root,nums);
        if (nums.size()==1) return true;
        for (int i=1;i<nums.size();++i) {
            if (nums[i]<=nums[i-1]) return false;
        }
        return true;
    }
};