首页 > 编程语言 >【算法题】得到K个半回文串的最小修改次数

【算法题】得到K个半回文串的最小修改次数

时间:2023-10-30 12:33:29浏览次数:31  
标签:head int tail 次数 算法 字符串 best 回文


题目:

给你一个字符串 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;
    } 
}


标签:head,int,tail,次数,算法,字符串,best,回文
From: https://blog.51cto.com/u_6813689/8087466

相关文章

  • 【算法题】统计无向图中无法互相到达点对数
    题目:给你一个整数n,表示一张无向图中有n个节点,编号为0到n-1。同时给你一个二维整数数组edges,其中edges[i]=[ai,bi]表示节点ai和bi之间有一条无向边。请你返回无法互相到达的不同点对数目。示例1:输入:n=3,edges=[[0,1],[0,2],[1,2]]输出:0解释:所......
  • 基于多尺度分形残差注意力网络的超分辨率重建算法
    1.引言深度神经网络可以显著提高超分辨率的质量,但现有方法难以充分利用低分辨率尺度特征和通道信息,从而阻碍了卷积神经网络的表达能力。针对此类问题,本章提出了一种多尺度分形残差注意力网络(Multi-scaleFractalResidualAttentionNetwork,MFRAN)。具体而言,MFRAN由分形残差块(Fra......
  • 算法:实现中序遍历(3种方法图例详解,小白也能看懂)
     中序遍历:左->中 ->右练习地址:力扣(LeetCode)官网-全球极客挚爱的技术成长平台1、递归法 #Definitionforabinarytreenode.classTreeNode(object):def__init__(self,val=0,left=None,right=None):self.val=valself.left=left......
  • 【智能优化算法】开普勒优化算法KOA附matlab代码
    ✅作者简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,代码获取、论文复现及科研仿真合作可私信。......
  • 去雨去雪去雾算法运行问题汇总记录
    问题一在进行去雨去雪去雾算法过程中,遇到了一个问题,这在先前的电脑运行是都没有出现过,但在博主新买的电脑上却出现了,讲道理是有点小抑郁的。RuntimeWarning:invalidvalueencounteredinscalardivideret=ret.dtype.type(ret/rcount)NaNorInffoundininputtensor.......
  • 国密sm4算法
    一、概述国密算法定义:即国家密码局认定的国产密码算法。通过定义我们可以知道,国密算法有两个要素:1、国家密码局认定在国家密码局官网上,可以看到由其发布的标准规范。2、密码算法首先知道什么是密码,密码就是将正常的信息加密后变为无法正常识别的编码,可以认为是一种混淆......
  • LeetCode每日算法2—两数相加
    题目描述给出两个非空的链表用来表示两个非负的整数。其中,它们各自的位数是按照逆序的方式存储的,并且它们的每个节点只能存储一位数字。如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。您可以假设除了数字0之外,这两个数都不会以0开头。示例输入:(2......
  • 10.30算法
    无重复字符的最长子串给定一个字符串s,请你找出其中不含有重复字符的 最长子串 的长度。 示例 1:输入:s="abcabcbb"输出:3解释:因为无重复字符的最长子串是"abc",所以其长度为3。示例2:输入:s="bbbbb"输出:1解释:因为无重复字符的最长子串是"b",所以其长度......
  • 基于深度学习的自动驾驶汽车语义分割与场景标注算法研究。
    自动驾驶汽车是当前研究的热点领域之一,其中基于深度学习的语义分割与场景标注算法在自动驾驶汽车的视觉感知中具有重要作用。本文将围绕自动驾驶汽车的语义分割与场景标注算法展开研究。一、研究背景随着人工智能技术的不断发展,自动驾驶汽车逐渐成为汽车产业的重要发展方向。在......
  • 【基础算法】枚举
    一、枚举思想枚举法,也称穷举法,是指在解决问题的时候穷举每一种可能的情况,最终得到符合要求的答案。枚举法的效率并不高,但适用于一些没有明显规律可循的场景。枚举的算法思想:在解决某些问题时,可能没有办法按一定规律从众多候选答案中找到正确的解。这时,可将所有候选答案逐一列出,......