3304. 找出第 K 个字符 I

题目描述

Alice 和 Bob 正在玩一个游戏。最初，Alice 有一个字符串 word = "a"。

给定一个正整数 k。

现在 Bob 会要求 Alice 执行以下操作 无限次 :

将 word 中的每个字符更改为英文字母表中的 下一个 字符来生成一个新字符串，并将其追加到原始的 word。

例如，对 "c" 进行操作生成 "cd"，对 "zb" 进行操作生成 "zbac"。

在执行足够多的操作后， word 中至少存在 k 个字符，此时返回 word 中第 k 个字符的值。

示例 1:

输入：k = 5

输出："b"

解释：

最初，word = "a"。需要进行三次操作:

生成的字符串是 "b"，word 变为 "ab"。
生成的字符串是 "bc"，word 变为 "abbc"。
生成的字符串是 "bccd"，word 变为 "abbcbccd"。

示例 2:

输入：k = 10

输出："c"

提示：

1 <= k <= 500

解法

方法一：模拟

思考

每次操作把当前串每位字母后移一位再拼到末尾，长度翻倍。\(k \le 500\)，直接模拟直到长度不小于 \(k\) 即可。

不必真正维护字符串对象：用 \(0..25\) 表示相对 \(\texttt{a}\) 的偏移，复制时统一加一并对 \(26\) 取模。

长度足够后取下标 \(k-1\) 对应的字母。

我们可以使用一个数组 \(\textit{word}\) 来存储每次操作后的字符串，当 \(\textit{word}\) 的长度小于 \(k\) 时，我们不断地对 \(\textit{word}\) 进行操作。

最后返回 \(\textit{word}[k - 1]\) 即可。

时间复杂度 \(O(k)\)，空间复杂度 \(O(k)\)。其中 \(k\) 为输入参数。

Python3JavaC++GoTypeScriptRust

class Solution:
    def kthCharacter(self, k: int) -> str:
        word = [0]
        while len(word) < k:
            word.extend([(x + 1) % 26 for x in word])
        return chr(ord("a") + word[k - 1])

class Solution {
    public char kthCharacter(int k) {
        List<Integer> word = new ArrayList<>();
        word.add(0);
        while (word.size() < k) {
            for (int i = 0, m = word.size(); i < m; ++i) {
                word.add((word.get(i) + 1) % 26);
            }
        }
        return (char) ('a' + word.get(k - 1));
    }
}

class Solution {
public:
    char kthCharacter(int k) {
        vector<int> word;
        word.push_back(0);
        while (word.size() < k) {
            int m = word.size();
            for (int i = 0; i < m; ++i) {
                word.push_back((word[i] + 1) % 26);
            }
        }
        return 'a' + word[k - 1];
    }
};

func kthCharacter(k int) byte {
    word := []int{0}
    for len(word) < k {
        m := len(word)
        for i := 0; i < m; i++ {
            word = append(word, (word[i]+1)%26)
        }
    }
    return 'a' + byte(word[k-1])
}

function kthCharacter(k: number): string {
    const word: number[] = [0];
    while (word.length < k) {
        word.push(...word.map(x => (x + 1) % 26));
    }
    return String.fromCharCode(97 + word[k - 1]);
}

impl Solution {
    pub fn kth_character(k: i32) -> char {
        let mut word = vec![0];
        while word.len() < k as usize {
            let m = word.len();
            for i in 0..m {
                word.push((word[i] + 1) % 26);
            }
        }
        (b'a' + word[(k - 1) as usize] as u8) as char
    }
}

3304. 找出第 K 个字符 I

题目描述

解法

方法一：模拟

评论