arrays - 根据对该数组有效的一组元素将列表拆分为数组的算法

Question

这是一道“最优算法”题。

我需要将混合值“a”、“b”和“c”的数组 A 分解为一个新的二维数组 B，其中包含相同的值，但根据以下规则在整个二维中拆分。

B记录开始于:

a: [a] || [a, a] || [a, b] || [a, b, b]
b: [b] || [b, b] || [b, a] || [b, b, a] || [b, b, b] || [b, b, b, b]
c: [c]

• 维持秩序

• A中的每个值只能在B中使用一次

例如我有一个数组 A:

['a', 'c', 'b', 'b', 'a', 'a', 'a', 'c', 'b', 'b', 'b', 'b']

我需要将它拆分成二维数组 B:

[
 ['a'],
 ['c'],
 ['b', 'b', 'a'],
 ['a', 'a'],
 ['c'],
 ['b', 'b', 'b', 'b']
]

我写的代码是很多嵌套的 if/else 语句。 'a' 的代码只包含在 while 循环中:

while(i<arrA.length) {
 if(arrA[i] == a) {
  if(arrA[i+1] == a) {
   arrB[] = [arrA[i], arrA[i+1]]; //creates arrB[n]['a', 'a']
   i = i+2;
   continue;
  } elseif (arrA[i+1] == b) {
   if(arrA[i+2] == b) {
    arrB[] = [arrA[i], arrA[i+1], arrA[i+2]]; //creates arrB[n]['a', 'b', 'b']
    i = i+3;
    continue;
   } elseif (arrA[i+2] != b) {
    arrB[] = [arrA[i], arrA[i+1]]; //creates arrB[n]['a', 'b']
    i = i+2;
    continue;
   }
  } elseif (arrA[i+1] == c) {
   arrB[] = [arrA[i]]; //creates arrB[n]['a']
   i++;
   continue;
  }
 } elseif (...)
 i++;
}

“c”的代码较短，“b”的代码较长。在这种情况下有没有更简洁的算法？如果这很重要，我正在用 PHP 编写。

Answer 1

有两个技巧:

• 任何一系列检查相等性的 if 语句都可以简化为对数组的检查。
• 您可以循环并记住每个循环中的“上一个”事物，并据此采取行动。

即:

• 您可以创建一个包含所有可能的有效组合的数组
• 然后您可以遍历序列数组，并在每一步检查您的组合是否与您的可能性列表中的组合相匹配。
• 如果您发现不匹配的东西，您会假设您之前的外观匹配并将其放入匹配组合列表中。

它可能不是绝对最优的 - 但它肯定比您目前拥有的更具可扩展性。

<?php

    $aPossibleCombinations = array( 'a', 'aa', 'ab', 'abb', 'b', 'bb', 'ba', 'bba', 'bbb', 'bbbb', 'c' );

    $aThingsToMatch = array( 'a', 'c', 'b', 'b', 'a', 'a', 'a', 'c', 'b', 'b', 'b', 'b' );

    $aMatchedThings = array();

    $sPreviousThing = '';
    $sCurrentThing  = '';

    foreach( $aThingsToMatch as $sSingleThing ) {

        $sCurrentThing .= $sSingleThing;

        if ( !in_array( $sCurrentThing, $aPossibleCombinations ) ) {
            $aMatchedThings[] = $sPreviousThing;
            $sCurrentThing = $sSingleThing;
        }

        $sPreviousThing = $sCurrentThing;
    }

    if ( in_array(  $sCurrentThing, $aPossibleCombinations ) ) {
        $aMatchedThings[] = $sPreviousThing;
        $sCurrentThing = '';
    }

    echo( "Matched Things: \r\n" );
    var_dump( $aMatchedThings );

    echo( "Remaining Things: \r\n" );
    var_dump( $sCurrentThing );

?>

我应该说我在那里留下了一个错误供您查找。它适用于当前的 aThingsToMatch 集，但它可能会中断。我将把它作为练习留给读者......