当前位置: 首页 > news >正文

代码随想录算法训练营第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.lryc.cn/news/344490.html

相关文章:

  • Leetcode 3128. Right Triangles
  • 力扣经典150题第五十三题:基本计算器
  • 如何为 Nestjs 编写单元测试和 E2E 测试
  • 基于Python的LSTM网络实现单特征预测回归任务(TensorFlow)
  • Spring - 8 ( 10000 字 Spring 入门级教程 )
  • 鸿蒙内核源码分析(忍者ninja篇) | 都忍者了能不快吗
  • Linux——守护进程化(独立于用户会话的进程)
  • 安卓开发--按键跳转页面,按键按下变色
  • Ps基础学习笔记
  • spring开发问题总结(持续更新)
  • Android 状态栏WiFi图标的显示逻辑
  • 更改 DeepXDE 的后端
  • SpringBoot之Zuul服务
  • Go-变量
  • 【CTF-Crypto】RSA-选择明密文攻击 一文通
  • Pytorch基础:torch.expand() 和 torch.repeat()
  • 如何正确安装Scrapy 2.6.1并解决常见的Python环境问题
  • 阵痛中的乳业产业,何时才能成为下一个啤酒产业?
  • 关于模型参数融合的思考
  • Windows MySQL本地服务器设置并导入数据库和数据
  • 豪投巨资,澳大利亚在追逐海市蜃楼吗?
  • 面试集中营—Redis架构篇
  • 05_kafka-整合springboot
  • 论UML在学情精准测评系统中的应用
  • Day23 代码随想录打卡|字符串篇---重复的子字符串
  • 【win10 文件夹数量和看到不一致查看隐藏文件已经打开,Thumb文件作妖】
  • ctfshow web入门 sql注入 web224--web233
  • 「Java开发指南」如何用MyEclipse搭建GWT 2.1和Spring?(一)
  • python同时进行字符串的多种替换
  • 【Java基础题型】用筛法求之N内的素数(老题型)