面试难度低过小厂?FB你变了….
秋招开启,让不少人蠢蠢欲动,但跟很多人想的不一样:小公司的bar可能比大厂还要高!
最近有同学向领扣🐱反馈:小厂十连拒,却依靠这道原题拿到FB $250k的offer!
一起来看下吧👇
LintCode 1361
统计文字并排
题目描述
给定一个单词数组和一个宽度maxWidth,格式化文本,使每行具有刚好maxWidth个字符并完全(左和右)对齐。
你应该用贪心法打包你的单词; 也就是说,在每行中包含尽可能多的单词。必要时填充额外的空格,以便每行具有正确的maxWidth字符。
单词之间的额外空格应尽可能均匀分布。如果一行上的空格数不均匀分配,则左侧的空插槽将分配比右侧插槽更多的空格。
对于最后一行文本,它应该是左对齐的,并且在单词之间不插入额外的空格。
- 单词定义为仅由非空格字符组成的字符序列。
- 每个单词的长度保证大于0且不超过maxWidth。
- 输入数组words至少包含一个单词。
扫码免费做题
↓↓↓
样例1:
输入:
words = ["This", "is", "an", "example", "of", "text", "justification."]
maxWidth = 16
输出:
[
"This is an",
"example of text",
"justification. "
]
样例 2:
输入:
words = ["What","must","be","acknowledgment","shall","be"]
maxWidth = 16
输出:
[
"What must be",
"acknowledgment ",
"shall be "
]
说明:请注意,最后一行是 "shall be " 而不是 "shall be",
因为最后一行必须左对齐而不是完全对齐。
请注意,第二行也是左对齐的,因为它只包含一个单词。
样例 3:
输入:
words = ["Science","is","what","we","understand","well","enough","to","explain",
"to","a","computer.","Art","is","everything","else","we","do"]
maxWidth = 20
输出:
[
"Science is what we",
"understand well",
"enough to explain to",
"a computer. Art is",
"everything else we",
"do "
]
解题思路
本题我们需要按照题目意思进行模拟,首先我们尽可能多的在一行内多放单词,如果不能放的话,我们就考虑空格的计算,尽可能的均摊,然后多余的按照题意数处理。
总体复杂度O(n)
源代码
publicclassSolution {
public ArrayList<String> fullJustify(String[] words, int L) {
int wordsCount = words.length; //获取单次数量
ArrayList<String> result = new ArrayList<String>(); //统计答案
int curLen = 0;
int lastI = 0;
for (int i = 0; i <= wordsCount; i++) {
if (i == wordsCount || curLen + words[i].length() + i - lastI > L) { //判断单行是否允许再放一个单词
StringBuffer buf = new StringBuffer();
int spaceCount = L - curLen;
int spaceSlots = i - lastI - 1;
if (spaceSlots == 0 || i == wordsCount) {
for(int j = lastI; j < i; j++){
buf.append(words[j]);
if(j != i - 1)
appendSpace(buf, 1);
}
appendSpace(buf, L - buf.length());
} else {
int spaceEach = spaceCount / spaceSlots; //如果不能,计算空格的数量和位置
int spaceExtra = spaceCount % spaceSlots;
for (int j = lastI; j < i; j++) {
buf.append(words[j]);
if (j != i - 1)
appendSpace(buf, spaceEach + (j - lastI < spaceExtra ? 1 : 0));
}
}
result.add(buf.toString());
lastI = i;
curLen = 0;
}
if (i < wordsCount)
curLen += words[i].length();
}
return result;
}
privatevoidappendSpace(StringBuffer sb, int count) {
for (int i = 0; i < count; i++)
sb.append(' ');
}
}
点击【阅读原文】,查看领扣原题。
阅读原文 关键词
字符
空格
单词
题目
最新评论
推荐文章
作者最新文章
你可能感兴趣的文章
Copyright Disclaimer: The copyright of contents (including texts, images, videos and audios) posted above belong to the User who shared or the third-party website which the User shared from. If you found your copyright have been infringed, please send a DMCA takedown notice to [email protected]. For more detail of the source, please click on the button "Read Original Post" below. For other communications, please send to [email protected].
版权声明:以上内容为用户推荐收藏至CareerEngine平台,其内容(含文字、图片、视频、音频等)及知识版权均属用户或用户转发自的第三方网站,如涉嫌侵权,请通知[email protected]进行信息删除。如需查看信息来源,请点击“查看原文”。如需洽谈其它事宜,请联系[email protected]。
版权声明:以上内容为用户推荐收藏至CareerEngine平台,其内容(含文字、图片、视频、音频等)及知识版权均属用户或用户转发自的第三方网站,如涉嫌侵权,请通知[email protected]进行信息删除。如需查看信息来源,请点击“查看原文”。如需洽谈其它事宜,请联系[email protected]。