格雷码生成 - n 位格雷码
Gray Code Generation - n-bit Gray Codes
这个问题是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 位 os 上时,这将工作到 63。如果在64位os上是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
这应该适合你:
<?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
似乎没问题。
另一个答案,它类似于@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";
}
?>
这个问题是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 位 os 上时,这将工作到 63。如果在64位os上是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
这应该适合你:
<?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
似乎没问题。
另一个答案,它类似于@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";
}
?>