暑假算法刷题日记 Day 10

目录

重点整理

054、 拼数

题目描述

输入格式

输出格式

输入输出样例

核心思路

代码

055、 求第k小的数

题目描述

输入格式

输出格式

输入输出样例

核心思路

代码

总结


这几天我们主要刷了洛谷上排序算法对应的一些题目,相对来说比较简单

一共是13道题,对应我暑假刷题的043--055。当然这些题目相对来说比较简单,我们挑着重点的说。

重点整理

排序这一块的题目总体来看包括,

1. 基本的排序算法,像快速排序、分治排序,这些知识点我写了专门的博客,欢迎大家阅读

快速排序、归并排序

2. 结构题的多因素、自定义排序规则。Java实现自定义排序

3. 特殊问题

针对这个特殊问题,我们就题目来说

054、 拼数

题目描述

设有 nn 个正整数 a1…ana1​…an​,将它们联接成一排,相邻数字首尾相接,组成一个最大的整数。

输入格式

第一行有一个整数,表示数字个数 nn。

第二行有 nn 个整数,表示给出的 nn 个整数 aiai​。

输出格式

一个正整数,表示最大的整数

输入输出样例

输入 #1复制

3
13 312 343

输出 #1复制

34331213

输入 #2复制

4
7 13 4 246

输出 #2复制对于

7424613

核心思路

本质来看还是一个自定义排序规则,但是这个题巧妙之处就是自定义的排序规则是如何确定的。对于两个字符串,如果将比较规则定义为大的放前面,那对于 321,32,这个例子来说的话,大的放前面那就是32132,但是32321要更大。所以简单的大的放前面是不合适的。

如果我们把比较规则定义为 a+b大于b+a,那么a在前面,反之b在前面。这样就避免了这个问题。

代码

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();String s[] = new String[n];for (int i = 0; i < n; i++) {s[i] = sc.next();}Arrays.sort(s,new Comparator<String>() {public int compare(String o1, String o2) {return (o2+o1).compareTo(o1+o2);}});for (int i = 0; i < n; i++) {System.out.print(s[i]);}}
}

055、 求第k小的数

题目描述

输入 nn(1≤n<50000001≤n<5000000 且 nn 为奇数)个数字 aiai​(1≤ai<1091≤ai​<109),输出这些数字的第 kk 小的数。最小的数是第 00 小。

请尽量不要使用 nth_element 来写本题,因为本题的重点在于练习分治算法。

输入格式

输出格式

输入输出样例

输入 #1复制

5 1
4 3 2 1 5

输出 #1复制

2

核心思路

这个题看起来并没有什么难度,但是题目给的样例卡时间,最后两个数据量太大,经典的快排和归并都会超时间。

我们回顾一下快排的思路,确定枢轴的过程是实质上就是把这个元素放到其排序后的正确位置上去,其实就是把第k小的数放在下标为k的位置上,根据这个思路我们可以在快排的代码上做优化。

我们在快排的基础上,确定好枢轴位置后,判断该位置是否是k,是的话直接结束程序,不是的话继续往后,为了节约时间,我们只排序k所在的那个区间。

代码

#include <iostream>  
#include <vector>  
using namespace std;  const int N=5e6 +10;int nums[N];
void quickSort(int left, int right, int k) {  // 判断排序区间长度  if (right <= left) {  if (right == left && left == k) {  cout << nums[k] << endl;  exit(0);  }  return;  }  // 选择基准值(这里使用最左边的值)  int pivot = nums[left];  int i = left, j = right;  while (i < j) {  // 从右向左找到第一个小于等于pivot的元素  while (nums[j] >= pivot && i < j) j--;  // 交换  if (i < j) nums[i++] = nums[j];  // 从左向右找到第一个大于pivot的元素  while (nums[i] <= pivot && i < j) i++;  if (i < j) nums[j--] = nums[i];  }  nums[i] = pivot;  // 判断基准值是否为目标位置  if (i == k) {  cout << nums[k] << endl;  exit(0);  }  // 递归排序  if (k < i) quickSort(left, i - 1, k);  if (k > i) quickSort(i + 1, right, k);  
}  int main() {  int n, k;  cin >> n >> k;  for (int i = 0; i < n; i++) {  scanf("%d",&nums[i]);  }  quickSort( 0, n - 1, k); return 0;  
}

总结

排序还是非常博大精深的,希望在后续的学习中不断精进!

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

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

相关文章

2024最新急速暴走小米运动自动刷步卡密版PHP源码

2023最新发布的急速暴走小米运动自动刷步卡密版PHP源码。该源码使用PHPTP6layui-Mini开发&#xff0c;旨在实现小米运动自动刷步功能。该程序支持通过微信修改步数&#xff0c;并采用卡密认证方式&#xff0c;用户只需提交提供的卡密&#xff0c;即可每日自助修改步数。 需要注…

Android 12系统源码_屏幕设备(二)DisplayAdapter和DisplayDevice的创建

前言 在Android 12系统源码_屏幕设备&#xff08;一&#xff09;DisplayManagerService的启动这篇文章中我们具体分析了DisplayManagerService 的启动流程&#xff0c;本篇文章我们将在这个的基础上具体来分析下设备屏幕适配器的创建过程。 一、注册屏幕适配器 系统是在Disp…

机器学习预处理

一、数据读取 数据的读取方式有多种&#xff0c;最终我们可以转化为numpy和pandas形式储存&#xff0c;方便后续的模型建立。 1.1 读取库的安装 需要用到的三个库 pip install pandas pip install numpy pip install openpyxl 1.2 库的使用 import pandas as pd ​ #### 1…

【故障处理】- ping不通的原因

PING不通是一个非常常见的网络问题&#xff0c;它可能由多种原因引起。如链路故障、ARP学习失败等 以一个Ping不通的尝试示例&#xff0c;介绍Ping不通故障的定位思路。如下图&#xff1a; PC3 Ping不通PC4 PC>ping 20.1.1.20Ping 20.1.1.20: 32 data bytes, Press Ctrl_C…

亚马逊铺货ERP国内采集,图片编辑文本翻译一键拉伸,自...

亚马逊全功能 ERP 铺货采集&#xff0c;自动生成 SKU。 说说国内平台采集的商品如何通过 ERP 自己做链接上传发布到亚马逊平台&#xff01; 1. 首先进入 ERP 插件&#xff0c;直接点击 1688 平台采集自己想做的产品类型。各位按照自身的需求选择搜索的 JK&#xff0c;选择想采…

【GH】【EXCEL】P1: Write DATA SET from GH into EXCEL

文章目录 WriteFast WriteGH data material :GH process and components instructionFast Write DataFast Write Data & Clear DataFast Write to Cell EXCEL written results Write by ColumnGH data material :Compile ColumnGH process and components instructionWrite…

Redis RDB三两事

rdb&#xff1a;将数据库的快照以二进制格式保存在文件中&#xff0c;redis重启后直接加载数据。可以通过save和bgsave命令生成rdb。当然我们可以在生成rdb文件时指定规则&#xff0c;例如 save 60 1000 如果60秒内不少于1000个key发生了改动&#xff0c;则生成一个新的rdb文件…

如何在C++ QT 程序中集成cef3开源浏览器组件去显示网页?

目录 1、问题描述 2、为什么选择cef3浏览器组件 3、cef3组件的介绍与下载 4、将cef3组件封装成sdk 5、如何使用cef3组件加载web页面 5.1、了解CefApp与CefClient 5.2、初始化与消息循环 5.3、如何创建浏览器 5.4、重载CefClient类 6、在qt客户端集成cef组件 7、最后…

什么是主机加固?主机加固的几种有效方法

在数字化时代&#xff0c;数据的价值不言而喻&#xff0c;但随之而来的安全威胁也日益严峻。从勒索病毒到内部泄露&#xff0c;企业的数据安全面临着前所未有的挑战。为了应对这些挑战&#xff0c;一种全新的主机加固解决方案应运而生。 MCK主机加固解决方案&#xff0c;采用先…

Using Azure openAI key rotation automation

