做一个网站做少钱,优化软件刷排名seo,合肥做网站行吗,东莞横沥新闻今天给定一个单词数组 words 和一个长度 maxWidth #xff0c;重新排版单词#xff0c;使其成为每行恰好有 maxWidth 个字符#xff0c;且左右两端对齐的文本。 你应该使用 “贪心算法” 来放置给定的单词#xff1b;也就是说#xff0c;尽可能多地往每行中放置单词。必要时可…给定一个单词数组 words 和一个长度 maxWidth 重新排版单词使其成为每行恰好有 maxWidth 个字符且左右两端对齐的文本。 你应该使用 “贪心算法” 来放置给定的单词也就是说尽可能多地往每行中放置单词。必要时可用空格 填充使得每行恰好有 maxWidth 个字符。 要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配则左侧放置的空格数要多于右侧的空格数。 文本的最后一行应为左对齐且单词之间不插入额外的空格。 注意: 单词是指由非空格字符组成的字符序列。 每个单词的长度大于 0小于等于 maxWidth。 输入单词数组 words 至少包含一个单词。
方法一基本贪心算法实现
function fullJustify(words: string[], maxWidth: number): string[] {let result: string[] [];let i 0;while (i words.length) {let lineWords: string[] [];let currentLength 0;// 尽可能多地往当前行添加单词while (i words.length currentLength words[i].length lineWords.length maxWidth) {lineWords.push(words[i]);currentLength words[i].length;i;}let spaces maxWidth - currentLength;let line ;if (i words.length || lineWords.length 1) {// 最后一行或只有一个单词的行左对齐line lineWords.join( );line .repeat(maxWidth - line.length);} else {// 非最后一行均匀分配空格let avgSpaces Math.floor(spaces / (lineWords.length - 1));let extraSpaces spaces % (lineWords.length - 1);for (let j 0; j lineWords.length - 1; j) {line lineWords[j];line .repeat(avgSpaces (j extraSpaces? 1 : 0));}line lineWords[lineWords.length - 1];}result.push(line);}return result;
}// 测试示例
let words [This, is, an, example, of, text, justification.];
let maxWidth 16;
let result fullJustify(words, maxWidth);
console.log(result);方法二拆分逻辑实现
function fullJustify(words: string[], maxWidth: number): string[] {let result: string[] [];let start 0;while (start words.length) {let end start;let lineLength 0;// 确定当前行能容纳的单词范围while (end words.length lineLength words[end].length (end - start) maxWidth) {lineLength words[end].length;end;}let spaces maxWidth - lineLength;let line ;if (end words.length || end - start 1) {// 最后一行或只有一个单词的行左对齐for (let i start; i end; i) {if (i start) {line ;spaces--;}line words[i];}line .repeat(spaces);} else {// 非最后一行均匀分配空格let avgSpaces Math.floor(spaces / (end - start - 1));let extraSpaces spaces % (end - start - 1);for (let i start; i end - 1; i) {line words[i];line .repeat(avgSpaces (i - start extraSpaces? 1 : 0));}line words[end - 1];}result.push(line);start end;}return result;
}// 测试示例
let words2 [What, must, be, acknowledgment, shall, be];
let maxWidth2 16;
let result2 fullJustify(words2, maxWidth2);
console.log(result2);方法三利用辅助函数实现
function createLine(words: string[], start: number, end: number, maxWidth: number, isLastLine: boolean): string {let lineLength 0;for (let i start; i end; i) {lineLength words[i].length;}let spaces maxWidth - lineLength;let line ;if (isLastLine || end - start 1) {// 最后一行或只有一个单词的行左对齐for (let i start; i end; i) {if (i start) {line ;spaces--;}line words[i];}line .repeat(spaces);} else {// 非最后一行均匀分配空格let avgSpaces Math.floor(spaces / (end - start - 1));let extraSpaces spaces % (end - start - 1);for (let i start; i end - 1; i) {line words[i];line .repeat(avgSpaces (i - start extraSpaces? 1 : 0));}line words[end - 1];}return line;
}function fullJustify(words: string[], maxWidth: number): string[] {let result: string[] [];let start 0;while (start words.length) {let end start;let currentLength 0;// 确定当前行能容纳的单词范围while (end words.length currentLength words[end].length (end - start) maxWidth) {currentLength words[end].length;end;}let isLastLine end words.length;let line createLine(words, start, end, maxWidth, isLastLine);result.push(line);start end;}return result;
}// 测试示例
let words3 [Science, is, what, we, understand, well, enough, to, explain, to, a, computer., Art, is, everything, else, we, do];
let maxWidth3 20;
let result3 fullJustify(words3, maxWidth3);
console.log(result3);复杂度分析
时间复杂度三种方法的时间复杂度均为 (O(n))其中 n 是单词数组 words 中所有字符的总数。因为每个单词只会被处理一次。空间复杂度三种方法的空间复杂度均为 (O(m))其中 m 是结果数组的长度主要用于存储排版后的每行文本。
这些方法的核心思路都是贪心算法尽可能多地往每行中放置单词然后根据不同情况最后一行或非最后一行来分配空格。不同方法只是在代码结构和实现细节上有所差异。
方法四动态规划
动态规划的核心在于将大问题拆解为小问题通过保存子问题的解来避免重复计算。对于这个单词排版问题我们可以定义状态并找出状态转移方程。
function fullJustify(words: string[], maxWidth: number): string[] {const n words.length;// cost[i][j] 表示从第 i 个单词到第 j 个单词放在一行的代价const cost: number[][] new Array(n).fill(0).map(() new Array(n).fill(Number.MAX_SAFE_INTEGER));// 计算每行放置不同单词组合的代价for (let i 0; i n; i) {let length 0;for (let j i; j n; j) {if (i j) {length words[j].length;} else {length words[j].length 1;}if (length maxWidth) {cost[i][j] Math.pow(maxWidth - length, 2);}}}// dp[i] 表示从第 i 个单词开始排版的最小代价const dp: number[] new Array(n 1).fill(Number.MAX_SAFE_INTEGER);// 用于记录每个位置的最优分割点const path: number[] new Array(n 1).fill(0);dp[n] 0;// 动态规划计算最小代价和最优分割点for (let i n - 1; i 0; i--) {for (let j i; j n; j) {if (cost[i][j]! Number.MAX_SAFE_INTEGER) {if (dp[i] cost[i][j] dp[j 1]) {dp[i] cost[i][j] dp[j 1];path[i] j 1;}}}}const result: string[] [];let start 0;// 根据最优分割点构建排版结果while (start n) {const end path[start];const lineWords words.slice(start, end);let line ;if (end n) {// 最后一行左对齐line lineWords.join( );line .repeat(maxWidth - line.length);} else {const spaces maxWidth - lineWords.reduce((acc, word) acc word.length, 0);if (lineWords.length 1) {line lineWords[0] .repeat(spaces);} else {const avgSpaces Math.floor(spaces / (lineWords.length - 1));const extraSpaces spaces % (lineWords.length - 1);for (let i 0; i lineWords.length - 1; i) {line lineWords[i];line .repeat(avgSpaces (i extraSpaces? 1 : 0));}line lineWords[lineWords.length - 1];}}result.push(line);start end;}return result;
}// 测试示例
const words [This, is, an, example, of, text, justification.];
const maxWidth 16;
console.log(fullJustify(words, maxWidth));方法五递归回溯
递归回溯是一种通过尝试所有可能的组合来找到最优解的方法。对于这个问题我们可以递归地尝试将单词放入不同的行直到找到满足条件的排版方式。
function fullJustify(words: string[], maxWidth: number): string[] {const result: string[] [];function backtrack(index: number): void {if (index words.length) {return;}let lineWords: string[] [];let currentLength 0;// 尽可能多地往当前行添加单词while (index words.length currentLength words[index].length lineWords.length maxWidth) {lineWords.push(words[index]);currentLength words[index].length;index;}let line ;if (index words.length) {// 最后一行左对齐line lineWords.join( );line .repeat(maxWidth - line.length);} else {const spaces maxWidth - currentLength;if (lineWords.length 1) {line lineWords[0] .repeat(spaces);} else {const avgSpaces Math.floor(spaces / (lineWords.length - 1));const extraSpaces spaces % (lineWords.length - 1);for (let i 0; i lineWords.length - 1; i) {line lineWords[i];line .repeat(avgSpaces (i extraSpaces? 1 : 0));}line lineWords[lineWords.length - 1];}}result.push(line);backtrack(index);}backtrack(0);return result;
}// 测试示例
const words2 [What, must, be, acknowledgment, shall, be];
const maxWidth2 16;
console.log(fullJustify(words2, maxWidth2));复杂度分析
动态规划方法
时间复杂度(O(n^2))其中 n 是单词的数量。主要开销在于填充 cost 数组和进行动态规划计算。空间复杂度(O(n^2))主要用于存储 cost 数组和 dp 数组。
递归回溯方法
时间复杂度(O(2^n))因为在最坏情况下每个单词都有两种选择放入当前行或放入下一行。空间复杂度(O(n))主要是递归栈的空间开销。
