一道简单的面试题

1.问题描述

有如下规律的数字串：

① 1
② 11                ①中有1个1
③ 21                ②中有2个1
④ 1211            ③中有1个2,1个1
⑤ 111221        ④中有1个1,1个2,2个1
⑥ 312211        ⑤中有3个1,2个2,1个1
⑦ 13112221
⑧ 1113213211

    …

假设任一数字串的长度都不小于它前面的串，比如⑦的长度大于⑥的，越往后推导得到的串越长。

 

给定两个数字串str1和str2，其中str1是属于上面中的某一串，str2是随机给的数字串，写一个函数判断判断str2是否也上面中的某一串，函数形如bool function(str1,str2)，是返回true，否则返回false。

2.解决方案

本来以为这题有什么窍门，当时想了半天都没发现有什么简便的方法，而且时间很紧，要在纸上手写代码，String类的函数也不太记得，没弄出来，面试就这样被鄙视了。最笨的方法是用给定的str1一级级的推导，先比较str1和str2的长度，如果str2的长度比str1小，说明它可能是str1前面的某一串，用str1往前推，将推导出的串与str2比较看是否相等，反之往后推。这道题主要是为了考察手写代码的能力，并不是找窍门，我路子走偏了。下面是笨方法的代码实现，敬请批评指正：

 

/*	1
 * 	1 1
 * 	2 1
 * 	1 2 1 1
 * 	1 1 1 2 2 1
 * 	3 1 2 2 1 1
 * 	1 3 1 1 2 2 2 1
 * 	...
 * 
 * */
public class Test {
	
	//对给定的有规律的数字串推出下一个串
	public static String nextString(String str) {
		char tmp = str.charAt(0);
		int i = 1;
		int j = 1;
		StringBuffer sbf= new StringBuffer();
		while(i < str.length()) {
			if(tmp == str.charAt(i)) {
				i++;
				j++;
			} else {
				sbf.append(String.valueOf(j)).append(tmp);
				tmp = str.charAt(i);
				i++;
				j = 1;
			}
		}
		sbf.append(String.valueOf(j)).append(tmp);
		return sbf.toString();
	}
	
	//对给定的有规律的数字串推出它前面的串
	public static String previousString(String str) {
		StringBuffer sbf= new StringBuffer();
		for(int i = 0; i < str.length(); i = i + 2) {
			char tem = str.charAt(i + 1);
			int num = Integer.parseInt(String.valueOf(str.charAt(i)));
			while(num > 0) {
				sbf.append(tem);
				num--;
			}
		}
		return sbf.toString();
	}
	
	public static boolean test(String str1, String str2) {
		boolean flag = false;
		if(str1.length() == str2.length()) {
			if(str1.equals(str2) || previousString(str1).equals(str2)
					|| nextString(str1).equals(str2)) {
				flag = true;
			}
		} else if(str1.length() > str2.length()) {
			String tempString =  previousString(str1);
			while(tempString.length() >= str2.length()) {
				if(tempString.equals(str2)) {
					flag = true;
					break;
				} else {
					tempString = previousString(tempString);
				}
			}
		} else {
			String tempString = nextString(str1);
			while(tempString.length() <= str2.length()) {
				if(tempString.equals(str2)) {
					flag = true;
					break;
				} else {
					tempString = nextString(tempString);
				}
			}
		}
		return flag;
	}
	
	public static void main(String[] args) {
		System.out.println(test("312211","111221"));
		System.out.println(test("312211","11"));
		System.out.println(test("21","111221"));
		System.out.println(test("21","11122"));
		System.out.println(test("111221","12"));
	}
}