题意&#xff1a;使用 Azure OpenAI 密钥轮换自动化 问题背景&#xff1a; We are planning to do the Azure OpenAI key rotation automatically. How can we achieve this? Do we have terraform resource for this. 我们计划自动执行 Azure OpenAI 密钥轮换。我们如何实现…

运维小技能:通过调整JVM的默认内存配置来解决内存溢出(‌OutOfMemoryError)‌或栈溢出(‌StackOverflowError)‌等错误

文章目录 引言I 调整JVM的默认堆内存配置1.1 java命令启动jar包时配置JVM 的内存参数1.2 基于Tomcat服务器部署的java应用,配置JVM 的内存参数II 案例: Linux 操作系统设置tomcat的 JVM 的内存参数查找Tomcat位置: 快速定位服务状态和部署位置具体配置步骤扩展: 监测Nginx访…

Mysql查询日志

Mysql查询日志 Mysql查询日志默认是关闭状态的。 mysql> show variables like %general_log%; --------------------------------------- | Variable_name | Value | --------------------------------------- | general_log | OFF …

Python数分实战

学习视频&#xff1a;【课程3.0】Python基础与分析实战_哔哩哔哩_bilibili 由于学习过python进行数据分析&#xff0c;所以就简单记录一下&#xff0c;最主要学习的还是视频最后的两个项目&#xff0c;进行实战 之前想不明白明明有很智能的软件做数据分析&#xff0c;为什么还要…

C++票据查验、票据ocr、文字识别

现在&#xff0c;80、90后的人们逐渐过渡为职场上的主力人员&#xff0c;在工作中当然也会碰到各种各样的问题。比如&#xff0c;当你的老板给你一个艰难的任务时&#xff0c;肯定是不能直接拒绝的。那么我们该怎么做呢&#xff1f;翔云建议您先认真考虑老板说的任务的难度&…

倍福ADS通信教程

介绍 TwinCAT3 TwinCAT3是Beckhoff推出的一款基于PC的控制器软件&#xff0c;简单理解是一套集成开发环境&#xff0c;里边有各种分析工具以及通信中间件&#xff1b;开发者可以很方便的用它来进行IPC和PLC之间的通信连接 ADS 倍福ADS&#xff08;‌Automation Device Spec…

WebRTC音视频开发读书笔记(六)

数据通道不仅可以发送文本消息, 还可以发送图片、二进制文件,将其类型binaryType属性设置成arraybuffer类型即可. 九\、文件传输 1、文件传输流程 &#xff08;1&#xff09;使用表单file打开本地文件 &#xff08;2&#xff09;使用FileReader读取文件的二进制数据 &#…

零基础学习Redis(5) -- redis单线程模型介绍

前面我们提到过&#xff0c;redis是单线程的&#xff0c;这期我们详细介绍一下redis的单线程模型 1. redis单线程模型 redis只使用一个线程处理所有的请求&#xff0c;并不是redis服务器进程内部只有一个线程&#xff0c;其实也存在多个线程&#xff0c;只不过多个线程是在处…

SparkSQL遵循ANSI标准

ANSI简介 ANSI Compliance通常指的是遵循美国国家标准学会&#xff08;American National Standards Institute, ANSI&#xff09;制定的标准。在计算机科学和技术领域&#xff0c;这通常涉及到数据库管理系统&#xff08;DBMS&#xff09;对于SQL语言的支持程度。 ANSI为SQL…

基于vue框架的爱学习分享平台ud317(程序+源码+数据库+调试部署+开发环境)系统界面在最后面。

系统程序文件列表 项目功能&#xff1a;用户,学科分类,交流答疑,论坛交流,学习资料 开题报告内容 基于Vue框架的爱学习分享平台 开题报告 一、项目背景与意义 随着互联网技术的飞速发展&#xff0c;知识的获取与传播方式正经历着前所未有的变革。在线教育平台逐渐成为满足…

如何理解:进程控制

文章目录 前言&#xff1a;进程创建&#xff1a;进程终止&#xff1a;如何终止进程&#xff1f;进程等待非阻塞等待&#xff1a; 总结&#xff1a; 前言&#xff1a; ​ 对于前面的地址空间的学习&#xff0c;我们现在了解到原来所谓变量的地址其实是虚拟地址&#xff0c;该虚…