算法通关村第9关【黄金】| 两道有挑战的问题

1. 将有序数组转换为二叉搜索树

思路:二分法,这个算法保证了每次选择的中间元素都能保持左右子树的高度差不超过 1,从而构建一个高度平衡的二叉搜索树。这个过程类似于分治法,通过递归不断将大问题分解成小问题并解决。

  1. 找到数组的中间元素,将它作为根节点。
  2. 以中间元素为界,将数组分成左右两个子数组。
  3. 递归地将左子数组构建为左子树,将右子数组构建为右子树。
  4. 返回根节点,连接左右子树。
class Solution {public TreeNode sortedArrayToBST(int[] nums) {return trace(nums,0,nums.length - 1);}public TreeNode trace(int[] nums,int left,int right) {if(left>right){return null;}int mid = (right + left)/2;TreeNode node = new TreeNode(nums[mid]);node.left = trace(nums,left,mid - 1);node.right = trace(nums,mid + 1,right);return node;}
}

2.寻找两个正序数组的中位数

 思路:找第k小的数字,每次抛弃k/2个数字

也就是奇数总数找第(len1+len2)/2的数字,偶数总数找第(len1+len2)/2和(len1+len2)/2 + 1的数字

 /* 主要思路:要找到第 k (k>1) 小的元素,那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较

         * 这里的 "/" 表示整除

         * nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个

         * nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个

         * 取 pivot = min(pivot1, pivot2),两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个

         * 这样 pivot 本身最大也只能是第 k-1 小的元素

         * 如果 pivot = pivot1,那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除",剩下的作为新的 nums1 数组

         * 如果 pivot = pivot2,那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除",剩下的作为新的 nums2 数组

         * 由于我们 "删除" 了一些元素(这些元素都比第 k 小的元素要小),因此需要修改 k 的值,减去删除的数的个数

         */

