一、两名字的缘分值
题目 ：缘分值定义：两个名字（字符串）通过删除字符，使得留下的子串一直，所删除的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); } }}