西藏建设厅官方网站一体化/举例说明什么是seo
题目链接
Leetcode.321 拼接最大数
hard
题目描述
给定长度分别为 m m m 和 n n n 的两个数组,其元素由 0 ∼ 9 0 \sim 9 0∼9 构成,表示两个自然数各位上的数字。现在从这两个数组中选出 k k k ( k ≤ m + n ) (k \leq m + n) (k≤m+n) 个数字拼接成一个新的数,要求从同一个数组中取出的数字保持其在原数组中的相对顺序。
求满足该条件的最大数。结果返回一个表示该最大数的长度为 k k k 的数组。
说明: 请尽可能地优化你算法的时间和空间复杂度。
示例 1:
输入:
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
输出:
[9, 8, 6, 5, 3]
示例 2:
输入:
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
输出:
[6, 7, 6, 0, 4]
示例 3:
输入:
nums1 = [3, 9]
nums2 = [8, 9]
k = 3
输出:
[9, 8, 9]
解法:单调栈
我们假设由 k k k 个元素组成的最大数,其中有 x x x 个元素来自 n u m s 1 nums1 nums1,那么就有 k − x k - x k−x 个元素来自 n u m s 2 nums2 nums2。
我们定义 m a x _ s e q u e n c e ( S , m ) max\_sequence(S,m) max_sequence(S,m) 表示从集合 S S S 中,选出 m m m 个元素构成的最大数(元素之间要保持在集合 S S S 中的相对位置)。
- s 1 = m a x _ s e q u e n c e ( n u m s 1 , x ) s1 = max\_sequence(nums1,x) s1=max_sequence(nums1,x), s 1 s1 s1 表示从集合 n u m s 1 nums1 nums1 中选出 x x x 个元素组成的最大数;
- s 2 = m a x _ s e q u e n c e ( n u m s 2 , k − x ) s2 = max\_sequence(nums2,k-x) s2=max_sequence(nums2,k−x), s 2 s2 s2 表示从集合 n u m s 2 nums2 nums2 中选出 k − x k-x k−x 个元素组成的最大数;
我们最后再将 s 1 s1 s1 和 s 2 s2 s2 拼接成一个最大数 S S S,那么这个 S S S 就是答案之一。所以我们就要遍历 x x x ,求出所有的 S S S,最后返回最大的那个。
在实现上:
m a x _ s e q u e n c e ( S , m ) max\_sequence(S,m) max_sequence(S,m) 可以利用单调栈实现:
- 如果 S . s i z e ( ) ≤ m S.size() \leq m S.size()≤m,那么直接返回集合 S S S 即可;
- 我们定义一个栈 s t k stk stk,因为我们要返回的是 m m m 个元素组成的最大数,也就是说 s t k stk stk 最终有 m m m 个元素,即 s t k stk stk 能够弹出去的元素最多只有 d e l = S . s i z e ( ) − m del = S.size() - m del=S.size()−m 个。
- 假设当前遍历到的元素为 x x x,如果 x > s t k . t o p ( ) x > stk.top() x>stk.top() 并且 d e l > 0 del > 0 del>0,那么就可以弹出栈顶元素,因为我们要是 s t k stk stk 中的数字典序尽可能的大。
- 最终返回 s t k stk stk 即可。需要注意的是:如果 S S S 中所有元素都相同 或者 S S S 是一个非降序的序列,那么 s t k stk stk 中就没有弹出的元素,一共就有 S . s i z e ( ) S.size() S.size() 个元素,我们只需要前 m m m 个即可。
在这里需要介绍一个 STL algorithm 库的函数 lexicographical_compare(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2)
template<class InputIt1, class InputIt2>
bool lexicographical_compare(InputIt1 first1, InputIt1 last1,InputIt2 first2, InputIt2 last2)
{for (; (first1 != last1) && (first2 != last2); ++first1, (void) ++first2){if (*first1 < *first2)return true;if (*first2 < *first1)return false;}return (first1 == last1) && (first2 != last2);
}
上述这个函数的作用是:判断区间一 [ f i r s t 1 , l a s t 1 ) [first1,last1) [first1,last1) 字典序是否不大于 区间二 [ f i r s t 2 , l a s t 2 ) [first2,last2) [first2,last2)。
- 是的话,最终返回
true
; - 否,返回
false
;
时间复杂度: O ( m + n + k 2 ) O(m + n + k^2) O(m+n+k2)
C++代码:
class Solution {
public:vector<int> max_sequence(vector<int> vec,int k){int n = vec.size();if(n <= k) return vec;vector<int> stk;int del = n - k;for(int i = 0;i < n;i++){while(stk.size() && vec[i] > stk.back() && del){del--;stk.pop_back();}stk.push_back(vec[i]);}stk.resize(k);return stk;}vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {int m = nums1.size() , n = nums2.size();vector<int> res(k,0);for(int x = max(0,k - n);x <= min(k,m);x++){vector<int> temp;auto s1 = max_sequence(nums1,x);auto s2 = max_sequence(nums2,k - x);auto it1 = s1.begin() , it2 = s2.begin();while(it1 != s1.end() || it2 != s2.end()){temp.push_back(lexicographical_compare(it1,s1.end(),it2,s2.end() )? *it2++ : *it1++);}res = lexicographical_compare(res.begin(),res.end(),temp.begin(),temp.end()) ? move(temp) : res;}return res;}
};
相关文章:

Leetcode.321 拼接最大数
题目链接 Leetcode.321 拼接最大数 hard 题目描述 给定长度分别为 m m m 和 n n n 的两个数组,其元素由 0 ∼ 9 0 \sim 9 0∼9 构成,表示两个自然数各位上的数字。现在从这两个数组中选出 k k k ( k ≤ m n ) (k \leq m n) (k≤mn) 个数字拼接成…...

数学建模竞赛常用代码总结-PythonMatlab
数学建模过程中有许多可复用的基础代码,在此对 python 以及 MATLAB 中常用代码进行简单总结,该总结会进行实时更新。 一、文件读取 python (pandas) 文件后缀名(扩展名)并不是必须的,其作用主要一方面是提示系统是用…...

在Ubuntu上安装CUDA和cuDNN以及验证安装步骤
在Ubuntu上安装CUDA和cuDNN以及验证安装步骤 本教程详细介绍了如何在Ubuntu操作系统上安装CUDA(NVIDIA的并行计算平台)和cuDNN(深度神经网络库),以及如何验证安装是否成功。通过按照这些步骤操作,您将能够…...

SecureCRT ssh链接服务器
SecureCRT通过密钥进行SSH登录 说明: 一般的密码方式登录容易被密码暴力破解。所以一般我们会将 SSH 的端口设置为默认22以外的端口,或者禁用root账户登录。其实可以通过密钥登录这种方式来更好地保证安全。 密钥形式登录的原理是:利用密钥…...

linux之perf(3)top实时性能
Linux之perf(3)top实时性能 Author:Onceday Date:2023年9月3日 漫漫长路,才刚刚开始… 注:该文档内容采用了GPT4.0生成的回答,部分文本准确率可能存在问题。 参考文档: Tutorial - Perf Wiki (kernel.org)perf-to…...

【linux命令讲解大全】076.pgrep命令:查找和列出符合条件的进程ID
文章目录 pgrep补充说明语法选项参数实例 从零学 python pgrep 根据用户给出的信息在当前运行进程中查找并列出符合条件的进程ID(PID) 补充说明 pgrep 命令以名称为依据从运行进程队列中查找进程,并显示查找到的进程ID。每一个进程ID以一个…...

微信小程序开发---条件渲染和列表渲染
目录 一、条件渲染 (1)基本使用 (2)block (3)hidden 二、列表渲染 (1)基本使用 (2)手动指定索引和当前项的变量名 (3)wx:key的…...

【ES6】require、export和import的用法
在JavaScript中,require、export和import是Node.js的模块系统中的关键字,用于处理模块间的依赖关系。 1、require:这是Node.js中引入模块的方法。当你需要使用其他模块提供的功能时,可以使用require关键字来引入该模块。例如&…...

