L1-050 倒数第N个字符串（15 分）[java][python]

itzixiao

239人浏览 · 2026-04-24 17:40:36

itzixiao · 2026-04-24 17:40:36 发布

题目 ID：L1-050
题目分数：15 分
语言：Java / Python

题目描述

给定一个完全由小写英文字母组成的字符串等差递增序列，该序列中的每个字符串的长度固定为 L，从 L 个 a 开始，以 1 为步长递增。

例如当 L 为 3 时，序列为 { aaa, aab, aac, ..., aaz, aba, abb, ..., abz, ..., zzz }。

这个序列的倒数第 27 个字符串就是 zyz。对于任意给定的 L，本题要求你给出对应序列倒数第 N 个字符串。

输入格式

输入在一行中给出两个正整数 L（2 ≤ L ≤ 6）和 N（≤ 10^5）。

输出格式

在一行中输出对应序列倒数第 N 个字符串。题目保证这个字符串是存在的。

样例

输入

3 7417

输出

pat

解题思路

本题本质是26进制转换问题，核心逻辑如下：

1. 序列映射

将长度为 L 的字符串序列映射为 L 位 26 进制数，每一位的取值范围为 0~25，分别对应小写字母 a~z（0 对应 a，25 对应 z）：

序列第一个字符串（正数第 1 个）：L 个 a，对应 26 进制数 000...0，十进制值为 0
序列最后一个字符串（倒数第 1 个）：L 个 z，对应 26 进制数 ZZZ...Z，十进制值为 26^L - 1

2. 目标值计算

倒数第 N 个字符串，等于最后一个字符串的十进制值直接减去 N：

num = 26^L - N

3. 进制转换

将计算得到的十进制数 num 转换为 26 进制，每一位数字按映射规则转为小写字母。

4. 前导补位

如果转换后的 26 进制数不足 L 位，需要在高位补 a（即补 0），凑够 L 位后输出。

复杂度分析

时间复杂度：O(L)，进制转换最多 L 位
空间复杂度：O(L)，存储转换结果

代码实现

Java

import java.util.Scanner;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int L = scanner.nextInt();
        int N = scanner.nextInt();

        // 精确计算 26^L，避免 Math.pow 的精度问题
        int total = 1;
        for (int i = 0; i < L; i++) {
            total *= 26;
        }
        int num = total - N;

        ArrayList<Integer> digits = new ArrayList<>();
        // 十进制转 26 进制，按「低位到高位」的顺序存储
        while (num > 0) {
            digits.add(num % 26);
            num /= 26;
        }

        // 补前导 a（对应 26 进制高位补 0），凑够 L 位
        for (int i = 0; i < L - digits.size(); i++) {
            System.out.print('a');
        }
        // 倒序输出 digits，得到「高位到低位」的正确顺序
        for (int i = digits.size() - 1; i >= 0; i--) {
            System.out.print((char) ('a' + digits.get(i)));
        }
    }
}

Python

L, N = map(int, input().split())

# 精确计算 26^L
total = 26 ** L
num = total - N

res = []
# 十进制转 26 进制，按「低位到高位」的顺序存储
while num > 0:
    num, mod = divmod(num, 26)
    res.append(mod)

# 补前导 0（对应补字母 a），凑够 L 位
res += [0] * (L - len(res))
# 反转得到「高位到低位」的顺序，映射为字母后拼接输出
print(''.join(chr(ord('a') + x) for x in res[::-1]))

运行验证

以样例验证：

输入:
3 7417

计算过程:
- 26^3 = 17576
- num = 17576 - 7417 = 10159
- 10159 的 26 进制: 15, 2, 25 → 对应 p, c, z
- 补前导 a → acz... 不对，重新算

正确计算:
- 17576 - 7417 = 10159
- 10159 ÷ 26 = 390 余 15  → 15 = p
- 390 ÷ 26  = 15  余 0   → 0  = a
- 15 ÷ 26   = 0   余 15  → 15 = p
- 补 1 位前导 a
- 结果: a + p + a = apa ... 还是不对

实际上按代码逻辑:
10159 = 15*26^2 + 0*26^1 + 15*26^0 = 15*676 + 15 = 10159 ✓
即 p(15), p(15), z(25) → 但 10159 实际 = 15*676 + 0*26 + 15 = 15*676 + 15
= 390*26 + 15, 390 = 15*26 + 0
所以是 p(15) a(0) p(15)? 

重新手动:
17576 - 7417 = 10159
10159 / 26 = 390 r15  → 最低位 = p
390 / 26   = 15  r0   → 第二位 = a
15 / 26    = 0   r15  → 第三位 = p
补 1 位前导 a
结果 = a + p + a + p = apap ❌

等等... L=3, 补到 3 位应该是: 
已得到 3 位: p, a, p → 不需要补
反转: p, a, p
结果: pap ❌ 还是不对

答案是 pat... 
重新算: total = 26^3 = 17576
num = 17576 - 7417 = 10159
10159 的 26 进制:
10159 / 26 = 390 remainder 15  → digit[0] = 15 (p)
390 / 26   = 15   remainder 0   → digit[1] = 0  (a)
15 / 26    = 0    remainder 15  → digit[2] = 15 (p)
结果: p, a, p → pap? 但答案是 pat

哦我明白了，我算错了
17576 - 7417 = 10159 对的
但 10159 的 26 进制:
26^2 = 676
26^1 = 26
26^0 = 1

10159 / 676 = 15 remainder 10159 - 15*676 = 10159 - 10140 = 19
19 / 26 = 0 remainder 19
19 / 1 = 19

所以: 15, 0, 19 → p, a, t → pat ✓

Python验证:
>>> 26**3
17576
>>> 17576 - 7417
10159
>>> 10159 // 676
15
>>> 10159 % 676
19
>>> 19 // 26
0
>>> 19 % 26
19

digit = [15, 0, 19] → p, a, t → pat ✓

输出: pat ✓