Leetcode秋招冲刺（专题13--15）

发布于：2024-07-05 ⋅ 阅读:(16) ⋅ 点赞:(0)

专题13：广度优先搜索

题目559：N叉树的最大深度（YES）

  • 解题思路：使用广度优先搜索，广度优先搜索的核心就是使用队列queue存储每个根节点，然后再存储孩子节点。

给定一个 N 叉树，找到其最大深度。

最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    int maxDepth(Node* root) {
        if(root==NULL)
        {
            return 0;
        }
        //使用广度优先搜索，核心的点就是使用队列
        queue<Node*>que;
        que.push(root);
        int high=0;

        //不为空，就继续
        while(!que.empty())
        {
            int size =que.size();
            for(int i=0;i<size;i++)
            {
                Node*front=que.front();
                que.pop();//出队

                //添加孩子节点
                int children_size=front->children.size();
                for(int j=0;j<children_size;j++)
                {
                    que.push(front->children[j]);
                }
            }
            high++;
        }
        return high;
        
    }
};

题目617：合并二叉树（NO）

  • 解题思路：这题得用深度优先搜索，广度优先所搜过于繁琐。

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == nullptr) {
            return t2;
        }
        if (t2 == nullptr) {
            return t1;
        }
        auto merged = new TreeNode(t1->val + t2->val);
        merged->left = mergeTrees(t1->left, t2->left);
        merged->right = mergeTrees(t1->right, t2->right);
        return merged;
    }
};

题目965：单值二叉树（YES）

  • 解题思路：使用二叉树的遍历算法进行判断就行，我这里用的是前序遍历，其实使用广度优先搜索也一样。

如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。

只有给定的树是单值二叉树时，才返回 true；否则返回 false。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void preorder(TreeNode*root,int ans,bool &sign)
    {
        if(root==NULL)
        {
            return ;
        }
        if(root->val!=ans)
        {
            sign=false;
        }
        preorder(root->left,ans,sign);
        preorder(root->right,ans,sign);
    }
    bool isUnivalTree(TreeNode* root) {
        //使用二叉树的遍历算法即可，这里用二叉树的前序遍历
        int ans=root->val;
        bool sign=true;
        preorder(root,ans,sign);

        return sign;
    }
};

题目637：二叉树的层平均值（YES）

  • 解题思路：使用层序遍历也就是广度优先搜索即可

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        //使用层序遍历，也就是广度优先搜索就行
        queue<TreeNode*>que;
        que.push(root);
        vector<double>ans;
        while(!que.empty())
        {
            int size=que.size();
            double sum=0;
            for(int i=0;i<size;i++)
            {
                TreeNode*front=que.front();
                que.pop();
                sum+=front->val;

                //将孩子节点入队
                if(front->left!=NULL)
                {
                    que.push(front->left);
                }

                if(front->right!=NULL)
                {
                    que.push(front->right);
                }
            }
            ans.push_back(sum/size);
        }

        return ans;
    }
};

题目175:计算二叉树的深度（YES）

  • 解题思路：使用层序遍历

某公司架构以二叉树形式记录，请返回该公司的层级数。

  • myself
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int calculateDepth(TreeNode* root) {
        //使用层序遍历
        if(root==NULL)
        {
            return 0;
        }

        queue<TreeNode*>que;
        que.push(root);
        int ans=0;
        while(!que.empty())
        {
            int size=que.size();
            ans++;
            for(int i=0;i<size;i++)
            {
                TreeNode*front=que.front();
                que.pop();

                //将孩子节点入队
                if(front->left!=NULL)
                {
                    que.push(front->left);
                }
                if(front->right!=NULL)
                {
                    que.push(front->right);
                }
            }
        }

        return ans;
    }
};

题目1379：找出克隆二叉树中的相同节点（YES）

  • 解题思路：这里我使用的是二叉树的遍历算法，使用前序遍历，当找到original时候，也就找到了cloned的目标节点。这题我刚开始犯了一个很经典的错误。

给你两棵二叉树，原始树 original 和克隆树 cloned，以及一个位于原始树 original 中的目标节点 target。

其中，克隆树 cloned 是原始树 original 的一个 副本 。

请找出在树 cloned 中，与 target 相同 的节点，并返回对该节点的引用（在 C/C++ 等有指针的语言中返回 节点指针，其他语言返回节点本身）。

