计算字符串相似度

对于不同的字符串，我们希望能有办法判断相似程度，我们定义了一套操作方法来把两个不相同的字符串变得相同，具体的操作方法如下： 1 修改一个字符，如把“a”替换为“b”。 2 增加一个字符，如把“abdd”变为“aebdd”。 3 删除一个字符，如把“travelling”变为“traveling”。 比如，对于“abcdefg”和“abcdef”两个字符串来说，我们认为可以通过增加和减少一个“g”的方式来达到目的。上面的两种方案，都只需要一次操作。把这个操作所需要的次数定义为两个字符串的距离，而相似度等于“距离＋1”的倒数。也就是说，“abcdefg”和“abcdef”的距离为1，相似度为1/2=0.5. 给定任意两个字符串，你是否能写出一个算法来计算出它们的相似度呢？

import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; /** * 计算两个字符串的距离 = 由一个字符串转换成另一个字符串所需的最少编辑操作次数。 * 许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。 * @author chronos * */ public class Main { public static void main(String[] args) throws IOException { BufferedReader read = new BufferedReader(new InputStreamReader(System.in)); String input; while ((input = read.readLine()) != null){ String str2 = read.readLine(); System.out.println("1/"+stringDistance(input, str2)); } } public static int stringDistance(String str1, String str2) { char[] a = str1.toCharArray(); char[] b = str2.toCharArray(); int[][] len = new int[a.length + 1][b.length + 1]; for (int i = 0; i < a.length + 1; i++) { len[i][0] = i; } for (int j = 0; j <b.length + 1; j++) { len[0][j] = j; } for (int i = 1; i < a.length + 1; i++) { for (int j = 1; j < b.length + 1; j++) { if (a[i-1] == b[j-1]) { len[i][j] = len[i-1][j-1]; } else { len[i][j] = Math.min(Math.min(len[i - 1][j], len[i - 1][j - 1]), len[i][j - 1]) + 1; } } } return len[a.length][b.length]+1; } } #include <vector> #include <iostream> using namespace std; int main() { string s1, s2; while (cin >> s1 >> s2) { vector<vector<int> > dp(s1.length()+1, vector<int>(s2.length()+1, 0)); for (int i = 1; i <= s1.length(); ++i) dp[i][0] = i; for (int i = 1; i <= s2.length(); ++i) dp[0][i] = i; for (int i = 1; i <= s1.length(); ++i) for (int j = 1; j <= s2.length(); ++j) { if (s1[i-1] == s2[j-1]) dp[i][j] = dp[i-1][j-1]; else dp[i][j] = min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1])) + 1; } cout << "1/" << (dp[s1.length()][s2.length()]+1) << endl; } return 0; }

表示数字

将一个字符中所有出现的数字前后加上符号“*”，其他字符保持不变

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String str; while (null != (str = br.readLine())){ char[] strs = str.toCharArray(); StringBuilder result = new StringBuilder(); int i = 0; while (i<strs.length){ if ('0'<=strs[i]&&strs[i]<='9'){ result.append("*"); result.append(strs[i]); while (++i< strs.length&&'0'<=strs[i]&&strs[i]<='9'){ result.append(strs[i]); } result.append("*"); }else{ result.append(strs[i]); i++; } } System.out.println(result.toString().trim()); } } } #include <stdio.h> #include <string.h> bool isNum(char c){ return '0'<=c && c<='9'; } int main(){ char str[100] = {0}; while(scanf("%s", str)!=EOF){ int len = strlen(str); if(isNum(str[0])){ printf("*"); } for(int i=0;i<(len-1);i++){ if(isNum(str[i]) && !isNum(str[i+1])){ printf("%c*", str[i]); } else if(!isNum(str[i]) && isNum(str[i+1])){ printf("%c*", str[i]); } else{ printf("%c", str[i]); } } if(isNum(str[len-1])){ printf("%c*", str[len-1]); } else{ printf("%c", str[len-1]); } printf("\n"); } return 0; }

合法IP

现在IPV4下用一个32位无符号整数来表示，一般用点分方式来显示，点将IP地址分成4个部分，每个部分为8位，表示成一个无符号整数（因此不需要用正号出现），如10.137.17.1，是我们非常熟悉的IP地址，一个IP地址串中没有空格出现（因为要表示成一个32数字）。 现在需要你用程序来判断IP是否合法。

import java.io.*; import java.util.*; public class Main{ public static void main(String[] args)throws IOException{ BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); String str = ""; while((str = bf.readLine()) != null){ String[] subIP = str.split("\\."); for(int i =0; i < subIP.length; i++){ Integer intIP = Integer.valueOf(subIP[i]); if(intIP >= 0 && intIP<=255){ if(i == subIP.length-1){ System.out.println("YES"); } continue; } else{ System.out.println("NO"); break; } } } } } #include <string> #include <stdio.h> #include <stdlib.h> using namespace std; int main(void){ int a,b,c,d; while(scanf("%d.%d.%d.%d",&a,&b,&c,&d) != EOF){ if(a<0 || a>255) puts("NO"); else if(b<0 || b>255) puts("NO"); else if(c<0 || c>255) puts("NO"); else if(d<0 || d>255) puts("NO"); else puts("YES"); } return 0; }

