题解 | #字母交换#

字母交换

https://www.nowcoder.com/practice/8da0ea4b4853464795f5c32634a1b06f

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);

        while(in.hasNext()){
            solution(in);
        }
    }

    /**
     * 动态规划
     * 
     * dp[i][j]表示使字符串中从第i个a到第j个a(共j-i+1个a)位置连续时需要进行的最少交换次数(以a为例)
     * 为了得到最少交换次数, 应该使用的移动策略: 从两边到中间
     * dp[i][j] = dp[i+1][j-1] + (pos(j)-pos(i)) - (j-i)
     * 
     * 推导过程:
     * dp[i][j] = dp[i+1][j-1] + (pos(i+1)-pos(i)-1) + (pos(j)-pos(j-1)-1) + [(pos(j-1)-pos(i+1)+1) - (j-i-1)]
     *          = dp[i+1][j-1] + (pos(j)-pos(i)) - (j-i)
     *          
     * 示例:
     * letters    a  b  a  c  d  a  f  f  a  b
     * posList    0  1  2  3  4  5  6  7  8  9
     * i    j     0     1        2        3
     * 
     * i=0 j=3
     * dp[0][3] = dp[1][2] + (pos(1)-pos(0)-1) + (pos(3)-pos(2)-1) + [(pos(2)-pos(1)+1) - (3-0-1)]
     *          = 2 + (2-0-1) + (8-5-1) + [(5-2+1) - (3-0-1)]
     *          = 2 + 1 + 2 + 4 - 2
     *          = 7
     * dp[0][3] = dp[1][2] + (pos(3)-pos(0)) - (3-0)
     *          = 2 + (8-0) - (3-0)
     *          = 2 + 8 - 3
     *          = 7
     * 
     * @param in
     */
    private static void solution(Scanner in){
        String letters = in.next();
        int m = in.nextInt();

        // 记录同一字母的不同位置index
        HashMap<Character, List<Integer>> letterMap = new HashMap<>();
        for(int i=0; i<letters.length(); i++){
            char letter = letters.charAt(i);
            List<Integer> list = letterMap.getOrDefault(letter, new ArrayList<>());
            list.add(i);
            letterMap.put(letter, list);
        }

        int result = 1;
        for(List<Integer> posList: letterMap.values()){
            int size = posList.size();
            // 该字母总数小于等于结果
            if(size <= result){
                continue;
            }
            
            int[][] dp = new int[size][size];
            for(int interval=1; interval<size; interval++){
                for(int i=0; i+interval<size; i++){
                    int j = i+interval;
                    dp[i][j] = dp[i+1][j-1]+(posList.get(j)-posList.get(i))-interval;
                    if(dp[i][j] <= m){
                        result = Math.max(result, j-i+1);
                    }
                }
            }
        }

        System.out.println(result);
    }
}

全部评论

相关推荐

点赞 评论 收藏
分享
Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务