多玩的三个大题：
1：X和Y是两串长度一样的字符串，X和Y的差异值定义为在两个字符串上对应位置上不一样的字符的个数，比如“ant”和“art”的差异值是1.给定两个字符串A和B，A的长度小于或者等于B，你可以在A的前面或者后面任意添加字符，使得A和B长度一样。写一个方法求出最后能得到的最小的差异值是多少？
说明：A和B的长度范围是[1，50] ， A和B的字符只包含‘a’-'z' ，A的长度小于或者等于B
这个题目做出来了，可是在笔试的时候递归那个地方写错了一点～～没有比较count了，下面是我的递归解法：
int minimize(String a , String b){
int alen = a.length(); int blen = b.length(); int count =50; if(alen==blen){ count=0; for(int i=0;i<alen;i++){ if(a.charAt(i)!=b.charAt(i)) count++; } return count; } String first = b.substring(1); String last = b.substring(0, b.length()-1); return Math.min(Math.min(minimize(a,first), minimize(a,last)),count); }int minimize(String a , String b){
int alen = a.length(); int blen = b.length(); int count =50; if(alen==blen){ count=0; for(int i=0;i<alen;i++){ if(a.charAt(i)!=b.charAt(i)) count++; } return count; } String first = b.substring(1); String last = b.substring(0, b.length()-1); return Math.min(Math.min(minimize(a,first), minimize(a,last)),count); }2：有一堆石子，或者被涂成红色或者被涂成绿色，从左到右排成一排。要求你用最小的次数对石子进行重新上色（不过只能涂成红色或者绿色），使得所有红色的石子都排在绿色石子的左边。程序输入参数为一个字符串String row，里面的每个字符只能是‘R’（代表红色）或者‘G’（代表绿色）。求出最少涂色几次，就能让所有红色的石子排在绿色石子的左边。
在考试的时候我是用递归来做，具体方法是求较小的值min("把一个石子上红色",“把一石子上绿色”)这样递归下去，终止条件是当字符串满足题意的时候。后来回来一想，根本没那么复杂，只要求做右边的R前面有几个G，最左边的G后面有几个R，然后取他们中的较小就可以了。只恨考试的时候怎么没发挥出来！！！！！（这个方法我测试了很多都正确，具体原理还有待考察），代码如下：
[java] view plaincopyprint? int minPaint(String row){ char[] c = row.toCharArray(); int rCount = 0; int gCount = 0; int i; for( i=c.length-1;i>=0;i--){ if(c[i]=='R') //求做右边的R break; } while(i>=0){ if(c[i]=='G') //最右边的R前面有几个G gCount++; i--; } for(i=0;i<c.length;i++){ if(c[i]=='G') //求最左边的G break; } while(i<c.length){ if(c[i]=='R') //最左边的G后面有几个R rCount++; i++; } return Math.min(rCount, gCount); //取教小的 }
int minPaint(String row){
char[] c = row.toCharArray(); int rCount = 0; int gCount = 0; int i; for( i=c.length-1;i>=0;i--){ if(c[i]=='R') //求做右边的R break; } while(i>=0){ if(c[i]=='G') //最右边的R前面有几个G gCount++; i--; } for(i=0;i<c.length;i++){ if(c[i]=='G') //求最左边的G break; } while(i<c.length){ if(c[i]=='R') //最左边的G后面有几个R rCount++; i++; } return Math.min(rCount, gCount); //取教小的}
3：有一个简单的编辑器只有两种命令
‘type <c>’,c是一个字符：把c添加到文本的末尾
‘undo <t>’,t是一个正整数：回滚t秒前所执行的操作，说明undo命令也可以被undo，undo命令对很久之前的操作不起作用
要求：编写一个函数public String getText(String[] cmds,int[] time)
cmd是输入的命令，包括上面两种命令，c取值a～z，t范围1～10^9 time是每个命令执行的时间。
示例：{"type a","type b","type c","type 3"} {1,2,3,5} Return：“a”
{"type a","type b","undo 2","type 2"} {1,2,3,4} Return：“a”
{"type a","undo 1","undo 1"} {1,2,3} Return：“a”
{"type a","type b","type c","undo 10"} {1,2,3,1000} Return：“abc”这个题目是最后一道编程题，我没有时间做了，回来想了一下，没那么难，为什么现场笔试的时候会时间不够呢？？？？？？？ 我的思路是：从后往前读命令，遇到undo命令就比较undo需要回退的时间，把这一段时间的操作都忽略，如果遇到type命令，则保留字符。最后输出字符的反转就ok了。我的代码如下：
public static void main(String[] args) {
String[] c = {"type a","type b","type c","undo 10"}; int[] t = {1,2,3,1000}; System.out.println(getText(c,t)); } public static String getText(String[] cmds,int[] time){ StringBuffer sb = new StringBuffer(""); int t = time[time.length-1]; for(int i=cmds.length-1;i>0;){ //从后往前读命令 if(cmds[i].contains("undo")){ // 遇到undo命令 if(time[i]-time[i-1]>100){ //如果是隔了100秒以上，则undo命令不失效 i--; continue; } else{ int u = Integer.parseInt(cmds[i].substring(5)); t = time[i]-u-1; //undo命令回退的时间 while(time[i]>t){ i--; } } } else{ sb.append(cmds[i].substring(5)); //遇到type命令 i--; } } if(cmds[0].contains("undo")) //第一个命令单独处理 return sb.reverse().toString(); else return sb.append(cmds[0].substring(5)).reverse().toString(); }public static void main(String[] args) {
String[] c = {"type a","type b","type c","undo 10"}; int[] t = {1,2,3,1000}; System.out.println(getText(c,t)); } public static String getText(String[] cmds,int[] time){ StringBuffer sb = new StringBuffer(""); int t = time[time.length-1]; for(int i=cmds.length-1;i>0;){ //从后往前读命令 if(cmds[i].contains("undo")){ // 遇到undo命令 if(time[i]-time[i-1]>100){ //如果是隔了100秒以上，则undo命令不失效 i--; continue; } else{ int u = Integer.parseInt(cmds[i].substring(5)); t = time[i]-u-1; //undo命令回退的时间 while(time[i]>t){ i--; } } } else{ sb.append(cmds[i].substring(5)); //遇到type命令 i--; } } if(cmds[0].contains("undo")) //第一个命令单独处理 return sb.reverse().toString(); else return sb.append(cmds[0].substring(5)).reverse().toString(); }以上算法都是我自己的思考，不对之处，还望读者在后面指出，如果大家有更好的解法，也欢迎一起探讨！！！其中试卷中还有一个小问题影响很深，现在也没弄明白，题目是这样的，下面代码输出什么：
[java] view plaincopyprint?
class Country { } public class City extends Country { public static void main(String[] args) { City c=new City(); new City().yy(); } public void yy() { System.out.println(this.getClass().getName()); System.out.println(super.getClass().getName()); } }class Country {
} public class City extends Country { public static void main(String[] args) { City c=new City(); new City().yy(); } public void yy() { System.out.println(this.getClass().getName()); System.out.println(super.getClass().getName()); } }结果都是City，望知道的解释一下！！！