class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {int length1 = nums1.length, length2 = nums2.length;int totalLength = length1 + length2;if (totalLength % 2 == 1) {int midIndex = totalLength / 2;double median = getKthElement(nums1, nums2, midIndex + 1);return median;} else {int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2;double median = (getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0;return median;}}public int getKthElement(int[] nums1, int[] nums2, int k) {int length1 = nums1.length, length2 = nums2.length;int index1 = 0, index2 = 0;int kthElement = 0;while (true) {// 边界情况if (index1 == length1) {return nums2[index2 + k - 1];}if (index2 == length2) {return nums1[index1 + k - 1];}if (k == 1) {return Math.min(nums1[index1], nums2[index2]);}// 正常情况int half = k / 2;int newIndex1 = Math.min(index1 + half, length1) - 1;int newIndex2 = Math.min(index2 + half, length2) - 1;int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2];if (pivot1 <= pivot2) {k -= (newIndex1 - index1 + 1);index1 = newIndex1 + 1;} else {k -= (newIndex2 - index2 + 1);index2 = newIndex2 + 1;}}}
}

 

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

链路聚合原理

文章目录 一、定义二、功能三、负载分担四、分类五、常用命令 首先可以看下思维导图&#xff0c;以便更好的理解接下来的内容。 一、定义 在网络中&#xff0c;端口聚合是一种将连接到同一台交换机的多个物理端口捆绑在一起&#xff0c;形成一个逻辑端口的技术。通过端口聚合&…

Redis 主从复制和哨兵模式

一、概念 主从复制&#xff0c;是指将一台 Redis 服务器的数据&#xff0c;复制到其他的 Redis 服务器。前者称为主节点&#xff08;master/leader&#xff09;&#xff0c;后者称为从节点&#xff08;slave/follower&#xff09;。数据的复制是单向的&#xff0c;只能由主节点…

学习JAVA打卡第四十五天

StringBuffer类 StringBuffer对象 String对象的字符序列是不可修改的&#xff0c;也就是说&#xff0c;String对象的字符序列的字符不能被修改、删除&#xff0c;即String对象的实体是不可以再发生变化&#xff0c;例如&#xff1a;对于 StringBuffer有三个构造方法&#xff…

JPA在不写sql的情况下实现模糊查询

本文已收录于专栏 《Java》 目录 背景介绍概念说明单字段模糊匹配&#xff1a;多字段模糊匹配&#xff1a; 实现过程代码实现1.写一个实体类去实现Specification接口&#xff0c;重写toPredicate方法2.定义一个接口去继承JpaRepository接口&#xff0c;并指定返回的类型和参数类…

家宽用户家庭网的主要质量问题是什么?原因有哪些

1 引言 截至2020年底&#xff0c;我国家庭宽带&#xff08;以下简称“家宽”&#xff09;普及率已达到96%。经过一年多的发展&#xff0c;当前&#xff0c;家庭宽带的市场空间已经饱和。运营商在家宽市场的竞争也随之从新增用户数的竞争转移到家宽品质的竞争。 早期运营商的家…

多张图片转为pdf怎么弄?

多张图片转为pdf怎么弄&#xff1f;在网络传输过程中&#xff0c;为了避免图片格式文件出现差错&#xff0c;并确保图片的清晰度和色彩不因不同设备而有所改变&#xff0c;常见的做法是将图片转换为PDF格式。然而&#xff0c;当涉及到多张图片时&#xff0c;逐一转换将会变得相…

IP基本原理(上)

文章目录 一、IP的定义二、IP的作用1.标识节点和链路2.寻址和转发3.适应各种数据链路 三、IP头部封装格式四、MTU五、IP地址1.定义2.格式2.1 点分十进制和二进制关系与转换2.2 由网络位主机位组成2.3 网络位长度决定网段 3.分类3.1 A类3.2 B类3.3 C类3.4 D类3.5 E类 4.特殊地址…

职场中的团队建设:超越任务,铸就默契

团队建设在职场中的重要性日益凸显。无论是初创公司还是大型企业&#xff0c;都需要一个高效、和谐且有创新能力的团队来推动业务发展。本文将深入探讨团队建设的活动和策略&#xff0c;帮助您构建一个卓越的团队。 1. 团队建设的重要性 提高团队凝聚力 团队凝聚力不仅仅是团…

手写数字识别之网络结构

目录 手写数字识别之网络结构 数据处理 经典的全连接神经网络 卷积神经网络 手写数字识别之网络结构 无论是牛顿第二定律任务&#xff0c;还是房价预测任务&#xff0c;输入特征和输出预测值之间的关系均可以使用“直线”刻画&#xff08;使用线性方程来表达&#xff09…

SSM - Springboot - MyBatis-Plus 全栈体系(三)

第二章 SpringFramework 一、技术体系架构 1. 总体技术体系 1.1 单一架构 一个项目&#xff0c;一个工程&#xff0c;导出为一个war包&#xff0c;在一个Tomcat上运行。也叫all in one。 单一架构&#xff0c;项目主要应用技术框架为&#xff1a;Spring , SpringMVC , Myba…

基于Jenkins构建生产CICD环境(第三篇)

目录 基于Jenkins自动打包并部署docker环境 1、安装docker-ce 2、阿里云镜像加速器 3、构建tomcat 基础镜像 4、构建一个Maven项目 基于Jenkins自动化部署PHP环境 基于rsync部署 基于Jenkins自动打包并部署docker环境 1、安装docker-ce 在192.168.2.123 机器上&#x…

Qt中XML文件创建及解析

一 环境部署 QT的配置文件中添加xml选项&#xff1a; 二 写入xml文件 头文件&#xff1a;#include <QXmlStreamWriter> bool MyXML::writeToXMLFile() {QString currentTime QDateTime::currentDateTime().toString("yyyyMMddhhmmss");QString fileName &…

【算法日志】动态规划刷题:股票买卖问题(day41)

代码随想录刷题60Day 目录 前言 买卖股票的最佳时机1 买卖股票的最佳时机2 买卖股票的最佳时机3 买卖股票的最佳时机4 前言 本日着重于多状态问题的处理&#xff0c;各状态之间会有一定联系&#xff0c;状态转移方程将不再局限一个。 买卖股票的最佳时机1 int maxProfit(…

详细对比超融合服务器硬件平滑升级方案:新建集群 VS 滚动升级

作者&#xff1a;深耕行业的金融团队 刘慧敏 在企业 IT 基础架构运维中&#xff0c;经常会遇到以下问题&#xff0c;从而需要对服务器硬件进行更换或升级&#xff1a; 服务器达到维护期限&#xff1a;通常在金融行业中&#xff0c;生产环境的服务器维护期限在 5 年左右&#…

三十七个常见Vue面试题,背就完事了二

八、vue.mixin的使用场景和原理? Vue的mixin的作用就是抽离公共的业务逻辑&#xff0c;原理类似对象的继承&#xff0c;当组件初始化的时候&#xff0c;会调用mergeOptions方法进行合并&#xff0c;采用策略模式针对不同的属性进行合并。 如果混入的数据和本身组件的数据有冲突…

《向量数据库》——为何向量数据库对大模型LLM很重要?

当您浏览Twitter、LinkedIn或新闻源上的时间轴时,可能会看到一些关于聊天机器人、LLM和GPT的内容。因为每周都有新的LLM发布,很多人都在谈论LLM。 我们目前置身于一场人工智能革命,许多新应用都依赖于向量嵌入。不妨让我们更多地了解向量数据库以及为什么它们对LLM很重要。…

图书管理系统Java书店进销存jsp源代码MySQL

本项目为前几天收费帮学妹做的一个项目&#xff0c;Java EE JSP项目&#xff0c;在工作环境中基本使用不到&#xff0c;但是很多学校把这个当作编程入门的项目来做&#xff0c;故分享出本项目供初学者参考。 一、项目描述 图书管理系统 系统有1权限&#xff1a;管理员 用所技…

产能紧张,联电、日月光急单要涨价 | 百能云芯

台积电在CoWoS先进封装领域的产能紧张&#xff0c;这导致英伟达在AI芯片方面的生产受到限制。有消息称&#xff0c;英伟达正考虑通过加价寻找除台积电以外的替代生产能力&#xff0c;以应对这一局面。这一消息引发了巨大的订单涌入效应。 联电公司作为提供CoWoS中间层材料的供应…

Android开发血动脉——Binder机制

Binder是Android中的一个类&#xff0c;它继承了IBinder接口。从IPC角度来说&#xff0c;Binder是Android中的一种跨进程通信方式&#xff0c;Binder还可以理解为一种虚拟的物理设备&#xff0c;它的设备驱动是/dev/binder&#xff0c;该通信方式在linux中没有。从Android Fram…

什么是OLAP

一、什么是OLAP OLAP&#xff08;On-line Analytical Processing&#xff0c;联机分析处理&#xff09;是在基于数据仓库多维模型的基础上实现的面向分析的各类操作的集合。可以比较下其与传统的OLTP&#xff08;On-line Transaction Processing&#xff0c;联机事务处理&…