2021-11-23：规定：L[1]对应a，L[2]对应b，L[3]对应c，...

原创

福大大架构师每日一题

修改于 2021-11-24 08:09:52

9650

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2021-11-23：规定：L1对应a，L2对应b，L3对应c，...，L25对应y。

S1 = a，

S(i) = S(i-1) + Li + 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 + L3 + 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字符。

来自网易。

答案2021-11-23：

单边递归。

时间复杂度：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)
}

执行结果如下：