前言
今天通知过了笔试，但觉得笔试没来得及做的题还是要做一下。
题目
第二道题，字符串的，大意就是，给你个形如a,b,c,ab,bb,cb,ac,bc,cc,aab,bab,cab,abb,bbb,cbb,acb,bcb,ccb......按某种规律排列的无限长的字符串数组，要求：
1）给定一个位置，输出对应的字符串。
2）给定一个字符串，找出它在这个数组里的位置。
思路
仔细观察会发现其实就是用a,b,c在每一个字符串上不断循环头插得到新的字符串，比如a,b,c循环在b,c字符上头插得到,ab,bb,cb,ac,bc,cc，然后又在,ab,bb,cb,ac,bc,cc字符串的头部插入得到,aab,bab,cab,abb,bbb,cbb,acb,bcb,ccb......ccc。也就是说N位长度的一系列字符串是在N-1位长度的字符串上头插a,b,c得到的。那么可以用一个动态增长的数组来模拟这种情况，c++的vector是个不错的选择。
另外还要知道的是：N位长的字符串集合的最后一个字符串在该数组中的位置是3 ^ N，比如1位长的最后一个字符是“c”,位置在3^1 = 3。同理2位长度的最后一个字符串"cc"位置为9，同理"ccc"位置为27，以此类推。所以数组不管如何更新，它的长度一定是3^N，且N位长度的字符串的个数为2 * 3^(N - 2)。
那么对于 题目1) 求指定位置的字符串有如下代码：
#include<iostream> #include<vector> #include<math.h> using namespace std; const string base = "abc"; int main() { int pos; vector<string> res = {"woshishabi","a","b","c"}; //动态增长的字符串数组，从1开始操作更方便 while(cin >> pos) //根据输入的位置来更新数组 { int index = pos + 1; //加一，因为题目要求从0开始，但是从1开始便于操作。 int len = res.size() - 1; if(index <= len) //先判断指定位置的字符串所在的字符串集合是否已经在数组中了。 { cout << res[index] << endl; continue; } //没有的话就把它所在的对应位数的所有字符串放入数组中 int digit = 1; while(pow(3,digit) < index) { digit++; //循环结束得到需要更新的digit位长的字符串 } int End = pow(3,digit - 1); //digit - 1位字符串的结束位置 //int dis = num - len; int start = 1 + len - 2 * pow(3,res[len].size() - 1); //res中的最多位数的字符串集合的开始位置 while(start != End) //开始更新字符串数组 { for(int i = 0;i < base.size();i++) { string temp = res[start]; temp.insert(0,1,base[i]); res.push_back(temp); } start++; } cout << res[index] << endl; //输出对应位置的字符串即可 } }
可以看到初始我是先把a,b,c放入数组中。然后基于输入的位置来确定需要更新到的最大位数。
对于题目2)求指定字符串的位置，
1.可以根据它的长度L确定它所在集合的最后一个字符串的位置lastpos = pow(3,L)。
2.求这个字符串集合的首位置startpos = lastpos - 2 * 3^(L- 2) + 1。
3.然后在[startpos,lastpos]区间找这个字符串就行，如果lastpos > res的长度，转4.
4.如果lastpos > res的长度就用题目1)的解决方法更新res的内容就行，然后再去查找。