dis*_*kit 5 string algorithm data-structures
问题陈述如下——
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\n即使n以 99 为基数表示，只需要一个字符，您仍然需要单独检查每个单词的长度。
\n\n我怀疑词块之间的最佳分布并不是将单词（和空格）放入行中直到下一个项目不适合的简单方法：最好早点在某处制作一些较小的块以实现更好的效果稍后打包。然而，这不是库存问题，因为必须保留订单。
\n\n通过简单的方法，我的意思是假设少于 10 个块来打包单词，如果没有，则基于少于 100 个块重新开始，例如在 VB.NET 中：
\n\nImports System.Text\nImports System.Text.RegularExpressions\n\nModule Module1\n\n Function NumberLength(n As Integer) As Integer\n Return If(n < 10, 1, 2)\n End Function\n\n Sub Main()\n 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\xc3\xada la h\xc3\xbamedo 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\xc3\xada ansioso el de sub\xc3\xada 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\xc3\xadsima 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\xc3\xbamedo tr\xc3\xa1nsito tierra la la aire olvidando recodos de de la ligeros los t\xc3\xa9rmino por luna bajaba tierra llenando del al que bajo de que de a pupila mueven que grupos se tr\xc3\xa1nsito los ciudades de de nino m\xc3\xa1rmol vuelve lenguas se los pisotean la vengo con fara\xc3\xb3n tr\xc3\xa1nsito 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\xc3\xada tierra me mi de talco escaleras el duro los desangradas sus buscando desangradas de pies algod\xc3\xb3n 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\xc3\xada 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\xc3\xbamedo 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"\n Dim nPart = 1\n Dim nPartsTotal = 1 \'assume 9 or less parts\n Dim nPartsTotalLength = 1\n Dim maxPartLength = 30\n\n If msg.Length <= maxPartLength Then\n Console.WriteLine("1")\n Console.ReadLine()\n Exit Sub\n End If\n\n Dim words = Regex.Split(msg, "( )")\n\n Dim suffixLength = 5 \' up to 9 parts\n\n Dim pos = 0\n Dim nWord = 0\n\n Dim thisPart As New StringBuilder\n Dim partText As New List(Of String)\n\n While nWord < words.Count()\n suffixLength = 3 + NumberLength(nPart) + nPartsTotalLength\n If pos + suffixLength + words(nWord).Length <= maxPartLength Then\n pos += words(nWord).Length\n nWord += 1\n thisPart.Append(words(nWord - 1))\n Else\n partText.Add(thisPart.ToString())\n pos = 0\n nPart += 1\n nPartsTotal += 1\n thisPart.Clear()\n\n If nPartsTotal > 9 AndAlso nPartsTotalLength = 1 Then\n \' start again knowing that there are more than 9 parts required\n nPartsTotalLength = 2\n nPart = 1\n nPartsTotal = 1\n nWord = 0\n partText.Clear()\n End If\n End If\n\n End While\n\n If thisPart.Length > 0 Then\n partText.Add(thisPart.ToString())\n End If\n\n Console.WriteLine(nPartsTotal)\n Console.WriteLine(New String("|"c, maxPartLength)) \' show max length\n\n For i = 1 To partText.Count()\n Console.WriteLine($"{partText(i - 1)}({i}/{nPartsTotal})")\n Next\n\n Console.ReadLine()\n\n End Sub\n\nEnd Module\n这恰好生成了 99 个块。这个问题并不要求实际块的输出 - 示例代码的这一部分是为了看看是否明显不同的算法可以做得更好。
\n