多玩最新笔试题目

多玩的三个大题：

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);
	}

2：有一堆石子，或者被涂成红色或者被涂成绿色，从左到右排成一排。要求你用最小的次数对石子进行重新上色（不过只能涂成红色或者绿色），使得所有红色的石子都排在绿色石子的左边。程序输入参数为一个字符串String row，里面的每个字符只能是‘R’（代表红色）或者‘G’（代表绿色）。求出最少涂色几次，就能让所有红色的石子排在绿色石子的左边。

在考试的时候我是用递归来做，具体方法是求较小的值min("把一个石子上红色",“把一石子上绿色”)这样递归下去，终止条件是当字符串满足题意的时候。后来回来一想，根本没那么复杂，只要求做右边的R前面有几个G，最左边的G后面有几个R，然后取他们中的较小就可以了。只恨考试的时候怎么没发挥出来！！！！！（这个方法我测试了很多都正确，具体原理还有待考察），代码如下：

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();
	}

以上算法都是我自己的思考，不对之处，还望读者在后面指出，如果大家有更好的解法，也欢迎一起探讨！！！

其中试卷中还有一个小问题影响很深，题目是这样的，下面代码输出什么：

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());
	}
}

getClass方法是final的,方法的含义是返回运行时对象的类 运行时的对象是new City(),虚拟机现在只有City对象,所以getclass返回的必然是YY, 至于super,不要把它想成指像Country的引用，他只是个关键字 用来调用父类的方法的.

参考：

http://topic.csdn.net/u/20110612/22/a76763f4-ab32-4a1f-8fa0-608224e0a52b.html