当前位置: 首页 > 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…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#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样…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录&#xff0c;但是由于这个树组件的节点越来越多&#xff0c;导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多&#xff0c;导致的浏览器卡顿&#xff0c;这里很明显就需要用到虚拟列表的技术&…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

视觉slam十四讲实践部分记录——ch2、ch3

ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...

08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险

C#入门系列【类的基本概念】&#xff1a;开启编程世界的奇妙冒险 嘿&#xff0c;各位编程小白探险家&#xff01;欢迎来到 C# 的奇幻大陆&#xff01;今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类&#xff01;别害怕&#xff0c;跟着我&#xff0c;保准让你轻松搞…...