扑克牌大小

扑克牌游戏大家应该都比较熟悉了，一副牌由54张组成，含3~A、2各4张，小王1张，大王1张。牌面从小到大用如下字符和字符串表示（其中，小写joker表示小王，大写JOKER表示大王）： 3 4 5 6 7 8 9 10 J Q K A 2 joker JOKER 输入两手牌，两手牌之间用"-“连接，每手牌的每张牌以空格分隔，”-"两边没有空格，如：4 4 4 4-joker JOKER。 请比较两手牌大小，输出较大的牌，如果不存在比较关系则输出ERROR。 基本规则： （1）输入每手牌可能是个子、对子、顺子（连续5张）、三个、炸弹（四个）和对王中的一种，不存在其他情况，由输入保证两手牌都是合法的，顺子已经从小到大排列； （2）除了炸弹和对王可以和所有牌比较之外，其他类型的牌只能跟相同类型的存在比较关系（如，对子跟对子比较，三个跟三个比较），不考虑拆牌情况（如：将对子拆分成个子）； （3）大小规则跟大家平时了解的常见规则相同，个子、对子、三个比较牌面大小；顺子比较最小牌大小；炸弹大于前面所有的牌，炸弹之间比较牌面大小；对王是最大的牌； （4）输入的两手牌不会出现相等的情况。

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; /** * Puke * @author uyz * 20/09/07 */ public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String str; while ((str = br.readLine()) != null) { System.out.println(compare(str)); } } public static String compare(String str) { String[] strings = str.split("-"); String[] puk1 = strings[0].split(" "); String[] puk2 = strings[1].split(" "); int count1 = puk1.length; int count2 = puk2.length; // 当两组牌数不同时，进行如下比较 // 当有一个为对王时，直接输出 // 当有一个是炸弹时，直接输出，其余情况不可比较 if (count1 != count2) { if (puk1[0].equals("joker") || puk1[0].equals("JOKER")) { return strings[0]; } else if (puk2[0].equals("joker") || puk2[0].equals("JOKER")) { return strings[1]; } else if (count1 == 4) { return strings[0]; } else if (count2 == 4) { return strings[1]; } else { return "ERROR"; } } else { // 当两组牌的个数相同时，有如下判断逻辑 // 当一组为对王时，说明其他一组为对子，直接输出对王 // 当两组为炸弹时，比较大小 // 当两组为顺子时，比较最小牌大小 // 当两组为对子时，比较最大牌 // 当两组均为单牌时，王为最大牌，比较最大牌 if (count2 == 2) { if (puk1[0].equals("joker") || puk1[0].equals("JOKER")) { return strings[0]; } else if (puk2[0].equals("joker") || puk2[0].equals("JOKER")) { return strings[1]; } else { return compare2(strings); } } else if (count1 == 4) { return compare2(strings); } else if (count1 == 5) { // 顺子比较最小的 return compare2(strings); } else if (count1 == 3) { // 三个比较 return compare2(strings); } else if (count1 == 1) { return compare2(strings); } else { return "ERROR"; } } } public static String compare2(String[] str) { String string = "345678910JQKA2jokerJOKER"; String[] puk1 = str[0].split(" "); String[] puk2 = str[1].split(" "); if (string.indexOf(puk1[0]) > string.indexOf(puk2[0])) { return str[0]; } else { return str[1]; } } } //“输入每手牌可能是个子，对子，顺子（连续5张），三个，炸弹（四个）和对王中的一种， //不存在其他情况，由输入保证两手牌都是合法的，顺子已经从小到大排列“ //这句规则让牌面类型的确定和大小的比较直接可以转换为牌个数的比较了，这是解决测试问题的捷径！ //所以一定要善于利用题目已知条件！！！ #include <iostream> #include <string> #include <algorithm> using namespace std; int main(){ string line; while(getline(cin,line)){ if(line.find("joker JOKER")!=-1) cout<<"joker JOKER"<<endl; else{ int dash=line.find('-'); string car1=line.substr(0,dash); string car2=line.substr(dash+1); int c1=count(car1.begin(),car1.end(),' '); int c2=count(car2.begin(),car2.end(),' '); string first1=car1.substr(0,car1.find(' ')); string first2=car2.substr(0,car2.find(' ')); string str="345678910JQKA2jokerJOKER"; if(c1==c2){ if(str.find(first1)>str.find(first2)) cout<<car1<<endl; else cout<<car2<<endl; }else if(c1==3) cout<<car1<<endl; else if(c2==3) cout<<car2<<endl; else cout<<"ERROR"<<endl; } } }