归并排序-面试例子
小数和问题
描述
在一个数组中,一个数左边比它小的数的总和,叫数的小和,所有数的小和累加起来,叫数组小和。求数组小和。
例子
5 2 6 1 7 小和原始的求法是:任何一个数左边比它小的数累加起来。 5左边比它小数累加:0 2左边比它小数累加:0 6左边比它小数累加:5 + 2 = 7 1左边比它小数累加:0 7左边比它小数累加:5 + 2 + 6 + 1 = 14 总共21。
思路
如果左侧某数a比右侧某数b小,则在求b的小和的时候,肯定会累加一个a,即sum+=a。 反过来,在遍历到a的时候,如果我们知道右侧有几个数比a大,则可以提前知道会累加几个a 使用归并排序时恰好有左右对比操作,所以使用归并排序来做 即: 每个数右边比它大的数的个数 * 这个数自身 所以: 在原来归并排序的基础上,增加一个ans用于记录结果 在进行归并时左侧<右侧时产生小数 n * number
小和求法还可以是:每个数右边比它大的数的个数 * 这个数自身5 2 6 1 7 5的右边比它大的数的个数:2个(6和7),所以产生:2个 * 5 = 10 2的右边比它大的数的个数:2个(6和7),所以产生:2个 * 2 = 4 6的右边比它大的数的个数:1个(7),所以产生:1个 * 6 = 6 1的右边比它大的数的个数:1个(7),所以产生:1个 * 1 = 1 7的右边比它大的数的个数:0个,所以产生:0个 * 7 = 0 总共21。
code
非递归
public static int smallSum(int [] arr){if(arr == null || arr.length <2)return 0;int [] help = new int[arr.length];int step = 1;int N = arr.length;int L = 0;int ans = 0;while (step < N){L = 0;while (L < N){//左组最后一个数位置int m = L + step - 1;if(m >= N){break;}if(step >= N - L){break;}int R = Math.min(m+step,N-1);ans += merge(arr,L,m,R,help);L = R + 1;}if(step > N/2){break;}step <<= 1;}return ans;}public static int merge(int[] arr,int l,int m,int r,int [] help){//help indexint i = 0;//p1 左侧开始index,p2 右侧开始indexint p1 = l;int p2 = m+1;//结果保存int ans = 0;while (p1 <= m && p2 <= r){ans += arr[p1]<arr[p2]?arr[p1] *(r-p2+1):0;help[i++] = arr[p1]<arr[p2]?arr[p1++]:arr[p2++];}while (p1 <= m){help[i++] = arr[p1++];}while (p2 <= r){help[i++] = arr[p2++];}for (i = 0; i < r-l+1 ; i++) {arr[l+i] = help[i];}return ans;}
递归
public static int progress(int [] arr,int l,int r,int [] help){if(l == r)return 0;int m = l + ((r -l) >> 1);return progress(arr,l,m,help)+ progress(arr,m+1,r,help)+ merge(arr,l,m,r,help);}
逆序对问题
描述
一个数组中,左边的数比右边的数大,求有多少个这样的组合
比如 [3,1,0,4,3,1] 有7个逆序对,分别是
(3,1),(3,0),(3,1)
(1,0)
(4,3),(4,1)
(3,1)
code
//递归public static int reversePair(int [] arr){if(arr == null || arr.length <2)return 0;return progress(arr,0,arr.length -1);}public static int progress(int [] arr,int l,int r){if(l == r)return 0;int m = l + ((r-l)>>1);return progress(arr,l,m)+progress(arr,m+1,r)+merge(arr,l,m,r);}//非递归public static int reversePair2(int [] arr){if(arr == null || arr.length < 2)return 0;int ans = 0;int L = 0;int N = arr.length;int step = 1;while (step < N){L = 0;while (L < N){if(L+step >= N)break;int m = L + step - 1;if(m >= N)break;int r = Math.min(N-1,m+step);int temp = merge(arr,L,m,r);ans += temp;L = r + 1;}if(step > N/2)break;step <<= 1;}return ans;}public static int merge(int [] arr,int L,int M,int R){// 先算有多少逆序对// 和归并过程分离int res = 0;int p = M + 1;for (int i = L; i <= M; i++) {while (p <= R && arr[i] > arr[p]) {p++;}res += p - (M + 1);}// 下面完全和归并排序一样int[] help = new int[R - L + 1];int i = 0;int p1 = L;int p2 = M + 1;while (p1 <= M && p2 <= R) {help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];}// 要么p1越界了,要么p2越界了while (p1 <= M) {help[i++] = arr[p1++];}while (p2 <= R) {help[i++] = arr[p2++];}for (i = 0; i < help.length; i++) {arr[L + i] = help[i];}return res;}
左边大于右边倍数的数
描述
在一个数组中, 对于每个数num,求有多少个后面的数 * 2 依然<num,求总个数 比如:[3,1,7,0,2] 3的后面有:1,0 1的后面有:0 7的后面有:0,2 0的后面没有 2的后面没有 所以总共有5个
思路
右边有多少个数*2比左边的数小 在归并排序过程中,分组后左侧有序,右侧有序,在进行左右侧合并时,统计验证关系【2倍关系】 这样可以得到该左侧位置相对于右侧位置的2倍关系统计和
code
//递归public static int biggerThatRightTwice(int []arr){if(arr == null || arr.length<2){return 0;}return progress(arr,0,arr.length-1);}public static int progress(int[] arr,int l,int r){if(l == r){return 0;}int m = l + ((r-l)>>1);System.out.println("l,m,r:"+l+","+m+","+r);return progress(arr,l,m)+progress(arr,m+1,r)+merge(arr,l,m,r);}//非递归public static int biggerThatRightTwice2(int [] arr){if(arr == null || arr.length <2)return 0;int L = 0;int step = 1;int N = arr.length;int ans = 0;while (step < N){L = 0;while (L < N){if(step >= N-L)break;int m = L + step - 1;if(m >= N)break;int r = Math.min(m+step,N-1);ans += merge(arr,L,m,r);L = r + 1;}if(step > N/2)break;step <<=1;}return ans;}public static int merge(int[] arr,int l,int m,int r){//[l,m] [m+1,r]进行归并,其中[l,m],[m+1,r]分别已经有序//先计算int p1 = l,p2 = m+1;int ans = 0;//左侧遍历lwhile (p1 <= m){//右侧遍历while (p2 <= r){//如果左侧 > 右侧 * 2,则继续判断,知道不满足条件//当不满足条件时,则右侧从开始位置m+1到p2位置为p1满足条件的数if(arr[p1] > arr[p2] *2){p2++;}else{break;}}//p2 - (m+1) => [m+1,p2) 即从m+1到p2个元素个数,不包含p2ans += (p2 - (m+1));p1++;}//再进行归并int [] help = new int[r-l+1];int i = 0;p1 = l;p2 = m+1;while (p1<=m && p2<=r){help[i++] = arr[p1]<arr[p2]?arr[p1++]:arr[p2++];}while (p1<=m){help[i++] = arr[p1++];}while (p2<=r){help[i++] = arr[p2++];}for(i=0;i<help.length;i++){arr[l+i] = help[i];}return ans;}
相关文章:
归并排序-面试例子
小数和问题 描述 在一个数组中,一个数左边比它小的数的总和,叫数的小和,所有数的小和累加起来,叫数组小和。求数组小和。 例子 5 2 6 1 7 小和原始的求法是:任何一个数左边比它小的数累加起来。 5左边比它小数累加…...

docker 生成镜像的几个问题
docker 生成镜像的几个问题 根据jdk8.tar.gz 打包Jdk8 镜像失败运行镜像报错差不多是网络ip错误,在网上说重启docker即可解决运行mysql5.7.25 镜像失败向daemon.json文件添加内容导致docker重启失败docker run 命令常用参数根据jdk8.tar.gz 打包Jdk8 镜像失败 首选做准备工作…...

云计算时代的采集利器
大家好!在今天的知识分享中,我们将探讨一个在云计算环境中的爬虫应用利器——独享IP。如果你是一名爬虫程序员,或者对数据采集和网络爬虫有浓厚的兴趣,那么这篇文章将向你展示独享IP在云计算环境下的应用价值。 1. 什么是独享IP&…...

【Unity编辑器扩展】| Inspector监视器面板扩展
前言【Unity编辑器扩展】| Inspector监视器面板扩展一、ContextMenu和ContextMenuItem二、Custom Editors 自定义编辑器三、Property Drawer 属性绘制器总结前言 前面我们介绍了Unity中编辑器扩展的一些基本概念及基础知识,还有编辑器扩展中用到的相关特性Attribute介绍。后面…...

Redis配置
关系型数据库和非关系型数据库 ①了解关系和非关系 关系型数据库 一个结构化的数据库,创建在关系模型基础上,一般面向于记录,包括Oracle、MySQL、SQL Server、Microsoft Access、DB2、postgreSQL等 非关系型数据库 除了主流的关系型数据库…...
CSDN每日一练 |『小艺照镜子』『Ctrl+X,Ctrl+V』『括号上色』2023-09-11
CSDN每日一练 |『小艺照镜子』『Ctrl+X,Ctrl+V』『括号上色』2023-09-11 一、题目名称:小艺照镜子二、题目名称:Ctrl+X,Ctrl+V三、题目名称:括号上色一、题目名称:小艺照镜子 时间限制:1000ms内存限制:256M 题目描述: 已知字符串str。 输出字符串str中最长回文串的长度…...

React 全栈体系(四)
第二章 React面向组件编程 六、组件的生命周期 1. 效果 需求:定义组件实现以下功能: 让指定的文本做显示 / 隐藏的渐变动画从完全可见,到彻底消失,耗时2S点击“不活了”按钮从界面中卸载组件 <!DOCTYPE html> <html lang"e…...
各种UI库使用总结
各种UI库使用总结 工作了这么年,使用了一些UI库,简单的总结一下,UI库也是五花八门,根据自己的产品,应用场景吧,没有绝对合适的,各有各的应用场景吧! QT 这几年前后在一些嵌入式上…...

2023Web前端开发面试手册
HTML基础 1. HTML 文件中的 DOCTYPE 是什么作用? HTML超文本标记语言: 是一个标记语言, 就有对应的语法标准 DOCTYPE 即 Document Type,网页文件的文档类型标准。 主要作用是告诉浏览器的解析器要使用哪种 HTML规范 或 XHTML规范…...

一文了解数据科学Notebook
编者按: 主要介绍什么是Notebook,Notebook在数据科学领域的应用的重要性与优势,以及数据科学家/算法团队在选择Notebook时需考虑哪些关键因素。同时,基于Notebook的筛选考量维度,对常见的Notebook进初步对比分析&#…...

2020年12月 C/C++(二级)真题解析#中国电子学会#全国青少年软件编程等级考试
C/C++编程(1~8级)全部真题・点这里 第1题:数组指定部分逆序重放 将一个数组中的前k项按逆序重新存放。例如,将数组8,6,5,4,1前3项逆序重放得到5,6,8,4,1。 时间限制:1000 内存限制:65536 输入 输入为两行: 第一行两个整数,以空格分隔,分别为数组元素的个数n(1 < n…...

关于ChatGPT的个人的一些观点
问题 1 Q: 你认为ChatGPT是一款非常有用的工具吗? A: 我认为ChatGPT是一款非常有用的工具。它可以帮助人们解决各种问题,包括技术问题、心理问题、生活问题等等。同时,ChatGPT也可以成为人们分享想法和交流的平台,增强人与人之间…...

Solidity 小白教程:13. 继承
Solidity 小白教程:13. 继承 这一讲,我们介绍solidity中的继承(inheritance),包括简单继承,多重继承,以及修饰器(modifier)和构造函数(constructorÿ…...

队列(Queue)的顶级理解
目录 1.队列(Queue) 的概念 2.单链表模拟实现队列 2.1创建队列 2.2入队列 2.3判断是否为空 2.4出队列 2.5获取队头元素 2.6完整代码: 2.7双向链表模拟实现队列代码 3.数组模拟实现队列代码 3.1创建队列 3.2判断是否为满 3.3检查是否为空 3.4插入元素 3…...

选择 Guava EventBus 还是 Spring Framework ApplicationEvent
文章首发地址 Spring Framework ApplicationEvent Spring Framework 的 ApplicationEvent 是 Spring 框架提供的一种事件机制,用于实现发布和订阅事件的功能。它基于观察者模式,允许应用程序内的组件之间进行松耦合的通信。 下面是关于 Spring Frame…...

Linux下go环境安装、环境配置并执行第一个go程序
一、安装 1.Golang对Linux的内核版本要求 GO对Linux内核版本最低要求是 2.6.23,对应要求操作系统版本是: RHEL 6.0CentOS 6.0即,不支持 (RHEL 和 CentOS) 的 (4.x or 5.x)。2.下载golang的代码版本 Golang的官网下载地址:https:…...
自定义Dynamics 365实施和发布业务解决方案 - 5. 高级自定义
本章的目的是探索可应用于Dynamics365的高级自定义。这包括使用插件和自定义工作流活动实现复杂的业务流程。此外,您还将了解如何使用SPKL任务运行器来部署这些,这在第2章中进行了讨论。最后,您还将看到使用Web API查询数据。 准备工作 若要从高级自定义开始,必须首先创建…...

软件测试下的AI之路(2)
😏作者简介:博主是一位测试管理者,同时也是一名对外企业兼职讲师。 📡主页地址:【Austin_zhai】 🙆目的与景愿:旨在于能帮助更多的测试行业人员提升软硬技能,分享行业相关最新信息。…...
前端面试的话术集锦第 7 篇:高频考点(浏览器渲染原理 安全防范)
这是记录前端面试的话术集锦第七篇博文——高频考点(浏览器渲染原理 & 安全防范),我会不断更新该博文。❗❗❗ 1. 浏览器渲染原理 注意:该章节都是⼀个⾯试题。 1.1 渲染过程 1.1.1 浏览器接收到HTML⽂件并转换为DOM树 当我们打开⼀个⽹⻚时,浏览器都会去请求对应的…...

打印剪刀手“耶”(V形)
用给定单个字符和首行宽度(奇数), 打印首行宽度为给定奇数“V”字形状)。 (本笔记适合Py 推崇的插件字符串格式化的 coder 翻阅) 【学习的细节是欢悦的历程】 Python 官网:https://www.python.org/ Free:大咖免费“圣经”教程《 python 完全…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...

Docker 离线安装指南
参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性,不同版本的Docker对内核版本有不同要求。例如,Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本,Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

vscode(仍待补充)
写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh? debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略
本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装;只需暴露 19530(gRPC)与 9091(HTTP/WebUI)两个端口,即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

AI书签管理工具开发全记录(十九):嵌入资源处理
1.前言 📝 在上一篇文章中,我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源,方便后续将资源打包到一个可执行文件中。 2.embed介绍 🎯 Go 1.16 引入了革命性的 embed 包,彻底改变了静态资源管理的…...
LeetCode - 199. 二叉树的右视图
题目 199. 二叉树的右视图 - 力扣(LeetCode) 思路 右视图是指从树的右侧看,对于每一层,只能看到该层最右边的节点。实现思路是: 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

使用LangGraph和LangSmith构建多智能体人工智能系统
现在,通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战,比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...
Mysql8 忘记密码重置,以及问题解决
1.使用免密登录 找到配置MySQL文件,我的文件路径是/etc/mysql/my.cnf,有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...
学习一下用鸿蒙DevEco Studio HarmonyOS5实现百度地图
在鸿蒙(HarmonyOS5)中集成百度地图,可以通过以下步骤和技术方案实现。结合鸿蒙的分布式能力和百度地图的API,可以构建跨设备的定位、导航和地图展示功能。 1. 鸿蒙环境准备 开发工具:下载安装 De…...