doocs/leetcode 精讲:LeetCode 68. 文本左右对齐(Text Justification)——贪心取词与空格均匀分配的模拟解法全解析 示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载本文以 68. 文本左右对齐 题解文档为主线完整拆解这道困难标签下实为「贪心 模拟」的经典题目如何用贪心策略尽可能多地往每行塞入单词如何让多余空格在词间尽量均匀、左侧偏多地分配以及最后一行/单单词行必须左对齐的特殊规则。读完本文你将掌握一套可直接运行的六语言实现Python/Java/C/Go/TypeScript/C#并能独立推导出任意输入下的逐行输出。一、题目概述给出一份两端对齐的文本给定一个单词数组words和一个行宽maxWidth要求重新排版单词使得每一行恰好有maxWidth个字符并且左右两端对齐fully justified。这是文字处理软件中常见的两端对齐排版需求本题要求你用算法把这一排版过程精确复现出来。题目要求使用贪心算法放置单词尽可能多地往每行中放置单词必要时用空格 填充使每行恰好达到maxWidth个字符。其核心排版规则可以归纳为三条贪心取词从左到右扫描每行尽量多装单词装不下就换行均匀分配词间空格要尽可能均匀若无法整除则左侧间隙多放空格即左侧空格数 ≥ 右侧空格数末行左对齐文本的最后一行应为左对齐单词之间只保留 1 个空格剩余宽度全部补在行尾同理一行只有一个单词时也按左对齐处理。题目还给出三条注意项单词是由非空格字符组成的字符序列每个单词长度大于 0 且不超过maxWidth输入单词数组至少包含一个单词。数据约束约束项取值范围说明words.length1 words.length 300单词总数最多 300 个words[i].length1 words[i].length 20单次长度上限 20maxWidth1 maxWidth 100行宽上限 100单词与行宽关系words[i].length maxWidth保证任意单词可单独成行不会出现单词放不下的死局数据规模很小复杂度不是瓶颈真正的难点在于空格分配的各种边界细节。二、示例逐行推演把规则落到输出上示例 1普通行的均匀分配输入: words [This, is, an, example, of, text, justification.], maxWidth 16 输出: [ This is an, example of text, justification. ]逐行验证.表示一个空格第 1 行取This is an字符总长42210两处词间基础空格共 2 个还差16-124个空格需要补进 2 个间隙 → 每个间隙再补 2 个 → 词间各 3 个空格This...is...an4424216。第 2 行取example of text字符总长72413基础空格 2 个共 15还差 1 个空格补进 2 个间隙 → 按左多右少规则左侧间隙 1example..of.text7322416。第 3 行只有justification.14 个字符→ 左对齐行尾补2个空格。示例 2末行左对齐 单单词行输入: words [What,must,be,acknowledgment,shall,be], maxWidth 16 输出: [ What must be, acknowledgment , shall be ]第 1 行What must be字符总长44210基础空格 2共 12还差 4 个空格 → 2 个间隙各补 2 个 → 词间各 3 个空格What...must...be。第 2 行只有acknowledgment14 字符→ 左对齐行尾补 2 个空格。题目解释明确指出第二行同样为左对齐因为这一行只包含一个单词。第 3 行是最后一行 → 必须左对齐shall be8 字符只保留 1 个空格行尾补16-88个空格即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 ]其中第 4 行a computer. Art is字符总长193215基础空格 3共 18还差 2 个空格补进 3 个间隙 →w0, m2前 2 个间隙各 1 → 词间空格依次为 2、2、1a..computer...Art.is。第 6 行是末行do2 字符左对齐后行尾补 18 个空格。提示题目文档示例中的多个连续空格在 HTML 渲染时会被折叠阅读原始输出时需结合空格实体nbsp;或上述数学推演理解真实字符数。三、解题思路贪心取词 模拟排版这道题的算法骨架并不复杂从左到右扫描单词每轮先贪心地取出一行能放下的所有单词再根据该行性质决定排版方式。整个过程不需要回溯因为每一行的内容只由当前剩余单词 maxWidth决定行与行之间不存在需要回头调整的依赖关系。步骤拆解贪心取词以当前指针i为行首先把words[i]放入本行然后持续尝试加入下一个单词前提是已占用字符数 cnt 1 下一个单词长度 maxWidth1代表词间必须保留的基础空格。判断排版方式若i n当前行是最后一行或len(t) 1本行只有一个单词→左对齐单词间以 1 个空格连接行尾用空格补齐到maxWidth否则 →均匀分配把多余空格尽量均匀地填进词间空隙余数优先给左侧。循环直到所有单词处理完毕逐行加入答案数组。均匀分配公式推导设本行单词数为k len(t)累计计数cnt的语义是所有单词字符长度之和 (k-1) 个基础空格。因此纯字符总长 cnt - (k - 1)需要在词间额外分配的空格总数space_width maxWidth - (cnt - k 1)即maxWidth - 纯字符总长 - (k-1) 个基础空格每个间隙的基础额外空格w space_width // (k - 1)余数m space_width % (k - 1)前m个间隙各多放 1 个空格从而天然满足左侧间隙空格数 ≥ 右侧的要求。当space_width恰好能被k-1整除时m 0所有间隙完全均匀例如示例 1 第 1 行与示例 3 第 2 行。复杂度分析设L为所有单词的长度之和时间复杂度O(L)每个单词恰好被扫描、加入、输出一次空间复杂度O(L)答案数组与单行临时容器累计占用与总字符量同阶。原题解文档明确指出单词数不超过 300、行宽不超过 100从左到右贪心取词即可不必回溯。四、源码逐段解析以 Python3 为主线仓库 Solution.py 与题解文档中的 Python3 实现完全一致下面逐段拆解class Solution: def fullJustify(self, words: List[str], maxWidth: int) - List[str]: ans [] i, n 0, len(words) while i n: # —— 阶段一贪心取词确定本行单词 t —— t [] cnt len(words[i]) t.append(words[i]) i 1 while i n and cnt 1 len(words[i]) maxWidth: cnt 1 len(words[i]) t.append(words[i]) i 1 # —— 阶段二左对齐分支末行或单单词行—— if i n or len(t) 1: left .join(t) right * (maxWidth - len(left)) ans.append(left right) continue # —— 阶段三均匀分配分支 —— space_width maxWidth - (cnt - len(t) 1) w, m divmod(space_width, len(t) - 1) row [] for j, s in enumerate(t[:-1]): row.append(s) row.append( * (w (1 if j m else 0))) row.append(t[-1]) ans.append(.join(row)) return ans三个关键细节cnt的累积策略cnt 1 len(words[i])中的1表示新单词与上一单词之间的基础空格这保证cnt始终等于本行已取单词字符长度 词间基础空格数divmod(space_width, len(t) - 1)一次得到基础额外空格w与余数mj m的间隙多放 1 个空格实现左侧优先row.append(t[-1])最后一个单词之后不再追加空格行宽恰好由前面分配的间隙填满。五、多语言实现对照原题解文档提供了六种语言的同构实现方法名均为fullJustify仓库中也存在对应的独立源码文件Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.cs。算法骨架完全相同仅语法层面有差异语言单词连接构造空格拼接输出备注JavaString.join( , t) .repeat(n)StringBuilder需 Java 11 的repeatC循环left t[j]string(n, )string拼接emplace_back追加单词Gostrings.Join(t, )strings.Repeat( , n)strings.Builder余数用if j m追加 1 个空格TypeScriptt.join( ) .repeat(n)row.join()Math.floor求wC#string.Join( , t)new string( , n)StringBuilder方法名FullJustify以 Java 为例的完整实现class Solution { public ListString fullJustify(String[] words, int maxWidth) { ListString ans new ArrayList(); for (int i 0, n words.length; i n;) { ListString t new ArrayList(); t.add(words[i]); int cnt words[i].length(); i; while (i n cnt 1 words[i].length() maxWidth) { cnt 1 words[i].length(); t.add(words[i]); } if (i n || t.size() 1) { String left String.join( , t); String right .repeat(maxWidth - left.length()); ans.add(left right); continue; } int spaceWidth maxWidth - (cnt - t.size() 1); int w spaceWidth / (t.size() - 1); int m spaceWidth % (t.size() - 1); StringBuilder row new StringBuilder(); for (int j 0; j t.size() - 1; j) { row.append(t.get(j)); row.append( .repeat(w (j m ? 1 : 0))); } row.append(t.get(t.size() - 1)); ans.add(row.toString()); } return ans; } }C 实现中值得注意的写法左对齐时用string(maxWidth - left.size(), )一次性构造填充空格均匀分配时用row t[j] string(w (j m ? 1 : 0), )将单词 空格一并拼入class Solution { public: vectorstring fullJustify(vectorstring words, int maxWidth) { vectorstring ans; for (int i 0, n words.size(); i n;) { vectorstring t {words[i]}; int cnt words[i].size(); i; while (i n cnt 1 words[i].size() maxWidth) { cnt 1 words[i].size(); t.emplace_back(words[i]); } if (i n || t.size() 1) { string left t[0]; for (int j 1; j t.size(); j) { left t[j]; } string right string(maxWidth - left.size(), ); ans.emplace_back(left right); continue; } int spaceWidth maxWidth - (cnt - t.size() 1); int w spaceWidth / (t.size() - 1); int m spaceWidth % (t.size() - 1); string row; for (int j 0; j t.size() - 1; j) { row t[j] string(w (j m ? 1 : 0), ); } row t.back(); ans.emplace_back(row); } return ans; } };Go 与 TypeScript 的实现则分别利用了strings.Builder和数组join来避免频繁的字符串拼接开销整体结构与其他语言一一对应。六、边界情况与易错点总结这类困难题目的失分点几乎全部集中在边界处理上做题与 review 代码时建议逐条核对末行判定i n意味着当前行是最后一行必须左对齐——即使它包含多个单词也不能做均匀分配只能行尾补空格单单词行一行只有一个单词时len(t) - 1 0均匀分配公式会出现除零因此必须单独走左对齐分支示例 2 的第二行整除与余数w space_width / (k - 1)、m space_width % (k - 1)要分开处理余数m只影响前 m 个间隙末行行尾空格最后一行补齐的空格数 maxWidth - 已排版字符数一个都不能少示例 2 第三行需补 8 个空格恰好放满当一行单词含基础空格恰好等于maxWidth时space_width 0此时所有间隙保持 1 个空格例如示例 3 的第 3 行enough to explain to单词等于行宽由于words[i].length maxWidth最坏情况是某个单词长度恰好等于maxWidth此时它独占一行行尾补 0 个空格。七、仓库中的完整资源与延伸阅读本题在仓库中的资源非常完整除题解文档外还有独立的多语言源码文件可直接在对应语言环境中运行验证中文题解README.md英文题解README_EN.md独立源码Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.cs题目本身位于 solution/0000-0099 目录区间该区间收录了 200 道题目编号 0000-0099的中英文题解。同类数组 字符串 模拟标签的题目如滑动窗口、双指针类模拟题可以在该目录中交叉检索加深对规则复杂但实现直接类题目的理解。小结LeetCode 68「文本左右对齐」是一道典型的算法简单、规则繁琐的模拟题核心算法只有贪心取词 线性扫描时间复杂度 O(L)但空格分配必须同时满足均匀与左侧偏多两条约束还要单独处理末行与单单词行的左对齐场景。掌握cnt计数、divmod求w/m、j m左侧优先这三板斧你就能在任何语言中快速复现这道题的完整解法。建议用示例 2、示例 3 的输入自测输出重点核对行尾空格数即可确认实现与题解完全一致。赞分享示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐LeetCode 68. 文本左右对齐困难题解LogicStack-LeetCode 仓库中的字符串模拟与贪心空格分配详解LeetCode 68. 文本左右对齐困难题解LogicStack LeetCode 仓库中的字符串模拟与贪心空格分配详解 本篇技术指南以 LogicSt教程文档文本两端对齐Text Justification贪心解法全解析以 leetcode 仓库 68 题多语言实现为例文本两端对齐Text Justification贪心解法全解析以 leetcode 仓库 68 题多语言实现为例 本文围绕 LeetCode 第 68 题示例工程LogicStack-LeetCode 题解精讲整数转罗马数字的贪心模拟解法LeetCode 12 中等LogicStack LeetCode 题解精讲整数转罗马数字的贪心模拟解法LeetCode 12 中等 本文以「宫水三叶的刷题日记」刷穿 LeetCod教程文档上一篇绿色AI革命TensorFlow Models能耗优化与碳足迹计算指南下一篇shared_preferences_foundation 演进全解Flutter 官方 iOS/macOS 偏好存储插件的架构、版本脉络与工程细节创作声明:本文部分内容由AI辅助生成(AIGC),仅供参考