代码随想录算法训练营第36期DAY23

DAY23

530二叉搜索树的最小绝对差

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. private:
  14.     vector<int> tv;
  15.     void getv(TreeNode* root)
  16.     {
  17.         if(root==nullptrreturn ;
  18.         getv(root->left);
  19.         tv.push_back(root->val);
  20.         getv(root->right);
  21.     }
  22. public:
  23.     int getMinimumDifference(TreeNode* root) {
  24.     tv.clear();
  25.     getv(root);
  26.     if(tv.size()<2return 0;
  27.     int m=INT_MAX;
  28.     for(int i=0;i<tv.size()-1;i++)
  29.     {
  30.         m=min(m,abs(tv[i]-tv[i+1]));
  31.     }
  32.     return m;
  33.     }
  34. };

递归法,待二刷:

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. private:
  14.     int result=INT_MAX;
  15.     TreeNode* pre=nullptr;
  16.     void getres(TreeNode* cur)
  17.     {
  18.         if(cur==nullptrreturn ;
  19.         getres(cur->left);
  20.         //中:
  21.         if(pre!=nullptr)
  22.         {
  23.             result=min(result,abs(cur->val-pre->val));
  24.         }
  25.         pre=cur;
  26.         getres(cur->right);
  27.     }
  28. public:
  29.     int getMinimumDifference(TreeNode* root) {
  30.         getres(root);
  31.         return result;
  32.     }
  33. };

501二叉搜索树中的众数

MAP:

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. private:
  14.     void gemap(TreeNode*cur,unordered_map<int,int> &map)
  15.     {
  16.         if(cur==nullptr) return;
  17.         map[cur->val]++;
  18.         gemap(cur->left,map);
  19.         gemap(cur->right,map);
  20.         return ;
  21.     }
  22.     //重载运算符:注意有很多细节,不要漏了static
  23.     bool static mycmp(const pair<int,int>&a,const pair<int,int>&b)
  24.     {
  25.         return a.second>b.second;
  26.     }
  27. public:
  28.     vector<intfindMode(TreeNode* root) {
  29.         unordered_map<int,int>map;
  30.         vector<int>result;
  31.         if(root==nullptr) return result;
  32.         gemap(root,map);
  33.         vector<pair<int,int>> tmp(map.begin(),map.end());
  34.         sort(tmp.begin(),tmp.end(),mycmp);
  35.         result.push_back(tmp[0].first);
  36.         for(int i=1;i<tmp.size();i++)
  37.         {
  38.             if(tmp[i].second==tmp[0].second) result.push_back(tmp[i].first);
  39.             else break;
  40.         }
  41.         return result;
  42.     }
  43. };

递归带一点回溯:

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. private:
  14.     int count=0;
  15.     int maxcount=0;
  16.     TreeNode* pre=nullptr;
  17.     vector<int> result;
  18.     void countnum(TreeNode* cur){
  19.         if(cur==nullptrreturn;
  20.         countnum(cur->left);
  21.         if(pre==nullptr)
  22.         {
  23.             count=1;
  24.         }
  25.         else if(cur->val==pre->val)
  26.         {
  27.             count++;
  28.         }
  29.         else{
  30.             count=1
  31.         }
  32.         pre=cur;
  33.         if(count==maxcount)
  34.         {
  35.             result.push_back(cur->val);
  36.         }
  37.         else if(count>maxcount)
  38.         {
  39.             result.clear();
  40.             maxcount=count;
  41.             result.push_back(cur->val);
  42.         }
  43.         countnum(cur->right);
  44.         return ;
  45.     }
  46. public:
  47.     vector<intfindMode(TreeNode* root) {
  48.         //记得把private的变量重新赋值或者清空
  49.         vector.clear();
  50.         count=0;
  51.         maxcount=0;
  52.         pre=nullptr;
  53.         countnum(root);
  54.         return result;
  55.     }
  56. };

236二叉树的最近公共祖先

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8.  * };
  9.  */
  10. class Solution {
  11. public:
  12.     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
  13.         //自己就是答案或者空树
  14.         if(root==p||root==q||root==NULL)return root;
  15.         TreeNode* l=lowestCommonAncestor(root->left,p,q);
  16.         TreeNode* r=lowestCommonAncestor(roor->right,p,q);
  17.         if(l!=NULL&&r!=NULLreturn root;
  18.         else if(l==NULL&&r!=NULLreturn r;
  19.         else if(l!=NULL&&r==NULLreturn l;
  20.         else return NULL;
  21.     }
  22. };

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

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

相关文章

python面向函数

组织好的&#xff0c;可重复利用的&#xff0c;用来实现单一&#xff0c;或相关联功能的代码段&#xff0c;避免重复造轮子&#xff0c;增加程序复用性。 定义方法为def 函数名 (参数) 参数可动态传参&#xff0c;即使用*args代表元组形式**kwargs代表字典形式&#xff0c;代替…

tsconfig 备忘清单

前言 ❝ Nealyang/blog0 使用 ts 已多年&#xff0c;但是貌似对于 tsconfig 总是记忆不清&#xff0c;每次都是 cv 历史项目&#xff0c;所以写了这篇备忘录&#xff0c;希望能帮助到大家。 本文总结整理自 Matt Pocock 的一篇文章3&#xff0c;加以个人理解&#xff0c;并做了…

【爬虫基础1.1课】——requests模块

目录索引 requests模块的作用&#xff1a;实例引入&#xff1a; 特殊情况&#xff1a;锦囊1&#xff1a;锦囊2: 这一个栏目&#xff0c;我会给出我从零开始学习爬虫的全过程。感兴趣的小伙伴可以关注一波&#xff0c;用于复习和新学都是不错的选择。 那么废话不多说&#xff0c…

【Matlab-动画-附源码】3分钟教你用Matlab做一个Lorenz动画

lorenz-x-y-z Lorenz三个维度数据 在科研工作中&#xff0c;经常需要将数据可视化以便更好地理解和传达研究成果。 但大家主要放静态图片&#xff0c;而视频或动画通常比静态图片更具吸引力和表现力。AE, Manim太难学&#xff0c;Matlab就可以用来制作动画。 在这篇博客中&…

Linux-信号执行

1. 信号什么时候被处理 当进程从内核态返回到用户态的时候&#xff0c;进行信号的检测和处理 什么内核态&#xff0c;什么又是用户态呢&#xff1f; 当进程在CPU上运行时&#xff0c;内核态&#xff1a;允许进程访问操作系统的代码和数据&#xff0c;用户态&#xff1a;进程只…

视频降噪算法 hqdn3d 原理分析

视频降噪 视频降噪是一种处理技术&#xff0c;旨在减少视频中的噪声&#xff0c;提高画面质量。噪声可能来自多种源头&#xff0c;包括摄像机的传感器、压缩算法、传输过程中的干扰等。降噪处理对于视频监控、视频会议、电影后期制作以及任何需要高画质输出的应用场景都非常重…

【面经】网络

了解TCP/IP协议,了解常用的网络协议&#xff1a;study-area 一、TCP/IP协议 TCP/IP协议是一组网络通信协议&#xff0c;旨在实现不同计算机之间的信息传输。 1、TCP/IP四层模型&#xff1a; 网络接口层、网络层、传输层和应用层。 网络接口层&#xff1a;定义了数据的格式和…

揭秘抖音快速涨10000粉的方法:巨量千川投流让你轻松快速增粉

抖音已经成为了当今社交平台的热门之一&#xff0c;而如何快速涨粉已经成为了很多人关注的焦点。本文将揭秘一种高效的方式——巨量千川投流&#xff0c;通过官方真实流量和真实粉丝&#xff0c;每天快速涨关注&#xff0c;实现快速增粉1000~10万。 巨量千川投流是一种专业的抖…

Python-VBA函数之旅-pow函数

目录 一、pow函数的常见应用场景 二、pow函数使用注意事项 三、如何用好pow函数&#xff1f; 1、pow函数&#xff1a; 1-1、Python&#xff1a; 1-2、VBA&#xff1a; 2、推荐阅读&#xff1a; 个人主页&#xff1a;神奇夜光杯-CSDN博客 一、pow函数的常见应用场景 Py…

中小学校活动向媒体投稿报道宣传有哪些好方法

作为一所中小学校的教师,我肩负着向外界展示学校风采、宣传校园文化活动的重要使命。起初,每当学校举办特色活动或取得教学成果时,我都会满怀热情地撰写新闻稿,希望通过媒体的平台让更多人了解我们的故事。然而,理想丰满,现实骨感,我很快发现,通过电子邮件向媒体投稿的过程充满…

如何进行资产梳理

前言 为什么要进行资产梳理&#xff1f; 资产梳理方式一: 一、安全防护设备资产 二、对外开放服务项目资产 三、项目外包业务流程资产 资产梳理方式二: 一、业务资源梳理 二、设备资产梳理 三、第三方的服务信息梳理 风险梳理 风险有哪些&#xff1f; 一,账号权限风…

在此计算机上找不到autocad20*你需要安装autocad20*才可以安装此语言包,安装不成功的解决办法

因为AutoCAD2020未卸载干净导致&#xff0c;需要把AutoCAD2020的注册表清理干净&#xff0c;才可以安装 注册表打开&#xff0c;HKEY LOCAL MACHINE SOFTWARE Classesinstaller Products\7D2F3875100F0000102000060BECB6AB AHKEY LOCAL MACHINE SOFTWARE Classesinstaller Pro…

2024.5.9

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this);this->resize(1000,600);this->setFixedSize(1000,600);//设置按钮大小位置完成btn1 new QPushButton(&…

安卓开发--按键跳转页面,按键按下变色

前面已经介绍了一个空白按键工程的建立以及响应方式&#xff0c;可以参考这里&#xff1a;安卓开发–新建工程&#xff0c;新建虚拟手机&#xff0c;按键事件响应。 安卓开发是页面跳转是基础&#xff01;&#xff01;&#xff01;所以本篇博客介绍利用按键实现页面跳转&#…

随手笔记-GNN(朴素图神经网络)

自己看代码随手写的一点备忘录&#xff0c;自己看的&#xff0c;不喜勿喷 GNN (《------ 代码) 刚开始我还在怀疑为什么没有加weigth bias&#xff0c;已经为什么权重才两个&#xff0c;原来是对node_feats进行的network的传播&#xff0c;而且自己内部直接进行了。 下面是一…

Linux|进程地址空间

Linux|内存地址空间 现象基本概念理解如何理解地址空间什么是划分区域&#xff1f;地址空间的理解为什么要有地址空间&#xff1f;如何进一步理解页表和写时拷贝如何理解虚拟地址 Linux真正的进程调度方案 现象 #include <stdio.h> #include <string.h> #include …

兔子繁衍问题<C语言>

问题&#xff1a;一对兔子&#xff0c;从出生后第3个月起每个月都生一对兔子。小兔子长到第3个月后每个月又生一对兔子。假如兔子都不死&#xff0c;请问第1个月出生的一对兔子&#xff0c;至少需要繁衍到第几个月时兔子总数才可以达到N对&#xff1f; 分析&#xff1a; 可以观…

HTML5 Canvas发光Loading动画源码

源码介绍 之前我们分享过很多基于CSS3的Loading动画效果&#xff0c;相信大家都很喜欢。今天我们要来分享一款基于HTML5 Canvas的发光Loading加载动画特效。Loading旋转图标是在canvas画布上绘制的&#xff0c;整个loading动画是发光3D的视觉效果&#xff0c;HTML5非常强大。 …

Docker入门指南:Docker镜像的使用(二)

&#x1f340; 前言 博客地址&#xff1a; CSDN&#xff1a;https://blog.csdn.net/powerbiubiu &#x1f44b; 简介 在本章节中&#xff0c;将深入探讨 Docker 镜像的概念&#xff0c;以及如何使用镜像的一系列操作。 &#x1f4d6; 正文 1 什么是镜像 1.1 Docker镜像的简…

C++对象引用作为函数参数

使用对象引用作为函数参数最常见&#xff0c;它不但有指针作为参数的优点&#xff0c;而且比指针作为参数更简单、更方便。 引用方式进行参数传递&#xff0c;形参对象就是实参对象的“别名”&#xff0c;对形参的操作其实就是对实参的操作。 例如:用对象引用进行参数传…
最新文章