一道简单的面试题
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"));}}?