读题:
一串只含大写字母的字符串,按照把一个字母连续写它在字母表里的顺序遍的方式,求经过106次变换后得到的字符串的第n位
思路:
仔细想想,模拟肯定不行,因为模拟的话你都不知道它重复几遍。我们来算一下,一个A变化106次后变成了1的 (106)次方个A,说白了还是A。但B开始不一样了。那B怎么变呢?第一遍B变成BB,第二遍变成BBBB,第三遍变成BBBBBBBB,……,106遍后变成了2的(106)个B。我们知道int上限为2147483647,即231-1,而这个可怕的数值比max_int大的多;对于max_int而言,它又比106大的多了,也就是说,如果一个字符串为AAAAB,那么变换后它符合要求的第n位就直接得到B。
那么,现在思路差不多有了吧。先开一个计数变量idx,初始化为0,遇到A加1,如果idx等于输入的n,那么直接输出A。当然,遇到B甚至在B后面的字母,直接输出这个字母就行了,因为n去最大值106也没有它变化完的长度长。遍历完字符串时,如果还没有结束,即idx<n的情况,此时只可能是全程只有A的情况,那么输出A即可。
代码: