【算法题】得到K个半回文串的最小修改次数
题目:
给你一个字符串 s 和一个整数 k ,请你将 s 分成 k 个 子字符串 ,使得每个 子字符串 变成 半回文串 需要修改的字符数目最少。
请你返回一个整数,表示需要修改的 最少 字符数目。
注意:
如果一个字符串从左往右和从右往左读是一样的,那么它是一个 回文串 。
如果长度为 len 的字符串存在一个满足 1 <= d < len 的正整数 d ,len % d == 0 成立且所有对 d 做除法余数相同的下标对应的字符连起来得到的字符串都是 回文串 ,那么我们说这个字符串是 半回文串 。比方说 “aa” ,“aba” ,“adbgad” 和 “abab” 都是 半回文串 ,而 “a” ,“ab” 和 “abca” 不是。
子字符串 指的是一个字符串中一段连续的字符序列。
示例 1:
输入:s = “abcac”, k = 2
输出:1
解释:我们可以将 s 分成子字符串 “ab” 和 “cac” 。子字符串 “cac” 已经是半回文串。如果我们将 “ab” 变成 “aa” ,它也会变成一个 d = 1 的半回文串。
该方案是将 s 分成 2 个子字符串的前提下,得到 2 个半回文子字符串需要的最少修改次数。所以答案为 1 。
示例 2:
输入:s = “abcdef”, k = 2
输出:2
解释:我们可以将 s 分成子字符串 “abc” 和 “def” 。子字符串 “abc” 和 “def” 都需要修改一个字符得到半回文串,所以我们总共需要 2 次字符修改使所有子字符串变成半回文串。
该方案是将 s 分成 2 个子字符串的前提下,得到 2 个半回文子字符串需要的最少修改次数。所以答案为 2 。
示例 3:
输入:s = “aabbaa”, k = 3
输出:0
解释:我们可以将 s 分成子字符串 “aa” ,“bb” 和 “aa” 。
字符串 “aa” 和 “bb” 都已经是半回文串了。所以答案为 0 。
提示:
2 <= s.length <= 200
1 <= k <= s.length / 2
s 只包含小写英文字母。
java代码:
class Solution {char[] chars;int[][] dps;int[][] checks;public int minimumChanges(String s, int k) {this.chars = s.toCharArray();final int n = chars.length;this.dps = new int[n][k + 1];this.checks = new int[n][n];return dp(0, k) - k;}private int checkD(int head, int tail, int d) {final int length = tail - head + 1;int res = 0;for (int x = 0; x < d; x++) {for (int left = head + x, right = left + length - d; left < right; left += d, right -= d) {if (chars[left] != chars[right]) res++;}}return res;}private int check(int head, int tail) {if (checks[head][tail] > 0) return checks[head][tail];int length = tail - head + 1;int sq = (int)Math.sqrt(length);int best = checkD(head, tail, 1);for (int d = 2; d <= sq; d++) {if (length % d > 0) continue;best = Math.min(best, checkD(head, tail, d));best = Math.min(best, checkD(head, tail, length / d));}return checks[head][tail] = best + 1;}private int dp(int head, int k) {if (k == 1) return check(head, chars.length - 1);if (dps[head][k] > 0) return dps[head][k];final int end = chars.length - (k - 1) * 2;int best = Integer.MAX_VALUE;for (int tail = head + 1; tail < end; tail++) {int res = check(head, tail) + dp(tail + 1, k - 1);best = Math.min(best, res);}return dps[head][k] = best;}
}相关文章:
【算法题】得到K个半回文串的最小修改次数
题目: 给你一个字符串 s 和一个整数 k ,请你将 s 分成 k 个 子字符串 ,使得每个 子字符串 变成 半回文串 需要修改的字符数目最少。 请你返回一个整数,表示需要修改的 最少 字符数目。 注意: 如果一个字符串从左往…...
C# 通过IP获取Mac地址(ARP)
C# 通过IP获取Mac地址 [DllImport("Iphlpapi.dll")] private static unsafe extern int SendARP(Int32 dest, Int32 host, ref Int32 mac, ref Int32 length);[DllImport("Ws2_32.dll")] private static extern Int32 inet_addr(string ip);public static…...
【QT】信号和槽
一、前置示例代码 main.cpp #include "widget.h"#include <QApplication>int main(int argc, char *argv[]) {QApplication a(argc, argv); // 应用程序对象a,在Qt中,应用程序对象,有且仅有一个。Widget w; // 窗口对…...
有话则长,无话则短
有话则长,无话则短...
云台/稳定器/无人机姿态控制之欧拉角与四元数控制优缺点分析
基于欧拉角的姿态控制简述: 通过陀螺仪数据解算出姿态:pitch,roll,yaw(相对航向),根据目标 姿态:dst_pitch,dst_roll,dst_yaw计算出误差姿态pitch_err,roll_err,yaw_err。将误差姿态转换为目标速度e_pitch_rate,e_roll_rate,e_yaw_rate。然后…...
Go 工具链详解(六):依赖管理神器
go mod 是 Golang 的官方依赖管理工具,从 Go 1.11 版本开始引入。go mod 使用一种被称为模块(modules)的方式来管理依赖,每个模块都包含了一组 Golang 包。一个 Go 程序可以由多个模块组成,每个模块都可以有自己的 go.…...
C语言解决约瑟夫环问题
约瑟夫环问题是一个经典的数学问题,它的描述如下:有n个人围成一圈,从第1个人开始报数,数到第m个人出列,然后从出列的下一个人开始重新报数,数到第m个人出列,如此循环,直到最后一个人…...
6.6 Elasticsearch(六)京淘项目改造
文章目录 1.项目准备2.基础配置2.1 添加pom.xml依赖2.2 yml配置es服务器地址列表 3.具体实现3.1 item实体类封装3.2 添加接口3.3 SearchController 4.search.jsp界面4.1 搜索内容展示4.2 高亮内容样式设置4.3 搜索框内容回填4.4 添加上下页按钮 1.项目准备 我们切换回到此前的…...
Socks5代理:数字化时代的技术支柱
随着数字化时代的到来,技术不仅改变了我们的日常生活,还重新定义了商业、通信、娱乐和全球互联。在这一浪潮中,Socks5代理技术崭露头角,成为跨界电商、爬虫数据分析、企业出海和游戏体验的关键推动力。这项技术不仅在实现数字化愿…...
基本微信小程序的汽车租赁公司小程序
项目介绍 任何系统都要遵循系统设计的基本流程,本系统也不例外,同样需要经过市场调研,需求分析,概要设计,详细设计,编码,测试这些步骤,基于Java语言、微信小程序技术设计并实现了汽…...
Leetcode刷题详解——搜索插入位置
1. 题目链接:35. 搜索插入位置 2. 题目描述: 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。…...
centos升级openssh
注意: openssh升级异常会造成服务失联,如果在允许的情况下可以安装talent服务,使用talent升级; 如果不能安装talent服务,可以打开多个终端,启动ping命令,防止升级终端失败后,作为备用…...
架构、框架、模式,极简文字介绍
1、架构、框架、模式是一种从大到小的关系,也是一种组合关系 2、架构一般针对一个行业或一类应用,是技术和应用的完美组合 3、框架比较小,很多表现为中间件,框架一般是从技术角度解决同类问题,从技术的横切面来解决实…...
Java实现Fisher‘s Exact Test 的置信区间的计算
实现代码 package com.bgi.aigi.common.utils;public class FisherExactUtils {public static double[] getConfidenceInterval(double[][] data) {if (datanull||data.length!2||data[0].length!2||data[1].length!2) {return null;}double[] intervalnew double[2];double …...
YOLOv8改进:全网原创首发 | 新颖的多尺度卷积注意力(MSCA),即插即用,助力小目标检测 | NeurIPS2022
💡💡💡本文全网首发独家改进:多尺度卷积注意力(MSCA),有效地提取上下文信息,新颖度高,创新十足。 1)作为注意力MSCA使用; 推荐指数:五星 MSCA | 亲测在多个数据集能够实现涨点,多尺度特性在小目标检测表现也十分出色。 💡💡💡Yolov8魔术师,独家首发…...
linux中好玩的数据流定向和管道命令一
知识点复习: 什么是数据流定向,个人理解就是将 一些结果信息不打印在屏幕上,而是定位在某一个文件里面 ll /wdf > file 会覆盖file的原内容 ll /wdf >> 会追加到原文件后面 比如在自己的目录新建1.TXT, 2.txt ll /…...
tesseract-ocr-w64-setup-5.3.3.20231005.exe 百度网盘下载
链接:https://pan.baidu.com/s/1q6u-nRvj2S8n6jSYz2iqig?pwdbtm4 提取码:btm4...
Linux环境下Redis 集群部署
Linux环境下Redis 集群部署 1.单机Redis部署2.Redis 集群配置2.1 创建redis集群安装目录2.2 将redis单机部署目录下的redis.confi文件复制到每个目录下2.3 修改每个文件夹下的redis.conf2.4 修改完六个配置内容后开始启动2.5 启动完后查看进程2.6 建集群 1.单机Redis部署 Linu…...
html iframe 框架有哪些优缺点?
目录 前言: 用法: 理解: 优点: 嵌套外部内容: 独立性: 分离安全性: 跨平台兼容性: 方便维护: 缺点: 性能开销: 用户体验问题…...
git 版本管理
标签管理 git tag: 标签的操作 用于给某次提交打个标签 命令:git tag B08P09 为当前提交打上 B08P09 的标签 命令:git tag B08P09 ab1591eb4e06c1e93fdd50126b9fab8a88d89155 为这个节点打上 B08P09 的标签 命令:git tag -a <tagname>…...
Open UI5 源代码解析之735:DynamicPageAccessibleLandmarkInfo.js
源代码仓库: https://github.com/SAP/openui5 源代码位置:src\sap.f\src\sap\f\DynamicPageAccessibleLandmarkInfo.js DynamicPageAccessibleLandmarkInfo 文件深度解析 文件定位与总体判断 当前分析对象位于 src/sap.f/src/sap/f/DynamicPageAccessibleLandmarkInfo.j…...
对比学习演进笔记:从Memory Bank到MoCo的负样本队列设计
1. 对比学习的核心思想与演进背景 对比学习(Contrastive Learning)作为自监督学习的重要分支,其核心思想可以用一句话概括:让相似样本的特征表示尽可能接近,不相似样本的特征表示尽可能远离。这种思想最早可以追溯到20…...
让你的调试日志五彩斑斓:J-Link RTT高级封装技巧(支持中文、浮点数、十六进制)
让你的调试日志五彩斑斓:J-Link RTT高级封装技巧(支持中文、浮点数、十六进制) 调试是嵌入式开发中不可或缺的一环,而高效的调试工具能显著提升开发效率。J-Link RTT(Real Time Transfer)作为一种无需额外硬…...
卡证检测矫正模型中小企业降本:替代万元级专用证件扫描仪方案
卡证检测矫正模型:中小企业降本利器,替代万元级专用证件扫描仪方案 1. 引言:一个被忽视的降本痛点 如果你在中小企业负责行政、人事或财务,一定对下面这个场景不陌生:每天要处理一堆身份证、护照、驾照的复印件或扫描…...
用Python的igraph和leidenalg搞定知识图谱布局:一个科研领域的可视化实战
科研知识图谱实战:用PythonLeiden算法揭示学科交叉规律 当你在文献海洋中寻找研究方向时,是否曾被复杂的学科交叉关系困扰?传统的关键词共现分析已经不能满足现代科研的需求。本文将带你用Python的igraph和leidenalg构建一个能自动识别学科社…...
OpenRGB:开源跨平台RGB灯光控制方案,告别多软件困扰实现设备统一管理
OpenRGB:开源跨平台RGB灯光控制方案,告别多软件困扰实现设备统一管理 【免费下载链接】OpenRGB Open source RGB lighting control that doesnt depend on manufacturer software. Supports Windows, Linux, MacOS. Mirror of https://gitlab.com/CalcPr…...
新手别怕!用Volatility 2.6分析WinXP内存镜像,一步步揪出隐藏的svchost木马
从零开始的内存取证实战:用Volatility 2.6解剖WinXP内存中的svchost木马 当你第一次接触内存取证时,面对黑底白字的命令行界面和陌生的术语,难免会感到无从下手。但别担心,今天我们就用一个真实的WinXP SP2内存镜像案例࿰…...
PyTorch矩阵操作小技巧:用torch.triu和torch.tril快速提取邻接矩阵的上下三角部分
PyTorch矩阵操作实战:高效处理邻接矩阵的三角部分提取技巧 邻接矩阵是图神经网络(GNN)和社交网络分析中最基础的数据结构之一。在处理无向图时,我们常常需要提取邻接矩阵的上三角或下三角部分来避免重复计算或进行特定操作。PyTor…...
OpenClaw是什么?OpenClaw能做什么?OpenClaw详细介绍及保姆级部署教程-周红伟
1. 什么是 OpenClaw? 1.1 核心定义 OpenClaw(前身为 Clawdbot/Moltbot)是一款开源、本地优先、可执行任务的 AI 自动化代理引擎,遵循 MIT 协议。它以自然语言指令为驱动,在本地或私有云环境中完成文件操作、流程编排…...
Java整型溢出:越界运算后结果如何
Java整形溢出详细说明:越界操作后的结果和类型在Java程序中,理解数据类型的值范围非常重要。本文将深入探讨越界操作后int类型的行为,并解释int类型的值范围和越界操作结果。Javaint类型的值范围为-2、147、483、648至2、147、483、647。当计算结果超出此…...