Vue + Element UI 前端篇(九):接口格式定义
接口请求格式定义 前台显示需要后台数据,我们这里先把前后端交互接口定义好,没有后台的时候,也方便用mock模拟。 接口定义遵循几个规范: 1. 接口按功能模块划分。 系统登录:登录相关接口 用户管理:用户…...

部署Django报错-requires SQLite 3.8.3 or higher
记一次CentOS7部署Django项目时的报错 问题出现 在部署测试环境时,有需要用到一个python的后端服务,要部署到测试环境中去 心想这不是so easy吗,把本地调试时使用的python版本及Django版本在服务器上对应下载好,然后直接执行命…...

什么是网络存储服务器
网络存储器就像一台只有存储功能的终端,独立地工作,里面带有固定的系统,但可以自己设置部分参数功能,可以接入服务器或者电脑进行设置,网络存储服务器实际上就是精简的、小型化的服务器,同样由主板、CPU&am…...

lv3 嵌入式开发-10 NFS服务器搭建及使用
目录 1 NFS服务器介绍 1.1 NFS服务器的介绍 1.2 NFS服务器的特点 1.3 NFS服务器的适用场景 2 NFS服务器搭建 2.1 配置介绍 2.2 常见错误 3 WINDOWS下NFS服务器搭建(扩展) 1 NFS服务器介绍 1.1 NFS服务器的介绍 nfs(Network File Sys…...

后流量时代的跨境风口:Facebook广告
Facebook拥有超过25亿各个年龄段和人群的每月活跃用户,可以帮助您接触世界各地的相关消费者。无论您是需要吸引新的潜在客户还是吸引回头客访问您的在线商店,Facebook广告都可以为电子商务提供丰厚的投资回报;无论您是在沃尔玛、eBay、亚马逊…...

Java基础学习笔记-2
前言 在计算机编程领域,条件语句和控制流结构是构建程序逻辑的基本组成部分。它们允许程序员根据不同的条件执行不同的操作,从而使程序更加灵活和智能。本文将深入探讨Java编程语言中的条件语句和控制流,提供了一系列实用的示例和技巧&#…...

Mongodb 安装脚本(附服务器自启动)
shell脚本 #!/bin/bash #mail:xuelanchnet.com #function:auto install mongodb [ $(id -u) ! "0" ] && echo "Error: You must be root to run this script" && exit 1 logfile"/var/log/mongod_install.log" softdir"/s…...

yolov5的pytorch配置
1. conda create -n rdd38 python3.82、pip install torch1.8.0 torchvision0.9.0 torchaudio0.8.0 -f https://download.pytorch.org/whl/cu113/torch_stable.html -i https://pypi.tuna.tsinghua.edu.cn/simple 3、conda install cudatoolkit10.2...

ISO 19712-1-2008装饰用实体面材检测
实体面材是指由聚合物材料、填料和颜料组成,经浇筑或压制等工艺成型的板型产品或非板型产品,主要用于厨房台面,家具等领域。 ISO 19712-1-2008装饰用实体面材测试 测试项目 测试标准 耐干热 ISO 19712-3 ISO 19712-2 耐湿热 ISO 19712-…...

华为OD机试 - 最多颜色的车辆 - 数据结构map(Java 2022Q4 100分)
目录 专栏导读一、题目描述二、输入描述三、输出描述四、解题思路1、核心思想2、题做多了,你就会发现,这道题属于送分题,为什么这样说?3、具体解题思路: 五、Java算法源码六、效果展示1、输入2、输出 华为OD机试 2023B…...

Mybatis 插入、修改、删除
前面几篇我们介绍了使用Mybatis查询数据,并且也了解了如何在Mybatis中使用JDK的日志系统打印日志;本篇我们继续介绍如何使用Mybatis完成数据的插入、修改和删除。 如果您对查询数据和Mybatis集成JDK日志系统不太了解,建议您先进行了解后再阅…...

2023年9月DAMA-CDGA/CDGP数据治理认证火热招生中
DAMA认证为数据管理专业人士提供职业目标晋升规划,彰显了职业发展里程碑及发展阶梯定义,帮助数据管理从业人士获得企业数字化转型战略下的必备职业能力,促进开展工作实践应用及实际问题解决,形成企业所需的新数字经济下的核心职业…...

【SpringCloudAlibaba】Seata分布式事务使用
文章目录 分布式事务问题示例Seata概述、官网一个典型的分布式事务过程处理过程全局GlobalTransactional分布式交易解决方案流程图 Seata安装下载修改conf目录下的application.yml配置文件dashboard demo 分布式事务问题示例 单体应用被拆分成微服务应用,原来的三个…...

Java-day13(IO流)
IO流 凡是与输入,输出相关的类,接口等都定义在java.io包下 1.File类的使用 File类可以有构造器创建其对象,此对象对应着一个文件(.txt,.avi,.doc,.mp3等)或文件目录 File类对象是与平台无关的 File中的方法仅涉及到如何创建,…...

Vue2项目练手——通用后台管理项目第四节
Vue2项目练手——通用后台管理项目 数据的请求mock数据模拟实战文件目录src/api/mock.jssrc/api/mockServeData/home.jsmain.js 首页组件布局可视化图表可视化图表布局Home.vue echarts表Home.vue 数据的请求 mock数据模拟实战 mock官方文档 前端用来模拟后端接口的工具&…...

linux运维(二)内存占用分析
一、centos内存高,查看占用内存, top命令详解 1.1: free 命令是 free 单位K free -m 单位M free -h 单位Gfree最常规的查看内存占用情况的命令 1.2: 参数说明 total 总物理内存 used 已经使用的内存 free 没有使用的内存 shared 多进程共享内存 buff/cache 读写…...

go logger 不侵入业务代码 用slog 替换 zap 并实现 callerSkip
快速体验 以下是 项目中 已经用slog替换 zap 后的 logger 使用方法,无任何感知,与之前一模一样 package mainimport "github.com/webws/go-moda/logger"func main() {// 格式化打印 {"time":"2023-09-08T01:25:21.31346308:00","level&qu…...

vuez 与 Vue3 响应式比较
Vue2 的响应式 对象:通过 defineProperty 对对象的已有属性值的读取和修改进行劫持(监视/拦被)。 数组:通过重写数组、更新数组等一系列更新元素的方法来实现元素修改的劫持。 存在的问题如下: &#…...

【Apollo学习笔记】——规划模块TASK之PIECEWISE_JERK_SPEED_OPTIMIZER
文章目录 TASK系列解析文章前言PIECEWISE_JERK_SPEED_OPTIMIZER功能简介PIECEWISE_JERK_SPEED_OPTIMIZER相关配置PIECEWISE_JERK_SPEED_OPTIMIZER流程QP问题的标准类型定义:优化变量设计目标函数约束条件相关矩阵二次项系数矩阵 H H H一次项系数向量 q q q设定OSQP求…...

CNI、CSI 和 CRI在 Docker 中的角色和作用
摘要 CNI(Container Network Interface): CNI 是用于容器网络的接口标准,它定义了容器和网络插件之间的通信协议。CNI 的主要作用是为容器创建和管理网络接口。当创建一个容器时,CNI 插件会被调用来为容器创建一个网络…...

「Docker」M1 Pro 打包docker image问题合集
运行docker 遇到 The requested images platform (linux/arm64/v8) does not match the detected host platform (linux/amd64/v4) and no specific platform was requested 说明打包的镜像没有 linux/amd64 解决方案:重新打包镜像 docker buildx build --platfor…...

Android发布依赖到 Jitpack
前言 我们在日常开发中,经常会用到第三方开源的库文件,有的来自JCenter,Maven Central,google等。但是随着JCenter的弃用,现在用的最多的还是Maven Central,google。今天我们就自己亲自发布一个依赖。 现…...