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

2023-2-18 刷题情况

删列造序 III

题目描述

给定由 n 个小写字母字符串组成的数组 strs ,其中每个字符串长度相等。

选取一个删除索引序列,对于 strs 中的每个字符串,删除对应每个索引处的字符。

比如,有 strs = [“abcdef”,“uvwxyz”] ,删除索引序列 {0, 2, 3} ,删除后为 [“bef”, “vyz”] 。

假设,我们选择了一组删除索引 answer ,那么在执行删除操作之后,最终得到的数组的行中的 每个元素 都是按字典序排列的(即 (strs[0][0] <= strs[0][1] <= … <= strs[0][strs[0].length - 1]) 和 (strs[1][0] <= strs[1][1] <= … <= strs[1][strs[1].length - 1]) ,依此类推)。

请返回 answer.length 的最小可能值 。

样例

样例输入

strs = [“babca”,“bbazb”]
strs = [“edcba”]
strs = [“ghi”,“def”,“abc”]

样例输出

3
解释:
删除 0、1 和 4 这三列后,最终得到的数组是 A = [“bc”, “az”]。
这两行是分别按字典序排列的(即,A[0][0] <= A[0][1] 且 A[1][0] <= A[1][1])。
注意,A[0] > A[1] —— 数组 A 不一定是按字典序排列的。

4
解释:如果删除的列少于 4 列,则剩下的行都不会按字典序排列。

0
解释:所有行都已按字典序排列。

提示

  • n == strs.length
  • 1 <= n <= 100
  • 1 <= strs[i].length <= 100
  • strs[i] 由小写英文字母组成

思路

问题求的是将一些数删除最后让所有是都是非递减的,这个问题可以置换为求数组中的最长上升子序列有多长。最终问题的答案为长度减去最长上序列的长度。

代码实现

class Solution {public int minDeletionSize(String[] strs) {int len = strs[0].length();int[] dp = new int[len];Arrays.fill(dp, 1);int ans = 1;for(int j = 1; j < len; j++){for(int i = j - 1; i >= 0; i--){boolean ok = true;for(String s : strs){if(s.charAt(j) < s.charAt(i)){ok = false;break;}}if(ok) dp[j] = Math.max(dp[j], dp[i] + 1); }ans = Math.max(ans, dp[j]);}return len - ans;}
}

乘积最大

题目描述

给定 N 个整数 1,2,⋯A1,A2,⋯AN1,2,⋯A_1,A_2,⋯A_N1,2,A1,A2,AN 。请你从中选出 K 个数,使其乘积最大。

请你求出最大的乘积,由于乘积可能超出整型范围,你只需输出乘积除以 109+910^9+9109+9的余数。

注意,如果 X<0,我们定义 X 除以 109+910^9+9109+9 的余数是负(−X)除以 109+910^9+9109+9 的余数。

即:0 - ( ( 0 - x ) % 10910^9109 + 9)

输入描述

第一行包含两个整数N, K;

以下N 行每行一个整数AIA_IAI

其中,1<=k<=N<=105,−105<=Ai<=1051 <= k <= N <= 10^5, -10^5 <= A_i <= 10^51<=k<=N<=105,105<=Ai<=105

输出描述

输出一个整数,表示答案。

样例

样例输入

5 3
-100000
-10000
2
100000
10000

样例输出

999100009

思路

之前是想用动态规划,但在递推的过程中,是需要进行取模操作,这回影响到状态转移过程中的变化,所以本题不宜使用动态规划。直接排序即可。

代码实现

import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {static int MOD = (int)1e9 + 9;public static void main(String[] args) {Scanner sc = new Scanner(System.in);//在此输入您的代码...int n = sc.nextInt(), k = sc.nextInt();long[] arr = new long[n];for(int i = 0; i < n; i++) arr[i] = sc.nextInt();Arrays.sort(arr);long ans = 1;int flag = 1, l = 0, r = n-1;if(k % 2 > 0){k--;ans = arr[r--];if(ans < 0) flag = -1;}while(k > 0){long s1 = arr[l] * arr[l+1];long s2 = arr[r] * arr[r-1];if(s1 * flag > s2 * flag){ans = (s1 % MOD) * ans % MOD;l += 2;}else{ans = (s2 % MOD) * ans % MOD;r -= 2;}k -= 2;}System.out.println(ans);sc.close();}
}

相关文章:

2023-2-18 刷题情况

删列造序 III 题目描述 给定由 n 个小写字母字符串组成的数组 strs &#xff0c;其中每个字符串长度相等。 选取一个删除索引序列&#xff0c;对于 strs 中的每个字符串&#xff0c;删除对应每个索引处的字符。 比如&#xff0c;有 strs [“abcdef”,“uvwxyz”] &#xf…...

【Linux】进程控制

文章目录进程创建简单认识一下fork()函数为什么fork()会有两个返回值fork通过写时拷贝的方式创建子进程进程终止进程退出码进程退出的方式exit()和_exit()进程等待进程等待方法 -- wait()和waitpid()status参数解释waitpid()的pid参数waitpid()的options参数 - 阻塞和非阻塞进程…...

谷歌seo快排技术怎么做?Google排名霸屏推广原理

本文主要分享关于谷歌快速排名的方法和所需要的条件。 本文由光算创作&#xff0c;有可能会被剽窃和修改&#xff0c;我们佛系对待这种行为吧。 首先提出一个问题&#xff1a;谷歌seo快排技术怎么做&#xff1f;如何达到谷歌霸屏的效果&#xff1f; 答案是&#xff1a;利用谷…...

MySQL的优化

目录 一.概念 二.查看SQL执行频率 三.定位低效率执行SQL 定位低效率执行SQL—慢查询日志 操作 定位低效率执行SQL—show processlist 四.explain分析执行计划 字段说明 explain中的id explain中的select_type explain中的type explain中的table explain中的rows ex…...

实现qq群消息接收和发送功能

QQWebsocketClient是什么 实现qq群消息接收和发送功能&#xff0c;基于websocket技术和cqhttp服务开发 一、 效果截图 二、实现思路 使用cqhttp进行socket反向代理&#xff0c;获取qq聊天的所有消息 编写java客户端&#xff0c;连接至cqhttp服务器获取聊天消息 获取聊天消…...

压缩20M文件从30秒到1秒的优化过程

压缩20M文件从30秒到1秒的优化过程 有一个需求需要将前端传过来的10张照片&#xff0c;然后后端进行处理以后压缩成一个压缩包通过网络流传输出去。之前没有接触过用Java压缩文件的&#xff0c;所以就直接上网找了一个例子改了一下用了&#xff0c;改完以后也能使用&#xff0…...

如何选择合适的固态继电器?

如何选择合适的固态继电器&#xff1f; 在选择固态继电器&#xff08;SSR&#xff09;时&#xff0c;应根据实际应用条件和SSR性能参数&#xff0c;特别要考虑到使用中的过流和过压条件以及SSR的负载能力&#xff0c;这有助于实现固态继电器的长寿命和高可靠性。然后&#xff0…...

SAP 忘记SAP系统Client 000的所有账号密码

忘记SAP系统Client 000的所有账号密码。 Solution 在SAP系统DB中删除账号SAP*&#xff0c;SAP系统会自动创建SAP*这个账号&#xff0c;然后初始密码是“PASS”&#xff0c;这样就获得Client 000 SAP*账号。 Step by Step 以Oracle数据库为例&#xff1a; 1.以<SID>ADM账…...

Connext DDS可扩展类型Extensible Types指南

RTI Connext DDS 可扩展类型Extensible Types指南 可扩展类型Extensible TypesConnextDDSv6.1.1版本,包含了对OMG“DDS的可扩展和动态主题类型Extensible andDynamic Topic Types for DDS”规范1.3版的部分支持,该规范来自对象管理组OMG。这种支持,允许系统以更灵活的方式定义…...

Docker简单使用

文章目录1、安装配置2、服务启动3、Docker镜像下载4、Docker启动容器5、容器的常用命令6、Docker进入容器内部7、宿主机与容器交换文件8、查看日志官网地址&#xff1a;1、安装配置 sudo yum install -y yum-utils 设置镜像地址 sudo yum-config-manager \--add-repo \https:…...

A Time Series is Worth 64 Words(PatchTST模型)论文解读

摘要 我们提出了一种高效的基于Transformer设计的模型&#xff0c;用于多变量时间序列预测和自我监督表征学习&#xff08;self-supervised learning&#xff09;。它基于两个关键部分&#xff1a;1、将时间序列分隔成子序列级别的patches&#xff0c;作为Transformer的输入&a…...

微服务学习:SpringCloud+RabbitMQ+Docker+Redis+搜索+分布式

目录 一、高级篇 二、面试篇 实用篇 day05-Elasticsearch01 安装elasticsearch 1.部署单点es 2.部署kibana 一、高级篇 二、面试篇 实用篇 day05-Elasticsearch01 安装elasticsearch 1.部署单点es 1.1.创建网络 因为我们还需要部署kibana容器&#xff0c;因此需要…...

nginx平滑升级

1.平滑升级操作1.1 备份安装目录下的nginxcd /usr/local/nginx/sbin mv nginx nginx.bak1.2 复制objs目录下的nginx到当前sbin目录下cp /opt/software/nginx/nginx-1.20.2/objs/nginx /usr/local/nginx/sbin/1.3 发送信号user2给nginx老版本对应的进程kill -user2 more /usr/lo…...

高可用的“异地多活”架构设计

前言 后台服务可以划分为两类&#xff0c;有状态和无状态。高可用对于无状态的应用来说是比较简单的&#xff0c;无状态的应用&#xff0c;只需要通过 F5 或者任何代理的方式就可以很好的解决。后文描述的主要是针对有状态的服务进行分析。 服务端进行状态维护主要是通过磁盘…...

【面试题】Map和Set

1. Map和Object的区别 形式不同 // Object var obj {key1: hello,key2: 100,key3: {x: 100} } // Map var m new Map([[key1, hello],[key2, 100],[key3, {x: 100}] ])API不同 // Map的API m.set(name, 小明) // 新增 m.delete(key2) // 删除 m.has(key3) // …...

Spring之事务底层源码解析

Spring之事务底层源码解析 1、EnableTransactionManagement工作原理 开启 Spring 事务本质上就是增加了一个 Advisor&#xff0c;当我们使用 EnableTransactionManagement 注解来开启 Spring 事务时&#xff0c;该注解代理的功能就是向 Spring 容器中添加了两个 Bean&#xf…...

【华为OD机试真题 Python】创建二叉树

前言:本专栏将持续更新华为OD机试题目,并进行详细的分析与解答,包含完整的代码实现,希望可以帮助到正在努力的你。关于OD机试流程、面经、面试指导等,如有任何疑问,欢迎联系我,wechat:steven_moda;email:nansun0903@163.com;备注:CSDN。 题目描述 请按下列描达构建…...

RuoYi-Vue-Plus搭建(若依)

项目简介 1.RuoYi-Vue-Plus 是重写 RuoYi-Vue 针对 分布式集群 场景全方位升级(不兼容原框架)2.环境安装参考&#xff1a;https://blog.csdn.net/tongxin_tongmeng/article/details/128167926 JDK 11、MySQL 8、Redis 6.X、Maven 3.8.X、Nodejs > 12、Npm 8.X3.IDEA环境配置…...

uboot和linux内核移植流程简述

一、移植uboot流程 1、从半导体芯片厂下载对应的demo&#xff0c;然后编译测试demo版的uboot 开发板基本都是参考半导体厂商的 dmeo 板&#xff0c;而半导体厂商会在他们自己的开发板上移植好 uboot、linux kernel 和 rootfs 等&#xff0c;最终制作好 BSP包提供给用户。我们可…...

【CS224W】(task2)传统图机器学习和特征工程

note 和CS224W课程对应&#xff0c;将图的基本表示写在task1笔记中了&#xff1b;传统图特征工程&#xff1a;将节点、边、图转为d维emb&#xff0c;将emb送入ML模型训练Traditional ML Pipeline Hand-crafted feature ML model Hand-crafted features for graph data Node-l…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

Java毕业设计:WML信息查询与后端信息发布系统开发

JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发&#xff0c;实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构&#xff0c;服务器端使用Java Servlet处理请求&#xff0c;数据库采用MySQL存储信息&#xff0…...

快刀集(1): 一刀斩断视频片头广告

一刀流&#xff1a;用一个简单脚本&#xff0c;秒杀视频片头广告&#xff0c;还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农&#xff0c;平时写代码之余看看电影、补补片&#xff0c;是再正常不过的事。 电影嘛&#xff0c;要沉浸&#xff0c;…...

Vue 模板语句的数据来源

&#x1f9e9; Vue 模板语句的数据来源&#xff1a;全方位解析 Vue 模板&#xff08;<template> 部分&#xff09;中的表达式、指令绑定&#xff08;如 v-bind, v-on&#xff09;和插值&#xff08;{{ }}&#xff09;都在一个特定的作用域内求值。这个作用域由当前 组件…...

vue3 daterange正则踩坑

<el-form-item label"空置时间" prop"vacantTime"> <el-date-picker v-model"form.vacantTime" type"daterange" start-placeholder"开始日期" end-placeholder"结束日期" clearable :editable"fal…...