原题链接:http://oj.leetcode.com/problems/text-justification/这道题属于纯粹的字符串操作,要把一串单词安排成多行限定长度的字符串。主要难点在于空格的安排,首先每个单词之间必须有空格隔开,而当当前行放不下更多的单词并且字符又不能填满长度L时,我们要把空格均匀的填充在单词之间。如果剩余的空格量刚好是间隔倍数那么就均匀分配即可,否则还必须把多的一个空格放到前面的间隔里面。实现中我们维护一个count计数记录当前长度,超过之后我们计算共同的空格量以及多出一个的空格量,然后将当行字符串构造出来。最后一个细节就是最后一行不需要均匀分配空格,句尾留空就可以,所以要单独处理一下。时间上我们需要扫描单词一遍,然后在找到行尾的时候在扫描一遍当前行的单词,不过总体每个单词不会被访问超过两遍,所以总体时间复杂度是O(n)。而空间复杂度则是结果的大小(跟单词数量和长度有关,不能准确定义,如果知道最后行数r,则是O(r*L))。代码如下:public ArrayList<String> fullJustify(String[] words, int L) {
ArrayList<String> res = new ArrayList<String>();
if(words==null || words.length==0)
return res;
int count = 0;
int last = 0;
for(int i=0;i<words.length;i++)
{
if(count+words[i].length()+(i-last)>L)
{
int spaceNum = 0;
int extraNum = 0;
if(i-last-1>0)
{
spaceNum = (L-count)/(i-last-1);
extraNum = (L-count)%(i-last-1);
}
StringBuilder str = new StringBuilder();
for(int j=last;j<i;j++)
{
str.append(words[j]);
if(j<i-1)
{
for(int k=0;k<spaceNum;k++)
{
str.append(" ");
}
if(extraNum>0)
{
str.append(" ");
}
extraNum--;
}
}
for(int j=str.length();j<L;j++)
{
str.append(" ");
}
res.add(str.toString());
count=0;
last=i;
}
count += words[i].length();
}
StringBuilder str = new StringBuilder();
for(int i=last;i<words.length;i++)
{
str.append(words[i]);
if(str.length()<L)
str.append(" ");
}
for(int i=str.length();i<L;i++)
{
str.append(" ");
}
res.add(str.toString());
return res;
}
这道题属于那种文本编辑的子操作之类的题目,从算法思路上没有什么特别,不过实现细节还是比较多的,不容易一次做对,可能要多练习几次哈。
分享到:
相关推荐
# [LeetCode](https://leetcode.com/problemset/algorithms/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![License]...
换行,对齐和可变字体 看一下换行和对齐方式,以及可变字体如何改善对齐文本。 在2018年Robothon大会上演示了使用可变字体改善对齐方式的演示。 如何使用 带上自己的可变字体。 :)代码引用了Gimlet可变字体,但是...
电子商务英文课件:ch14 Economics and Justification of.ppt
4.Apply intelligent justification and customized hyphenation to achieve fine text design 5.Typeset professional-looking tables and create bulleted and enumerated lists 6.Write sophisticated math ...
Android Full Justification About This library will provide you a way to justify text. It supports both plain text and Spannables. Additionally, the library can auto-hyphentate your displayed content ...
Text Justification Max Points on a Line Community QQ 群: 237669375 Github: https://www.github.com/soulmachine/algorithm-essentials 微博: @灵魂机器 License Book License: CC BY-SA 3.0 License
这个文档讲述了如何通过TOC和ROI来判断是否进行投资,同样可以通过这一点来说服企业管理层
AddChild(new TextWidget("Hello World", 320, 240, justification: Font.Justification.Center)); ShowAsSystemWindow(); } // and just for fun lets also draw a circle public ...
全英文,To Our Readers Changes: Readers of this publication are encouraged to submit suggestions and changes that will improve it. Recommendations ...• Justification and/or source of change
clauseN -default line,在defaults列表中增加一个缺陷:d:prerequisite:justification/consequent --先决条件的形式为子句1;子句2; ...;子句N --证明形式为子句1;子句2; ...;子句N --结果形式为子句1;子句2;...;...
justification. But design: what happens when we design? Is design about problems or about beauty? Does resolving forces while solving a problem force beauty into the design? Or can beauty and ideal ...
# 给定一个单词数组和一个长度 maxWidth...# words = ["This", "is", "an", "example", "of", "text", "justification."] # maxWidth = 16 # 输出: # [ # "This is an", # "example of text", # "justification. " # ]
Left Justification The Field Precision Value Explicit File output AWK Numerical Functions Trigonometric Functions Exponents, logs and square roots Truncating Integers "Random Numbers The Lotto...
" 1.4 provide further justification for the appearance of this text. Much of the information in this book is either absent from or incorrectly specified in the Java documentation and books by other ...
17.6 Mapping of other constant bit-rate signals with justification into OPUk 80 17.7 Mapping a 1000BASE-X and FC-1200 signal via timing transparent transcoding into OPUk 80 17.7.1 Mapping a 1000BASE-X...
17.6 Mapping of other constant bit-rate signals with justification into OPUk 80 17.7 Mapping a 1000BASE-X and FC-1200 signal via timing transparent transcoding into OPUk 80 17.7.1 Mapping a 1000BASE-X...
IT managers and project leaders are armed with details on building a business case for VoIP, including details of return-on-investment (ROI) analysis and justification. A VoIP deployment is presented...
While this book constitutes a comprehensive treatment of simulation methods, the theoretical justification of those methods has been considerably reduced, compared with Robert and Casella (2004)....
5.16.7 Justification of RFPE* 168 5.16.8 A robust multiple correlation coefficient 170 5.17 Problems 171 6 Multivariate Analysis 175 6.1 Introduction 175 6.2 Breakdown and efficiency of multivariate ...