对齐字符串算法 [已关闭]守则短(348 字符)算法/代码说明测试结果看到它运行!

2022-08-30 10:46:43

刚刚进行了一次面试,我被要求实现一个带有以下签名的函数:

function justify($str_in, $desired_length)

它需要模仿HTML的文本对齐方式:justify会做什么,这里有一些例子(desired_length = 48)

    hello world there ok then                              = hello......world......there.......ok.......then
    hello                                                  = .....................hello.....................
    ok then                                                = ok.........................................then
    this string is almost certainly longer than 48 I think = this.string.is.almost.certainly.longer.than.48.
    two words                                              = two.......................................words
    three ok words                                         = three.................ok..................words
    1 2 3 4 5 6 7 8 9                                      = 1....2....3.....4.....5.....6.....7.....8.....9

(我用句点替换了空格来说明)

单词之间的空格长度永远不会相差超过一个。

我已经写了一个PHP解决方案,但我更感兴趣的是人们可以想出什么算法来解决问题。这是我在求职面试中的第一个白板问题,我担心多种因素的结合使我花费的时间远远超过我应该花费的时间。


答案 1

这是我想到的。我添加了可选参数,以便您可以看到它输出的内容 - 当然,您可以将其拉入函数中,以便原型符合要求。$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)

还有一个演示!

编辑:清理了代码,它仍然:)工作


答案 2

使不使用任何循环/递归或正则表达式作为回调的个人挑战。我用一个单曲和一个单曲来实现这一点。大获成功!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);}

算法/代码说明

  1. 处理两个异常(字符串长度超过最大长度或只有一个单词)。
  2. 找到每个单词之间所需的平均间距 ()。$space_string_avg_length
  3. 创建一个长填充字符串和短填充字符串,分别基于 和 的单词之间使用。ceil()floor()$space_string_avg_length
  4. 找出我们需要多少个长填充字符串。().$limit+1
  5. 根据我们需要的长填充字符串数拆分文本。
  6. 将数组最后一部分(由拆分创建)中的空格替换为短填充字符串。
  7. 将拆分的文本与长填充字符串连接在一起。

测试

$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

看到它运行!


推荐