问题描述:
Given an array of words and a length L, format the text such that each line has exactly L 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 Lcharacters.
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.
For example,
words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16
.
Return the formatted lines as:
[ "This is an", "example of text", "justification. " ]
Note: Each word is guaranteed not to exceed L in length.
- A line other than the last line might contain only one word. What should you do in this case?
- In this case, that line should be left-justified.
原问题链接:https://leetcode.com/problems/text-justification/
问题分析
这个问题其实本身的逻辑不算很复杂,主要是各种处理很麻烦,比较费事。总的来说,可以这么来看。这边要求是每一行放若干个词,但是词和词之间的空格尽可能的均匀。从最基本的要求来看,就有这么几个步骤。首先,要计算确定每一行可以放多少个词,保证它们不超过指定的长度。同时,在判断出最多可以放多少个词之后要计算里面有多少个空格,再将这些空格平均的放到所有这些词之间。最后,针对最后的一行,将剩下的词按照左对齐的方式来排版。我们针对这每个步骤的详细实现来讨论。
首先看判断一行里可以放多少个词。我们可以用一个变量minL来记录在某一行里放置的单词的总长度。同时用s来表示当前行开始的词的索引。首先它放置第一个词的长度。然后我们每次尝试往里面放一个后面的词并判断它们的长度是否超过限定的长度。当超过给定长度的时候,我们要将当前minL的长度减去当前位置的这个字符串的长度。
这部分的代码实现如下:
int s = 0; // line starting index in words int n = words.length; int minL = words[s].length(); // min length needed for the words int e = s + 1; // first figure out how many words can fit in the line while (e < n) { minL += 1 + words[e].length(); if (minL > maxWidth) { minL -= 1 + words[e].length(); // keep minL valid break; } ++e; } // index e is exclusive
在上述的实现里我们需要注意一个地方。每次我们往minL里加词长度的时候要额外加1,这里的1是表示每个词后面所带的空格。因为我们最少要保证词和词之间有一个空格。这样,在索引e - 1到s这一段就是我们找到的放在给定maxWidth长度行里的词。
有了上面这部分的实现,我们相当于找到了一种最初始的一个词加一个空格排列的情况。但是因为这种方式不一定和给定的maxWidth完全对齐的,有可能后面有多余的空格。我们需要针对这些空格的数量进行一个总体的分配。所以这一步就是要计算并放置一行里字符串和对应的空格。
这部分的实现该怎么来考虑呢?首先,根据当前e和s的值可以知道里面有多少个词加空格。它的值是e - s - 1。另外,根据maxWidth - minL得到的剩余空格数也要考虑在内。用这个剩余的空格数除以所有放词加空格的数量,作为平均放到每个块里的空格补充。详细的实现如下:
StringBuilder sb = new StringBuilder(); sb.append(words[s]); // append the 1st word int slots = e - s - 1; // how many slots can be filled with spaces int extra = maxWidth - minL; // total extra spaces need to be distributed while (slots > 0) { // caculates how many extra spaces the current slot needs to take // it is the ceiling of (extra / slots) // in case of last line, 0 int spaces = n == e ? 0 : ((extra + slots - 1) / slots); for (int i = 0; i <= spaces; ++i) sb.append(' '); // append those spaces, plus one sb.append(words[e-slots]); // append next word --slots; // one less slot to worry about extra -= spaces; // reduce the number of extra spaces filled this time } // fill the rest of the extra space to cover the one word and the last line case for (int i = 0; i < extra; ++i) sb.append(' '); res.add(sb.toString());
上述的过程描述的其实是针对一行字符串填充和选择的情况。针对将所有字符串按照给定样式排版的情况,需要将上述的代码嵌套到一个循环里。
最后详细的代码实现如下:
public class Solution { public List<String> fullJustify(String[] words, int maxWidth) { List<String> res = new ArrayList<>(); int s = 0; // line starting index in words int n = words.length; while (s < n) { int minL = words[s].length(); // min length needed for the words int e = s+1; // first figure out how many words can fit in the line while (e < n) { minL += 1 + words[e].length(); if (minL > maxWidth) { minL -= 1 + words[e].length(); // keep minL valid break; } ++e; } // index e is exclusive StringBuilder sb = new StringBuilder(); sb.append(words[s]); // append the 1st word int slots = e - s - 1; // how many slots can be filled with spaces int extra = maxWidth - minL; // total extra spaces need to be distributed while (slots > 0) { // caculates how many extra spaces the current slot needs to take // it is the ceiling of (extra / slots) // in case of last line, 0 int spaces = n == e ? 0 : ((extra + slots - 1) / slots); for (int i = 0; i <= spaces; ++i) sb.append(' '); // append those spaces, plus one sb.append(words[e-slots]); // append next word --slots; // one less slot to worry about extra -= spaces; // reduce the number of extra spaces filled this time } // fill the rest of the extra space to cover the one word and the last line case for (int i = 0; i < extra; ++i) sb.append(' '); res.add(sb.toString()); s = e; // move on } return res; } }
相关推荐
正确的姿势,学习的态度来刷 LeetCode:高效的代码、简洁的注释、精炼的总结。
leetcode 非官方顺序leetcode题解,主要代码为Python和C++。 leetcode 第1题: leetcode 第2题: leetcode 第3题: leetcode 第4题: leetcode 第5题: leetcode 第6题: leetcode 第7题: leetcode 第9题: ...
leetcode11 top 1. 位运算 LeetCode191 : 二进制位1的个数 LeetCode338 : 比特位运算 2. 字典树 LeetCode209 : 实现一个Trie结构 LeetCode79 : 单词搜索(判断单词是否出现在给定的网格中) LeetCode212 : 单词搜索II...
LeetCode::laptop:LeetCode解决方案
leetcode 答案 leetCode :keyboard:我的 Leetcode 解题答案
lru缓存leetcode 力码 涵盖了 Geeks for Geeks 和 Leet Code 的各种问题。 LeetCode 1 : 二和 (46_Easy) LeetCode 2 : 两个数字相加 (96_Medium) LeetCode 3 : 无重复字符的最长子串 (214_Medium) LeetCode 4 : 两个...
LeetCode 在LeetCode和其他编码平台上解决的问题的集合
leetcode :ice_cream: LeetCode Kindem 的个人 LeetCode 题解仓库,欢迎交流学习。 下面的目录中 $number 题号代表经典 LeetCode 题目,$number.$number 题号表示 LeetCode 面试题。 :receipt: 目录 统计 值 AC 的...
leetcode 分类 LeetCode :bouquet::bouquet::bouquet: 介绍 leetcode 题解,Issues 会记录 leetcode 解题之路,并使用 label 进行了分类。 目录 链表
LeetCode 101:和你一起你轻松刷题(C++)
Leetcode:Leetcode提交
:fire: Leetcode :fire: 实践使完美 :party_popper: 开玩笑的单元测试 :sparkles: 简单的代码 :artist_palette: 可读代码 入门指南 git clone https: //github.com/tangweikun/leetcode.git cd leetcode npm ...
idea中leetcode插件Rust 中的 LeetCode 解决方案 怎么跑?...,所有解决方案代码都在leetcode::leetcode::editor::en并重用于leetcode 。 它有一个全局结构Solution ,所有解决方案条目都在其中实现。
leetcode:leetcode刷题
Leetcode:LeetCode解题代码
LeetCode:LeetCode的代码
LeetCode:LeetCode的注释
leetcode:LeetCode问题
加油站问题leetcode LeetCode LeetCode-JS分类列表: :smiling_face_with_smiling_eyes: :flushed_face: :winking_face: :face_with_tongue: :face_with_open_mouth: :beaming_face_with_smiling_...
leetcode:LeetCode题解