Leetcode 2911. Minimum Changes to Make K Semi-palindromes
- Leetcode 2911. Minimum Changes to Make K Semi-palindromes
- 1. 解题思路
- 2. 代码实现
- 题目链接:2911. Minimum Changes to Make K Semi-palindromes
1. 解题思路
这一题属实也是把我坑惨了……
坦率地说,这道题本身并没有啥难度,但是坑爹的是题目表述简直有毒,有两个细节题目里面压根没提,一个是我从中文版本的题目当中发现的,另一个则是我根据失败的样例当中反推出来的,这简直有毒……
这道题本身思路上还是挺直接的,就是一个动态规划的题目,考虑每一种切分的方式,然后考察其中最小的变化次数即可。
然后对于每一个切分得到的子串,我们要求其变化所需的最小变化次数,我们只需要找到其所有对长度 l l l整除的 d d d,然后切分semi子串,再考察其中每一种分法下所需的变化次数之和,最后取最小值即可。
因此,我们就将上述题目拆分完成了,后续只要对其实现一下即可,测试发现是可以在有效时间内完成所有测试样例的。
但是,这里但是就来了,题目中遗漏了两个非常非常重要的说明,把我给坑惨了!!!
首先,这里semi-palindrome的定义事实上要求将其使用d进行切分后,每一个子串都得是回文,其次,题中也没有具体说,但是实际测试发现,这里对子串的切分要求每一个子串长度至少为2。
这简直就是简直了!!!
到底谁出的题目啊,只能说,出来挨打!!!
2. 代码实现
给出python代码实现如下:
class Solution:def minimumChanges(self, s: str, k: int) -> int:n = len(s)@lru_cache(None)def count(sub):cnt = 0n = len(sub)for i in range(n//2):if sub[i] != sub[n-1-i]:cnt += 1return cnt@lru_cache(None)def count_change(s):if s == s[::-1]:return 0n = len(s)ans = count(s)for d in range(len(s)//2, 0, -1):if n % d != 0:continuek = n // dcnt = 0for i in range(d):sub = "".join([s[i+j*d] for j in range(k)])cnt += count(sub)ans = min(ans, cnt)return ans@lru_cache(None)def dp(idx, k):if idx+2*k > n:return math.infelif k == 1:return count_change(s[idx:])return min(count_change(s[idx:j]) + dp(j, k-1) for j in range(idx+2, n))ans = dp(0, k)return ans
提交代码评测得到:耗时5650ms,占用内存71.8MB。
相关文章:
Leetcode 2911. Minimum Changes to Make K Semi-palindromes
Leetcode 2911. Minimum Changes to Make K Semi-palindromes 1. 解题思路2. 代码实现 题目链接:2911. Minimum Changes to Make K Semi-palindromes 1. 解题思路 这一题属实也是把我坑惨了…… 坦率地说,这道题本身并没有啥难度,但是坑爹…...
Node学习笔记之包管理工具
一、概念介绍 1.1 包是什么 『包』英文单词是package ,代表了一组特定功能的源码集合 1.2 包管理工具 管理『包』的应用软件,可以对「包」进行 下载安装 , 更新 , 删除 , 上传 等操作 借助包管理工具,可…...
分发糖果[困难]
优质博文:IT-BLOG-CN 一、题目 n个孩子站成一排。给你一个整数数组ratings表示每个孩子的评分。你需要按照以下要求,给这些孩子分发糖果: 【1】每个孩子至少分配到1个糖果。 【2】相邻两个孩子评分更高的孩子会获得更多的糖果。 请你给每个孩…...
Java验证邮箱格式是否正确的正则表达式
Java验证邮箱格式是否正确的正则表达式 import java.util.regex.Pattern;public class EmailUtil {final static Pattern partern Pattern.compile("[a-zA-Z0-9][\\.]{0,1}[a-zA-Z0-9][a-zA-Z0-9]\\.[a-zA-Z]");/*** 验证输入的邮箱格式是否符合* param email* ret…...
快速排序原理JAVA和Scala实现-函数式编程的简洁演示
快速排序原理JAVA和Scala实现-函数式编程的简洁演示 目录 快速排序原理JAVA和Scala实现-函数式编程的简洁演示 C语言快速排序实现 Java 快速排序实现 Scala 快速排序实现 本文章向大家介绍快速排序原理JAVA和Scala实现-函数式编程的简洁演示,主要内容包括C语言…...
如何在linux服务器上安装Anaconda与pytorch
如何在linux服务器上安装Anaconda与pytorch 1,安装anaconda1.1 下载anaconda安装包1.2 安装anaconda1.3 设计环境变量1.4 安装完成验证 2 Anaconda安装pytorch2.1 创建虚拟环境2.2 查看现存环境2.3 激活环境2.4 选择合适的pytorch版本下载2.5 检测是否安装成功&…...
FPGA设计FIR滤波器低通滤波器,代码及视频
名称:FIR滤波器低通滤波器 软件:Quartus 语言:Verilog/VHDL 本资源含有verilog及VHDL两种语言设计的工程,每个工程均可实现以下FIR滤波器的功能。 代码功能: 设计一个8阶FIR滤波器(低通滤波器ÿ…...
【数据结构】排序--快速排序
目录 一 概念 二 快速排序的实现 1. hoare版本 (1)代码实现 (2)单趟排序图解 (3) 递归实现图解 (4)细节控制 (5)时间复杂度 (6)三数取中优化 2 挖坑法 (1)代码实现 (2)单趟图解 3 前后指针法 (1) 代码实现 (2) 单趟图解 4 优化子区间 5 非递归快速排序 …...
【试题040】多个逻辑或例题2
1.题目:设int n0;,执行表达式n ||(n-1) ||(n0)||(n1)||(n2)后n的值是 ? 2.代码解析: 逻辑或 || 运算符是一个短路运算符,它从左到右依次计算表达式,如果遇到一个为真(非零)的值&am…...
自然语言处理---Self Attention自注意力机制
Self-attention介绍 Self-attention是一种特殊的attention,是应用在transformer中最重要的结构之一。attention机制,它能够帮助找到子序列和全局的attention的关系,也就是找到权重值wi。Self-attention相对于attention的变化,其实…...
推荐收藏系列!2万字图解Hadoop
今天我用图解的方式讲解pandas的用法,内容较长建议收藏,梳理不易,点赞支持。 学习 Python 编程,给我的经验就是:技术要学会分享、交流,不建议闭门造车。一个人可能走的很快、但一堆人可以走的更远。如果你…...
Python高级篇(08):生成器
一、生成器定义和作用 定义:Python中,一边循环一边计算的机制,生成器对象也是迭代器对象,支持for循环、next()方法…等。作用:循环的过程中不断推算出后续的元素,这样就不必创建完整的list,从而…...
力扣100114. 元素和最小的山形三元组 II(中等)
题目描述: 给你一个下标从 0 开始的整数数组 nums 。 如果下标三元组 (i, j, k) 满足下述全部条件,则认为它是一个 山形三元组 : i < j < knums[i] < nums[j] 且 nums[k] < nums[j] 请你找出 nums 中 元素和最小 的山形三元组…...
LuatOS-SOC接口文档(air780E)--lcdseg - 段式lcd
常量 常量 类型 解释 lcdseg.BIAS_STATIC number 没偏置电压(bias) lcdseg.BIAS_ONEHALF number 1/2偏置电压(bias) lcdseg.BIAS_ONETHIRD number 1/3偏置电压(bias) lcdseg.BIAS_ONEFOURTH number 1/4偏置电压(bias) lcdseg.DUTY_STATIC number 100%占空比(d…...
实现图像处理和分析的关键技术
在计算机视觉中,我们可以利用摄像头捕捉到的图像来进行各种分析和处理。以下是一些常见的计算机视觉任务: 对象检测:识别图像中的特定对象并标注其位置。人脸识别:识别和验证人脸身份。姿态估计:估计人体的姿态和动作…...
【C++学习笔记】内联函数
1. 概念 以inline修饰的函数叫做内联函数,编译时C编译器会在调用内联函数的地方展开,没有函数调 用建立栈帧的开销,内联函数提升程序运行的效率。 如果在上述函数前增加inline关键字将其改成内联函数,在编译期间编译器会用函数…...
macOS Sonoma 14.1RC(23B73)发布
黑果魏叔10 月 18 日消息,苹果今日向 Mac 电脑用户推送了 macOS 14.1 RC更新(内部版本号:23B73),本次更新距离上次发布隔了 7 天。 macOS Sonoma 14.1RC(23B73)的更新内容主要包括以下方面&…...
数据结构数组 Array 手写实现,扩容原理
数组数据结构 数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型数据的集合。 数组的特点: 数组是相同数据类型的元素集合(int 不能存放 double)数组中各元素的存储是有先…...
工作中几个问题的思考
对于需要并行多公司并行处理的任务,方案是什么? 多线程、并行流、并发库(ExecutorService、Futrue、Callable),分布式计算(1)按照公司ID分片 (2)按照业务类型分片 处理…...
Jmeter的性能测试
性能测试的概念 定义:软件的性能是软件的一种非功能特性,它关注的不是软件是否能够完成特定的功能,而是在完成该功能时展示出来的及时性。 由定义可知性能关注的是软件的非功能特性,所以一般来说性能测试介入的时机是在功能测试…...
网络六边形受到攻击
大家读完觉得有帮助记得关注和点赞!!! 抽象 现代智能交通系统 (ITS) 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 (…...
3.3.1_1 检错编码(奇偶校验码)
从这节课开始,我们会探讨数据链路层的差错控制功能,差错控制功能的主要目标是要发现并且解决一个帧内部的位错误,我们需要使用特殊的编码技术去发现帧内部的位错误,当我们发现位错误之后,通常来说有两种解决方案。第一…...
蓝桥杯 2024 15届国赛 A组 儿童节快乐
P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡,轻快的音乐在耳边持续回荡,小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下,六一来了。 今天是六一儿童节,小蓝老师为了让大家在节…...
对WWDC 2025 Keynote 内容的预测
借助我们以往对苹果公司发展路径的深入研究经验,以及大语言模型的分析能力,我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际,我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测,聊作存档。等到明…...
华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...
第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明
AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...
python执行测试用例,allure报乱码且未成功生成报告
allure执行测试用例时显示乱码:‘allure’ �����ڲ����ⲿ���Ҳ���ǿ�&am…...
Linux离线(zip方式)安装docker
目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1:修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本:CentOS 7 64位 内核版本:3.10.0 相关命令: uname -rcat /etc/os-rele…...
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要: 近期,在使用较新版本的OpenSSH客户端连接老旧SSH服务器时,会遇到 "no matching key exchange method found", "n…...
LLMs 系列实操科普(1)
写在前面: 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容,原视频时长 ~130 分钟,以实操演示主流的一些 LLMs 的使用,由于涉及到实操,实际上并不适合以文字整理,但还是决定尽量整理一份笔…...
