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

【图解算法数据结构】分治算法篇 + Java代码实现

文章目录

  • 一、重建二叉树
  • 二、数值的整数次方
  • 三、打印从 1 到最大的 n 位数
  • 四、二叉搜索树的后序遍历序列
  • 五、数组中的逆序对


一、重建二叉树

在这里插入图片描述

public class Solution {int[] preorder;HashMap<Integer, Integer> dic = new HashMap<>();public TreeNode buildTree(int[] preorder, int[] inorder) {this.preorder = preorder;for (int i = 0; i < inorder.length; i++) {dic.put(inorder[i], i);}return recur(0, 0, inorder.length - 1);}TreeNode recur(int root, int left, int right) {if (left > right) {// 递归终止return null;}// 建立根节点TreeNode node = new TreeNode(preorder[root]);// 划分根节点、左子树、右子树int i = dic.get(preorder[root]);// 开启左子树递归node.left = recur(root + 1, left, i - 1);// 开启右子树递归 i - left + root + 1 含义为 根节点索引 + 左子树长度 + 1node.right = recur(root + i - left + 1, i + 1, right);// 回溯返回根节点return node;}public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}}}

二、数值的整数次方

在这里插入图片描述

public class Solution {public double myPow(double x, int n) {long b = n;double res = 1.0;if (b < 0) {x = 1 / x;b = -b;}while (b > 0) {if ((b & 1) == 1) {res *= x;}x *= x;b >>= 1;}return res;}
}

三、打印从 1 到最大的 n 位数

在这里插入图片描述

public class Solution {public int[] printNumbers(int n) {int[] res = new int[(int) Math.pow(10, n) - 1];for (int i = 0; i < res.length; i++) {res[i] = i + 1;}return res;}
}

四、二叉搜索树的后序遍历序列

在这里插入图片描述

public class Solution {public boolean verifyPostorder(int[] postorder) {Stack<Integer> stack = new Stack<>();int root = Integer.MAX_VALUE;for(int i = postorder.length - 1; i >= 0; i--) {if(postorder[i] > root) {return false;}while(!stack.isEmpty() && stack.peek() > postorder[i]) {root = stack.pop();}stack.add(postorder[i]);}return true;}
}

五、数组中的逆序对

在这里插入图片描述

public class Solution {int[] nums, tmp;public int reversePairs(int[] nums) {this.nums = nums;tmp = new int[nums.length];return mergeSort(0, nums.length - 1);}private int mergeSort(int l, int r) {// 终止条件if (l >= r) {return 0;}// 递归划分int m = (l + r) / 2;int res = mergeSort(l, m) + mergeSort(m + 1, r);// 合并阶段int i = l, j = m + 1;for (int k = l; k <= r; k++) {tmp[k] = nums[k];}for (int k = l; k <= r; k++) {if (i == m + 1) {nums[k] = tmp[j++];} else if (j == r + 1 || tmp[i] <= tmp[j])nums[k] = tmp[i++];else {nums[k] = tmp[j++];res += m - i + 1; // 统计逆序对}}return res;}
}

相关文章:

【图解算法数据结构】分治算法篇 + Java代码实现

文章目录 一、重建二叉树二、数值的整数次方三、打印从 1 到最大的 n 位数四、二叉搜索树的后序遍历序列五、数组中的逆序对 一、重建二叉树 public class Solution {int[] preorder;HashMap<Integer, Integer> dic new HashMap<>();public TreeNode buildTree(in…...

Ubuntu系统环境搭建(八)——Ubuntu开机自动执行命令

ubuntu环境搭建专栏&#x1f517;点击跳转 Ubuntu系统环境搭建&#xff08;八&#xff09;——Ubuntu开机自动执行命令 修改文件 vim /etc/rc.local以自启动mysql为例&#xff0c;在文件末尾添加 /usr/local/mysql8/bin/mysqld_safe --defaults-file/usr/local/etc/my.cnf …...

c++(8.29)auto关键字,lambda表达式,数据类型转换,标准模板库,list,文件操作+Xmind

作业&#xff1a; 封装一个学生的类&#xff0c;定义一个学生这样类的vector容器, 里面存放学生对象&#xff08;至少3个&#xff09; 再把该容器中的对象&#xff0c;保存到文件中。 再把这些学生从文件中读取出来&#xff0c;放入另一个容器中并且遍历输出该容器里的学生。…...

Docker学习笔记(持续更新)

Docker学习目录 1.基础1.1 Docker简介1.1.1 Why Docker&#xff1f;1.1.2 Docker理念1.1.3 容器与虚拟机1.1.4 Docker能做什么&#xff1f; 1.2 Docker的基本组成1.2.1 Docker的三要素1.2.2 Docker平台架构 1.基础 1.1 Docker简介 1.1.1 Why Docker&#xff1f; 在个人笔记本…...

无涯教程-Android - 应用组件

应用程序组件是Android应用程序的基本组成部分&#xff0c;这些组件需要在应用程序清单文件 AndroidManifest.xml 注册&#xff0c;该文件描述了应用程序的每个组件以及它们如何交互。 Android应用程序可以使用以下四个主要组件- Sr.NoComponents & 描述1 Activities 它们…...

树与图c++

1.树 前言 本文主要介绍的数据结构之树型结构的相关知识&#xff0c;树型数据结构是面试官面试的时候非常喜欢考的一种数据结构&#xff0c;树形结构的遍历也是大厂笔试非常喜欢设置的考点&#xff0c;这些内容都会在本篇文章中进行详细的介绍&#xff0c;并且还会介绍一些常…...

中小企业常用的 IT 项目管理软件有哪些?

越热门&#xff0c;越贵的IT项目管理软件越好用吗&#xff1f;对于预算有限的中小型企业来说&#xff0c;如何选择一款适合自己的项目管理工具着实是个头疼的问题。 首先适用于中小型企业使用的 IT 项目管理软件需要具备哪些特点呢&#xff1f; 1、简单易用&#xff1a;中小企…...

汇编原理计算方法:物理地址=段地址*16+偏移地址

文章目录 计算方法计算错误分析 计算方法 根据进制的不同选择不同的计算方法 注意&#xff1a;物理地址、段地址和偏移地址的进制统一&#xff0c;要么都是二进制&#xff0c;要么都是十六进制&#xff0c;一般而言多是十六进制 若是二进制表达&#xff0c;则将段地址左移四…...

jdk-8u371-linux-x64.tar.gz jdk-8u371-windows-x64.exe 【jdk-8u371】 全平台下载

jdk-8u371 全平台下载 jdk-8u371-windows-x64.exejdk-8u371-linux-x64.rpmjdk-8u371-linux-x64.tar.gzjdk-8u371-macosx-x64.dmgjdk-8u371-linux-aarch64.tar.gz 下载地址 迅雷云盘 链接&#xff1a;https://pan.xunlei.com/s/VNdLL3FtCnh45nIBHulh_MDjA1?pwdw4s6 百度…...

数据结构体--5.0图

目录 一、定义 二、图的顶点与边之间的关系 三、图的顶点与边之间的关系 四、连通图 五、连通图的生成树定义 一、定义 图&#xff08;Graph&#xff09;是由顶点的又穷非空集合合顶点之间边的集合组成&#xff0c;通常表示为&#xff1a;G&#xff08;V&#xff0c;E&…...

深入剖析 Golang 程序启动原理 - 从 ELF 入口点到GMP初始化到执行 main!

大家好&#xff0c;我是飞哥&#xff01; 在过去的开发工作中&#xff0c;大家都是通过创建进程或者线程来工作的。Linux进程是如何创建出来的&#xff1f; 、聊聊Linux中线程和进程的联系与区别&#xff01; 和你的新进程是如何被内核调度执行到的&#xff1f; 这几篇文章就是…...

C语言——多文件编程

多文件编程 把函数声明放在头文件xxx.h中&#xff0c;在主函数中包含相应头文件在头文件对应的xxx.c中实现xxx.h声明的函数 防止头文件重复包含 当一个项目比较大时&#xff0c;往往都是分文件&#xff0c;这时候有可能不小心把同一个头文件 include 多次&#xff0c;或者头…...

Git学习part1

02.尚硅谷_Git&GitHub_为什么要使用版本控制_哔哩哔哩_bilibili 1.Git必要性 记录代码开发的历史状态 &#xff0c;允许很多人同时修改文件&#xff08;分布式&#xff09;且不会丢失记录 2.版本控制工具应该具备的功能 1&#xff09;协同修改 多人并行不悖的修改服务器端…...

2309C++均为某个类型

#include <常用> 构 A{空 f(){打印("啊");} }; 元<类 T>构 是点啊:假型{}; 元<>构 是点啊<A>:真型{}; 元<类 T>概念 是呀是点啊<T>::值;元<是呀...T>空 f(T&...t){(t.f(),...); }//均为元<类...T>要求 均为值&l…...

2023年打脸面试官之TCP--瞬间就懂

1.TCP 三次握手之为什么要三次呢&#xff1f;事不过三&#xff1f; 过程如下图&#xff1a; 先来解释下上述的各个标志的含义 序列号seq&#xff1a;占4个字节&#xff0c;用来标记数据段的顺序&#xff0c;TCP把连接中发送的所有数据字节都编上一个序号&#xff0c;第一个字节…...

设计模式-单例模式Singleton

单例模式 单例模式 (Singleton) (重点)1) 为什么要使用单例2) 如何实现一个单例2.a) 饿汉式2.b) 懒汉式2.c) 双重检查锁2.d) 静态内部类2.e) 枚举类2.f) 反射入侵2.g) 序列化与反序列化安全 3) 单例存在的问题3.a) 无法支持面向对象编程 单例模式 (Singleton) (重点) 一个类只…...

PPPoE连接无法建立的排查和修复

嗨&#xff0c;亲爱的读者朋友们&#xff01;你是否曾经遇到过PPPoE连接无法建立的问题&#xff1f;今天我将为你详细解析排查和修复这个问题的步骤。 检查物理连接 首先&#xff0c;我们需要确保物理连接没有问题。请按照以下步骤进行检查&#xff1a; - 检查网线是否插好&…...

QT 发布软件基本操作

一、配置环境变量 找到Qt安装时的bin目录的路径&#xff1a;D:\Qt\Qt5.14.2\5.14.2\mingw73_64\bin&#xff0c;将目录拷贝至下述环境变量中。 打开计算机的高级系统设置 选中环境变量-->系统变量-->Path 点击编辑-->新建-->粘贴 二、生成发布软件的可执行程序 …...

CTFhub-SSRF-内网访问

CTFHub 环境实例 | 提示信息 http://challenge-8bf41c5c86a8c5f4.sandbox.ctfhub.com:10800/?url_ 根据提示&#xff0c;在url 后门添加 127.0.0.1/flag.php http://challenge-8bf41c5c86a8c5f4.sandbox.ctfhub.com:10800/?url127.0.0.1/flag.php ctfhub{a6bb51530c8f6be0…...

Cenos7安装小火车程序动画

