-->

携程提前批笔试2021

一、两名字的缘分值

题目 :缘分值定义:两个名字(字符串)通过删除字符,使得留下的子串一直,所删除的ASCII之和最小值为两个名字的缘分值。
输入描述:输入两行名字,上下两行对应位置名字进行缘分值计算。
2<=每个名字的长度<=10,
2<=每个名字的<=20
输出描述:输出总缘分值。

样例输入:
Zhang San
Zhan Ai

样例输出:
563

说明
第一组名字,删除‘g’使其相等 ASCII =103,第二组都不同全要删掉,ASCII=290+170=460,总操作数103+460=563。

分析
1.该题有些误导,其主要过程是如果A的名字和B的名字的每个字的拼音分别相比较,而且区分大小写。
2.动态规划计算最长相同子序列,只是求完之后存下相同的char和出现频率
3.结果相加
ac 100%


import java.util.HashMap;
import java.util.Scanner;

public class Main {

    /**
     * 获取字符串的全部asc值
     * @param str 输入
     * @return 该字符串的asc值
     */
    static int getStrAsc(String str){
        int answer = 0;
        int len = str.length();
        for(int i = 0; i < len; i++){
            answer += (int)str.charAt(i);
        }
        return answer;
    }

    /**
     * 获取 strs 位于[start, end)之间的字符串asc值之和
     * @param strs 字符串数组
     * @param start 包含
     * @param end 不包含
     * @return 区间内asc之和
     */
    static int getStrsAsc(String[] strs, int start, int end){
        int answer = 0;
        for(int i = start; i < end; i++){
            answer += getStrAsc(strs[i]);
        }
        return answer;
    }

    /**
     * 主要计算函数
     * @param name1
     * @param name2
     * @return
     */
    static int calcSimilarity(String name1, String name2) {
        String[] name1s = name1.split(" ");
        String[] name2s = name2.split(" ");
        int len1 = name1s.length;
        int len2 = name2s.length;

        int answer = 0;
        // 算一下多出去的那部分字符串的asc值
        if(len2 > len1){
            answer += getStrsAsc(name2s, len1, len2);
        }else if(len1 > len2){
            answer += getStrsAsc(name1s, len2, len1);
        }
        int len = Math.min(len1, len2);

        for(int i = 0; i < len; i++){
            // 获得最长公共子序列的map,包含字符和出现次数
            HashMap<Character, Integer> map = getMap(name1s[i], name2s[i]);
            answer += getStrAsc(name1s[i]);
            answer += getStrAsc(name2s[i]);
            // 加和之和减去两倍公共的就是答案了
            for(Character item : map.keySet()){
                answer = answer - 2 * (int)item * map.get(item);
            }
        }

        return answer;
    }

    /**
     * 获得name1和name2的最长公共子序列的map,包含字符和次数
     * @param name1
     * @param name2
     * @return map
     */
    static HashMap<Character, Integer> getMap(String name1, String name2) {
        HashMap<Character, Integer> answer = new HashMap<>();

        int len1 = name1.length();
        int len2 = name2.length();
        int[][] dp = new int[len1+1][len2+1];
        // 记录这个最小值从哪里来,为了反向寻找
        int[][] from = new int[len1+1][len2+1];

        for(int i = 1; i <= len1; i++){
            for (int j = 1; j <= len2; j++) {
                if(name1.charAt(i-1) == name2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                    // 来自 i-1,j-1
                    from[i][j] = 0;
                }else if(dp[i-1][j] > dp[i][j-1]){
                    dp[i][j] = dp[i-1][j];
                    // 来自 i-1,j
                    from[i][j] = 1;
                }else{
                    dp[i][j] = dp[i][j-1];
                    // 来自 i,j-1
                    from[i][j] = 2;
                }
            }
        }
        
        int max = dp[len1][len2];
        // 反向寻找
        while(max > 0){
            int nexti = len1;
            int nextj = len2;
            // 下面的判断是找该节点来自哪里
            if(from[len1][len2] == 0){
                nexti--;
                nextj--;
            }else if(from[len1][len2] == 1){
                nexti--;
            }else {
                nextj--;
            }

            // 相同说明没贡献,找到第一个对最长序列有贡献的点就是最后一个相同的点
            if(dp[len1][len2] == dp[nexti][nextj]){
                len1 = nexti;
                len2 = nextj;
            }else {
                answer.put(name1.charAt(len1-1), answer.getOrDefault(name1.charAt(len1-1), 0)+1);
                len1 = nexti;
                len2 = nextj;
                max--;
            }
        }

        return answer;
    }


    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String name1 = in.nextLine();
            String name2 = in.nextLine();

            int sum = calcSimilarity(name1, name2);
            System.out.println(sum);
        }
    }
}



特别说明

由于众所周知的原因,本博客以往文章的图片无法显示,请谅解。

标签

生活纪实 (191) 感想 (115) ingress (54) 软件 (49) 小诗 (35) 梦境 (28) 教程 (21) 科幻 (21) 体会 (20) 杭州 (11) blogger (5) wordpress (5) Google adsense (4) Google voice (3) Chrome (2) Tensorflow (1) 谷粉 (1)