Open Barney30818 opened 2 years ago
題目: 每個小寫字符都會對應相對的數值,如a->1,b->2,c->3...z->26,由小寫字符組成的字符串的數值定義為其字符的數值之和。例如,字符串的數值等於。"abe"1 + 2 + 5 = 8,給你兩個整數n和k。返回長度等於且數值等於的最小字符串。"n,k",且按字母順序排序。 顧名思義,字串會從'a'開始排序,能排'a'就排'a'不能的話再從'b'開始考量,依序下去,如範例。
範例
Input: n = 5, k = 73 Output: "aaszz" Explanation: The numeric value of the string is 1 + 1 + 19 + 26 + 26 = 73, and it is the smallest string with such a value and length equal to 5.
思路: 去思考在字母對應的數字加起來等於k的情況下,前面盡可能的排'a'而後面只能放'z'來達到題意要求,開lastCharIndex()功能並跑遞迴直到前面放不了'a'且算出'a'跟'z'中間要放的字母的index,並用StringBuilder來拼接回傳的字串已減少記憶體使用。
解題:
class Solution { public String getSmallestString(int n, int k) { StringBuilder sb = new StringBuilder(); int aCount = 0; //宣告'a'字母要放幾個 if(n==1){ char ch = (char)(k+96); //+96為int轉成小寫英文字母 sb.append(String.valueOf(ch)); return sb.toString(); }else{ int[] result = lastCharIndex(n,k,aCount,sb); aCount = result[1]; sb.append((char)(result[0]+96)); //放完'a'和剩下的字母,其餘放'z' for(int j=0; j<n-aCount-1; j++){ sb.append("z"); } } return sb.toString(); } //算出'a'能放的最大數量下,剩下的英文字母對應的ASCII位置 public static int[] lastCharIndex(int n, int k, int aCount, StringBuilder sb){ if((n-1)*26>k-1){ sb.append("a"); return lastCharIndex(n-1,k-1,aCount+1,sb); } int[] result = new int[2]; int lastCharIndex=0; lastCharIndex = k-(n-1)*26; result[0]=lastCharIndex; result[1]=aCount; return result; } }
題目: 每個小寫字符都會對應相對的數值,如a->1,b->2,c->3...z->26,由小寫字符組成的字符串的數值定義為其字符的數值之和。例如,字符串的數值等於。"abe"1 + 2 + 5 = 8,給你兩個整數n和k。返回長度等於且數值等於的最小字符串。"n,k",且按字母順序排序。 顧名思義,字串會從'a'開始排序,能排'a'就排'a'不能的話再從'b'開始考量,依序下去,如範例。
範例
思路: 去思考在字母對應的數字加起來等於k的情況下,前面盡可能的排'a'而後面只能放'z'來達到題意要求,開lastCharIndex()功能並跑遞迴直到前面放不了'a'且算出'a'跟'z'中間要放的字母的index,並用StringBuilder來拼接回傳的字串已減少記憶體使用。
解題: