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

归并排序-面试例子

小数和问题

描述
在一个数组中,一个数左边比它小的数的总和,叫数的小和,所有数的小和累加起来,叫数组小和。求数组小和。
例子
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;}

相关文章:

归并排序-面试例子

小数和问题 描述 在一个数组中&#xff0c;一个数左边比它小的数的总和&#xff0c;叫数的小和&#xff0c;所有数的小和累加起来&#xff0c;叫数组小和。求数组小和。 例子 5 2 6 1 7 小和原始的求法是&#xff1a;任何一个数左边比它小的数累加起来。 5左边比它小数累加…...

docker 生成镜像的几个问题

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

云计算时代的采集利器

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

【Unity编辑器扩展】| Inspector监视器面板扩展

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

Redis配置

关系型数据库和非关系型数据库 ①了解关系和非关系 关系型数据库 一个结构化的数据库&#xff0c;创建在关系模型基础上&#xff0c;一般面向于记录&#xff0c;包括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. 效果 需求:定义组件实现以下功能&#xff1a; 让指定的文本做显示 / 隐藏的渐变动画从完全可见&#xff0c;到彻底消失&#xff0c;耗时2S点击“不活了”按钮从界面中卸载组件 <!DOCTYPE html> <html lang"e…...

各种UI库使用总结

各种UI库使用总结 工作了这么年&#xff0c;使用了一些UI库&#xff0c;简单的总结一下&#xff0c;UI库也是五花八门&#xff0c;根据自己的产品&#xff0c;应用场景吧&#xff0c;没有绝对合适的&#xff0c;各有各的应用场景吧&#xff01; QT 这几年前后在一些嵌入式上…...

2023Web前端开发面试手册

​​​​​​​​ HTML基础 1. HTML 文件中的 DOCTYPE 是什么作用&#xff1f; HTML超文本标记语言: 是一个标记语言, 就有对应的语法标准 DOCTYPE 即 Document Type&#xff0c;网页文件的文档类型标准。 主要作用是告诉浏览器的解析器要使用哪种 HTML规范 或 XHTML规范…...

一文了解数据科学Notebook

编者按&#xff1a; 主要介绍什么是Notebook&#xff0c;Notebook在数据科学领域的应用的重要性与优势&#xff0c;以及数据科学家/算法团队在选择Notebook时需考虑哪些关键因素。同时&#xff0c;基于Notebook的筛选考量维度&#xff0c;对常见的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是一款非常有用的工具吗&#xff1f; A: 我认为ChatGPT是一款非常有用的工具。它可以帮助人们解决各种问题&#xff0c;包括技术问题、心理问题、生活问题等等。同时&#xff0c;ChatGPT也可以成为人们分享想法和交流的平台&#xff0c;增强人与人之间…...

Solidity 小白教程:13. 继承

Solidity 小白教程&#xff1a;13. 继承 这一讲&#xff0c;我们介绍solidity中的继承&#xff08;inheritance&#xff09;&#xff0c;包括简单继承&#xff0c;多重继承&#xff0c;以及修饰器&#xff08;modifier&#xff09;和构造函数&#xff08;constructor&#xff…...

队列(Queue)的顶级理解

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

选择 Guava EventBus 还是 Spring Framework ApplicationEvent

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

Linux下go环境安装、环境配置并执行第一个go程序

一、安装 1.Golang对Linux的内核版本要求 GO对Linux内核版本最低要求是 2.6.23&#xff0c;对应要求操作系统版本是&#xff1a; RHEL 6.0CentOS 6.0即&#xff0c;不支持 (RHEL 和 CentOS) 的 (4.x or 5.x)。2.下载golang的代码版本 Golang的官网下载地址&#xff1a;https:…...

自定义Dynamics 365实施和发布业务解决方案 - 5. 高级自定义

本章的目的是探索可应用于Dynamics365的高级自定义。这包括使用插件和自定义工作流活动实现复杂的业务流程。此外,您还将了解如何使用SPKL任务运行器来部署这些,这在第2章中进行了讨论。最后,您还将看到使用Web API查询数据。 准备工作 若要从高级自定义开始,必须首先创建…...

软件测试下的AI之路(2)

&#x1f60f;作者简介&#xff1a;博主是一位测试管理者&#xff0c;同时也是一名对外企业兼职讲师。 &#x1f4e1;主页地址&#xff1a;【Austin_zhai】 &#x1f646;目的与景愿&#xff1a;旨在于能帮助更多的测试行业人员提升软硬技能&#xff0c;分享行业相关最新信息。…...

前端面试的话术集锦第 7 篇:高频考点(浏览器渲染原理 安全防范)

这是记录前端面试的话术集锦第七篇博文——高频考点(浏览器渲染原理 & 安全防范),我会不断更新该博文。❗❗❗ 1. 浏览器渲染原理 注意:该章节都是⼀个⾯试题。 1.1 渲染过程 1.1.1 浏览器接收到HTML⽂件并转换为DOM树 当我们打开⼀个⽹⻚时,浏览器都会去请求对应的…...

打印剪刀手“耶”(V形)

用给定单个字符和首行宽度(奇数)&#xff0c; 打印首行宽度为给定奇数“V”字形状)。 (本笔记适合Py 推崇的插件字符串格式化的 coder 翻阅) 【学习的细节是欢悦的历程】 Python 官网&#xff1a;https://www.python.org/ Free&#xff1a;大咖免费“圣经”教程《 python 完全…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

c#开发AI模型对话

AI模型 前面已经介绍了一般AI模型本地部署&#xff0c;直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型&#xff0c;但是目前国内可能使用不多&#xff0c;至少实践例子很少看见。开发训练模型就不介绍了&am…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...

GitHub 趋势日报 (2025年06月06日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...