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

【20230225】【剑指1】分治算法(中等)

1.重建二叉树

class Solution {
public:TreeNode* traversal(vector<int>& preorder,vector<int>& inorder){if(preorder.size()==0)  return NULL;int rootValue=preorder.front();TreeNode* root=new TreeNode(rootValue);//int rootValue=preorder[0];if(preorder.size()==1)  return root;int index;for(index=0;index<inorder.size();index++){if(inorder[index]==rootValue)break;}//中序的左右数组vector<int> inorderleft(inorder.begin(),inorder.begin()+index);vector<int> inorderright(inorder.begin()+index+1,inorder.end());//前序的左右数组vector<int> preorderleft(preorder.begin()+1,preorder.begin()+1+inorderleft.size());vector<int> preorderright(preorder.begin()+1+inorderleft.size(),preorder.end());root->left=traversal(preorderleft,inorderleft);root->right=traversal(preorderright,inorderright);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {if(preorder.size()==0||inorder.size()==0)   return NULL;return traversal(preorder,inorder);}
};

2.数值的整数次方

首先解决超级次方这个题目,这个题目有三个问题需要解决:

  • b是一个数组,应该如何处理?

  • 如何处理求模的结果?

  • 如何高效的进行幂运算?

<1> 如下图所示,每次都可以将数组中的最后一个元素提出来,于是这里面隐藏了一个递归的过程;

<2>每次遇到乘法时,都得防止发生溢出,利用如下公式,对每次a与乘出的结果都做一次取模运算;

(a * b) % k = (a % k) * (b % k) % k

<3>如下图所示,在幂运算过程中仍然可以递归,这样可以实现O(logn)的时间复杂度;

#define base 1337
class Solution {
public://1.幂运算常规做法//每次做乘法时都得防止溢出//(a*b)%k=(a%k)*(b%k)%k/*int myPow(int a,int b){a%=base;int res=1;for(int i=b;i>0;i++){res*=a;res%=base;}return res;}*///2.高效幂运算int myPow(int a,int b){if(b==0)    return 1;a%=base;if(b%2==1)        //如果b是奇数return (a*myPow(a,b-1))%base;else              //如果b是偶数{int sub=myPow(a,b/2);return (sub*sub)%base;}}int superPow(int a, vector<int>& b) {if(b.empty())   return 1;//b为空int last=b.back();//将b的最后一个元素提出来b.pop_back();int part1=myPow(a,last);int part2=myPow(superPow(a,b),10);return (part1*part2)%base;}
};

接下来是对本题进行讨论:

需要注意的是n的取值范围,可以发现当n为最小值时,直接取反会导致整型溢出,于是需要将这种情况单独进行讨论。

class Solution {
public:double myPow(double x, int n) {if(n==0)    return 1;//比较恶心的是注意一下n的范围,如果n为负的最小值,-2的31次方时,直接取负数会导致整型溢出if(n==INT_MIN)  return myPow(1/x,-(n+1))/x;//接下来再正常讨论,n为负、正时的情况if(n<0) return myPow(1/x,-n);//n为奇数时if(n%2==1)  return x*myPow(x,n-1);else{double sub=myPow(x,n/2);return sub*sub;}}
};

3.二叉搜索树的后序遍历

后序遍历 左右中,那么数组整体应该为左孩子-右孩子-根结点。

归根结底仍是数组与二叉树之间的转换问题,那么就离不开寻找切割点;

找到切割点后,右子树的所有点应该比根结点的值才对,否则返回false。

class Solution {
public:bool check(vector<int>& postorder,int left,int right){//终止条件if(left>=right)  return true;//空节点或者只有一个节点的时候int rootValue=postorder[right];//根结点的值//接下来还是分割数组,左孩子都比根结点小,右孩子都比根结点大int point=left;//分割点while(point<right&&postorder[point]<rootValue){point++;}//在point开始到right之间的所有值都应该比rootValue大int i=point;while(i<right&&postorder[i]>rootValue)  {i++;}if(i!=right)    return false;bool leftBool=check(postorder,left,point-1);bool rightBool=check(postorder,point,right-1);return leftBool&&rightBool;}bool verifyPostorder(vector<int>& postorder) {return check(postorder,0,postorder.size()-1);}
};

相关文章:

【20230225】【剑指1】分治算法(中等)

1.重建二叉树class Solution { public:TreeNode* traversal(vector<int>& preorder,vector<int>& inorder){if(preorder.size()0) return NULL;int rootValuepreorder.front();TreeNode* rootnew TreeNode(rootValue);//int rootValuepreorder[0];if(preo…...

「JVM 高效并发」Java 线程

进程是资源分配&#xff08;内存地址、文件 I/O 等&#xff09;的基本单位&#xff0c;线程是执行调度&#xff08;处理器资源调度&#xff09;的基本单位&#xff1b; Loom 项目若成功为 Java 引入纤程&#xff08;Fiber&#xff09;&#xff0c;则线程的执行调度单位可能变为…...

ADAS-可见光相机之Cmos Image Sensor

引言 “ 可见光相机在日常生活、工业生产、智能制造等应用有着重要的作用。在ADAS中更是扮演着重要的角色&#xff0c;如tesla model系列全车身10多个相机&#xff0c;不断感知周围世界。本文着重讲解下可见光相机中的CIS(CMOS Image Sensor)。” 定义 光是一种电磁波&…...

【ESP 保姆级教程】玩转emqx MQTT篇③ ——封装 EmqxIoTSDK,快速在项目集成

忘记过去,超越自己 ❤️ 博客主页 单片机菜鸟哥,一个野生非专业硬件IOT爱好者 ❤️❤️ 本篇创建记录 2023-02-26 ❤️❤️ 本篇更新记录 2023-02-26 ❤️🎉 欢迎关注 🔎点赞 👍收藏 ⭐️留言📝🙏 此博客均由博主单独编写,不存在任何商业团队运营,如发现错误,请…...

Python自动化测试面试题-编程篇

前言 随着行业的发展&#xff0c;编程能力逐渐成为软件测试从业人员的一项基本能力。因此在笔试和面试中常常会有一定量的编码题&#xff0c;主要考察以下几点。 基本编码能力及思维逻辑基本数据结构&#xff08;顺序表、链表、队列、栈、二叉树&#xff09;基本算法&#xf…...

CIT 594 Module 7 Programming AssignmentCSV Slicer

CIT 594 Module 7 Programming Assignment CSV Slicer In this assignment you will read files in a format known as “comma separated values” (CSV), interpret the formatting and output the content in the structure represented by the file. Q1703105484 Learning …...

链路追踪——【Brave】第一遍小结

前言 微服务链路追踪系列博客&#xff0c;后续可能会涉及到Brave、Zipkin、Sleuth内容的梳理。 Brave 何为Brave&#xff1f; github地址&#xff1a;https://github.com/openzipkin/brave Brave是一个分布式追踪埋点库。 #mermaid-svg-riwF9nbu1AldDJ7P {font-family:"…...

Vision Transformer(ViT)

1. 概述 Transformer[1]是Google在2017年提出的一种Seq2Seq结构的语言模型&#xff0c;在Transformer中首次使用Self-Atttention机制完全代替了基于RNN的模型结构&#xff0c;使得模型可以并行化训练&#xff0c;同时解决了在基于RNN模型中出现了长距离依赖问题&#xff0c;因…...

104-JVM优化

JVM优化为什么要学习JVM优化&#xff1a; 1&#xff1a;深入地理解 Java 这门语言 我们常用的布尔型 Boolean&#xff0c;我们都知道它有两个值&#xff0c;true 和 false&#xff0c;但你们知道其实在运行时&#xff0c;Java 虚拟机是 没有布尔型 Boolean 这种类型的&#x…...

QML 颜色表示法

作者: 一去、二三里 个人微信号: iwaleon 微信公众号: 高效程序员 如果你经常需要美化样式(最常见的有:文本色、背景色、边框色、阴影色等),那一定离不开颜色。而在 QML 中,颜色的表示方法有多种:颜色名、十六进制颜色值、颜色相关的函数,一起来学习一下吧。 老规矩…...

基础数据结构--线段树(Python版本)

文章目录前言特点操作数据存储updateLazy下移查询实现前言 月末了&#xff0c;划个水&#xff0c;赶一下指标&#xff08;更新一些活跃值&#xff0c;狗头&#xff09; 本文主要是关于线段树的内容。这个线段树的话&#xff0c;主要是适合求解我们一个数组的一些区间的问题&am…...

【micropython】SPI触摸屏开发

背景&#xff1a;最近买了几块ESP32模块&#xff0c;看了下mircopython支持还不错&#xff0c;所以买了个SPI触摸屏试试水&#xff0c;记录一下使用过程。硬件相关&#xff1a;SPI触摸屏使用2.4寸屏幕&#xff0c;常见淘宝均可买到&#xff0c;驱动为ILI9341&#xff0c;具体参…...

【云原生】k8s中Pod进阶资源限制与探针

一、Pod 进阶 1、资源限制 当定义 Pod 时可以选择性地为每个容器设定所需要的资源数量。 最常见的可设定资源是 CPU 和内存大小&#xff0c;以及其他类型的资源。 当为 Pod 中的容器指定了 request 资源时&#xff0c;调度器就使用该信息来决定将 Pod 调度到哪个节点上。当还…...

AI - stable-diffusion(AI绘画)的搭建与使用

最近 AI 火的一塌糊涂&#xff0c;除了 ChatGPT 以外&#xff0c;AI 绘画领域也有很大的进步&#xff0c;以下几张图片都是 AI 绘制的&#xff0c;你能看出来么&#xff1f; 一、环境搭建 上面的效果图其实是使用了开源的 AI 绘画项目 stable-diffusion 绘制的&#xff0c;这是…...

应用场景五: 西门子PLC通过Modbus协议连接DCS系统

应用描述&#xff1a; 西门子PLC&#xff08;S7200/300/400/200SMART&#xff09;通过桥接器可以支持ModbusRTU串口和ModbusTCP以太网&#xff08;有线和无线WIFI同时支持&#xff09;两种通讯方式连接DCS系统&#xff0c;不需要编程PLC通讯程序&#xff0c;直接在模块中进行地…...

我继续问了ChatGPT关于SAP顾问职业发展前景的问题,大家感受一下

目录 SAP 顾问 跟其他IT工作收入情况相比是怎么样的&#xff1f; 如何成为SAP FICO 优秀的顾问 要想成为SAP FICO 优秀的顾问 &#xff0c;需要ABA开发技能吗 SAP 顾问中哪个类型收入最多&#xff1f; 中国的ERP软件能够取代SAP吗&#xff1f; 今天我继续撩 ChatGPT。随便问…...

Python小白入门---00开篇介绍(简单了解一下)

Python 小白入门 系列教程 第一部分&#xff1a;Python 基础 介绍 Python 编程语言安装 Python 环境变量和数据类型运算符和表达式控制流程语句函数和模块异常处理 第二部分&#xff1a;Python 标准库和常用模块 Python 标准库简介文本处理和正则表达式文件操作和目录操作时…...

【算法基础】C++STL容器

一、Vector 1. 初始化(定义) (1)vector最基本的初始化: vector <int> a;(2)定义长度为10的vector: vector <int> a(10);(3)定义长度为10的vector,并且把所有元素都初始化为-3: vector <int...

【经典蓝牙】蓝牙 A2DP协议分析

A2DP 介绍 A2DP(Advanced Audio Distribution Profile)是蓝牙高音质音频传输协议&#xff0c; 用于传输单声道&#xff0c; 双声道音乐&#xff08;一般在 A2DP 中用于 stereo 双声道&#xff09; &#xff0c; 典型应用为蓝牙耳机。 A2DP旨在通过蓝牙连接传输高质量的立体声音…...

Objective-C 构造方法的定义和声明规范

总目录 iOS开发笔记目录 从一无所知到入门 文章目录源码中 NSArray 的构造方法与命名规律自定义类的构造方法命名截图代码输出源码中 NSArray 的构造方法与命名规律 interface NSArray<ObjectType> (NSArrayCreation) (instancetype)array;(instancetype)arrayWithObject…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

C++.OpenGL (14/64)多光源(Multiple Lights)

多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...

宇树科技,改名了!

提到国内具身智能和机器人领域的代表企业&#xff0c;那宇树科技&#xff08;Unitree&#xff09;必须名列其榜。 最近&#xff0c;宇树科技的一项新变动消息在业界引发了不少关注和讨论&#xff0c;即&#xff1a; 宇树向其合作伙伴发布了一封公司名称变更函称&#xff0c;因…...

4. TypeScript 类型推断与类型组合

一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式&#xff0c;自动确定它们的类型。 这一特性减少了显式类型注解的需要&#xff0c;在保持类型安全的同时简化了代码。通过分析上下文和初始值&#xff0c;TypeSc…...