问题陈述如下-
There is a text messaging service.It provides with an API to send SMSes to a user,
but they can be at most 30 characters long.
Also it doesn't guarantee the order in which the messages will be received.
You have to build a function which splits the text in chunks so that it can
be sent in multiple messages. Each chunk has to be :
- upto 30 characters long
- no word should be split in the middle
- each chunk has to have its order suffixed in the form of '(k/n)'
e.g. "this is the first chunk (1/2)", "this is the second chunk (2/2)"
- if the text provided to the function is within 30 characters limit,
no ordering should be suffixed
Input/Output Format
Each test case consists of a single line of words. Words are space
separated. Any other character other than space is considered part of
the word. For each test case, output the minimum number of chunks C
required to fit the entire SMS.
Restrictions
1 <=C<= 99; Input will be such that C remain in this mentioned limit
if your algorithm is optimal. No word will have a length that does
not fit in a single chunk (even after considering the suffix).
Sample Input:
The best lies are always mixed with a little truth
There is no creature on earth half so terrifying as a truly just man!!!!!
You know nothing, Jon Snow
Sample Output
3
3
1
Explanation:
In first case, we will have to split as below
The best lies are always (1/3)
mixed with a little (2/3)
truth (3/3)
First line is fully utilised with 30 characters in it.
Second line has 25 characters but if we try to fit last word in this line,
it becomes 31 characters. 'mixed with a little truth (2/2)
Hence we must split into 3 parts as above.
我的方法 -> 更多的是首先找到块的大致数量，然后对其进行扩展，但这不起作用。我想知道是否有可能首先计算数学上需要多少块，或者我们实际上必须构建块并查看，但是我们如何在不知道"k/n"的"n"的情况下构建块？
你必须知道n才能知道每个块中可以放多少个单词，因为这取决于n。
即使n以 99 为基数表示，因此它只需要一个字符，您仍然需要单独检查每个单词的长度。
我怀疑块之间单词的最佳分布不是将单词(和空格(放入行中直到下一个项目不适合的简单方法：最好早点在某个地方制作一些较小的块，以便以后更好地打包。但是，这不是切削库存问题，因为必须保留订单。
通过简单的方法，我的意思是将单词打包为假设少于十个块，如果没有，则基于少于 100 个块重新开始，例如在 VB.NET：
Imports System.Text
Imports System.Text.RegularExpressions
Module Module1
Function NumberLength(n As Integer) As Integer
Return If(n < 10, 1, 2)
End Function
Sub Main()
Dim msg = "Escobazos tu dios pisan amor sus el las grupos se y no de los pulso mudas muerte mi inocentes vilo los las bajaba viciosa tierra de amor horizonte la se deja de tierra heridas ni los la es los recodos horizonte diminutas la de es nube talco hombrecillo de piel los se escobazos nadadora de bajo consume las se con ni las en por que donde tierra es sillas el de de que latido viva lo a grupos torre escaleras desnudo dolor me a la la quedo que sepultura signos criaturas de desnudo subía la húmedo desnuda latido nube quedo de la el nadadora el cielo dolor arroyo escobazos quedo donde de amor venas el viva poniendo desangradas torre que resonancia los fría ansioso el de subía el tierra todo se ansioso manteles por amor amor con de el quemadas resonancia con mujer el y que luna los bajaba quedo los yo a alegrísima de ilesa huido el mi que los se bajo la hombrecillo luna en de vilo es de el aire despenada que latido aire para sus horizonte todo muelles heridas viva hule tierra para huido de las a los llenando los que por húmedo tránsito tierra la la aire olvidando recodos de de la ligeros los término por luna bajaba tierra llenando del al que bajo de que de a pupila mueven que grupos se tránsito los ciudades de de nino mármol vuelve lenguas se los pisotean la vengo con faraón tránsito ballenas la se los tierra del escaleras de tierra nunca lenta se musgos que desgarrados la de desgarrados la imperturbable la resonancia y duro subía tierra me mi de talco escaleras el duro los desangradas sus buscando desangradas de pies algodón golondrina por que las no larga con diana que el en imperturbable de los luna al la huevos muertos las los las larga para borrachos de el aire los la bajo tierra fría talco los los comida en llanura en en los todo que en olvidando es de el de tu la de los muerte los las de que húmedo llenando de los pasan los hombrecillo se duro lenta ballenas ninos hule la con a la tierra por gustada es y se tierra amor las recientes manteles tierra de para signos el es un diana es del dios es imperturbable de consume de muelles luna para al nube tierra bajo apariencia encuentro es diminutas"
Dim nPart = 1
Dim nPartsTotal = 1 'assume 9 or less parts
Dim nPartsTotalLength = 1
Dim maxPartLength = 30
If msg.Length <= maxPartLength Then
Console.WriteLine("1")
Console.ReadLine()
Exit Sub
End If
Dim words = Regex.Split(msg, "( )")
Dim suffixLength = 5 ' up to 9 parts
Dim pos = 0
Dim nWord = 0
Dim thisPart As New StringBuilder
Dim partText As New List(Of String)
While nWord < words.Count()
suffixLength = 3 + NumberLength(nPart) + nPartsTotalLength
If pos + suffixLength + words(nWord).Length <= maxPartLength Then
pos += words(nWord).Length
nWord += 1
thisPart.Append(words(nWord - 1))
Else
partText.Add(thisPart.ToString())
pos = 0
nPart += 1
nPartsTotal += 1
thisPart.Clear()
If nPartsTotal > 9 AndAlso nPartsTotalLength = 1 Then
' start again knowing that there are more than 9 parts required
nPartsTotalLength = 2
nPart = 1
nPartsTotal = 1
nWord = 0
partText.Clear()
End If
End If
End While
If thisPart.Length > 0 Then
partText.Add(thisPart.ToString())
End If
Console.WriteLine(nPartsTotal)
Console.WriteLine(New String("|"c, maxPartLength)) ' show max length
For i = 1 To partText.Count()
Console.WriteLine($"{partText(i - 1)}({i}/{nPartsTotal})")
Next
Console.ReadLine()
End Sub
End Module
这恰好生成 99 个块。这个问题并不要求实际块的输出 - 示例代码的那部分是为了看看，以防万一很明显不同的 alogorithm 可以做得更好。
它相当简单。我首先尝试找到块的数量，这就是它出错的地方。安德鲁的解决方案是正确的。
我正在用JavaScript附加我的代码(仅供参考(
function splitSMSIn10Chunks(string){
let parts = string.split(' ');
let suffix = '(x/y)';
let chunks = 0;
let currentChunk = '';
for(let i=0;i<parts.length;i++){
if((currentChunk.length+1+parts[i].length+suffix.length)<=30){
currentChunk = currentChunk + parts[i] + " ";
}else{
currentChunk = currentChunk + suffix;
currentChunk = parts[i]+" " ;
chunks++;
}
if(i==parts.length-1){
//Last chunk
currentChunk = currentChunk + suffix;
chunks++;
}
if(chunks==10) return -1;
}
return chunks;
};
function splitSMSIn99Chunks(string){
let parts = string.split(' ');
let suffix = '(x/yy)';
let chunks = 0;
let currentChunk = '';
for(let i=0;i<parts.length;i++){
if((currentChunk.length+1+parts[i].length+suffix.length)<=30){
currentChunk = currentChunk + parts[i] + " ";
}else{
currentChunk = currentChunk + suffix;
currentChunk = parts[i]+" " ;
chunks++;
if(chunks==9){
suffix = '(xx/yy)';
}
}
if(i==parts.length-1){
//Last chunk
currentChunk = currentChunk + suffix;
chunks++;
console.log(currentChunk);
}
}
return chunks;
};
let sms = "The best lies are always mixed with a little truth The best lies are always mixed with a little truth The best lies are always mixed with a little truth The best lies are always mixed with a little truth";
let chunksRequired = splitSMSIn10Chunks(sms);
if(chunksRequired==-1){
console.log(splitSMSIn99Chunks(sms));
}else{
console.log(chunksRequired);
}
它也可以在 1 个函数中完成，但为了使其更简单、更易于阅读，我创建了两个单独的函数。