2

问题是由hackerrank提出的，我得到了解决方案，但在最后的测试用例中解决方案存在问题。

问题如下。

1 <= $n <= 65

以下是 1 位序列 (n = 1)

0 1

输出

1

以下是 2 位序列 (n = 2)

00 01 11 10

输出

11 10

以下是 3 位序列 (n = 3)

000 001 011 010 110 111 101 100

输出

111 101 100

以下是 4 位序列 (n = 4)

 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 
  1110 1010 1011 1001 1000

输出

1010 1011 1001 1000

解决方案示例

以下是从 2 位格雷码列表生成 3 位格雷码列表的步骤。

  • L1 = {00, 01, 11, 10}（2 位格雷码列表）
  • L2 = {10, 11, 01, 00}（L1 的倒数）
  • L1 的所有条目都以 '0' 为前缀，L1 变为 {000, 001, 011, 010}
  • L2 的所有条目都以 '1' 为前缀，L2 变为 {110, 111, 101, 100}
  • 连接 L1 和 L2，我们得到 {000, 001, 011, 010, 110, 111, 101, 100}

下面给出第一个解决方案。（基于上面的解决方案示例）

但是下面给出的解决方案在 22,23 个数字之后将不起作用。发生内存分配错误。

<?php

$input = 2;

$list_array = ["0","1"];
$reverse_array = array_reverse($list_array);

for($i = 1; $i < $input; $i++ )
{
    for($j = 0; $j < sizeof($list_array); $j++)
    {
        $list_array[$j] = "0".$list_array[$j];
    }

    for($k = 0; $k < sizeof($reverse_array); $k++)
    {
        $reverse_array[$k] = "1".$reverse_array[$k];
    }

    $list_array = array_merge($list_array,$reverse_array);
    $reverse_array = array_reverse($list_array);
}

for($l = sizeof($list_array) - $input; $l < sizeof($list_array); $l++)  
{
    print_r($list_array[$l]);
    echo "<br />";
}

?>

第二种解决方案如下

此解决方案将一直有效到 63。在 63 之后，这将显示超时错误。

当 64 位 php 在 64 位操作系统上运行时，这将一直工作到 63 岁。如果是在 64 位操作系统上运行的 32 位 php，则在 31 之后将无法工作。

<?php

    $n = 59;

    $intial = pow(2, $n) - $n;

    $length = pow(2, $n) - 1;

    for($i= $intial; $i <= $length; $i++)
    {
        $decimal = ($i >> 1) ^ $i;
        print_r(decbin($decimal));
        echo "<br />";
    }
?>

请帮助我找到这个解决方案。

问题：如何解决上述问题，包括 $n = 64 和 $n = 65

参考：https ://www.geeksforgeeks.org/given-a-number-n-generate-bit-patterns-from-0-to-2n-1-so-that-successive-patterns-differ-by-one-少量/

4

2 回答 2

3

这应该适合你：

<?php

print_r( getResult( 4 ) );

function getResult ( $n ) {
    $result = [];
    for ( $i = 0; $i < $n; $i++ ) {
        $result[] = arr_xor(
          str_split( str_pad( str_pad( strtr( decbin($n - $i - 1), '01', '10' ), (int)ceil(log($n - $i - 1, 2)), '0', STR_PAD_LEFT ), $n, '1', STR_PAD_LEFT ) ),
          str_split( '0' . str_pad( substr( str_pad( strtr( decbin($n - $i - 1), '01', '10' ), (int)ceil(log($n - $i - 1, 2)), '0', STR_PAD_LEFT ), -1-(int)ceil(log($n - $i - 1, 2)), -1), $n - 1, '1', STR_PAD_LEFT ) )
        );
    }
    return $result;
}

function arr_xor( $a, $b ) {
    $result = [];
    for ( $i = 0; $i < count( $a ); $i++ )
        $result[] = (int)$a[$i] ^ (int)$b[$i];
    return implode( '', $result );
}

它仅使用您的第二个解决方案 ( ($i >> 1) ^ $i) 中的公式，但由于您不能将其用于大于 的整数PHP_INT_MAX，因此它使用一个数组，每个元素代表一位。这不是最有效的解决方案，但可以轻松超过 65。$n = 1000似乎没有问题。

于 2018-04-06T06:15:09.130 回答
0

另一个答案，它类似于@paulpro，这与我在第二个解决方案中应用的想法相同。($i >> 1) ^ $i 

<?php

$n = 65;

for ( $i = 0; $i < $n; $i++ ) 
{
    $decimal = decbin($n - $i - 1);

    $replace = strtr( $decimal, '01', '10' );

    $cast = (int)ceil(log($n - $i - 1, 2));

    $padding = str_pad( $replace , $cast , '0', STR_PAD_LEFT );

    $a_string = str_pad( $padding, $n, '1', STR_PAD_LEFT );

    //shifting the bit to right
    $substring = substr( $a_string , 0 , -1);
    $b_string = str_pad( $substring , $n, '0', STR_PAD_LEFT );

    $a = str_split( $a_string );
    $b = str_split( $b_string );

    for ( $j = 0; $j < count( $a ); $j++ )
    {
        print_r((int)$a[$j] ^ (int)$b[$j]);
    }

    echo "\n";
}

?>
于 2018-04-07T17:04:50.550 回答