规定:L[1]对应a,L[2]对应b,L[3]对应c,…,L[25]对应y。
S1 = a,
S(i) = S(i-1) + L[i] + reverse(invert(S(i-1)));
解释invert操作:
S1 = a,
S2 = aby。
假设invert(S(2)) = 甲乙丙,
a + 甲 = 26, 那么 甲 = 26 - 1 = 25 -> y,
b + 乙 = 26, 那么 乙 = 26 - 2 = 24 -> x,
y + 丙 = 26, 那么 丙 = 26 - 25 = 1 -> a,
如上就是每一位的计算方式,所以invert(S2) = yxa。
所以S3 = S2 + L[3] + reverse(invert(S2)) = aby + c + axy = abycaxy,
invert(abycaxy) = yxawyba, 再reverse = abywaxy。
所以S4 = abycaxy + d + abywaxy = abycaxydabywaxy。
直到S25结束。
给定两个参数n和k,返回Sn的第k位是什么字符,n从1开始,k从1开始,
比如n=4,k=2,表示S4的第2个字符是什么,返回b字符。
单边递归。
时间复杂度:O((1)。数量有限。
额外空间复杂度:O(1)。数量有限。
代码用golang编写。代码如下:
package main
import "fmt"
func main() {
ret := kth(7, 1)
fmt.Printf("%c\r\n", ret)
ret = kth(7, 2)
fmt.Printf("%c\r\n", ret)
ret = kth(7, 3)
fmt.Printf("%c\r\n", ret)
ret = kth(7, 4)
fmt.Printf("%c\r\n", ret)
ret = kth(7, 5)
fmt.Printf("%c\r\n", ret)
ret = kth(7, 6)
fmt.Printf("%c\r\n", ret)
ret = kth(7, 7)
fmt.Printf("%c\r\n", ret)
}
var lens []int
func fillLens() {
lens = make([]int, 26)
lens[1] = 1
for i := 2; i <= 25; i++ {
lens[i] = (lens[i-1] << 1) + 1
}
}
// 求sn中的第k个字符
// O(n), s <= 25 O(1)
func kth(n, k int) byte {
if lens == nil {
fillLens()
}
if n == 1 { // 无视k
return 'a'
}
// sn half
half := lens[n-1]
if k <= half {
return kth(n-1, k)
} else if k == half+1 {
return byte('a' + n - 1)
} else {
// sn
// 我需要右半区,从左往右的第a个
// 需要找到,s(n-1)从右往左的第a个
// 当拿到字符之后,invert一下,就可以返回了!
return invert(kth(n-1, ((half+1)<<1)-k))
}
}
func invert(c byte) byte {
return byte(('a' << 1) + 24 - c)
}
执行结果如下: