当前位置: 首页 > 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…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

STM32+rt-thread判断是否联网

一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

Java 二维码

Java 二维码 **技术&#xff1a;**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...