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

力扣K神图解算法数据结构解析10

十、分治算法

  1. 剑指07,重建二叉树

    //时间O(n),空间O(n)
    //自己一直觉得这道题很难,没想到还是能够拿下,其实理论也清楚,前序遍历和中序遍历
    //关键如下
    //1.recur递归参数的确定,根节点在前序遍历中的索引,子树在中序遍历中的左边界和右边界
    //2.关于中序遍历哈希表的建立,空间换时间,使得查询为O(1)
    //3.常规递归基本操作,先写出整个程序框架,然后慢慢补充
    class Solution {
    public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {for(size_t i=0;i<inorder.size();++i){mm[inorder[i]] = i;}return recur(preorder,inorder,0,0,inorder.size()-1);}
    private:unordered_map<int,int> mm;TreeNode* recur(vector<int>& preorder, vector<int>& inorder,int prenode,int inleft,int inright){if(inleft > inright) return nullptr;TreeNode* root = new TreeNode(preorder[prenode]);int temp = mm[preorder[prenode]];root->left = recur(preorder,inorder,prenode+1,inleft,temp-1);root->right = recur(preorder,inorder,prenode+1+temp-inleft,temp+1,inright);return root;}
    };
    
  2. 剑指16,数值的整数次方

    //时间O(logn),空间O(1)
    //快速幂求余时间复杂度为O(logn),循环求余时间复杂度为O(n)
    //关键点就是学会快速幂求余,没啥好说的,整个剑指里面一共有两道快速幂,解法完全一样
    class Solution {
    public:double myPow(double x, int n) {if(!n || x == 1) return 1;int a = abs(n);double res = 1;while(a > 0){if(a % 2) res *= x;x = x*x; a /= 2;}if(n > 0) return res;else if(n < 0) return 1.0/res;return -1;}
    };
    
  3. 剑指17,打印从1到最大的n位数

    //时间O(10^n),空间O(1)
    //此题进阶部分需要考虑大数越界问题,当然此部分没有考虑
    class Solution {
    public:vector<int> printNumbers(int n) {vector<int> res;for(int i=1;i<pow(10,n);++i){res.push_back(i);}return res;}
    };
    
  4. 剑指33,二叉搜索树的后序遍历序列

    //时间O(n^2),空间O(n)
    //关键点如下
    //1.后序遍历,最后一个值是根节点,且整个序列按左,右,根排序
    //2.二叉搜索树,左子树均小于根节点,右子树均大于根节点
    //3.确定好递归参数,整个过程按照递归标准流程来就好,可以先写框架
    class Solution {
    public:bool verifyPostorder(vector<int>& postorder) {return recur(postorder,0,postorder.size()-1);}
    private:bool recur(vector<int>& postorder,int left,int right){if(left >= right) return true;int mid;//从左往右找右子树的第一个索引,同时也证明左子树其值均小于根节点for(int i=left;i<right;++i){if(postorder[i] > postorder[right]){mid = i;break;}}//验证右子树其值均大于根节点,否则返回falsefor(int i=mid;i<right;++i){if(postorder[i] < postorder[right]) return false;}//递归调用return recur(postorder,left,mid-1) && recur(postorder,mid,right-1);}
    };//单调栈方法没看懂,理论上其比递归快,但递归容易想到,且通用
    //时间O(n),空间O(n)
    //略
    
  5. 剑指51,数组中的逆序对

    //时间O(logn),空间O(n)
    //此题本质上是归并排序,逆序对只是在最后“治”的过程中统计了一下而已
    //标准递归,算是二叉搜索树中的后序遍历
    //关键点
    //1.分,二分法,分到单个元素停止
    //2.治,先将范围内的元素拷贝一份,原容器用于容纳排序后元素,然后三指针合并
    //  同时统计逆序对,注意等于不算逆序对
    class Solution {
    public:int reversePairs(vector<int>& nums) {vector<int> tmp(nums.size());msort(nums,tmp,0,nums.size()-1);return cnt;}
    private:int cnt = 0;void msort(vector<int>& nums, vector<int>& tmp, int left, int right){//分if (left >= right) return;int mid = left + (right - left) / 2;msort(nums, tmp, left, mid);msort(nums, tmp, mid+1, right);//拷贝for (int i = left; i <= right; ++i){tmp[i] = nums[i];}//治int i = left;int j = mid + 1;int k = left;while (k <= right){if (i >= mid + 1)	nums[k++] = tmp[j++];else if (j >= right + 1) nums[k++] = tmp[i++];else if(tmp[i] <= tmp[j]) nums[k++] = tmp[i++];else {cnt += mid - i + 1;nums[k++] = tmp[j++];}}}
    };
    

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

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

Redis对象类型编码(补充内存篇)

欢迎大家观看之前的Redis系列文章 Redis安装和配置&#xff08;Windows和Linux&#xff09;Redis原来不止五种类型啊&#xff08;含常用命令&#xff09; Redis内存模型原来是这样的啊&#xff01; Redis对象类型编码&#xff08;补充内存篇&#xff09; 深入学习Redis持久化&a…...

vue如何实现数据双向绑定,我的阿里手淘面试经历分享,看这篇文章准没错!

前言 全网唯一一份&#xff0c;对标阿里P7年薪60w的Android高级工程师学习进阶路线&#xff08;图未完全展开&#xff0c;怕大家看不清楚&#xff09;&#xff1a; 本篇文章都会围绕这份脑图来写&#xff0c;详细的介绍你处于哪个阶段该如何进阶&#xff0c;以及年薪层次高低对…...

LeetCode练习——其他(有效的括号)

给定一个只包括 ‘(’&#xff0c;’)’&#xff0c;’{’&#xff0c;’}’&#xff0c;’[’&#xff0c;’]’ 的字符串 s &#xff0c;判断字符串是否有效。 有效字符串需满足&#xff1a; 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 解法一&#…...

Apollo学习笔记8-imu-lidarApollo3.0手动标定

imu-lidarApollo3.0手动标定参考文档参考文档 1:https://github.com/ApolloAuto/apollo/blob/r3.0.0/docs/specs/apollo_lidar_imu_calibration_guide.md. 2:https://github.com/ApolloAuto/apollo/blob/r3.0.0/docs/specs/D-kit/Auto_Driving–Sensor_calibration_cn.md. 3:h…...

什么是服务网格(Service Mesh)

本文来说下什么是服务网格 文章目录概述概述...

Hadoop Yarn

The fundamental idea of YARN is to split up the functionalities of resource management and job scheduling/monitoring into separate daemons. The idea is to have a global ResourceManager (RM) and per-application ApplicationMaster (AM). An application is eit...

redis加锁、解锁

在Java中&#xff0c;关于锁我想大家都很熟悉。在并发编程中&#xff0c;我们通过锁&#xff0c;来避免由于竞争而造成的数据不一致问题。通常&#xff0c;我们以synchronized 、Lock来使用它。 但是Java中的锁&#xff0c;只能保证在同一个JVM进程内中执行。如果在分布式集群…...

atcoder arc 122 a~b题Many Formulae、Insurance

A题链接 题目大意&#xff1a;不能存在两个及两个以上的减号&#xff0c;所有满足条件的式子之和。 题目思路&#xff1a;当时考试想到一半&#xff0c;就感觉编码能力不太会&#xff0c;然后就没做&#xff0c; 首先我们定义dp[N][2]&#xff0c;这种选或不选的问题&#xff0…...

04_set容器_查找和统计

#include<iostream> #include<string> #include<set> using namespace std;//查找 void test01() {set<int>s1;s1.insert(10);s1.insert(30);s1.insert(20);s1.insert(40);set<int>:: iterator pos s1.find(30);if (pos ! s1.end()){cout <&…...

【pandas】根据其他表格列数据更新相应的列字段,apply()操作实例

今天在学习中&#xff0c;遇到一个小问题&#xff0c;需要把主表中的出行网格id&#xff0c;和终点网格id替换成对应的枢纽地点&#xff0c;从表中有每个枢纽对应的id&#xff08;一个枢纽对应多个网格id&#xff09; 1.原始数据如下图 上面是枢纽id,下方是出行信息 2.将数…...

数据库课程设计 大学生综合管理系统

问题描述&#xff1a; 设计并开发一套完整的在校大学生学习的综合管理系统&#xff0c;其中可包括以下几个模块&#xff1a; &#xff08;一&#xff09;选课管理&#xff1a;该系统包括教师、学生、系、课程和教室等信息&#xff0c;基本情况如下&#xff1a; 教师有工作证号…...

第十二周.直播.DGL-KG, LifeSci讲解

文章目录知识图谱背景DGL-KELifeSci双线性系列RESCAL摘要2. Modelling and Notation模型DistMult摘要模型ConvE为什么是2D不是1D卷积模型本文内容整理自深度之眼《GNN核心能力培养计划》公式输入请参考&#xff1a; 在线Latex公式DGL有三个比较知名的开源库&#xff0c;DGL-KG,…...

No qualifying bean of type ‘com.kkb.dao.*Mapper‘ available

没有查找到 *mapper对象程序报错没有查找到 mapper对象 可能造成的原因&#xff1a;缺少相应的注解 在SpringBoot的启动类中缺少 MapperScan SpringBootApplication MapperScan("com.yhp.dao") public class Application {public static void main(String[] args) …...

WPF 简单使用keybd_event模拟触发键盘

主要是添加Win32函数 其次是定义键盘按下&#xff0c;抬起的两个固定值。 [DllImport("User32.dll")]public static extern void keybd_event(byte bVk, byte bScan, int dwFlags, int dwExtraInfo);/// <summary>/// 按下/// </summary>const int KEY…...

java程序员日常工作内容,Java面试题及解析

目录 Kafka的基本介绍Kafka的设计原理分析Kafka数据传输的事务特点Kafka消息存储格式副本&#xff08;replication&#xff09;策略Kafka消息分组&#xff0c;消息消费原理Kafak顺序写入与数据读取消费者&#xff08;读取数据&#xff09; Kafka的基本介绍 Kafka是最初由Lin…...

常用网络数据包丢失的分析与处理

网络管理维护过程中&#xff0c;经常会遇到数据包丢失的情况。用Ping命令进行连接测试&#xff0c;会发现Ping包的延迟远远超过正常值&#xff0c;甚至无法到达&#xff0c;同时伴随着网络服务应用的障碍&#xff0c;比如打开网站的速度太慢&#xff0c;严重时甚至无法打开网页…...

2021-06-23 SpringCloud Zuul网关filter添加或修改传递的参数

场景&#xff1a;通过网关转发服务到具体的ip地址 比如网关验证accessToken&#xff0c;需要拦截访问&#xff0c;然后在url中添加参数&#xff0c;如下 //1、这个是原来的参数数据 String accessToken request.getParameter("accessToken"); //2、转换后的数据 S…...

面试笔试题

1.src和href的区别 &#xff1f; 答:src用于替代当前的元素&#xff0c;而href用于建立这个标签与外部资源之间的关系。 href 是Hypertext Reference的简写&#xff0c;表示超文本引用&#xff0c;指向网络资源所在位置。 常用场景: <a href"http://www.baidu.com&…...

MySQL下载及配置过程

MySQL下载及配置过程 下载&#xff08;Windows&#xff09; 下载地址 https://dev.mysql.com/downloads/mysql/ 进入后的界面&#xff0c;点击Download下载。 点击Download进入此界面&#xff0c;点击标注的地方直接下载。 配置 这里只介绍 .zip 格式。 .zip格式不需要…...

DQL查询数据(最重点)

4、DQL查询数据&#xff08;最重点&#xff09; 4.1、DQL &#xff08;Data query Language&#xff1a;数据查询语言&#xff09; 所有的查询操作都用它 Select简单的查询&#xff0c;复杂的查询它都能做数据库中最核心的语言&#xff0c;最重要的语句使用频率最高的语句 …...

Java学习路线图//Java、Java学习路线、Java自学、Java经验分享、经验分享、资源分享

今天整理了群里大佬们的实践经验成文为学习路线图&#xff0c;目的是帮助后来者高效的学习Java。 该路线图在保留了文章的核心架构外&#xff0c;也做了一些优化&#xff0c;包括&#xff1a; 更详细的学习内容。更精确的学习时间。优化学习方法&#xff0c;避开前端知识。及…...

简单介绍下Python解释器

当我们编写Python代码时&#xff0c;我们得到的是一个包含Python代码的以.py为扩展名的文本文件。要运行代码&#xff0c;就需要Python解释器去执行.py文件。 由于整个Python语言从规范到解释器都是开源的&#xff0c;所以理论上&#xff0c;只要水平够高&#xff0c;任何人都…...

静态ip域名怎么设置?

要想在互联网上进行正常的联网使用&#xff0c;分别是&#xff1a;网站源码&#xff0c;服务器&#xff0c;域名。服务器就是用来在后台存储网站数据并支撑运行的平台&#xff0c;大家对服务器以及域名都不是很了解&#xff0c;因此&#xff0c;想要对此有了解的小伙伴&#xf…...

Linux 文件系统 整理

独栋别墅&#xff0c;容积率低 root 用户 高层。 用户组 用户 $more 预览 文件名 more /etc/group a.txt 文本 .java Java文件 Linux中不以后缀作为区分&#xff0c; 回车 &#xff1a;换行 空格&#xff1a;换页 q&#xff1a;退出 $tail&#xff1a; 尾巴 $tail -10 /etc/gr…...

PHP_JavaScript高级编程(2)

二、今日目标 1、理解什么是面向对象&#xff08;编程&#xff09; 2、掌握定义对象的多种方式&#xff0c;并知道各种方式的优缺点 3、掌握什么是原型对象&#xff08;难点&#xff09; 4、理解原型链的概念&#xff08;或原型链的查找方式&#xff09; 5、掌握什么是回调…...

Linux企业运维——Kubernetes(十六)容器资源监控

Linux企业运维——Kubernetes&#xff08;十六&#xff09;容器资源监控 文章目录Linux企业运维——Kubernetes&#xff08;十六&#xff09;容器资源监控1、Metrics-Server1.1、Metrics-Server简介1.2、Metrics-Server部署2、Dashboard2.1、Dashboard部署2.2、Dashboard可视化…...

IFRS17改造记录

一&#xff0c;为什么要推行IFRS17&#xff08;简称&#xff1a;I17&#xff09; 不同国家&#xff0c;不同的保险产品采用不同的会计计量方法&#xff08;中国保险业现行的会计准则是基于IFRS4准则&#xff09;保险行业的财务报告难于理解对风险没有明确的量化计量部分国家由…...

Java学习推荐书目

一、基础类 1、《Thinkinginjava》&#xff0c;入门第一位是建立正确的概念。 2、《CoreJava》&#xff0c;我没系统读过&#xff0c;这本书更贴近实践&#xff0c;更多API的介绍&#xff0c;同样&#xff0c;更新也更频繁。 二、进阶类 1、《EffectiveJava》&#xff0c;在熟…...

2021-08-23 arm开发板上执行程序报错:-sh: ./uart_app: No such file or directory

问题前提描述: 使用的是正点原子 arm alpha 开发板存在这个文件 其他相关问题: 刚出现这个问题时,我在csdn上搜到的其他造成原因: “doc格式(windows系统)、mac(苹果系统)在上传到xshell(unix系统)后, unix系统是不支持doc&#xff08;mac&#xff09;格式的” 如果是这种情况…...

PTA 基础编程题目集 7-2 然后是几点

目录 题目&#xff1a; 输入格式&#xff1a; 输出格式&#xff1a; 输入样例&#xff1a; 输出样例&#xff1a; 分析&#xff1a; 答案&#xff1a; 题目&#xff1a; 有时候人们用四位数字表示一个时间&#xff0c;比如 1106 表示 11 点零 6 分。现在&#xff0c;你…...

push代码报错:fatal: unable to access ‘https://github.com/JL-20191210/guigu.git/‘: OpenSSL SSL_read: Conn

解决方案&#xff1a;git config --global http.sslVerify "false" 解决方案二&#xff1a;使用浏览器看能否访问&#xff0c;不能则使用科学确定能访问后进行push...

hadoop退出安全模式Name node is in safe mode

解决方案&#xff1a; hadoop dfsadmin -safemode leave或者&#xff1a; hdfs dfsadmin -safemode leave...

window10下启动nacos报错问题解决

如果直接点击nacos文件夹下bin目录下的 startup.cmd 会报错&#xff0c;这是由于nacos默认会以集群模式启动&#xff0c;如果想单机测试启动的话&#xff0c;需要&#xff1a; 1. 进入 nacos 的 bin 文件夹下&#xff0c;输入 cmd &#xff0c;即可进入bin目录下得cmd窗口&…...

在Mapper接口中通过接口名自动生成sql映射

package com.guigu.admin.mapper; import com.baomidou.dynamic.datasource.annotation.DS; import org.apache.ibatis.annotations.Param;import com.guigu.admin.domain.Student; import com.baomidou.mybatisplus.core.mapper.BaseMapper;import java.util.List; import ja...

vue项目运行npm run dev报错

vue项目运行npm run dev 报错 原因&#xff1a; node_modules有意外改动&#xff0c;导致依赖库不完整 解决办法&#xff1a; 1.删除node_modules 2.运行 npm install 3.运行 npm run build 4.重新npm run dev...

Error creating bean with name ‘multipartResolver‘:怎样解决

Error creating bean with name ‘multipartResolver’:怎样解决&#xff1f; 这个错误原因是自己在加jar包时&#xff0c;没有加 这两个包。 但是此时tomcat文件夹下的lib文件夹还没有你添加的依赖。 下面有两种方法 一&#xff1a;去项目结构的如果&#xff0c;工件里面点击…...

HTTP Status 500 - Servlet.init() for servlet DispatcherServlet threw exception 解决方案

当出现&#xff1a; 并且在<bean>标签中出现红线时&#xff1a; 问题很简单&#xff0c;就是在配置spring-mvc.xml的表头是重复了,如下&#xff1a; 只需删除如下&#xff1a; xmlns:mvc"http://www.springframework.org/schema/cache" 随后就能解决问题&…...

查看 OpenFeign 的远程调用日志

Feign 提供了日志打印功能&#xff0c;我们可以通过配置来调整日志级别&#xff0c;从而了解 Feign 中 Http 请求的细节 第一步:在配置类中配置 Feign 的 Logger.Level Configuration public class FeignConfig {Beanpublic Logger.Level liver(){/** NONE&#xff1a;默认…...

win10一行命令查看所有wifi密码

win10一行命令查看所有wifi密码 将本机连接过的所有wifi及密码&#xff0c;保存在桌面txt文件 for /f "skip10 tokens1,2 delims:" %i in (netsh wlan show profiles) do for /f "tokens1-2 delims:" %k in (netsh wlan show profiles %j key ^ clear ^|f…...

类com.luffy.servlet.HelloServlet不是Servlet

类com.luffy.servlet.HelloServlet不是Servlet 问题&#xff1a; Tomcat 10及以上把Java EE迁移到了Jakarta EE&#xff0c;所有已实现API的主要软件包已从 javax.* 更改为 jakarta.* 解决方式&#xff1a; 将原有的依赖替换为下面两个依赖&#xff0c;然后刷新maven&#…...

解决vue-element-admin安装报错 npm ERR code 128 npm ERR An unknown git error occurred npm

在安装vue-element-admin的npm install的时候报错 解决方案&#xff1a; 一、桌面右键&#xff0c;git bash here 输入以下 ssh-keygen -t rsa -C “你的邮箱名称” overwrite 输入y 输入密码的时候直接回车 重复密码输入还是直接回车&#xff0c;然后把github上以前的sshkeys删…...

学习babel(转码器)时问题解决

学习babel(转码器)时问题解决&#xff1a;SyntaxError: D:\js-demo-study\12.13\Babeltest.babelrc: Error while parsing JSON - Unexpected EOF at line 1 column 2 of the JSON5 data. Still to read: "" 1、powershell的执行策略修改&#xff0c; 参考&#xf…...

【SpringBoot内容协商】

基于请求头的内容协商 Accept&#xff1a;Application/xml acceptableTypes producibleTypes mediaTypesToUse for (MediaType requestedType : acceptableTypes) {for (MediaType producibleType : producibleTypes) {if (requestedType.isCompatibleWith(producibleType)) {…...

Noqualifyingbeanoftype‘com..xxMapper‘available:expectedatleast1beanwhichqualifiesasautowirecandidate

具体报错是这样 No qualifying bean of type com..xxMapper available: expected at least 1 bean which qualifies as autowire candidate Dependency annotations:{org.springframework.beans.factory.annotation.Autowired(requiredtrue)} 首先&#xf…...

pytest文档84 - 把收集的 yaml 文件转成pytest 模块和用例

前言 前面实现了一个基础的读取yaml文件内容&#xff0c;当成用例去执行。虽然入门简单&#xff0c;但需要扩展功能&#xff0c;比如在 yaml 用例实现参数化&#xff0c;就不好扩展了。 因为它并不是一个真正的pytest的模块和用例&#xff0c;无法被钩子函数探测到。所以这篇会…...

MyBatis参数处理

参数处理 单个参数 通过#{参数名}取出参数值 接口定义如下 public User getUserByUserName(String userName);接口对应的 Mapper.xml 定义如下所示 <select id"getUserByUserName"parameterType"String"resultType"com.example.mybatis.entit…...

MyBatis的基础查询

1&#xff0c;导入MyBatis使用的依赖 <dependencies><!-- https://mvnrepository.com/artifact/org.mybatis/mybatis --><dependency><groupId>org.mybatis</groupId><artifactId>mybatis</artifactId><version>3.4.6</ve…...

vscode中前端vue项目详解_详解VSCode配置启动Vue项目_婳祎_前端开发者

下载安装并配置VSCode随便百度上搜个最新的VSCode安装好后&#xff0c;点击Ctrl Shit X打开插件扩展窗口进行插件扩展&#xff0c;这里要安装两个插件。1、vetur插件的安装该插件是"emmet.syntaxProfiles": {"2、eslint插件的安装eslint智能错误检测插件&…...

mysql hive sqoo,hive udaf 用maven打包执行create temporary function 时报错

用maven打包写好的jar&#xff0c;在放到hive中作临时函数时报错。错误信息如下&#xff1a;hive> create temporary function maxvalue as "com.leaf.data.Maximum";java.lang.SecurityException: Invalid signature file digest for Manifest main attributesat…...

BindingException: Invalid bound statement (not found): com.*..Mapper.get源码分析

问题分析 https://blog.csdn.net/msu9527/article/details/119059103 源码分析 2021-07-21 16:03:35.539 169254213631626854594179000022164 http-nio-8005-exec-4 ERROR c.a.f.c.a.ExceptionAdvice:27 - /user/list org.apache.ibatis.binding.BindingException: Invalid …...