Hard

题目描述

Alice 和 Bob 在玩一个游戏。初始时，Alice 有一个字符串 word = “a”。

给你一个正整数 k。同时给你一个整数数组 operations，其中 operations[i] 表示第 i 个操作的类型。

现在 Bob 会要求 Alice 按顺序执行所有操作：

  • 如果 operations[i] == 0，将 word 的副本追加到自身后面。
  • 如果 operations[i] == 1，生成一个新字符串，将 word 中的每个字符都变为英文字母表中的下一个字符，然后将其追加到原始 word 后面。例如，对 “c” 执行操作会生成 “cd”，对 “zb” 执行操作会生成 “zbac”。

返回执行完所有操作后 word 中第 k 个字符的值。

注意在第二种类型的操作中，字符 ‘z’ 可以变为 ‘a’。

示例 1：

输入：k = 5, operations = [0,0,0]
输出："a"
解释：
初始时，word == "a"。Alice 执行三个操作如下：
- 将 "a" 追加到 "a"，word 变为 "aa"。
- 将 "aa" 追加到 "aa"，word 变为 "aaaa"。  
- 将 "aaaa" 追加到 "aaaa"，word 变为 "aaaaaaaa"。

示例 2：

输入：k = 10, operations = [0,1,0,1]
输出："b"
解释：
初始时，word == "a"。Alice 执行四个操作如下：
- 将 "a" 追加到 "a"，word 变为 "aa"。
- 将 "bb" 追加到 "aa"，word 变为 "aabb"。
- 将 "aabb" 追加到 "aabb"，word 变为 "aabbaabb"。
- 将 "bbccbbcc" 追加到 "aabbaabb"，word 变为 "aabbaabbbbccbbcc"。

约束条件：

  • 1 <= k <= 10^14
  • 1 <= operations.length <= 100
  • operations[i] 是 0 或 1
  • 输入保证执行所有操作后 word 至少有 k 个字符

解题思路

这道题的关键观察是字符串长度会指数增长，但我们只需要找第 k 个字符，可以采用递归的思路。

核心思路：

  1. 每次操作后字符串长度都会翻倍，第 i 次操作后长度为 2^i
  2. 如果第 k 个字符在前半部分，它来自上一轮的结果
  3. 如果在后半部分，它来自前半部分经过当前操作变换的结果

算法步骤：

  1. 从后往前处理操作数组，找到哪些操作影响第 k 个字符
  2. 如果 k 在后半部分，将其映射到前半部分的对应位置
  3. 如果当前操作是类型1(增加字母)，记录需要增加的次数
  4. 递归处理直到回到初始状态，然后根据累计的变换次数计算最终字符

时间复杂度主要取决于操作数组的长度，空间复杂度为O(1)。

代码实现

class Solution {
public:
    char kthCharacter(long long k, vector<int>& operations) {
        return solve(k, operations, operations.size() - 1);
    }
    
private:
    char solve(long long k, vector<int>& operations, int opIndex) {
        if (opIndex < 0) {
            return 'a';
        }
        
        long long length = 1LL << (opIndex + 1);
        long long half = length / 2;
        
        if (k <= half) {
            return solve(k, operations, opIndex - 1);
        } else {
            char ch = solve(k - half, operations, opIndex - 1);
            if (operations[opIndex] == 1) {
                return ch == 'z' ? 'a' : ch + 1;
            }
            return ch;
        }
    }
};

class Solution:
    def kthCharacter(self, k: int, operations: List[int]) -> str:
        def solve(k, op_index):
            if op_index < 0:
                return 'a'
            
            length = 1 << (op_index + 1)
            half = length // 2
            
            if k <= half:
                return solve(k, op_index - 1)
            else:
                ch = solve(k - half, op_index - 1)
                if operations[op_index] == 1:
                    return 'a' if ch == 'z' else chr(ord(ch) + 1)
                return ch
        
        return solve(k, len(operations) - 1)

public class Solution {
    public char KthCharacter(long k, int[] operations) {
        return Solve(k, operations, operations.Length - 1);
    }
    
    private char Solve(long k, int[] operations, int opIndex) {
        if (opIndex < 0) {
            return 'a';
        }
        
        long length = 1L << (opIndex + 1);
        long half = length / 2;
        
        if (k <= half) {
            return Solve(k, operations, opIndex - 1);
        } else {
            char ch = Solve(k - half, operations, opIndex - 1);
            if (operations[opIndex] == 1) {
                return ch == 'z' ? 'a' : (char)(ch + 1);
            }
            return ch;
        }
    }
}

var kthCharacter = function(k, operations) {
    function solve(k, operations) {
        if (k === 1) return 0;
        
        let length = 1;
        let i = 0;
        
        while (length < k) {
            length *= 2;
            i++;
        }
        
        let prevLength = length / 2;
        
        if (k <= prevLength) {
            return solve(k, operations.slice(0, i - 1));
        } else {
            let shift = operations[i - 1];
            return (solve(k - prevLength, operations.slice(0, i - 1)) + shift) % 26;
        }
    }
    
    let result = solve(k, operations);
    return String.fromCharCode(97 + result);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(n)

其中 n 是 operations 数组的长度。时间复杂度为 O(n) 因为我们最多递归 n 次；空间复杂度为 O(n) 是由于递归调用栈的深度。

相关题目