深圳企业网站建设制作公司,百度网站加v,wordpress源码站整站源码,广州手机网站制作咨询1、英文的折行问题 给定一个单词序列#xff0c;以及一行中可以输入的字符数限制#xff08;线宽#xff09;。 在给定的顺序中放置换行符#xff0c;以便打印整齐。 假设每个单词的长度小于线宽。 像MS word这样的文字处理程序负责放置换行符。 这个想法是要有平衡的线条。… 1、英文的折行问题 给定一个单词序列以及一行中可以输入的字符数限制线宽。 在给定的顺序中放置换行符以便打印整齐。 假设每个单词的长度小于线宽。 像MS word这样的文字处理程序负责放置换行符。 这个想法是要有平衡的线条。 换句话说不是只有几行有很多额外空间有些行有少量额外空间。 2、中文的处理
文字断行完成后需要进行行内排版。 文档行中各个字符的宽度之和不大可能正好等于文档容器的客户区宽度。两者会有空白差。 由于中文字符和英文字符宽度不一样对于不等宽字体各个英文字符、数字字符等宽度还不一样。使得各个文本行的字符宽度之和是不一样的使得各个文档行右边缘是参差不齐的。这样比较严重的影响美观。 为此需要将文档行的宽度拉长成文档容器客户区宽度由此会额外的制造出不少空白此时需要将这些空白比较均匀的分摊到各个字符上。此处是比较均匀的分摊但不是完全均匀是有一定的分布算法的。 同一行中字符不是相对孤立的而且从逻辑上分为一组一组的对于汉字和标点符号它们是各自为政自己组成一组。对于连续的英文字母字符和阿拉伯数字它们逻辑上是同一组的一起构成一个完整的单词因此同一组之间的字符之间应该是紧密连接在一起不得拆开。[袁永福版权所有] 为此要分摊由于文字两边对齐而造成的额外空间时首先要对文档行的字符进行分组然后将额外的空白平均分摊到字符组上。
3 源程序
using System;
using System.Collections;
using System.Collections.Generic;namespace Legalsoft.Truffer.Algorithm
{public static partial class Algorithm_Gallery{public static int WordWrap_Solve(int[] nums, int k){int[,] memo new int[nums.Length, k 1];for (int i 0; i memo.GetLength(0); i){for (int j 0; j memo.GetLength(1); j){memo[i, j] -1;}}return WordWrap_Solve_UsingMemo(nums, nums.Length, k, 0, k, memo);}private static int WordWrap_Solve_Utility(int[] words, int n, int length, int wordIndex, int remLength, int[,] memo){if (wordIndex n - 1){memo[wordIndex, remLength] words[wordIndex] remLength ? 0 : Square(remLength);return memo[wordIndex, remLength];}int currWord words[wordIndex];if (currWord remLength){int sa WordWrap_Solve_UsingMemo(words, n, length, wordIndex 1, (remLength length) ? (remLength - currWord) : (remLength - currWord - 1), memo);int sb Square(remLength) WordWrap_Solve_UsingMemo(words, n, length, wordIndex 1, length - currWord, memo);return Math.Min(sa, sb);}else{return Square(remLength) WordWrap_Solve_UsingMemo(words, n, length, wordIndex 1, length - currWord, memo);}}private static int WordWrap_Solve_UsingMemo(int[] words, int n, int length, int wordIndex, int remLength, int[,] memo){if (memo[wordIndex, remLength] ! -1){return memo[wordIndex, remLength];}memo[wordIndex, remLength] WordWrap_Solve_Utility(words, n, length, wordIndex, remLength, memo);return memo[wordIndex, remLength];}private static int Square(int n){return n * n;}private static Liststring solution new Liststring();public static int WWP_Solution(int[] p, int n){int k;if (p[n] 1){k 1;}else{k WWP_Solution(p, p[n] - 1) 1;}solution.Add(Line number k : From word no. p[n] to n);return k;}public static void WordWrap_Solve(int[] sentence, int n, int M){int[,] extras new int[n 1, n 1];int[,] lc new int[n 1, n 1];int[] c new int[n 1];int[] p new int[n 1];for (int i 1; i n; i){extras[i, i] M - sentence[i - 1];for (int j i 1; j n; j){extras[i, j] extras[i, j - 1] - sentence[j - 1] - 1;}}for (int i 1; i n; i){for (int j i; j n; j){if (extras[i, j] 0){lc[i, j] int.MaxValue;}else if (j n extras[i, j] 0){lc[i, j] 0;}else{lc[i, j] extras[i, j] * extras[i, j];}}}c[0] 0;for (int j 1; j n; j){c[j] int.MaxValue;for (int i 1; i j; i){if (c[i - 1] ! int.MaxValue lc[i, j] ! int.MaxValue (c[i - 1] lc[i, j] c[j])){c[j] c[i - 1] lc[i, j];p[j] i;}}}solution.Clear();WWP_Solution(p, n);}}
}
