【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 线程
进程是资源分配(内存地址、文件 I/O 等)的基本单位,线程是执行调度(处理器资源调度)的基本单位; Loom 项目若成功为 Java 引入纤程(Fiber),则线程的执行调度单位可能变为…...

ADAS-可见光相机之Cmos Image Sensor
引言 “ 可见光相机在日常生活、工业生产、智能制造等应用有着重要的作用。在ADAS中更是扮演着重要的角色,如tesla model系列全车身10多个相机,不断感知周围世界。本文着重讲解下可见光相机中的CIS(CMOS Image Sensor)。” 定义 光是一种电磁波&…...
【ESP 保姆级教程】玩转emqx MQTT篇③ ——封装 EmqxIoTSDK,快速在项目集成
忘记过去,超越自己 ❤️ 博客主页 单片机菜鸟哥,一个野生非专业硬件IOT爱好者 ❤️❤️ 本篇创建记录 2023-02-26 ❤️❤️ 本篇更新记录 2023-02-26 ❤️🎉 欢迎关注 🔎点赞 👍收藏 ⭐️留言📝🙏 此博客均由博主单独编写,不存在任何商业团队运营,如发现错误,请…...
Python自动化测试面试题-编程篇
前言 随着行业的发展,编程能力逐渐成为软件测试从业人员的一项基本能力。因此在笔试和面试中常常会有一定量的编码题,主要考察以下几点。 基本编码能力及思维逻辑基本数据结构(顺序表、链表、队列、栈、二叉树)基本算法…...
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】第一遍小结
前言 微服务链路追踪系列博客,后续可能会涉及到Brave、Zipkin、Sleuth内容的梳理。 Brave 何为Brave? github地址:https://github.com/openzipkin/brave Brave是一个分布式追踪埋点库。 #mermaid-svg-riwF9nbu1AldDJ7P {font-family:"…...

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

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

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

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

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

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

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

应用场景五: 西门子PLC通过Modbus协议连接DCS系统
应用描述: 西门子PLC(S7200/300/400/200SMART)通过桥接器可以支持ModbusRTU串口和ModbusTCP以太网(有线和无线WIFI同时支持)两种通讯方式连接DCS系统,不需要编程PLC通讯程序,直接在模块中进行地…...

我继续问了ChatGPT关于SAP顾问职业发展前景的问题,大家感受一下
目录 SAP 顾问 跟其他IT工作收入情况相比是怎么样的? 如何成为SAP FICO 优秀的顾问 要想成为SAP FICO 优秀的顾问 ,需要ABA开发技能吗 SAP 顾问中哪个类型收入最多? 中国的ERP软件能够取代SAP吗? 今天我继续撩 ChatGPT。随便问…...
Python小白入门---00开篇介绍(简单了解一下)
Python 小白入门 系列教程 第一部分:Python 基础 介绍 Python 编程语言安装 Python 环境变量和数据类型运算符和表达式控制流程语句函数和模块异常处理 第二部分: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)是蓝牙高音质音频传输协议, 用于传输单声道, 双声道音乐(一般在 A2DP 中用于 stereo 双声道) , 典型应用为蓝牙耳机。 A2DP旨在通过蓝牙连接传输高质量的立体声音…...

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

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)
2025年能源电力系统与流体力学国际会议(EPSFD 2025)将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会,EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...
pam_env.so模块配置解析
在PAM(Pluggable Authentication Modules)配置中, /etc/pam.d/su 文件相关配置含义如下: 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块,负责验证用户身份&am…...

相机从app启动流程
一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

C# 类和继承(抽象类)
抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
Xen Server服务器释放磁盘空间
disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...
《C++ 模板》
目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板,就像一个模具,里面可以将不同类型的材料做成一个形状,其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式:templa…...
return this;返回的是谁
一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请,不同级别的经理有不同的审批权限: // 抽象处理者:审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...

【从零学习JVM|第三篇】类的生命周期(高频面试题)
前言: 在Java编程中,类的生命周期是指类从被加载到内存中开始,到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期,让读者对此有深刻印象。 目录 …...