本文共 4642 字,大约阅读时间需要 15 分钟。
题目链接:
Given an array of words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' '
when necessary so that each line has exactly maxWidth characters.
Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be left justified and no extra space is inserted between words.
Note:
words
contains at least one word.Example 1:
Input:words = ["This", "is", "an", "example", "of", "text", "justification."]maxWidth = 16Output:[ "This is an", "example of text", "justification. "]
Example 2:
Input:words = ["What","must","be","acknowledgment","shall","be"]maxWidth = 16Output:[ "What must be", "acknowledgment ", "shall be "]
Example 3:
Input:words = ["Science","is","what","we","understand","well","enough","to","explain", "to","a","computer.","Art","is","everything","else","we","do"]maxWidth = 20Output:[ "Science is what we", "understand well", "enough to explain to", "a computer. Art is", "everything else we", "do "]
这道题就是给你一个字符串数组(每个字符串内部没有空格),然后限定每一行的长度(大于等于字符串数组中每个字符串的长度)。让你按照两端对齐的方式格式化这个字符串数组(在两端对齐的格式化规则中,对于最后一行的字符,按照左对齐的方式格式化)。
两端对齐的格式化规则和Word文档中两端对齐的排列方式一样。在两端对齐中:
' '
。abc
,de
,f
和g
。那么格式化后的结果为abc de f g
,之间的空格数目分别为2,2,1。对于这道题,我们可以遍历字符串数组,记录当前行中包含的字符串。
如果当前字符串是否可以放入当前行。可以的话则放入,否则就格式化之前记录的字符串,然后另起一行。class Solution { public ListfullJustify(String[] words, int maxWidth) { List resultList = new ArrayList (); int start = 0; int tempWidth = 0; int count = 0; for (int i = 0; i < words.length; i++) { // 如果和下一个字符串一起的长度超过了 int nextWidth = tempWidth + words[i].length(); if (nextWidth + count > maxWidth) { // 只有一个word if (count == 1) { resultList.add(leftJustifyLine(words, start, i - 1, maxWidth, tempWidth)); } else { resultList.add(fullJustifyLine(words, start, i - 1, maxWidth, tempWidth)); } tempWidth = words[i].length(); start = i; count = 1; } else if (nextWidth + count == maxWidth) { resultList.add(leftJustifyLine(words, start, i, maxWidth, tempWidth)); start = i + 1; count = 0; tempWidth = 0; } else { count++; tempWidth = nextWidth; } } if (count != 0) { resultList.add(leftJustifyLine(words, start, words.length - 1, maxWidth, tempWidth)); } return resultList; } /** * 两端对齐 * @param words 字符串数组 * @param start 起始下标 * @param end 结束下标,需要格式化的字符串包含该位置对应的字符串 * @param maxWidth 规定的长度 * @param tempWidth 指定的字符串的长度之和,不包含填充的空格 * @return 两端对齐之后的字符串 */ private String fullJustifyLine(String[] words, int start, int end, int maxWidth, int tempWidth) { StringBuilder result = new StringBuilder(maxWidth); int numOfWord = end - start + 1; // 平均空格数 int minBlank = (maxWidth - tempWidth) / (numOfWord - 1); // 剩下的空格数 int leftBlank = (maxWidth - tempWidth) % (numOfWord - 1); for (int i = 0; i < leftBlank; i++) { result.append(words[start + i]); for (int j = 0; j <= minBlank; j++) { result.append(' '); } } for (int i = leftBlank; i < numOfWord - 1; i++) { result.append(words[start + i]); for (int j = 0; j < minBlank; j++) { result.append(' '); } } result.append(words[end]); return result.toString(); } // 左对齐 // 参数含义和上个方法相同 private String leftJustifyLine(String[] words, int start, int end, int maxWidth, int tempWidth) { StringBuilder result = new StringBuilder(maxWidth); for (int i = start; i < end; i++) { result.append(words[i]); result.append(' '); } result.append(words[end]); while (result.length() < maxWidth) { result.append(' '); } return result.toString(); }}
转载地址:http://nibmb.baihongyu.com/