具有给定数值的最小字符串 图解题解
这道题到底在问什么
- 输入
- n=3, k=27
- 输出
- aay
- 输入
- n=5, k=73
- 输出
- aaszz
- 输入
- n=1, k=1
- 输出
- a
最优解：一步一步想明白
- 3记牢两步:先全填 a 拿最小底盘;再从最后一位往前把要补的值铺成 z,剩的零头加到中间一位。下面每帧都在套这两步。
- 4上面这排六个占位点,就是要拼的六位串,现在一位都没填。右边账本记三样:目标数值 k 是 80,当前已凑到的数值,还有两者的差,也就是还要补多少。接下来先把每一位都铺成最小的 a。
- 5把第 0 位填成 a,亮起来的就是它。a 的数值是 1,填到这里累计数值是 1。先全用 a,既保证左边字典序最小,数值也从最小起步。
- 6把第 1 位填成 a,亮起来的就是它。a 的数值是 1,填到这里累计数值是 2。先全用 a,既保证左边字典序最小,数值也从最小起步。
- 7把第 2 位填成 a,亮起来的就是它。a 的数值是 1,填到这里累计数值是 3。先全用 a,既保证左边字典序最小,数值也从最小起步。
- 8把第 3 位填成 a,亮起来的就是它。a 的数值是 1,填到这里累计数值是 4。先全用 a,既保证左边字典序最小,数值也从最小起步。
- 9把第 4 位填成 a,亮起来的就是它。a 的数值是 1,填到这里累计数值是 5。先全用 a,既保证左边字典序最小,数值也从最小起步。
- 10把第 5 位填成 a,亮起来的就是它。a 的数值是 1,填到这里累计数值是 6。先全用 a,既保证左边字典序最小,数值也从最小起步。
- 11六位现在全是 a,串是 "aaaaaa",数值是 6。这是字典序能给到的最小底盘。但目标数值是 80,眼下只有 6,还差一大截,下面要把缺口补上。
- 12目标 80 减去底盘 6,得到缺口 74。这 74 点就是要靠把某些 a 换成更大的字母补回来的量。问题只剩一个:这些增大放在哪几位最划算。
- 13字典序是从左往右比的,越靠左越想留小字母 a。所以把增大数值这件事尽量推到最右边,从最后一位也就是第 5 位开始动手。指针先停在第 5 位上。
- 14看第 5 位。现在还要补 74 点,比 25 多,说明这一位可以从 a 直接顶到 z。a 到 z 差 25,顶上去正好吃掉 25 点缺口,把最大的增量压在这个靠右的位置最省字典序。
- 15把第 5 位从 a 改成 z,蓝色标出来的就是已经铺好的 z。缺口从 74 减到 49。串现在是 "aaaaaz"。接着往左挪一位,看还要不要继续铺。
- 16看第 4 位。现在还要补 49 点,比 25 多,说明这一位可以从 a 直接顶到 z。a 到 z 差 25,顶上去正好吃掉 25 点缺口,把最大的增量压在这个靠右的位置最省字典序。
- 17把第 4 位从 a 改成 z,蓝色标出来的就是已经铺好的 z。缺口从 49 减到 24。串现在是 "aaaazz"。接着往左挪一位,看还要不要继续铺。
- 18挪到第 3 位,现在只剩 24 点要补,不够再铺一个满 z 了。所以铺 z 的过程到此为止,剩下这点零头要一次性加到当前这一位上。
- 19这第 3 位就是中间那个调整字符。把剩下的 24 点加到它头上,也就是从 a 往后数 24 个字母。零头只有一份,所以这种调整位至多一个,它左边全是 a、右边全是 z。
- 20a 往后数 24 个字母,落在 y 上,把第 3 位定成 y。缺口正好清零。现在串是 "aaayzz",左边三个 a、中间一个 y、右边两个 z,全部就位。
- 21六位全部定下来,串是 "aaayzz",长度正好 6,第一个要求满足。下面再核一遍数值对不对、字典序是不是真的最小。
- 22把每位的数值加起来:三个 a 各 1,一个 y 是 25,两个 z 各 26,合起来 1 加 1 加 1 加 25 加 26 加 26,正好是 80。数值这一关也对上了。
- 23再看字典序:最左边能留的位置全留了最小的 a,不得不增大的 y 和两个 z 全被压到了右边。任何把大字母往左挪的改法都会让字典序变大,所以这就是字典序最小的那个串。
- 24整体回放一遍:先把六位都铺成 a 拿到最小底盘,算出还差 74,从最后一位往左把缺口铺成两个 z,剩下的 24 点加到中间一位变成 y。三步走完,得到 "aaayzz",和题目要的答案严丝合缝。
⚠️ 容易写错的地方
✗ 错：把缺口直接算成 k,忘了每位至少是 a
✓ 对：缺口要算成 k 减 n,因为 n 位每位最少贡献 1
一上来全填 a 已经占掉了 n 点数值,真正还需要额外补的是 k 减 n。要是拿 k 当缺口去铺 z,数值会超标,拼出来的串数值大于 k
✗ 错：铺 z 的条件写成「剩余大于等于 25 就铺」
✓ 对：条件是「剩余大于 25 才铺满 z」,等于 25 时留给中间位
当剩余正好 25 时,这一位应该由中间调整位吸收,a 加 25 正好变成 z;若写成大于等于 25,下标 i 会往左多挪一步,遇到剩下数值刚好铺满所有位的情况,比如 n 等于 2、k 等于 52,下标会挪到负一越界。本稿先铺满 z、再无条件把零头加到当前位的写法,循环条件必须用严格大于 25
✗ 错：为了凑数值把大字母往左边堆
✓ 对：增大的部分一律往最右边推,左边尽量留 a
字典序从左往右比,左边的位权重最大。把 z 放左边会让字典序立刻变大,只有把小字母 a 留在左边、大字母压在右边,才是字典序最小
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def getSmallestString(self, n: int, k: int) -> str:
ans = ['a'] * n
i, d = n - 1, k - n
while d > 25:
ans[i] = 'z'
d -= 25
i -= 1
ans[i] = chr(ord(ans[i]) + d)
return ''.join(ans)C++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
string getSmallestString(int n, int k) {
string ans(n, 'a');
int i = n - 1, d = k - n;
for (; d > 25; d -= 25) {
ans[i--] = 'z';
}
ans[i] += d;
return ans;
}
};Java
import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
public String getSmallestString(int n, int k) {
char[] ans = new char[n];
Arrays.fill(ans, 'a');
int i = n - 1, d = k - n;
for (; d > 25; d -= 25) {
ans[i--] = 'z';
}
ans[i] = (char) ('a' + d);
return String.valueOf(ans);
}
}复杂度
时间
O(n)
先把 n 位全填 a 是一遍 O(n);再从末尾往前铺 z,每位最多被改一次,也是 O(n) 之内;没有任何排序。两段加起来还是线性的 O(n),n 是字符串长度
空间
O(n)
按峰值算,主要是那个长度 n 的字符数组或字符串,占 O(n),它既是中间结果也是最终答案。除它之外只用了 d 和 i 两个变量,是常数 O(1)。所以不计输出本身时辅助空间是 O(1),计入输出则是 O(n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 具有给定数值的最小字符串 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么先把每一位都填成 a,再从后往前改,而不是从前往后凑?+
a 是最小字符,全填 a 同时给出了字典序最小的底盘和最小的起步数值 n。字典序是从左往右比的,左边的位越小越占便宜,所以要让不得不增大的部分尽量远离左边、推到最右。从后往前改正好做到这一点:右边先顶到 z,左边能保留多少 a 就保留多少。要是从前往后凑,会过早地把大字母放在靠左的位置,字典序立刻变大。
中间那个调整字符是怎么冒出来的,为什么至多只有一个?+
从后往前每铺一个满 z,就消化掉 25 点缺口,因为 a 到 z 差 25。一直铺到剩下的缺口不足 25 时,这点零头没法再凑成一个满 z,就一次性加到当前这一位上,让它从 a 变成 a 到 z 之间的某个字母。因为缺口除以 25 的余数只有一个,所以这种夹在 a 和 z 之间的调整字符至多出现一个,它左边全是 a、右边全是 z。
这道题的时间和空间复杂度是多少,需要排序吗?+
不需要排序。填底盘是一遍线性扫描,从末尾往前铺 z 每位最多改一次,也在线性之内,所以时间是 O(n),n 是字符串长度。空间上,主要开销是那个长度 n 的字符数组,既当中间结果又当最终答案,占 O(n);除它之外只用了缺口 d 和下标 i 两个变量,是常数。所以不计输出时辅助空间 O(1),计入输出则 O(n)。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 具有给定数值的最小字符串 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。