1663. 具有给定数值的最小字符串【贪心算法】
小写字符的【数值】是它在字母表中的位置（从 1 开始），因此 a 的数值为 1 ，b 的数值为 2 ，c 的数值为 3 ，以此类推。
字符串由若干小写字符组成，字符串的数值 为各字符的数值之和。例如，字符串 “abe” 的数值等于 1 + 2 + 5 = 8 。
给你两个整数 n 和 k 。返回 长度 等于 n 且 数值 等于 k 的 字典序最小 的字符串。
注意，如果字符串 x 在字典排序中位于 y 之前，就认为 x 字典序比 y 小，有以下两种情况：
1、x 是 y 的一个前缀；
2、如果 i 是 x[i] != y[i] 的第一个位置，且 x[i] 在字母表中的位置比 y[i] 靠前。
- 方法一：自己写的算法
时间复杂度：O(n)，空间复杂度：xx
var getSmallestString = function (n, k) {
// 返回一个数组：长度为n，值为val
let setArr = (length, value) => {
if (length <= 0) {
return [];
}
let arr = [];
for(let i = 0;i < length; i++) {
arr.push(value);
}
return arr;
}
// 返回数字对应的字母
let getLetter = (num) => {
if (num === 0) {
return ''
}
// A - 65; a - 97
return String.fromCharCode(num + 96);
}
let left = k % 26; // 余数
let mul = Math.floor(k / 26); // 倍数
// mul 位值为 26 数组
let max = setArr(mul, 'z');
// 余数全部拆解 + mul 能够补齐 n 位
let ones = 0;
let mid = 0;
if((left + mul) === n) {
// 刚好补齐，直接返回 z
let min = setArr(left, 'a'); // 多个值为 1 的数组
return [...min, ...max].join('');
} else if((left + mul) > n ) {
// 可以补齐
ones = n - mul - 1;
mid = left - ones;
} else {
// 不能直接补齐，找 z 补齐
ones = n - mul - 1;
let zNum = ones;
do {
max.shift();
ones += 1; // z 的数量变少了
zNum += 1; // zNum 代表的是 ones，所以 ones + 1，zNum 也要 + 1
zNum = zNum > 26 ? (zNum - 26) : ones;
}while(zNum > 26)
mid = k - (ones + 26*(max.length));
if (mid < 0) {
mid += 26;
mid -= 1; // 倒数过来序号问题
ones += 1; // z 的数量变少了
max.shift();
}
// 缺少一位
if(mid === 0) {
ones += 1; // z 的数量变少了
mid = 25;
max.shift();
}
}
let min = setArr(ones, 'a'); // 多个值为 1 的数组
let midChar = getLetter(mid);
return [...min, midChar, ...max].join('');
};
- 方法二：贪心算法
时间复杂度：O(n)，空间复杂度：xx
// 策略：先全部都填充为 a，再从后往前填充z
var getSmallestString = (n, k) => {
// 全部填充为a --> 初始解
let arr = [];
for (let i = 0; i < n; i++) {
arr.push('a');
}
// n-- 相当于结果数组从后往前
while (n > 0) {
// n - 1 是 a 的个数 (n-1)个a
if (k - 26 >= n - 1) {
// k-26 的结果是否大于所需要的 a 的个数 -> 大于就赋值 26
arr[n - 1] = 'z';
k -= 26;
} else {
// 相当于k的值已经不能再减26了，否则n数量就不够了
// n - 1 是 a 的数量；由于ASC码从 a-97 算起，k 是 数量，从1算起，所以 97 - 1
arr[n - 1] = String.fromCharCode((97 - 1) + k - (n - 1));
break
}
n--;
}
return arr.join('');
}