网站备案主体,网站经常被黑,苏州的互联网公司有哪些,宣威市网站建设代码训练(34)文本左右对齐
Author: Once Day Date: 2025年6月13日
漫漫长路#xff0c;才刚刚开始…
全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客
参考文章:
68. 文本左右对齐 - 力扣#xff08;LeetCode#xff09;力扣 (LeetCode) 全球极客挚爱的技…代码训练(34)文本左右对齐
Author: Once Day Date: 2025年6月13日
漫漫长路才刚刚开始…
全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客
参考文章:
68. 文本左右对齐 - 力扣LeetCode力扣 (LeetCode) 全球极客挚爱的技术成长平台 文章目录 代码训练(34)文本左右对齐1. 原题2. 分析3. 代码实现4. 总结 1. 原题 给定一个单词数组 words 和一个长度 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
]2. 分析
这道题目要求我们将一组单词根据指定的宽度 maxWidth 进行左右对齐的排版。具体要求如下
每行尽可能多地放置单词但不能超过 maxWidth。单词间的空格要尽量均匀分布。如果不能均匀分配则左侧空格多于右侧。最后一行单词左对齐单词间只有一个空格右侧填充空格至 maxWidth。
解题思路
初始化定义一个空列表 result 来存储每一行的结果定义 current_line 和 current_length 分别存储当前行的单词列表和当前行的字符长度不包括单词间的空格。遍历单词对于数组 words 中的每一个单词 检查是否可以添加到当前行如果当前单词加上当前行的长度加上至少一个空格后仍然不超过 maxWidth则将其添加到 current_line。如果超过长度则处理 current_line将其格式化为一个字符串添加到 result然后重置 current_line 和 current_length。 格式化行 对于非最后一行计算需要的空格数并尽量均匀地分配到单词间。对于最后一行单词间只放一个空格其余空格追加到行末。 处理最后一行因为最后退出循环时最后一行可能还未处理。
分析步骤以示例 1 为例输入是 words [This, is, an, example, of, text, justification.]maxWidth 16。
第一行可以放置 “This”, “is”, “an”它们之间分别有 4 和 2 个空格形成 “This is an”。第二行放置 “example”, “of”, “text”空格分布为 “example of text”。最后一行 “justification.” 后面填充空格。
性能优化关键点
内存管理确保每次分配的内存适当释放避免内存泄露。计算空格减少在每行处理时的重复计算通过计算总空格和每个间隔的空格来优化。
3. 代码实现
#include stdio.h
#include string.h
#include stdlib.h#define MAX_WORDS 1000// Helper function to add spaces
void addSpaces(char *line, int count) {for (int i 0; i count; i)strcat(line, );
}// Main function to justify text
char **fullJustify(char **words, int wordsSize, int maxWidth, int *returnSize) {char **result malloc(sizeof(char *) * MAX_WORDS);int resultIndex 0;int currentLength 0;int wordCount 0;for (int i 0; i wordsSize; i) {int wordLength strlen(words[i]);if (currentLength wordLength wordCount maxWidth) {// Create a new linechar *line malloc(sizeof(char) * (maxWidth 1));line[0] \0;int spacesNeeded maxWidth - currentLength;int eachSpace wordCount 1 ? spacesNeeded / (wordCount - 1) : spacesNeeded;int extraSpace wordCount 1 ? spacesNeeded % (wordCount - 1) : 0;for (int j i - wordCount; j i; j) {strcat(line, words[j]);if (spacesNeeded 0) {int spaceCount eachSpace (j - i wordCount extraSpace);addSpaces(line, spaceCount);spacesNeeded - spaceCount;}}result[resultIndex] line;currentLength 0;wordCount 0;}currentLength wordLength;wordCount;}// Handle the last linechar *line malloc(sizeof(char) * (maxWidth 1));line[0] \0;for (int i wordsSize - wordCount; i wordsSize; i) {strcat(line, words[i]);if (i wordsSize - 1) strcat(line, );}addSpaces(line, maxWidth - strlen(line));result[resultIndex] line;*returnSize resultIndex;return result;
}int main() {char *words[] {This, is, an, example, of, text, justification.};int wordsSize 7;int maxWidth 16;int returnSize;char **justifiedText fullJustify(words, wordsSize, maxWidth, returnSize);for (int i 0; i returnSize; i) {printf(\%s\\n, justifiedText[i]);}return 0;
}性能优化关键点
内存管理确保每次分配的内存适当释放避免内存泄露。计算空格减少在每行处理时的重复计算通过计算总空格和每个间隔的空格来优化。
4. 总结
这道题目主要考察字符串处理和格式化输出的能力通过合理的循环和条件判断以及对字符串操作的熟悉度。为了进一步提高编程能力可以通过解决更多类似的字符串处理问题来熟悉字符串操作和内存管理。
