刚刚在一次求职面试中，我被要求实现一个具有此签名的函数：
function justify($str_in, $desired_length)
它需要模仿HTML的文本对齐：justing会做什么，这里有一些例子（desired_length = 48）
你好世界那里好吧=你好......世界。。。。。。那里。。。。。。。还行。。。。。。。然后 你好 = ...你好。。。。。。。。。。。。。。。。。。。。。 好的，然后=好的..................然后 这个字符串几乎肯定比 48 长，我认为 = this.string.is.almost.certainly.longer.than.48。 两个字=两个的话 三个好的词=三个......还行。。。。。。。。。。。。。。。。。。的话 1 2 3 4 5 6 7 8 9 = 1....2....3....4.....5....6.....7....8.....9
（我用句点替换了空格来说明）
单词之间的空格长度相差不得超过一个。
我写了一个PHP解决方案，但我更感兴趣的是人们可以想出什么算法来解决问题。这是我在求职面试中的第一个白板问题，恐怕多种因素的综合作用使我花费的时间比我应该花的时间要长得多。
这就是我想出的。我添加了可选的 $char 参数，以便您可以看到它输出的内容 - 当然，您可以将其拉入函数中，以便原型符合要求。
function justify($str_in, $desired_length, $char = '_') {
// Some common vars and simple error checking / sanitation
$return = '';
$str_in = trim( $str_in);
$desired_length = intval( $desired_length);
// If we've got invalid input, we're done
if( $desired_length <= 0)
return $str_in;
// If the input string is greater than the length, we need to truncate it WITHOUT splitting words
if( strlen( $str_in) > $desired_length) {
$str = wordwrap($str_in, $desired_length);
$str = explode("'n", $str);
$str_in = $str[0];
}
$words = explode( ' ', $str_in);
$num_words = count( $words);
// If there's only one word, it's a simple edge case
if( $num_words == 1) {
$length = ($desired_length - strlen( $words[0])) / 2;
$return .= str_repeat( $char, floor( $length)) . $words[0] . str_repeat( $char, ceil( $length));
} else {
$word_length = strlen( implode( '', $words));
// Calculate the number of spaces to distribute over the words
$num_words--; // We're going to eliminate the last word
$spaces = floor( ($desired_length - $word_length) / $num_words);
$remainder = $desired_length - $word_length - ($num_words * $spaces);
$last = array_pop( $words);
foreach( $words as $word) {
// If we didn't get an even number of spaces to distribute, just tack it on to the front
$spaces_to_add = $spaces;
if( $remainder > 0) {
$spaces_to_add++;
$remainder--;
}
$return .= $word . str_repeat( $char, $spaces_to_add);
}
$return .= $last;
}
return $return;
}
和测试用例：
$inputs = array(
'hello world there ok then',
'hello',
'ok then',
'this string is almost certainly longer than 48 I think',
'two words',
'three ok words',
'1 2 3 4 5 6 7 8 9'
);
foreach( $inputs as $x) {
$ret = justify( $x, 48);
echo 'Inp: ' . $x . " - strlen(" . strlen( $x) . ")'n";
echo 'Out: ' . $ret . " - strlen(" . strlen( $ret) . ")'n'n";
}
和输出：
Inp: hello world there ok then - strlen(25)
Out: hello_______world_______there_______ok______then - strlen(48)
Inp: hello - strlen(5)
Out: _____________________hello______________________ - strlen(48)
Inp: ok then - strlen(7)
Out: ok__________________________________________then - strlen(48)
Inp: this string is almost certainly longer than 48 I think - strlen(54)
Out: this_string_is_almost_certainly_longer_than_48_I - strlen(48)
Inp: two words - strlen(9)
Out: two________________________________________words - strlen(48)
Inp: three ok words - strlen(14)
Out: three__________________ok__________________words - strlen(48)
Inp: 1 2 3 4 5 6 7 8 9 - strlen(17)
Out: 1_____2_____3_____4_____5_____6_____7_____8____9 - strlen(48)
还有一个演示！
编辑：清理了代码，它仍然可以:)工作。
使不使用任何循环/递归或带有回调的正则表达式成为个人挑战。我使用了一个explode()和一个implode()来实现这一点。大获成功！
《守则》
function justify($str, $maxlen) {
$str = trim($str);
$strlen = strlen($str);
if ($strlen >= $maxlen) {
$str = wordwrap($str, $maxlen);
$str = explode("'n", $str);
$str = $str[0];
$strlen = strlen($str);
}
$space_count = substr_count($str, ' ');
if ($space_count === 0) {
return str_pad($str, $maxlen, ' ', STR_PAD_BOTH);
}
$extra_spaces_needed = $maxlen - $strlen;
$total_spaces = $extra_spaces_needed + $space_count;
$space_string_avg_length = $total_spaces / $space_count;
$short_string_multiplier = floor($space_string_avg_length);
$long_string_multiplier = ceil($space_string_avg_length);
$short_fill_string = str_repeat(' ', $short_string_multiplier);
$long_fill_string = str_repeat(' ', $long_string_multiplier);
$limit = ($space_string_avg_length - $short_string_multiplier) * $space_count;
$words_split_by_long = explode(' ', $str, $limit+1);
$words_split_by_short = $words_split_by_long[$limit];
$words_split_by_short = str_replace(' ', $short_fill_string, $words_split_by_short);
$words_split_by_long[$limit] = $words_split_by_short;
$result = implode($long_fill_string, $words_split_by_long);
return $result;
}
短 （348 字符）
function j($s,$m){$s=trim($s);$l=strlen($s);if($l>=$m){$s=explode("'n",wordwrap($s,$m));$s=$s[0];$l=strlen($s);}$c=substr_count($s,' ');if($c===0)return str_pad($s,$m,' ',STR_PAD_BOTH);$a=($m-$l+$c)/$c;$h=floor($a);$i=($a-$h)*$c;$w=explode(' ',$s,$i+1);$w[$i]=str_replace(' ',str_repeat(' ',$h),$w[$i]);return implode(str_repeat(' ',ceil($a)),$w);}
算法/代码说明
- 处理两个异常（长度超过最大长度的字符串或仅一个单词）。
- 找到每个单词之间所需的平均间距（
$space_string_avg_length）。 - 分别根据
$space_string_avg_length的ceil()和floor()创建用于单词之间的长填充字符串和短填充字符串。 - 了解我们需要多少个长填充字符串。（
$limit+1）。 - 根据我们需要的长填充字符串数量拆分文本。
- 将数组最后一部分中由拆分创建的空格替换为短填充字符串。
- 将拆分的文本与长填充字符串连接在一起。
测试
$tests = array(
'hello world there ok then',
'hello',
'ok then',
'this string is almost certainly longer than 48 I think',
'two words',
'three ok words',
'1 2 3 4 5 6 7 8 9'
);
foreach ($tests as $test) {
$len_before = strlen($test);
$processed = str_replace(' ', '_', justify($test, 48));
$len_after = strlen($processed);
echo "IN($len_before): $test'n";
echo "OUT($len_after): $processed'n";
}
结果
IN(25): hello world there ok then
OUT(48): hello_______world_______there_______ok______then
IN(5): hello
OUT(48): _____________________hello______________________
IN(7): ok then
OUT(48): ok__________________________________________then
IN(54): this string is almost certainly longer than 48 I think
OUT(48): this_string_is_almost_certainly_longer_than_48_I
IN(9): two words
OUT(48): two________________________________________words
IN(14): three ok words
OUT(48): three__________________ok__________________words
IN(17): 1 2 3 4 5 6 7 8 9
OUT(48): 1_____2_____3_____4_____5_____6_____7_____8____9
看它跑！
这是我
的解决方案，没有讨厌的循环
function justify( $str_in, $desired_length=48 ) {
if ( strlen( $str_in ) > $desired_length ) {
$str_in = current( explode( "'n", wordwrap( $str_in, $desired_length ) ) );
}
$string_length = strlen( $str_in );
$spaces_count = substr_count( $str_in, ' ' );
$needed_spaces_count = $desired_length - $string_length + $spaces_count;
if ( $spaces_count === 0 ) {
return str_pad( $str_in, $desired_length, ' ', STR_PAD_BOTH );
}
$spaces_per_space = ceil( $needed_spaces_count / $spaces_count );
$spaced_string = preg_replace( '~'s+~', str_repeat( ' ', $spaces_per_space ), $str_in );
return preg_replace_callback(
sprintf( '~'s{%s}~', $spaces_per_space ),
function ( $m ) use( $spaces_per_space ) {
return str_repeat( ' ', $spaces_per_space-1 );
},
$spaced_string,
strlen( $spaced_string ) - $desired_length
);
}
注释和输出...
https://gist.github.com/2939068
- 找出有多少个车位
- 了解需要多少个空间
- 将现有空间替换为满足或刚好超过所需行长度所需的空间量（均匀分布）
- 使用preg_replace_callback将
's{spaces_inserted}量替换为满足所需行长度所需的's{spaces_inserted-1}
量
我想看看哪种算法最有效，所以我运行了一些基准测试。我对所有 7 个测试用例进行了 100k 次迭代。（在单核 Ubuntu VM 中运行它）
省略了@ppsreejith和@Kristian Antonsen代码的结果，因为当我尝试运行它们时，它们的代码崩溃了。
基准测试结果
$ php justify.bench.php盖伦（理由1）： 5.1464750766754尼克B（理由2）： 3.8629620075226保罗·贝甘蒂诺（理由3）： 4.3705048561096用户381521（理由5）： 8.5988481044769Vlzvl（Justify7）： 6.6795041561127亚历山大（理由8）： 6.7060301303864OHAAL（Justify9）： 2.9896130561829PhpMyCoder： 6.1514630317688 （已修复！
理由.板凳.php
<?php
$tests = array(
'hello world there ok then',
'hello',
'ok then',
'this string is almost certainly longer than 48 I think',
'two words',
'three ok words',
'1 2 3 4 5 6 7 8 9'
);
$testers = array(
'Galen' => 'justify1',
'nickb' => 'justify2',
'Paolo Bergantino' => 'justify3',
// 'Kristian Antonsen' => 'justify4',
'user381521' => 'justify5',
// 'ppsreejith' => 'justify6',
'vlzvl' => 'justify7',
'Alexander' => 'justify8',
'ohaal' => 'justify9'
);
// ppsreejith and Kristian Antonsen's code crashed and burned when I tried to run it
// PhpMyCoder is a special case, but his code also crashed when doing $jus->format(48);
foreach ($testers as $tester => $func) {
$b=microtime(true);
for($i=0;$i<100000;$i++)
foreach ($tests as $test)
$func($test,48);
$a=microtime(true);
echo $tester.'('.$func.'): '.($a-$b)."'n";
}
echo "'n";
// Fixed!
$jus = new Justifier($tests);
$b=microtime(true);
for($i=0;$i<100000;$i++) {
$jus->format(54);
}
$a=microtime(true);
echo 'PhpMyCoder: '.($a-$b)." (Fixed!)'n";
// ALGORITHMS BELOW
// Galen
function justify1( $str_in, $desired_length=48 ) {
if ( strlen( $str_in ) > $desired_length ) {
$str_in = current( explode( "'n", wordwrap( $str_in, $desired_length ) ) );
}
$string_length = strlen( $str_in );
$spaces_count = substr_count( $str_in, ' ' );
$needed_spaces_count = $desired_length - $string_length + $spaces_count;
if ( $spaces_count === 0 ) {
return str_pad( $str_in, $desired_length, ' ', STR_PAD_BOTH );
}
$spaces_per_space = ceil( $needed_spaces_count / $spaces_count );
$spaced_string = preg_replace( '~'s+~', str_repeat( ' ', $spaces_per_space ), $str_in );
return preg_replace_callback(
sprintf( '~'s{%s}~', $spaces_per_space ),
function ( $m ) use( $spaces_per_space ) {
return str_repeat( ' ', $spaces_per_space-1 );
},
$spaced_string,
strlen( $spaced_string ) - $desired_length
);
}
// nickb
function justify2($str_in, $desired_length, $char = '_') {
// Some common vars and simple error checking / sanitation
$return = '';
$str_in = trim( $str_in);
$desired_length = intval( $desired_length);
// If we've got invalid input, we're done
if( $desired_length <= 0)
return $str_in;
// If the input string is greater than the length, we need to truncate it WITHOUT splitting words
if( strlen( $str_in) > $desired_length) {
$str = wordwrap($str_in, $desired_length);
$str = explode("'n", $str);
$str_in = $str[0];
}
$words = explode( ' ', $str_in);
$num_words = count( $words);
// If there's only one word, it's a simple edge case
if( $num_words == 1) {
$length = ($desired_length - strlen( $words[0])) / 2;
$return .= str_repeat( $char, floor( $length)) . $words[0] . str_repeat( $char, ceil( $length));
} else {
$word_length = strlen( implode( '', $words));
// Calculate the number of spaces to distribute over the words
$num_words--; // We're going to eliminate the last word
$spaces = floor( ($desired_length - $word_length) / $num_words);
$remainder = $desired_length - $word_length - ($num_words * $spaces);
$last = array_pop( $words);
foreach( $words as $word) {
// If we didn't get an even number of spaces to distribute, just tack it on to the front
$spaces_to_add = $spaces;
if( $remainder > 0) {
$spaces_to_add++;
$remainder--;
}
$return .= $word . str_repeat( $char, $spaces_to_add);
}
$return .= $last;
}
return $return;
}
// Paolo Bergantino
function justify3($str, $to_len) {
$str = trim($str);
$strlen = strlen($str);
if($str == '') return '';
if($strlen >= $to_len) {
return substr($str, 0, $to_len);
}
$words = explode(' ', $str);
$word_count = count($words);
$space_count = $word_count - 1;
if($word_count == 1) {
return str_pad($str, $to_len, ' ', STR_PAD_BOTH);
}
$space = $to_len - $strlen + $space_count;
$per_space = $space/$space_count;
if(is_int($per_space)) {
return implode($words, str_pad('', $per_space, ' '));
}
$new_str = '';
$spacing = floor($per_space);
$new_str .= $words[0] . str_pad('', $spacing);
foreach($words as $x => $word) {
if($x == $word_count - 1 || $x == 0) continue;
if($x < $word_count - 1) {
$diff = $to_len - strlen($new_str) - (strlen(implode('', array_slice($words, $x))));
$new_str .= $word . str_pad('', floor($diff/($space_count - $x)), ' ');
}
}
$new_str .= $words[$x];
return $new_str;
}
// Kristian Antonsen
function justify4($str_in, $desired_length)
{
foreach ($str_in as &$line) {
$words = explode(' ', $line);
$word_count = count($words) - 1;
$spaces_to_fill = $desired_length - strlen($line) + $word_count;
if (count($words) == 1) {
$line = str_repeat('_', ceil($spaces_to_fill/2)) . $line
. str_repeat('_', floor($spaces_to_fill/2));
continue;
}
$next_space = floor($spaces_to_fill/$word_count);
$leftover_space = $spaces_to_fill % $word_count;
$line = array_shift($words);
foreach($words as $word) {
$extra_space = ($leftover_space) ? ceil($leftover_space / $word_count) : 0;
$leftover_space -= $extra_space;
$line .= str_repeat('_', $next_space + $extra_space) . $word;
}
}
return $str_in;
}
// user381521
function justify5 ($str, $len)
{
// split by whitespace, remove empty strings
$words = array_diff (preg_split ('/'s+/', $str), array (""));
// just space if no words
if (count ($words) == 0)
return str_repeat (" ", $len);
// add empty strings if only one element
if (count ($words) == 1)
$words = array ("", $words[0], "");
// get number of words and spaces
$wordcount = count ($words);
$numspaces = $wordcount - 1;
// get number of non-space characters
$numchars = array_sum (array_map ("strlen", $words));
// get number of characters remaining for space
$remaining = $len - $numchars;
// return if too little spaces remaining
if ($remaining <= $numspaces)
return substr (implode (" ", $words), 0, $len);
// get number of spaces per space
$spaces_per_space = $remaining / $numspaces;
$spaces_leftover = $remaining % $numspaces;
// make array for spaces, spread out leftover spaces
$spaces = array_fill (0, $numspaces, $spaces_per_space);
while ($spaces_leftover--)
$spaces[$numspaces - $spaces_leftover - 1]++;
$spaces[] = 0; // make count ($words) == count ($spaces)
// join it all together
$result = array ();
foreach ($words as $k => $v)
array_push ($result, $v, str_repeat (" ", $spaces[$k]));
return implode ($result);
}
// ppsreejith
function justify6($str, $to_len) {
$str = trim($str);
$strlen = strlen($str);
if($str == '') return '';
if($strlen >= $to_len) {
return substr($str, 0, $to_len);
}
$words = explode(' ', $str);
$word_count = count($words);
$space_count = $word_count - 1;
if($word_count == 1) {
return str_pad($str, $to_len, ' ', STR_PAD_BOTH);
}
$space = $to_len - $strlen + $space_count;
$per_space = floor($space/$space_count);
$spaces = str_pad('', $per_space, ' ');
$curr_word = implode($words, $spaces);
while(strlen($curr_word) < $to_len){
$curr_word = substr($curr_word,0,preg_match("[! ][".$spaces."][! ]",$curr_word)." ".preg_match("[! ][".$spaces."][! ]",$curr_word));
}
return $curr_word;
}
// vlzvl
function justify7($str_in, $desired_length)
{
$str_in = preg_replace("!'s+!"," ",$str_in); // get rid of multiple spaces
$words = explode(" ",$str_in); // break words
$num_words = sizeof($words); // num words
if ($num_words==1) {
return str_pad($str_in,$desired_length,"_",STR_PAD_BOTH);
}
else {
$num_chars = 0; $lenwords = array();
for($x=0;$x<$num_words;$x++) { $num_chars += $lenwords[$x] = strlen($words[$x]); }
$each_div = round(($desired_length - $num_chars) / ($num_words-1));
for($x=0,$sum=0;$x<$num_words;$x++) { $sum += ($lenwords[$x] + ($x<$num_words-1 ? $each_div : 0)); }
$space_to_addcut = ($desired_length - $sum);
for($x=0;$x<$num_words-1;$x++) {
$words[$x] .= str_repeat("_",$each_div+($each_div>1? ($space_to_addcut<0?-1:($space_to_addcut>0?1:0)) :0));
if ($each_div>1) { $space_to_addcut += ($space_to_addcut<0 ? 1 : ($space_to_addcut>0?-1:0) ); }
}
return substr(implode($words),0,$desired_length);
}
}
// Alexander
function justify8($str, $length) {
$words = explode(' ', $str);
if(count($words)==1) $words = array("", $str, "");
$spaces = $length - array_sum(array_map("strlen", $words));
$add = (int)($spaces / (count($words) - 1));
$left = $spaces % (count($words) - 1);
$spaced = implode(str_repeat("_", $add + 1), array_slice($words, 0, $left + 1));
$spaced .= str_repeat("_", max(1, $add));
$spaced .= implode(str_repeat("_", max(1, $add)), array_slice($words, $left + 1));
return substr($spaced, 0, $length);
}
// ohaal
function justify9($s,$m){$s=trim($s);$l=strlen($s);if($l>=$m){$s=explode("'n",wordwrap($s,$m));$s=$s[0];$l=strlen($s);}$c=substr_count($s,' ');if($c===0)return str_pad($s,$m,' ',STR_PAD_BOTH);$a=($m-$l+$c)/$c;$h=floor($a);$i=($a-$h)*$c;$w=explode(' ',$s,$i+1);$w[$i]=str_replace(' ',str_repeat(' ',$h),$w[$i]);return implode(str_repeat(' ',ceil($a)),$w);}
// PhpMyCoder
class Justifier {
private $text;
public function __construct($text) {
if(!is_string($text) && !is_array($text)) {
throw new InvalidArgumentException('Expected a string or an array of strings, instead received type: ' . gettype($text));
}
if(is_array($text)) {
// String arrays must be converted to JustifierLine arrays
$this->text = array_map(function($line) {
return JustifierLine::fromText($line);
}, $text);
} else {
// Single line of text input
$this->text = $text;
}
}
public function format($width = NULL) {
// Strings have to be broken into an array and then jusitifed
if(is_string($this->text)) {
if($width == null) {
throw new InvalidArgumentException('A width must be provided for separation when an un-split string is provided');
}
if($width <= 0) {
throw new InvalidArgumentException('Expected a positive, non-zero width, instead received width of ' . $width);
}
// Break up a JustifierLine of all text until each piece is smaller or equal to $width
$lines = array(JustifierLine::fromText($this->text));
$count = 0;
$newLine = $lines[0]->breakAtColumn($width);
while($newLine !== null) {
$lines[] = $newLine;
$newLine = $lines[++$count]->breakAtColumn($width);
}
} else {
$lines = $this->text;
// Allow for fluid width (uses longest line with single space)
if($width == NULL) {
$width = -1;
foreach($lines as $line) {
// Width of line = Sum of the lengths of the words and the spaces (number of words - 1)
$newWidth = $line->calculateWordsLength() + $line->countWords() - 1;
if($newWidth > $width) { // Looking for the longest line
$width = $newWidth;
}
}
}
}
// Justify each element of array
//$output = array_map(function($line) use ($width) {
// return $this->justify($line, $width);
//}, $lines);
$output = array();
foreach($lines as $line) {
$output[] = $this->justify($line, $width);
}
// If a single-line is passed in, a single line is returned
if(count($output)) {
return $output[0];
}
return $output;
}
private function justify(JustifierLine $line, $width) {
// Retrieve already calculated line information
$words = $line->extractWords();
$spaces = $line->countWords() - 1;
$wordLens = $line->findWordLengths();
$wordsLen = $line->calculateWordsLength();
$minWidth = $wordsLen + $spaces;
$output = '';
if($minWidth > $width) {
throw new LengthException('A minimum width of ' . $minWidth . ' was required, but a width of ' . $width . ' was given instead');
}
// No spaces means only one word (center align)
if($spaces == 0) {
return str_pad($words[0], $width, ' ', STR_PAD_BOTH);
}
for(;$spaces > 0; $spaces--) {
// Add next word to output and subtract its length from counters
$output .= array_shift($words);
$length = array_shift($wordLens);
$wordsLen -= $length;
$width -= $length;
if($spaces == 1) { // Last Iteration
return $output . str_repeat(' ', $width - $wordsLen) . $words[0];
}
// Magic padding is really just simple math
$padding = floor(($width - $wordsLen) / $spaces);
$output .= str_repeat(' ', $padding);
$width -= $padding;
}
}
}
class JustifierLine {
private $words;
private $numWords;
private $wordLengths;
private $wordsLength;
public static function fromText($text) {
// Split words into an array
preg_match_all('/[^ ]+/', $text, $matches, PREG_PATTERN_ORDER);
$words = $matches[0];
// Count words
$numWords = count($words);
// Find the length of each word
$wordLengths = array_map('strlen', $words);
//And Finally, calculate the total length of all words
$wordsLength = array_reduce($wordLengths, function($result, $length) {
return $result + $length;
}, 0);
return new JustifierLine($words, $numWords, $wordLengths, $wordsLength);
}
private function __construct($words, $numWords, $wordLengths, $wordsLength) {
$this->words = $words;
$this->numWords = $numWords;
$this->wordLengths = $wordLengths;
$this->wordsLength = $wordsLength;
}
public function extractWords() { return $this->words; }
public function countWords() { return $this->numWords; }
public function findWordLengths() { return $this->wordLengths; }
public function calculateWordsLength() { return $this->wordsLength; }
public function breakAtColumn($column) {
// Avoid extraneous processing if we can determine no breaking can be done
if($column >= ($this->wordsLength + $this->numWords - 1)) {
return null;
}
$width = 0;
$wordsLength = 0;
for($i = 0; $i < $this->numWords; $i++) {
// Add width of next word
$width += $this->wordLengths[$i];
// If the line is overflowing past required $width
if($width > $column) {
// Remove overflow at end & create a new object with the overflow
$words = array_splice($this->words, $i);
$numWords = $this->numWords - $i;
$this->numWords = $i;
$wordLengths = array_splice($this->wordLengths, $i);
$tempWordsLength = $wordsLength;
$wordsLength = $this->wordsLength - $wordsLength;
$this->wordsLength = $tempWordsLength;
return new JustifierLine($words, $numWords, $wordLengths, $wordsLength);
}
$width++; // Assuming smallest spacing to fit
// We also have to keep track of the total $wordsLength
$wordsLength += $this->wordLengths[$i];
}
return null;
}
}
这是我的解决方案。没有讨厌的正则表达式:)
function justify($str, $length) {
$words = explode(' ', $str);
if(count($words)==1) $words = array("", $str, "");
$spaces = $length - array_sum(array_map("strlen", $words));
$add = (int)($spaces / (count($words) - 1));
$left = $spaces % (count($words) - 1);
$spaced = implode(str_repeat("_", $add + 1), array_slice($words, 0, $left + 1));
$spaced .= str_repeat("_", max(1, $add));
$spaced .= implode(str_repeat("_", max(1, $add)), array_slice($words, $left + 1));
return substr($spaced, 0, $length);
}
这是由PHP数组函数驱动的。
这是工作示例。
只是为了没有人认为我试图让他们为我做功课，这是我（我认为有效的）解决方案。
但是，我不确定我是否可以根据需要在白板上编写这么多代码，所以我最好奇的是，如果不看我的代码，其他人会如何解决这个问题。（可以这么说，在他们叫我"时间"之前，我在采访中绕到了
他们身边）function justify($str, $to_len) {
$str = trim($str);
$strlen = strlen($str);
if($str == '') return '';
if($strlen >= $to_len) {
return substr($str, 0, $to_len);
}
$words = explode(' ', $str);
$word_count = count($words);
$space_count = $word_count - 1;
if($word_count == 1) {
return str_pad($str, $to_len, ' ', STR_PAD_BOTH);
}
$space = $to_len - $strlen + $space_count;
$per_space = $space/$space_count;
if(is_int($per_space)) {
return implode($words, str_pad('', $per_space, ' '));
}
$new_str = '';
$spacing = floor($per_space);
$new_str .= $words[0] . str_pad('', $spacing);
foreach($words as $x => $word) {
if($x == $word_count - 1 || $x == 0) continue;
if($x < $word_count - 1) {
$diff = $to_len - strlen($new_str) - (strlen(implode('', array_slice($words, $x))));
$new_str .= $word . str_pad('', floor($diff/($space_count - $x)), ' ');
}
}
$new_str .= $words[$x];
return $new_str;
}
$tests = array(' hello world there ok then ', 'hello', 'ok then', 'this string is almost certainly longer than 48 I think', 'two words', 'three ok words', '1 2 3 4 5 6 7 8 9');
foreach($tests as $word) {
print $word . ' = ' . str_replace(' ', '_', justify($word, 48)) . '<br>';
}
我想念我在 Python 中的列表理解......
<?php
function justify ($str, $len)
{
// split by whitespace, remove empty strings
$words = array_diff (preg_split ('/'s+/', $str), array (""));
// just space if no words
if (count ($words) == 0)
return str_repeat (" ", $len);
// add empty strings if only one element
if (count ($words) == 1)
$words = array ("", $words[0], "");
// get number of words and spaces
$wordcount = count ($words);
$numspaces = $wordcount - 1;
// get number of non-space characters
$numchars = array_sum (array_map ("strlen", $words));
// get number of characters remaining for space
$remaining = $len - $numchars;
// return if too little spaces remaining
if ($remaining <= $numspaces)
return substr (implode (" ", $words), 0, $len);
// get number of spaces per space
$spaces_per_space = $remaining / $numspaces;
$spaces_leftover = $remaining % $numspaces;
// make array for spaces, spread out leftover spaces
$spaces = array_fill (0, $numspaces, $spaces_per_space);
while ($spaces_leftover--)
$spaces[$numspaces - $spaces_leftover - 1]++;
$spaces[] = 0; // make count ($words) == count ($spaces)
// join it all together
$result = array ();
foreach ($words as $k => $v)
array_push ($result, $v, str_repeat (" ", $spaces[$k]));
return implode ($result);
}
?>
这是我
的尝试。
function justify($str_in, $desired_length)
{
foreach ($str_in as &$line) {
$words = explode(' ', $line);
$word_count = count($words) - 1;
$spaces_to_fill = $desired_length - strlen($line) + $word_count;
if (count($words) == 1) {
$line = str_repeat('_', ceil($spaces_to_fill/2)) . $line
. str_repeat('_', floor($spaces_to_fill/2));
continue;
}
$next_space = floor($spaces_to_fill/$word_count);
$leftover_space = $spaces_to_fill % $word_count;
$line = array_shift($words);
foreach($words as $word) {
$extra_space = ($leftover_space) ? ceil($leftover_space / $word_count) : 0;
$leftover_space -= $extra_space;
$line .= str_repeat('_', $next_space + $extra_space) . $word;
}
}
return $str_in;
}
我试图保持相对简洁，这影响了可读性。但这是它的工作原理：
对于每个条目，我们将单词拆分为一个数组$words 。因为我们可能需要单词前后的空格，所以我们还要在数组的开头和结尾添加一个空字符串。
我们计算$leftover_space剩余的空格量（即我们需要在某处插入的空格），并将其除以$word_count单词数，因此我们知道每个单词之间放置多少空格的平均值。
每当我们添加一个单词时，我们也会$extra_space添加一些空格，具体取决于剩余的数量。之后，我们删除添加的金额 从$leftover_space .
示例输出
$data = justify($data, 48);
print_r($data);
Array
(
[0] => 123456789012345678901234567890123456789012345678
[1] => hello_______world_______there_______ok______then
[2] => ______________________hello_____________________
[3] => ok__________________________________________then
[4] => this__string__is_almost_certainly_longer_than_48
[5] => two________________________________________words
[6] => three__________________ok__________________words
[7] => 1_____2_____3_____4_____5_____6_____7_____8____9
)
我认为这完全有效：（"_"只是保持空间可见）
function justify($str_in, $desired_length)
{
$str_in = preg_replace("!'s+!"," ",$str_in); // get rid of multiple spaces
$words = explode(" ",$str_in); // break words
$num_words = sizeof($words); // num words
if ($num_words==1) {
return str_pad($str_in,$desired_length,"_",STR_PAD_BOTH);
}
else {
$num_chars = 0; $lenwords = array();
for($x=0;$x<$num_words;$x++) { $num_chars += $lenwords[$x] = strlen($words[$x]); }
$each_div = round(($desired_length - $num_chars) / ($num_words-1));
for($x=0,$sum=0;$x<$num_words;$x++) { $sum += ($lenwords[$x] + ($x<$num_words-1 ? $each_div : 0)); }
$space_to_addcut = ($desired_length - $sum);
for($x=0;$x<$num_words-1;$x++) {
$words[$x] .= str_repeat("_",$each_div+($each_div>1? ($space_to_addcut<0?-1:($space_to_addcut>0?1:0)) :0));
if ($each_div>1) { $space_to_addcut += ($space_to_addcut<0 ? 1 : ($space_to_addcut>0?-1:0) ); }
}
return substr(implode($words),0,$desired_length);
}
}
编辑：
函数现在也摆脱了单词之间的多个空格。工作原理（简而言之）：
- 删除单词之间的连续空格
- 数单词，所以如果一个（"你好"示例）只是填充两者并回显它。
- ..否则计算所用单词的字符数
- 计算要添加的全局和部分空间（示例中为"_"）。
- 计算要添加的额外空间（<所需的字符串>所需的字符串 Len）并将其应用于填充。
- 最后，将最终字符串减少到所需的长度。
测试：
$tests = array(
'hello world there ok then',
'hello',
'ok then',
'this string is almost certainly longer than 48 I think',
'three ok words',
'1 2 3 4 5 6 7 8 9',
'Lorem Ipsum is simply dummy text'
);
$arr = array();
foreach($tests as $key=>$val) {
$arr[$key] = justify($val,50);
$arr[$key] .= " - (chars: ".strlen($arr[$key]).")";
}
echo "<pre>".print_r($arr,TRUE)."</pre>";
结果是：
Array
(
[0] => hello________world_______there_______ok_______then - (chars: 50)
[1] => ______________________hello_______________________ - (chars: 50)
[2] => ok____________________________________________then - (chars: 50)
[3] => this_string_is_almost_certainly_longer_than_48_I_t - (chars: 50)
[4] => three___________________ok___________________words - (chars: 50)
[5] => 1______2_____3_____4_____5_____6_____7_____8_____9 - (chars: 50)
[6] => Lorem____Ipsum____is_____simply_____dummy_____text - (chars: 50)
)
这很难
:)编辑2：
功能现在快了大约 20%，因为这个基准让我感动:)
（半长）解决方案
我花了一段时间来完善（可能比面试官允许的要长得多），但我已经为这个问题提出了一个优雅的 162 行 OOP 解决方案。我包含的功能允许对齐单个字符串、字符串数组（已分成行）或需要先分解为最大宽度的行的长字符串。演示遵循代码块。
$this。快速检查匿名函数的文档显示，$this 在 5.4 之前无法在匿名函数的上下文中使用。如果有人能找到解决此问题的干净方法，请将其放在评论中。<?php
class Justifier {
private $text;
public function __construct($text) {
if(!is_string($text) && !is_array($text)) {
throw new InvalidArgumentException('Expected a string or an array of strings, instead received type: ' . gettype($text));
}
if(is_array($text)) {
// String arrays must be converted to JustifierLine arrays
$this->text = array_map(function($line) {
return JustifierLine::fromText($line);
}, $text);
} else {
// Single line of text input
$this->text = $text;
}
}
public function format($width = null) {
// Strings have to be broken into an array and then jusitifed
if(is_string($this->text)) {
if($width == null) {
throw new InvalidArgumentException('A width must be provided for separation when an un-split string is provided');
}
if($width <= 0) {
throw new InvalidArgumentException('Expected a positive, non-zero width, instead received width of ' . $width);
}
// Break up a JustifierLine of all text until each piece is smaller or equal to $width
$lines = array(JustifierLine::fromText($this->text));
$count = 0;
$newLine = $lines[0]->breakAtColumn($width);
while($newLine !== null) {
$lines[] = $newLine;
$newLine = $lines[++$count]->breakAtColumn($width);
}
} else {
$lines = $this->text;
// Allow for fluid width (uses longest line with single space)
if($width == NULL) {
$width = -1;
foreach($lines as $line) {
// Width of line = Sum of the lengths of the words and the spaces (number of words - 1)
$newWidth = $line->calculateWordsLength() + $line->countWords() - 1;
if($newWidth > $width) { // Looking for the longest line
$width = $newWidth;
}
}
}
}
// Justify each element of array (PHP 5.4 ONLY)
//$output = array_map(function($line) use ($width) {
// return $this->justify($line, $width);
//}, $lines);
// Support for PHP 5.3
$output = array();
foreach($lines as $line) {
$output = $this->justify($line, $width);
}
// If a single-line is passed in, a single line is returned
if(count($output)) {
return $output[0];
}
return $output;
}
private function justify(JustifierLine $line, $width) {
// Retrieve already calculated line information
$words = $line->extractWords();
$spaces = $line->countWords() - 1;
$wordLens = $line->findWordLengths();
$wordsLen = $line->calculateWordsLength();
$minWidth = $wordsLen + $spaces;
$output = '';
if($minWidth > $width) {
throw new LengthException('A minimum width of ' . $minWidth . ' was required, but a width of ' . $width . ' was given instead');
}
// No spaces means only one word (center align)
if($spaces == 0) {
return str_pad($words[0], $width, ' ', STR_PAD_BOTH);
}
for(;$spaces > 0; $spaces--) {
// Add next word to output and subtract its length from counters
$output .= array_shift($words);
$length = array_shift($wordLens);
$wordsLen -= $length;
$width -= $length;
if($spaces == 1) { // Last Iteration
return $output . str_repeat(' ', $width - $wordsLen) . $words[0];
}
// Magic padding is really just simple math
$padding = floor(($width - $wordsLen) / $spaces);
$output .= str_repeat(' ', $padding);
$width -= $padding;
}
}
}
class JustifierLine {
private $words;
private $numWords;
private $wordLengths;
private $wordsLength;
public static function fromText($text) {
// Split words into an array
preg_match_all('/[^ ]+/', $text, $matches, PREG_PATTERN_ORDER);
$words = $matches[0];
// Count words
$numWords = count($words);
// Find the length of each word
$wordLengths = array_map('strlen', $words);
//And Finally, calculate the total length of all words
$wordsLength = array_reduce($wordLengths, function($result, $length) {
return $result + $length;
}, 0);
return new JustifierLine($words, $numWords, $wordLengths, $wordsLength);
}
private function __construct($words, $numWords, $wordLengths, $wordsLength) {
$this->words = $words;
$this->numWords = $numWords;
$this->wordLengths = $wordLengths;
$this->wordsLength = $wordsLength;
}
public function extractWords() { return $this->words; }
public function countWords() { return $this->numWords; }
public function findWordLengths() { return $this->wordLengths; }
public function calculateWordsLength() { return $this->wordsLength; }
public function breakAtColumn($column) {
// Avoid extraneous processing if we can determine no breaking can be done
if($column >= ($this->wordsLength + $this->numWords - 1)) {
return null;
}
$width = 0;
$wordsLength = 0;
for($i = 0; $i < $this->numWords; $i++) {
// Add width of next word
$width += $this->wordLengths[$i];
// If the line is overflowing past required $width
if($width > $column) {
// Remove overflow at end & create a new object with the overflow
$words = array_splice($this->words, $i);
$numWords = $this->numWords - $i;
$this->numWords = $i;
$wordLengths = array_splice($this->wordLengths, $i);
$tempWordsLength = $wordsLength;
$wordsLength = $this->wordsLength - $wordsLength;
$this->wordsLength = $tempWordsLength;
return new JustifierLine($words, $numWords, $wordLengths, $wordsLength);
}
$width++; // Assuming smallest spacing to fit
// We also have to keep track of the total $wordsLength
$wordsLength += $this->wordLengths[$i];
}
return null;
}
}
演示
原始问题（将文本行与宽度对齐 = 48）
您可以传入一个包含多个字符串的数组，也可以只传递一个字符串来传递Justifier 。调用 Justifier::format($desired_length) 将
$jus = new Justifier(array(
'hello world there ok then',
'hello',
'ok then',
'two words',
'three ok words',
'1 2 3 4 5 6 7 8 9'
));
print_r( $jus->format(48) );
输出
Array
(
[0] => hello world there ok then
[1] => hello
[2] => ok then
[3] => two words
[4] => three ok words
[5] => 1 2 3 4 5 6 7 8 9
)
您可能会注意到我省略了OP的一条测试线。这是因为它是 54 个字符，并且会超过传递给Justifier::format() $desired_length。该函数将为宽度不是正数、超过或等于最小宽度的非零数字抛出IllegalArgumentException。最小宽度是通过查找具有单个间距的最长行（传递给构造函数的所有行）来计算的。
使用字符串数组对齐的流体宽度
如果省略宽度，Justifier将使用单行距时（传递给构造函数的最长行）的宽度。这与在上一个演示中查找最小宽度的计算相同。（代码板演示）
$jus = new Justifier(array(
'hello world there ok then',
'hello',
'ok then',
'this string is almost certainly longer than 48 I think',
'two words',
'three ok words',
'1 2 3 4 5 6 7 8 9'
));
print_r( $jus->format() );
输出
Array
(
[0] => hello world there ok then
[1] => hello
[2] => ok then
[3] => this string is almost certainly longer than 48 I think
[4] => two words
[5] => three ok words
[6] => 1 2 3 4 5 6 7 8 9
)
对齐单个文本字符串（宽度 = 48）
我还在类中包含一个功能，它允许您将单个未损坏的字符串传递给构造函数。此字符串可以是任意长度。调用Justifier::format($desired_length)时，字符串被分成几行，以便在开始新行之前用尽可能多的文本填充并对齐。该类会抱怨InvalidArgumentException因为您必须提供一个可以中断字符串的宽度。如果有人能想到一个合理的默认值或以编程方式确定字符串默认值的方法，我完全愿意接受建议。（代码板演示）
$jus = new Justifier(
'hello world there ok then hello ok then this string is almost certainly longer than 48 I think two words three ok words 1 2 3 4 5 6 7 8 9'
);
print_r( $jus->format(48) );
输出
Array
(
[0] => hello world there ok then hello ok then this
[1] => string is almost certainly longer than 48 I
[2] => think two words three ok words 1 2 3 4 5 6 7 8 9
)
这是我的解决方案。 对于它的价值，我花了大约 20 分钟来为它进行对齐函数和验收测试;其中 5 分钟调试对齐函数。 此外，我使用了notpad++而不是更强大的IDE，试图在某种程度上模拟面试环境。
我认为这对于白板面试问题来说可能太大了，除非面试官让你用伪代码编写，并且对你的思维过程更感兴趣，而不是你放在黑板上的东西。
<?php
function justify($str_in, $desired_length) {
$words = preg_split("/ +/",$str_in);
// handle special cases
if(count($words)==0) { return str_repeat(" ",$desired_length); }
// turn single word case into a normal case
if(count($words)==1) { $words = array("",$words[0],""); }
$numwords = count($words);
$wordlength = strlen(join("",$words));
// handles cases where words are longer than the desired_length
if($wordlength>($desired_length-$numwords)) {
return substr(join(" ",$words),0,$desired_length);
}
$minspace = floor(($desired_length-$wordlength)/($numwords-1));
$extraspace = $desired_length - $wordlength - ($minspace * ($numwords-1));
$result = $words[0];
for($i=1;$i<$numwords;$i++) {
if($extraspace>0) {
$result.=" ";
$extraspace--;
}
$result.=str_repeat(" ",$minspace);
$result.=$words[$i];
}
return $result;
}
function acceptance_justify($orig_str, $just_str, $expected_length) {
// should be the correct length
if(strlen($just_str)!=$expected_length) { return false; }
// should contain most of the words in the original string, in the right order
if(preg_replace("/ +/","",substr($orig_str,0,$expected_length)) != preg_replace("/ +/","",substr($just_str,0,$expected_length))) { return false; }
//spacing should be uniform (+/- 1 space)
if(!preg_match("/( +)/",$just_str,$spaces)) { return false; }
$space_length=strlen($spaces[0]);
$smin=$space_length;
$smax=$space_length;
for($i=1;$i<count(@spaces);$i++) {
$smin=min($smin,strlen($spaces));
$smax=max($smax,strlen($spaces));
}
if(($smax-$smin)>1) { return false; }
return true;
}
function run_test($str,$len) {
print "<pre>";
print "$str ==> 'n";
$result = justify($str,$len);
print preg_replace("/ /",".",$result) . "'n";
print acceptance_justify($str,$result,$len)?"passed":"FAILED";
print "'n'n</pre>";
}
run_test("hello world there ok then",48);
run_test("hello",48);
run_test("this string is almost certainly longer than 48 I think",48);
run_test("two words",48);
run_test("three ok words",48);
run_test("1 2 3 4 5 6 7 8 9",48);
这是最后的一点不同的实现。
<?php
function justify($str, $to_len) {
$str = trim($str);
$strlen = strlen($str);
if($str == '') return '';
if($strlen >= $to_len) {
return substr($str, 0, $to_len);
}
$words = explode(' ', $str);
$word_count = count($words);
$space_count = $word_count - 1;
if($word_count == 1) {
return str_pad($str, $to_len, ' ', STR_PAD_BOTH);
}
$space = $to_len - $strlen + $space_count;
$per_space = floor($space/$space_count);
$spaces = str_pad('', $per_space, ' ');
$curr_word = implode($words, $spaces);
while(strlen($curr_word) < $to_len){
$curr_word = substr($curr_word,0,preg_match("[! ][".$spaces."][! ]",$curr_word))." ".preg_match("[! ][".$spaces."][! ]",$curr_word));
}
return $curr_word;
?>
我不确定regexp，我的意思是$spaces而不是下一个空间。