注意：你 不能 对两棵二叉树，以及 target 节点进行更改。只能 返回对克隆树 cloned 中已有的节点的引用。

  • 刚开始的错误代码：
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    
    void preorder(TreeNode*original,TreeNode*cloned,TreeNode*target,TreeNode*ans)
    {
        //前序遍历
        if(original==NULL&&cloned==NULL) return ;
        if(original==target) ans=cloned;

        preorder(original->left,cloned->left,target,ans);
        preorder(original->right,cloned->right,target,ans);
        
    }

    TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
        //使用二叉树的遍历算法，使用前序遍历
        TreeNode*ans=NULL;
        preorder(original,cloned,target,ans);

        return ans;

    }
};
  • 正确代码
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    TreeNode*ans=NULL;
    void preorder(TreeNode*original,TreeNode*cloned,TreeNode*target)
    {
        //前序遍历
        if(original==NULL&&cloned==NULL) return ;
        if(original==target) ans=cloned;

        preorder(original->left,cloned->left,target);
        preorder(original->right,cloned->right,target);
        
    }

    TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
        //使用二叉树的遍历算法，使用前序遍历
        
        preorder(original,cloned,target);

        return ans;

    }
};

  • 对比一下两个代码就可以看出，第一次我使用ans 是作为局部变量来使用的，而函数的返回值是TreeNode*和返回引用是一样的，这种情况不能用局部变量返回，因为局部变量在作用域结束后就被系统释放了，此时返回的引用本身就是ans本体，而局部的ans被释放了，返回的也就同样失效了。

  • 所以第二次我就将ans作为成员函数，他的生命周期就不会那么局限了。

专题14：回溯算法

题目3033：修改矩阵（YES）

  • 解题思路：for循环遍历每个列然后记录比较就行

给你一个下标从 0 开始、大小为 m x n 的整数矩阵 matrix ，新建一个下标从 0 开始、名为 answer 的矩阵。使 answer 与 matrix 相等，接着将其中每个值为 -1 的元素替换为所在列的 最大 元素。

返回矩阵 answer 。

class Solution {
public:
    vector<vector<int>> modifiedMatrix(vector<vector<int>>& matrix) {
        //这题就遍历每一个列，然后记录最大值，当找到-1时，就将最大数赋值给-1
        //遍历每一列
        
        for(int i=0;i<matrix[0].size();i++)
        {
            int max_count=-2;
            vector<int>row;//记录是-1的行坐标
            vector<int>col;//记录是-1的列坐标
            for(int j=0;j<matrix.size();j++)
            {
                if(max_count<matrix[j][i])
                {
                    max_count=matrix[j][i];
                }

                if(matrix[j][i]==-1)
                {
                    //记录坐标
                    row.push_back(j);
                    col.push_back(i);
                }
            }
            
            //一列遍历结束，对-1进行处理
            for(int k=0;k<row.size();k++)
            {
                matrix[row[k]][col[k]]=max_count;
            }
        }

        return matrix;
    }
};

题目401：二进制手表（NO）

  • 解题思路：使用两层for遍历所有的时间，看1的个数是否符合，这里主要用到了__builtin_popcount（）统计一个整数中二进制1的个数。

二进制手表顶部有 4 个 LED 代表 小时（0-11），底部的 6 个 LED 代表 分钟（0-59）。每个 LED 代表一个 0 或 1，最低位在右侧。

例如，下面的二进制手表读取 “4:51” 。

给你一个整数 turnedOn ，表示当前亮着的 LED 的数量，返回二进制手表可以表示的所有可能时间。你可以 按任意顺序 返回答案。

小时不会以零开头：

例如，“01:00” 是无效的时间，正确的写法应该是 “1:00” 。
分钟必须由两位数组成，可能会以零开头：

例如，“10:2” 是无效的时间，正确的写法应该是 “10:02” 。

  • 官方题解
class Solution {
public:
    vector<string> readBinaryWatch(int turnedOn) {
        vector<string> ans;
        for (int h = 0; h < 12; ++h) {
            for (int m = 0; m < 60; ++m) {
                if (__builtin_popcount(h) + __builtin_popcount(m) == turnedOn) {
                    ans.push_back(to_string(h) + ":" + (m < 10 ? "0" : "") + to_string(m));
                }
            }
        }
        return ans;
    }
};
  • __builtin_popcount并不是所有的编译器都这么写，vs2022用的就是__popcnt，这个是内置函数，不同的编译器可能会有差异。

题目257：二叉树的所有路径（NO）

  • 解题思路：广度优先搜索

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

  • 官方题解
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> paths;
        if (root == nullptr) {
            return paths;
        }
        queue<TreeNode*> node_queue;
        queue<string> path_queue;

        node_queue.push(root);
        path_queue.push(to_string(root->val));

        while (!node_queue.empty()) {
            TreeNode* node = node_queue.front(); 
            string path = path_queue.front();
            node_queue.pop();
            path_queue.pop();

            if (node->left == nullptr && node->right == nullptr) {
                paths.push_back(path);
            } else {
                if (node->left != nullptr) {
                    node_queue.push(node->left);
                    path_queue.push(path + "->" + to_string(node->left->val));
                }

                if (node->right != nullptr) {
                    node_queue.push(node->right);
                    path_queue.push(path + "->" + to_string(node->right->val));
                }
            }
        }
        return paths;
    }
};

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布