文本左右对齐
给定一个单词数组和一个长度 maxWidth,重新排版单词,使其成为每行恰好有 maxWidth 个字符,且左右两端对齐的文本。
你应该使用“贪心算法”来放置给定的单词;也就是说,尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充,使得每行恰好有 maxWidth 个字符。
要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配,则左侧放置的空格数要多于右侧的空格数。
文本的最后一行应为左对齐,且单词之间不插入额外的空格。
说明:
单词是指由非空格字符组成的字符序列。
每个单词的长度大于 0,小于等于 maxWidth。
输入单词数组 words 至少包含一个单词。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/text-justification
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
示例 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 " ]
实现代码
class Solution { public: vectorfullJustify(vector& words, int maxWidth) { vector res; mapwordsSqe; int n = 0; int length = 0; int step = 0; vector temp; while (n < words.size()) { length += words[n].size(); if (length < maxWidth) { temp.push_back(words[n]); length++; } else if (length == maxWidth) { temp.push_back(words[n]); res.push_back(temp); length = 0; temp.clear(); } else if (length > maxWidth) { res.push_back(temp); temp.clear(); temp.push_back(words[n]); length = words[n].size(); length++; } n++; } if (!temp.empty()) res.push_back(temp); vector result; for (int i = 0; i < res.size(); i++) { string tempString; int totalLength = 0; for (int j = 0; j < res[i].size(); j++) totalLength += res[i][j].size(); int nullNumber; if (i != res.size() - 1) { if (res[i].size() > 1) { nullNumber = (maxWidth - totalLength) / (res[i].size() - 1); int fullNumber = (maxWidth - totalLength) % (res[i].size() - 1); int count = 0; for (int j = 0; j < res[i].size(); j++) { if (j != res[i].size() - 1) { if (fullNumber == 0) tempString.append(res[i][j]).append(nullNumber, ' '); else { if (count != fullNumber) { tempString.append(res[i][j]).append(nullNumber + 1, ' '); count++; } else tempString.append(res[i][j]).append(nullNumber, ' '); } } else tempString.append(res[i][j]); } } else tempString.append(res[i][0]).append(maxWidth - totalLength, ' '); } else { if (res[i].size() > 1) { nullNumber = maxWidth - totalLength - (res[i].size() - 1); for (int j = 0; j < res[i].size(); j++) { if (j != res[i].size() - 1) tempString.append(res[i][j]).append(" "); else tempString.append(res[i][j]).append(nullNumber, ' '); } } else tempString.append(res[i][0]).append(maxWidth - totalLength, ' '); } result.push_back(tempString); } return result; } };