具有给定数值的最小字符串【LC1663】
The numeric value of a lowercase character is defined as its position (1-indexed) in the alphabet, so the numeric value of a is 1, the numeric value of b is 2, the numeric value of c is 3, and so on.
The numeric value of a string consisting of lowercase characters is defined as the sum of its characters’ numeric values. For example, the numeric value of the string "abe" is equal to 1 + 2 + 5 = 8.
You are given two integers n and k. Return the lexicographically smallest string with length equal to n and numeric value equal to k.
Note that a string x is lexicographically smaller than string y if x comes before y in dictionary order, that is, either x is a prefix of y, or if i is the first position such that x[i] != y[i], then x[i] comes before y[i] in alphabetic order.
- 思路:贪心
局部最优:在保证字符串长度一定,优先在字符串尾部插入数值最大的字符,即使首部字符串尽可能为a、尾部字符串尽可能为z
全局最优:字符串的字典顺序最小
- 实现【总体超时】
从尾部开始插入字符,当n和k一定时,前n−1个字符需要的分数最少为n−1,那么可供第n个字符使用的分数为k−(n−1),因此第n个字符一定
。如果k−(n−1)>=26,那么尾部可以插入的最小字符为z='a'+25,贡献的分数为26
。如果k−(n−1)<26,那么尾部可以插入的最小字符为'a' + k-n,贡献的分数为k−n+1
class Solution { public String getSmallestString(int n, int k) { StringBuilder sb = new StringBuilder(); while (n > 0){ if (k - n + 1 >= 26){ sb.insert(0, (char)('a' + 25)); k -= 26; }else{ sb.insert(0, (char)('a' + k - n)); k -= k - n + 1; } n--; } return sb.toString(); } }
。复杂度
- 时间复杂度:O ( n 2 ) ,每构造一位字符需要将字符串后移一位,需要的时间复杂度为O(n),因此总时间复杂度为O ( n 2 )
- 空间复杂度:O ( 1 )
- 实现
从头部开始插入字符,当n 和k一定时,使前面的字符尽可能为a,后面的字符尽可能为z。当构造第i个字符时,后n−i个字符全为z需要的分数为(n−i)∗26,那么第i个字符需要贡献的分数为max(1,k−(n−i)∗26)
。如果k−(n−i)∗26>1,那么表示尾部全部插入z,仍有分数剩余,那么第i个字符应插入'a'+k-(n-i)*26-1,贡献的分数为k−(n−i)∗26
。如果k−(n−i)∗26<=1,那么表示尾部全部插入z,没有分数剩余甚至还有同于,那么第i个字符可以插入的最小字符'a',贡献的分数为1
class Solution { public String getSmallestString(int n, int k) { StringBuilder sb = new StringBuilder(); while (n > 0){ int lower = Math.max(1, k - (n - 1) * 26); sb.append((char)('a'+ lower - 1)); k -= lower; n--; } return sb.toString(); } }
。复杂度
- 时间复杂度:O ( n )
- 空间复杂度:O ( 1 )