AlgoPressAppearance
1663-具有给定数值的最小字符串
题目描述
https://leetcode.cn/problems/smallest-string-with-a-given-numeric-value/description/
小写字符 的 数值 是它在字母表中的位置（从 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 <= 10^5
- n <= k <= 26 * n
思路：贪心
要想字符串尽量最小，应该尽量从前往后都编码为a，然后从后往前依次根据情况编码为z 先把所有数字编号为1，然后从后往前累计
csharp
public class Solution {
public string GetSmallestString(int n, int k) {
int[] arr = new int[n];
Array.Fill(arr,1);
int index = n-1;
k = k - n;
while(k > 0){
if(k >= 25){
k-=25;
arr[index] = 26;
index--;
}
else{
arr[index] += k;
k = 0;
}
}
//注意这里要使用 StringBuilder 否则会超时
StringBuilder result = new StringBuilder();
for(int i=0; i<arr.Length; i++){
result.Append((char)(arr[i]+96));
}
return result.ToString();
}
}
优化字符串处理
csharp
public class Solution {
//思路，先把所有数字编号为1，然后从后往前累计到
public string GetSmallestString(int n, int k) {
char[] result = new char[n];
Array.Fill(result,'a');
int index = n-1;
k = k - n;
while(k > 0){
if(k >= 25){
k-=25;
result[index] = 'z';
index--;
}
else{
result[index] = (char)('a' + k);
k = 0;
}
}
return new string(result);
}
}
思路2：贪心【官方】
贪心：从前往后开始计算 计算当前位置字符的时候，首先看后面都编码为 z 之后，当前的位置是否还能大于1，是的话，就按照增加的字符编码，否则就编码为 a 更加简洁
csharp
public class Solution {
public string GetSmallestString(int n, int k) {
StringBuilder ans = new StringBuilder();
for (int i = 1; i <= n; i++) {
int lower = Math.Max(1, k - (n - i) * 26);
k -= lower;
ans.Append((char) ('a' + lower - 1));
}
return ans.ToString();
}
}