class Solution {
public:
string getSmallestString(int n, int k) {
}
};
1663. 具有给定数值的最小字符串
小写字符 的 数值 是它在字母表中的位置（从 1 开始），因此 a 的数值为 1 ，b 的数值为 2 ，c 的数值为 3 ，以此类推。
字符串由若干小写字符组成，字符串的数值 为各字符的数值之和。例如，字符串 "abe" 的数值等于 1 + 2 + 5 = 8 。
给你两个整数 n 和 k 。返回 长度 等于 n 且 数值 等于 k 的 字典序最小 的字符串。
注意，如果字符串 x 在字典排序中位于 y 之前，就认为 x 字典序比 y 小，有以下两种情况：
x 是 y 的一个前缀；i 是 x[i] != y[i] 的第一个位置，且 x[i] 在字母表中的位置比 y[i] 靠前。
示例 1：
输入：n = 3, k = 27 输出："aay" 解释：字符串的数值为 1 + 1 + 25 = 27，它是数值满足要求且长度等于 3 字典序最小的字符串。
示例 2：
输入：n = 5, k = 73 输出："aaszz"
提示：
1 <= n <= 105n <= k <= 26 * n原站题解
python3 解法, 执行用时: 44 ms, 内存消耗: 15.6 MB, 提交时间: 2022-12-08 11:12:22
class Solution:
def getSmallestString(self, n: int, k: int) -> str:
k -= n
cnt_z = k // 25
last = k % 25
return 'a' * (n - 1 - cnt_z) + (chr(ord('a') + last) if cnt_z != n else '') + 'z' * cnt_z
cpp 解法, 执行用时: 28 ms, 内存消耗: 20.6 MB, 提交时间: 2022-12-08 11:11:22
class Solution {
public:
string getSmallestString(int n, int k) {
string res(n, 'a');
int diff = k - n;
int p = n - 1;
while (diff > 25) {
res[p--] = 'z';
diff -= 25;
}
res[p] = 'a' + diff;
return res;
}
};
javascript 解法, 执行用时: 176 ms, 内存消耗: 59.8 MB, 提交时间: 2022-12-08 11:10:33
/**
* @param {number} n
* @param {number} k
* @return {string}
*/
var getSmallestString = function(n, k) {
// k - n 每一位都是a的时候还差多少;i是下一个要进行填充的位
let res = Array(n).fill('a'), remain = k - n, i = n - 1;
while(remain) {
if(remain > 25) { // 当前位无法填充完
remain -= 25;
res[i] = 'z';
i --;
} else { // 当前位可以填充完剩余的值
res[i] = String.fromCharCode(97 + remain);
remain = 0;
}
}
return res.join('');
};
cpp 解法, 执行用时: 20 ms, 内存消耗: 30.2 MB, 提交时间: 2022-12-08 11:10:14
/**
* 首先将所有字符串都置为a，从后往前，依次将第i位置成相应的字母，
* 使用 （k - n）/ 25 计算出需要置为z的个数
* 然后通过 （k - n ) % 25 计算出z之前的那一位应该置为多少
* 超时是因为当n太大时，计算z的位数的过程中如果是按位遍历，计算次数太多。其实一步就能完成，（k - n）/ 25。
**/
class Solution {
public:
string getSmallestString(int n, int k) {
string res(n, 'a');
int bound = (k - n) / 25; // 需要置为 ‘z’的数量
int r = (k - n) % 25; // 第一个 z 前面那位
if (n - bound - 1 < 0) {
return string(bound, 'z');
}
return string (n - bound - 1, 'a') + string(1, 'a' + r) + string(bound, 'z');
}
};
cpp 解法, 执行用时: 28 ms, 内存消耗: 20.7 MB, 提交时间: 2022-12-08 11:09:52
/**
* 首先将所有字符串都置为a，从后往前，依次将第i位置成相应的字母，
* 使用 （k - n）/ 25 计算出需要置为z的个数
* 然后通过 （k - n ) % 25 计算出z之前的那一位应该置为多少
* 超时是因为当n太大时，计算z的位数的过程中如果是按位遍历，计算次数太多。其实一步就能完成，（k - n）/ 25。
**/
class Solution {
public:
string getSmallestString(int n, int k) {
string res(n, 'a');
int bound = (k - n) / 25; // 需要置为 ‘z’的数量
int r = (k - n) % 25; // 第一个 z 前面那位
if (n - bound - 1 >= 0) res[n-bound-1] = 'a' + r;
for (int i = n - bound; i < n; i++) {
res[i] = 'z';
}
return res;
}
};
python3 解法, 执行用时: 580 ms, 内存消耗: 17.5 MB, 提交时间: 2022-12-08 11:08:11
class Solution:
def getSmallestString(self, n: int, k: int) -> str:
ans = list()
for rest in range(n, 0, -1):
bound = k - 26 * (rest - 1)
if bound > 0:
ans.append(chr(bound + 96))
k -= bound
else:
ans.append("a")
k -= 1
return "".join(ans)