运维Shell脚本小试牛刀(一) 运维Shell脚本小试牛刀(二) 运维Shell脚本小试牛刀(三)::$(cd $(dirname $0)&#xff1b; pwd)命令详解 运维Shell脚本小试牛刀(四): 多层嵌套if...elif...elif....else fi_蜗牛杨哥的博客-CSDN博客 Cenos7安装小火车程序动画 一&#xff1a;替换…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...

c++第七天 继承与派生2

这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分&#xff1a;派生类构造函数与析构函数 当创建一个派生类对象时&#xff0c;基类成员是如何初始化的&#xff1f; 1.当派生类对象创建的时候&#xff0c;基类成员的初始化顺序 …...

淘宝扭蛋机小程序系统开发:打造互动性强的购物平台

淘宝扭蛋机小程序系统的开发&#xff0c;旨在打造一个互动性强的购物平台&#xff0c;让用户在购物的同时&#xff0c;能够享受到更多的乐趣和惊喜。 淘宝扭蛋机小程序系统拥有丰富的互动功能。用户可以通过虚拟摇杆操作扭蛋机&#xff0c;实现旋转、抽拉等动作&#xff0c;增…...

windows系统MySQL安装文档

概览&#xff1a;本文讨论了MySQL的安装、使用过程中涉及的解压、配置、初始化、注册服务、启动、修改密码、登录、退出以及卸载等相关内容&#xff0c;为学习者提供全面的操作指导。关键要点包括&#xff1a; 解压 &#xff1a;下载完成后解压压缩包&#xff0c;得到MySQL 8.…...

如何做好一份技术文档?从规划到实践的完整指南

如何做好一份技术文档&#xff1f;从规划到实践的完整指南 &#x1f31f; 嗨&#xff0c;我是IRpickstars&#xff01; &#x1f30c; 总有一行代码&#xff0c;能点亮万千星辰。 &#x1f50d; 在技术的宇宙中&#xff0c;我愿做永不停歇的探索者。 ✨ 用代码丈量世界&…...

工厂方法模式和抽象工厂方法模式的battle

1.案例直接上手 在这个案例里面&#xff0c;我们会实现这个普通的工厂方法&#xff0c;并且对比这个普通工厂方法和我们直接创建对象的差别在哪里&#xff0c;为什么需要一个工厂&#xff1a; 下面的这个是我们的这个案例里面涉及到的接口和对应的实现类&#xff1a; 两个发…...

java+webstock

maven依赖 <dependency><groupId>org.java-websocket</groupId><artifactId>Java-WebSocket</artifactId><version>1.3.5</version></dependency><dependency><groupId>org.apache.tomcat.websocket</groupId&…...