Leetcode秋招冲刺(专题13--15)

专题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;
    }
};

专题15:递归

题目231:2的幂(YES)

  • 解题思路:每次除以2看余数是否为零,不为零则返回false

给你一个整数 n,请你判断该整数是否是 2 的幂次方。如果是,返回 true ;否则,返回 false 。

如果存在一个整数 x 使得 n == 2x ,则认为 n 是 2 的幂次方。

class Solution {
public:
   bool isPowerOfTwo(int n) {
        if(n <= 0) {
            return false;
        }
        
        while(n > 1) {
            if(n % 2 != 0) {
                return false;
            }
            n /= 2;
        }
        
        return true;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/775005.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

BSI 第七届万物互联智慧高峰论坛:主题:拥抱AI时代,标准赋能组织实现可持续发展

BSI 第七届万物互联智慧高峰论坛&#xff1a;主题&#xff1a;拥抱AI时代&#xff0c;标准赋能组织实现可持续发展 主要收到 BSI 温女士的邀请参加的本次论坛。还是学到的很多 。 在科技日新月异的时代背景下&#xff0c;BSI 第七届万物互联智慧高峰论坛于[时间&#xff1a;6…

mac安装docker

1、首先打开docker官网 https://docs.docker.com/engine/install/ 2、下载好后安装到app应用 3、安装好环境变量 #docker echo export PATH"/usr/local/Cellar/docker/20.10.11/bin:$PATH" >> .bash_profile

百度云智能媒体内容分析一体机(MCA)建设

导读 &#xff1a;本文主要介绍了百度智能云MCA产品的概念和应用。 媒体信息海量且复杂&#xff0c;采用人工的方式对视频进行分析处理&#xff0c;面临着效率低、成本高的困难。于是&#xff0c;MCA应运而生。它基于百度自研的视觉AI、ASR、NLP技术&#xff0c;为用户提供音视…

不错的用户需求访谈方法

不错的用户需求访谈方法&#xff0c;可以用如下的矩阵&#xff0c;用来引导用户访谈&#xff1a;

vue实现搜索文章关键字,滑到指定位置并且高亮

1、输入搜索条件&#xff0c;点击搜索按钮 2、滑到定位到指定的搜索条件。 <template><div><div class"search_form"><el-inputv-model"searchVal"placeholder"请输入关键字查询"clearablesize"small"style&quo…

Go源码--channel源码解读

简介 channel顾名思义就是channel的意思&#xff0c;主要用来在协程之间传递数据&#xff0c;所以是并发安全的。其实现原理&#xff0c;其实就是一个共享内存再加上锁&#xff0c;底层阻塞机制使用的是GMP模型。可见 GMP模型就是那个道&#xff0c;道生一,一生二,二生三,三生…

2024.8月28号杭州电商博览会,在杭州国博举办

2024杭州电商新渠道博览会暨集脉电商节 时间&#xff1a;2024年08月28-30日 地点&#xff1a;杭州国际博览中心&#xff08;G20&#xff09; 主办单位&#xff1a;浙江集脉展览有限公司、杭州华维展览有限公司 承办单位&#xff1a;浙江集脉展览有限公司 报名参展&#xf…

Navicat和MySQL的安装

1、下载 Navicat Navicat 官网&#xff1a;www.navicat.com.cn/ 在产品中可以看到很多的产品&#xff0c;点击免费试用 Navicat Premium 即可&#xff0c;是一套多连数据库开发工具&#xff0c;其他的只能连接单一类型数据库 点击试用 选择系统直接下载 二、安装 Navicat 安…

03:EDA的进阶使用

使用EDA设计一个38译码器电路和245放大电路 1、38译码器1.1、查看74HC138芯片数据1.2、电路设计 2、245放大电路2.1、查看数据手册2.2、设计电路 3、绘制PCB3.1、导入3.2、放置3.3、飞线3.4、特殊方式连接GND3.5、泪滴3.6、配置丝印和划分区域3.7、添加typc接口供电 1、38译码器…

‘艾’公益——微笑行动「广安站」为艾祝福,让笑起舞

艾多美“微笑行动”广安站拉开帷幕 此次爱心帮助7名唇腭裂患儿 重新绽放微笑 艾多美“微笑行动”广安站拉开帷幕 此次爱心帮助7名唇腭裂患儿 重新绽放微笑 不让笑容留有缺憾 每个孩子都有微笑的权利 艾多美向唇腭裂儿童伸出援手 绽放笑容&#xff0c;拥抱全新的未来 2…

通信安全员考试精选练习题库,2024年备考必刷题!

16.设计单位必须在设计文件中&#xff08;&#xff09;计列安全生产费。 A.全额 B.部分 C.按建设单位要求 D.按工程建设需要 答案&#xff1a;A 17.日最高气温达到&#xff08;&#xff09;℃以上&#xff0c;应当停止当日室外露天作业。 A.38 B.36 C.35 D.40 答案&…

2024年智慧教育与社会科学国际会议 (ICSSS 2024)

2024年智慧教育与社会科学国际会议 (ICSSS 2024) 2024 International Conference on Smart Education and Social Sciences 【重要信息】 大会地点&#xff1a;北京 大会官网&#xff1a;http://www.icicsss.com 投稿邮箱&#xff1a;icicssssub-conf.com 【注意&#xff1a;稿…

达梦数据库的系统视图v$auditrecords

达梦数据库的系统视图v$auditrecords 在达梦数据库&#xff08;DM Database&#xff09;中&#xff0c;V$AUDITRECORDS 是专门用来存储和查询数据库审计记录的重要系统视图。这个视图提供了对所有审计事件的访问权限&#xff0c;包括操作类型、操作用户、时间戳、目标对象等信…

2024年07月03日 Redis部署方式和持久化

Redis持久化方式&#xff1a;RDB和AOF&#xff0c;和混合式 RDB&#xff1a;周期备份模式&#xff0c;每隔一段时间备份一份快照文件&#xff0c;从主线程Fork一个备份线程出来备份&#xff0c;缺点是会造成数据的丢失。 AOF&#xff1a;日志模式&#xff0c;每条命令都以操作…

【docker nvidia/cuda】ubuntu20.04安装docker踩坑记录

docker nvidia 1.遇到这个错误&#xff0c;直接上魔法(科学上网) OpenSSL SSL_connect: Could not connect to nvidia.github.io:443 这个error是运行 NVIDIA官方docker安装教程 第一个 curl 命令是遇到的 2. apt-get 更新 sudo apt update遇到 error https://download.do…

kylin arm xcb版本异常问题解决

源码编译qt 未生成xcb库&#xff0c;查看源码xcb readme.txt 提示 版本要求 下载 [ANNOUNCE] libxcb 1.14 [ANNOUNCE] xcb-proto 1.14 解压源码编译, 先编译xcb-proto sudo ./configure --prefix/usr/local/xcb-proto make make install 在编译xcb export PKG_CONFIG_PATH…

解决uni-app中全局设置页面背景颜色只有部分显示颜色的问题

在页面的style标签设置了背景色但是只显示一部分 <style lang="scss"> .content{background-color: #f7f7f7;height: 100vh; } </style>我们在app.vue里设置就行了 注意一定要是**page{}** <style>/*每个页面公共css */page{background-color:

劲爆!华为享界两款新车曝光,等等党有福了

文 | AUTO芯球 作者 | 雷慢 劲爆啊&#xff0c;北汽的一份环境影响分析报告&#xff0c; 不仅曝光了享界S9的生产进展&#xff0c; 还泄露了自家的另两款产品&#xff0c; 第一款是和享界S9同尺寸的旅行车&#xff0c; 我一看&#xff0c;这不是我最喜欢的“瓦罐”吗&…

【吊打面试官系列-MyBatis面试题】Xml 映射文件中,除了常见的 select|insert|updae|delete标签之外,还有哪些标签?

大家好&#xff0c;我是锋哥。今天分享关于 【Xml 映射文件中&#xff0c;除了常见的 select|insert|updae|delete标签之外&#xff0c;还有哪些标签&#xff1f;】面试题&#xff0c;希望对大家有帮助&#xff1b; Xml 映射文件中&#xff0c;除了常见的 select|insert|updae|…

江汉大学刘春萌同学整理的wifi模块 上传mqtt实验步骤

一.固件烧录 1.打开安信可官网 2.点击wifi模组系列的ESP8266 3.点击各类固件后选择固件号1471下载 4.打开烧录工具将下载的二进制文件导入并将后面的起始地址写为0x00000,下面勾选40mhz QIO 8Mbit点击start下载即可 二.本地部署mqtt服务器(windows) 1.下载mosquitto后有一个m…