e*****e
发帖数: 1275 | 1 Initially you have a 2x2 matrix, say zoom1:
a b
c d
zooming it results in a 4x4 matrix (zoom2) as follows:
aa ab ba bb
ac ad bc bd
ca cb da db
cc cd dc dd
zooming it again will result in an 8x8 matrix and so on..
aaaa aaab abaa abab baba babb bbba bbbb
aaac aaad abac abad babc babd bdba bdbb
acaa acab adaa adab bcba bcbb bdba bdbb
acac acad adac adad bcbc bcbd bdbc bdbd
caca cacb cbca cbcb dada dadb dbda dbda
cacc cacd cbcc cbcd dadc dadd dbdc dbdd
ccca cccb cdca cdcb dcda dcdb ddda dddb
cccc cccd cdcc cdcd dcdc dcdd dddc dddd
The question is, given a sequence say abaaccda... we need to find out the
sequence coming just left to it. For e.g. if the given sequence is "bd" for
zoom2, the sequence coming just left to it is "bc". For "cd" it's "cc" etc. | g***s
发帖数: 3811 | 2 这个zoom是把每一个2×2扩大到4×4.是不是？
首先可以容易发现，这些字符串都有一个特性：把它分成前后两半，只有最后一位是不
同的。
根据这个特性，我们可以把任何一个2^n位的字符串，一一对应到一个n+1位的字符串
encode(s) = encode( s的前一半）+ s后一半的最后一位
同时，这个逆过程也是存在的。设为decode(s).具体就不列了。
那么现在我们题目可以转化成为，找f(s)的左边。
算法如下：
假设encode(s)=src=x1x2...xn
t[a]=b
t[b]=a
t[c]=d
t[d]=c
string prev(src,n) {
if (n==-1) return '' ; //最左元素的左边元素为同行最右边的；
lastChar = src[n-1];
if (lastChar=='d' || lastChar== 'b‘） return src.substring(0,n-1) + t(
lastChar);
else return prev(src.substring(0,n-1)) + t(lastChar);
}
所以，给定字符串 X 找到方法是
1. 用encode(X)得到Y
2. 用prev(Y)得到Z
3. 用decode（Z)得到W
返回W
× 如果我们不希望最左的元素返回同行最右边元素 |
|
