0 と 1 を持つ NxN 行列が与えられます。a を含むすべての行をすべての に設定し、a0を含むすべての列をすべての0に設定します。00
例えば
1 0 1 1 0
0 1 1 1 0
1 1 1 1 1
1 0 1 1 1
1 1 1 1 1
結果は
0 0 0 0 0
0 0 0 0 0
0 0 1 1 0
0 0 0 0 0
0 0 1 1 0
Microsoft のエンジニアが、余分なメモリを必要とせず、2 つのブール変数と 1 つのパスだけを使用するソリューションがあると教えてくれたので、その答えを探しています。
ところで、それがビットマトリックスであると想像してください。したがって、マトリックスに含めることができるのは1と0だけです。
ここでは午前 3 時なので疲れていますが、行列の各数値に対して正確に 2 回のパスを配置して最初の試行を行っているため、O(NxN) では行列のサイズが線形になります。
最初の列と最初の行をマーカーとして使用して、1 のみの行/列がどこにあるかを確認します。次に、最初の行/列もすべて1である場合に覚えておくべき2つの変数lとcがあります。したがって、最初のパスはマーカーを設定し、残りを 0 にリセットします。
2 番目のパスは、行と列が 1 とマークされている場所に 1 を設定し、l と c に応じて最初の行/列をリセットします。
最初の正方形は最後の正方形に依存するため、1回のパスで実行できるかどうかは強く疑問です。たぶん、2回目のパスをより効率的にすることができます...
import pprint
m = [[1, 0, 1, 1, 0],
[0, 1, 1, 1, 0],
[1, 1, 1, 1, 1],
[1, 0, 1, 1, 1],
[1, 1, 1, 1, 1]]
N = len(m)
### pass 1
# 1 rst line/column
c = 1
for i in range(N):
c &= m[i][0]
l = 1
for i in range(1,N):
l &= m[0][i]
# other line/cols
# use line1, col1 to keep only those with 1
for i in range(1,N):
for j in range(1,N):
if m[i][j] == 0:
m[0][j] = 0
m[i][0] = 0
else:
m[i][j] = 0
### pass 2
# if line1 and col1 are ones: it is 1
for i in range(1,N):
for j in range(1,N):
if m[i][0] & m[0][j]:
m[i][j] = 1
# 1rst row and col: reset if 0
if l == 0:
for i in range(N):
m [i][0] = 0
if c == 0:
for j in range(1,N):
m [0][j] = 0
pprint.pprint(m)
1 つのビットが任意の順序でその前後のビットに影響を与えるため、これは 1 回のパスでは実行できません。IOW 配列をどのような順序でトラバースしても、後で 0 に遭遇する可能性があります。これは、前に戻って前の 1 を 0 に変更する必要があることを意味します。
アップデート
N を特定の固定値 (たとえば 8) に制限することで、これを 1 回のパスで解決できると考える人がいるようです。それは、a) ポイントが抜けていて、b) 元の質問ではありません。私はソートに関する質問を投稿せず、「ソートしたいのは8つだけだと仮定して...」という答えを期待しません。
とはいえ、N が実際には 8 に制限されていることがわかっている場合、これは合理的なアプローチです。上記の私の答えは、そのような制限がない元の質問に答えます。
したがって、私の考えは、最後の行/列の値をフラグとして使用して、対応する列/行のすべての値が 1 であるかどうかを示すことです。
最後の行/列を除くマトリックス全体をジグザグ スキャンします。各要素で、現在の要素の値とそれ自体の論理 AND として、最後の行/列に値を設定します。つまり、0 をヒットすると、最終的な行/列は 0 に設定されます。1 を指定すると、最終的な行/列の値は、既に 1 である場合にのみ 1 になります。いずれにせよ、現在の要素を 0 に設定します。
終了したら、対応する列/行が 1 で埋められていれば、最終的な行/列には 1 が含まれているはずです。
最後の行と列を線形スキャンし、1 を探します。最後の行と列が両方とも 1 である行列の本体の対応する要素に 1 を設定します。
off-by-one エラーなどを避けるためにコーディングするのは難しいですが、1 回のパスで動作するはずです。
ここに解決策があります。これは単一のパスで実行され、余分なメモリを使用せずにすべての処理を「その場で」実行します (スタックを大きくするために保存します)。
再帰を使用して、もちろん他の行と列の行列を破壊するゼロの書き込みを遅らせます。
#include <iostream>
/**
* The idea with my algorithm is to delay the writing of zeros
* till all rows and cols can be processed. I do this using
* recursion:
* 1) Enter Recursive Function:
* 2) Check the row and col of this "corner" for zeros and store the results in bools
* 3) Send recursive function to the next corner
* 4) When the recursive function returns, use the data we stored in step 2
* to zero the the row and col conditionally
*
* The corners I talk about are just how I ensure I hit all the row's a cols,
* I progress through the matrix from (0,0) to (1,1) to (2,2) and on to (n,n).
*
* For simplicities sake, I use ints instead of individual bits. But I never store
* anything but 0 or 1 so it's still fair ;)
*/
// ================================
// Using globals just to keep function
// call syntax as straight forward as possible
int n = 5;
int m[5][5] = {
{ 1, 0, 1, 1, 0 },
{ 0, 1, 1, 1, 0 },
{ 1, 1, 1, 1, 1 },
{ 1, 0, 1, 1, 1 },
{ 1, 1, 1, 1, 1 }
};
// ================================
// Just declaring the function prototypes
void processMatrix();
void processCorner( int cornerIndex );
bool checkRow( int rowIndex );
bool checkCol( int colIndex );
void zeroRow( int rowIndex );
void zeroCol( int colIndex );
void printMatrix();
// This function primes the pump
void processMatrix() {
processCorner( 0 );
}
// Step 1) This is the heart of my recursive algorithm
void processCorner( int cornerIndex ) {
// Step 2) Do the logic processing here and store the results
bool rowZero = checkRow( cornerIndex );
bool colZero = checkCol( cornerIndex );
// Step 3) Now progress through the matrix
int nextCorner = cornerIndex + 1;
if( nextCorner < n )
processCorner( nextCorner );
// Step 4) Finially apply the changes determined earlier
if( colZero )
zeroCol( cornerIndex );
if( rowZero )
zeroRow( cornerIndex );
}
// This function returns whether or not the row contains a zero
bool checkRow( int rowIndex ) {
bool zero = false;
for( int i=0; i<n && !zero; ++i ) {
if( m[ rowIndex ][ i ] == 0 )
zero = true;
}
return zero;
}
// This is just a helper function for zeroing a row
void zeroRow( int rowIndex ) {
for( int i=0; i<n; ++i ) {
m[ rowIndex ][ i ] = 0;
}
}
// This function returns whether or not the col contains a zero
bool checkCol( int colIndex ) {
bool zero = false;
for( int i=0; i<n && !zero; ++i ) {
if( m[ i ][ colIndex ] == 0 )
zero = true;
}
return zero;
}
// This is just a helper function for zeroing a col
void zeroCol( int colIndex ) {
for( int i=0; i<n; ++i ) {
m[ i ][ colIndex ] = 0;
}
}
// Just a helper function for printing our matrix to std::out
void printMatrix() {
std::cout << std::endl;
for( int y=0; y<n; ++y ) {
for( int x=0; x<n; ++x ) {
std::cout << m[y][x] << " ";
}
std::cout << std::endl;
}
std::cout << std::endl;
}
// Execute!
int main() {
printMatrix();
processMatrix();
printMatrix();
}
私はそれが実行可能だとは思わない。最初の正方形にいて、その値が 1 の場合、同じ行と列にある他の正方形の値を知る方法はありません。したがって、それらをチェックして、ゼロがある場合は、最初の正方形に戻り、その値をゼロに変更する必要があります。2 つのパスで行うことをお勧めします。最初のパスでは、どの行と列をゼロにする必要があるかに関する情報を収集します (情報は配列に格納されるため、余分なメモリを使用します)。2 回目のパスで値が変更されます。それがあなたが探している解決策ではないことはわかっていますが、実用的なものだと思います。あなたによって与えられた制約は、問題を解決不可能にします。
2つの整数変数と2つのパス（最大32行と列...）でそれを行うことができます
bool matrix[5][5] =
{
{1, 0, 1, 1, 0},
{0, 1, 1, 1, 0},
{1, 1, 1, 1, 1},
{1, 0, 1, 1, 1},
{1, 1, 1, 1, 1}
};
int CompleteRows = ~0;
int CompleteCols = ~0;
// Find the first 0
for (int row = 0; row < 5; ++row)
{
for (int col = 0; col < 5; ++col)
{
CompleteRows &= ~(!matrix[row][col] << row);
CompleteCols &= ~(!matrix[row][col] << col);
}
}
for (int row = 0; row < 5; ++row)
for (int col = 0; col < 5; ++col)
matrix[row][col] = (CompleteRows & (1 << row)) && (CompleteCols & (1 << col));
AND で結合されたすべての行が何であるかを追跡するために、1 つの変数を保持します。
行が -1 (すべて 1) の場合、次の行をその変数への参照にします。
行がそれ以外の場合、それは 0 です。1 回のパスですべてを実行できます。疑似コード:
foreach (my $row) rows {
$andproduct = $andproduct & $row;
if($row != -1) {
zero out the row
} else {
replace row with a reference to andproduct
}
}
1回のパスでそれを行う必要があります-ただし、ここでは、NがCPUが単一の行で算術演算を行うのに十分小さいという前提があります。そうでない場合は、各行をループして、すべてかどうかを判断する必要があります1かどうか、私は信じています。しかし、あなたがアルゴについて質問しており、私のハードウェアを制約していないことを考えると、「N ビット演算をサポートする CPU を構築する...」から答えを始めるだけです。
ここに、C でそれを行う方法の 1 つの例を示します。注: values と arr を一緒にすると配列を表し、p と numproduct はイテレータであり、AND 積の変数は問題を実装するために使用します。(自分の作業を検証するためにポインター演算で arr をループすることもできましたが、一度で十分でした!)
int main() {
int values[] = { -10, 14, -1, -9, -1 }; /* From the problem spec, converted to decimal for my sanity */
int *arr[5] = { values, values+1, values+2, values+3, values+4 };
int **p;
int numproduct = 127;
for(p = arr; p < arr+5; ++p) {
numproduct = numproduct & **p;
if(**p != -1) {
**p = 0;
} else {
*p = &numproduct;
}
}
/* Print our array, this loop is just for show */
int i;
for(i = 0; i < 5; ++i) {
printf("%x\n",*arr[i]);
}
return 0;
}
これにより、指定された入力の結果である 0、0、6、0、6 が生成されます。
または、PHP で、私の C でのスタック ゲームが不正行為であると人々が考えている場合 (そうではないことをお勧めします。行列を好きなように保存できるはずだからです):
<?php
$values = array(-10, 14, -1, -9, -1);
$numproduct = 127;
for($i = 0; $i < 5; ++$i) {
$numproduct = $numproduct & $values[$i];
if($values[$i] != -1) {
$values[$i] = 0;
} else {
$values[$i] = &$numproduct;
}
}
print_r($values);
何か不足していますか？
さて、これはその解決策です
#include <stdio.h> #define BIT30 (1<<24) #define COLMASK 0x108421L #define ROWMASK 0x1fL
unsigned long long STARTGRID =
((0x10 | 0x0 | 0x4 | 0x2 | 0x0) << 20) |
((0x00 | 0x8 | 0x4 | 0x2 | 0x0) << 15) |
((0x10 | 0x8 | 0x4 | 0x2 | 0x1) << 10) |
((0x10 | 0x0 | 0x4 | 0x2 | 0x1) << 5) |
((0x10 | 0x8 | 0x4 | 0x2 | 0x1) << 0);
void dumpGrid (char* comment, unsigned long long theGrid) {
char buffer[1000];
buffer[0]='\0';
printf ("\n\n%s\n",comment);
for (int j=1;j<31; j++) {
if (j%5!=1)
printf( "%s%s", ((theGrid & BIT30)==BIT30)? "1" : "0",(((j%5)==0)?"\n" : ",") );
theGrid = theGrid << 1;
}
}
int main (int argc, const char * argv[]) {
unsigned long long rowgrid = STARTGRID;
unsigned long long colGrid = rowgrid;
unsigned long long rowmask = ROWMASK;
unsigned long long colmask = COLMASK;
dumpGrid("Initial Grid", rowgrid);
for (int i=0; i<5; i++) {
if ((rowgrid & rowmask)== rowmask) rowgrid |= rowmask;
else rowgrid &= ~rowmask;
if ((colGrid & colmask) == colmask) colmask |= colmask;
else colGrid &= ~colmask;
rowmask <<= 5;
colmask <<= 1;
}
colGrid &= rowgrid;
dumpGrid("RESULT Grid", colGrid);
return 0;
}
実際。アルゴリズムを実行して結果を出力したい (つまり、結果を復元したくない) 場合は、1 回のパスで簡単に実行できます。問題は、アルゴリズムの実行中に配列を変更しようとすると発生します。
これが私の解決策です。ギブイン（i、j）の要素の行/列の値をANDして出力するだけです。
#include <iostream>
#include "stdlib.h"
void process();
int dim = 5;
bool m[5][5]{{1,0,1,1,1},{0,1,1,0,1},{1,1,1,1,1},{1,1,1,1,1},{0,0,1,1,1}};
int main() {
process();
return 0;
}
void process() {
for(int j = 0; j < dim; j++) {
for(int i = 0; i < dim; i++) {
std::cout << (
(m[0][j] & m[1][j] & m[2][j] & m[3][j] & m[4][j]) &
(m[i][0] & m[i][1] & m[i][2] & m[i][3] & m[i][4])
);
}
std::cout << std::endl;
}
}
この問題を C# で解決しようとしました。
実際の行列とその次元を表す n とは別に、2 つのループ変数 (i と j) を使用しました。
私が試したロジックは次のとおりです。
コード：
void Evaluate(bool [,] matrix, int n)
{
bool tempvar1, tempvar2;
for (var i = 0; i < n; i++)
{
tempvar1 = matrix[i, i];
tempvar2 = matrix[n - i - 1, n - i - 1];
var j = 0;
for (j = 0; j < n; j++)
{
if ((i < n/2) || (((n % 2) == 1) && (i == n/2) && (j <= i)))
{
// store the row and col & results in corner cells of concentric squares
tempvar1 &= matrix[j, i];
matrix[i, i] &= matrix[i, j];
tempvar2 &= matrix[n - j - 1, n - i - 1];
matrix[n - i - 1, n - i - 1] &= matrix[n - i - 1, n - j - 1];
}
else
{
// skip corner cells of concentric squares
if ((j == i) || (j == n - i - 1)) continue;
// calculate the & values for rest of them
matrix[i, j] = matrix[i, i] & matrix[n - j - 1, j];
matrix[n - i - 1, j] = matrix[n - i - 1, n - i - 1] & matrix[n - j - 1, j];
if ((i == n/2) && ((n % 2) == 1))
{
// if n is odd
matrix[i, n - j - 1] = matrix[i, i] & matrix[j, n - j - 1];
}
}
}
if ((i < n/2) || (((n % 2) == 1) && (i <= n/2)))
{
// transfer the values from temp variables to appropriate corner cells of its corresponding square
matrix[n - i - 1, i] = tempvar1;
matrix[i, n - i - 1] = tempvar2;
}
else if (i == n - 1)
{
// update the values of corner cells of each concentric square
for (j = n/2; j < n; j++)
{
tempvar1 = matrix[j, j];
tempvar2 = matrix[n - j - 1, n - j - 1];
matrix[j, j] &= matrix[n - j - 1, j];
matrix[n - j - 1, j] &= tempvar2;
matrix[n - j - 1, n - j - 1] &= matrix[j, n - j - 1];
matrix[j, n - j - 1] &= tempvar1;
}
}
}
}
ナイスチャレンジ。このソリューションでは、スタックで作成された 2 つのブール値のみを使用しますが、関数が再帰的であるため、スタックでブール値が数回作成されます。
typedef unsigned short WORD;
typedef unsigned char BOOL;
#define true 1
#define false 0
BYTE buffer[5][5] = {
1, 0, 1, 1, 0,
0, 1, 1, 1, 0,
1, 1, 1, 1, 1,
1, 0, 1, 1, 1,
1, 1, 1, 1, 1
};
int scan_to_end(BOOL *h,BOOL *w,WORD N,WORD pos_N)
{
WORD i;
for(i=0;i<N;i++)
{
if(!buffer[i][pos_N])
*h=false;
if(!buffer[pos_N][i])
*w=false;
}
return 0;
}
int set_line(BOOL h,BOOL w,WORD N,WORD pos_N)
{
WORD i;
if(!h)
for(i=0;i<N;i++)
buffer[i][pos_N] = false;
if(!w)
for(i=0;i<N;i++)
buffer[pos_N][i] = false;
return 0;
}
int scan(int N,int pos_N)
{
BOOL h = true;
BOOL w = true;
if(pos_N == N)
return 0;
// Do single scan
scan_to_end(&h,&w,N,pos_N);
// Scan all recursive before changeing data
scan(N,pos_N+1);
// Set the result of the scan
set_line(h,w,N,pos_N);
return 0;
}
int main(void)
{
printf("Old matrix\n");
printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[0][0],(WORD)buffer[0][1],(WORD)buffer[0][2],(WORD)buffer[0][3],(WORD)buffer[0][4]);
printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[1][0],(WORD)buffer[1][1],(WORD)buffer[1][2],(WORD)buffer[1][3],(WORD)buffer[1][4]);
printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[2][0],(WORD)buffer[2][1],(WORD)buffer[2][2],(WORD)buffer[2][3],(WORD)buffer[2][4]);
printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[3][0],(WORD)buffer[3][1],(WORD)buffer[3][2],(WORD)buffer[3][3],(WORD)buffer[3][4]);
printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[4][0],(WORD)buffer[4][1],(WORD)buffer[4][2],(WORD)buffer[4][3],(WORD)buffer[4][4]);
scan(5,0);
printf("New matrix\n");
printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[0][0],(WORD)buffer[0][1],(WORD)buffer[0][2],(WORD)buffer[0][3],(WORD)buffer[0][4]);
printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[1][0],(WORD)buffer[1][1],(WORD)buffer[1][2],(WORD)buffer[1][3],(WORD)buffer[1][4]);
printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[2][0],(WORD)buffer[2][1],(WORD)buffer[2][2],(WORD)buffer[2][3],(WORD)buffer[2][4]);
printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[3][0],(WORD)buffer[3][1],(WORD)buffer[3][2],(WORD)buffer[3][3],(WORD)buffer[3][4]);
printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[4][0],(WORD)buffer[4][1],(WORD)buffer[4][2],(WORD)buffer[4][3],(WORD)buffer[4][4]);
system( "pause" );
return 0;
}
これは次のようなパターンでスキャンします。
s,s,s,s,s
s,0,0,0,0
s,0,0,0,0
s,0,0,0,0
s,0,0,0,0
0,s,0,0,0
s,s,s,s,s
0,s,0,0,0
0,s,0,0,0
0,s,0,0,0
等々
そして、各スキャン関数の戻り時にこのパターンの値を変更します。（一気飲み）：
0,0,0,0,c
0,0,0,0,c
0,0,0,0,c
0,0,0,0,c
c,c,c,c,c
0,0,0,c,0
0,0,0,c,0
0,0,0,c,0
c,c,c,c,c
0,0,0,c,0
等々
2 つのパスを必要とする別の解決策は、水平方向と垂直方向に AND を累積することです。
1 0 1 1 0 | 0
0 1 1 1 0 | 0
1 1 1 1 1 | 1
1 0 1 1 1 | 0
1 1 1 1 1 | 1
----------+
0 0 1 1 0
パリティ ビット、ハミング コード、または動的計画法を使用して、おそらくこれら 2 つのブール値を 2 ビットの数値として使用して、このようなアルゴリズムを設計できると考えましたが、まだ成功していません。
問題の説明をエンジニアに再確認して、お知らせください。もし本当に解決策があるのなら、私はその問題を少しずつ削り続けたいと思っています。
制約を考えると不可能ですが、それを行うための最もスペース効率の良い方法は、重なり合う、交互の行/列の方法でマトリックスをトラバースすることです。これにより、レンガをジグザグに配置するのと同様のパターンが作成されます。
-----
|----
||---
|||--
||||-
これを使用すると、示されているように各行/列に移動し、いつでも0に遭遇した場合は、ブール変数を設定し、その行/列を再度ウォークして、エントリを0に設定します。
これは余分なメモリを必要とせず、1つのブール変数のみを使用します。残念ながら、「遠い」エッジがすべて0に設定されている場合、それは最悪のケースであり、配列全体を2回ウォークします。
結果マトリックスを作成し、すべての値を1に設定します。0が検出されたらすぐにデータマトリックスを調べ、結果マトリックスの行の列を0に設定します。
最初のパスの終わりに、結果マトリックスは正解になります。
とてもシンプルに見えます。私が見逃しているトリックはありますか？結果セットの使用は許可されていませんか？
編集：
F＃関数のように見えますが、シングルパスを実行している場合でも、関数が再帰的になる可能性があるため、少し不正行為があります。
関数型プログラミングを知っているかどうかをインタビュアーが理解しようとしているようです。
1つのマトリックススキャン、2つのブール値、再帰なし。
2番目のパスを回避する方法は？2番目のパスは、行または列の最後にゼロが表示されたときに行または列をクリアするために必要です。
ただし、行#iをスキャンすると、行＃i-1の行ステータスがすでにわかっているため、この問題は解決できます。したがって、行#iをスキャンしているときに、必要に応じて行＃i-1を同時にクリアできます。
同じソリューションが列に対しても機能しますが、次の反復でデータが変更されないようにしながら、行と列を同時にスキャンする必要があります。
アルゴリズムの主要部分の実行中に値が変更されるため、最初の行と最初の列のステータスを格納するには2つのブール値が必要です。
ブール値の追加を回避するために、行列の最初の行と列の行と列に「クリア」フラグを格納しています。
public void Run()
{
const int N = 5;
int[,] m = new int[N, N]
{{ 1, 0, 1, 1, 0 },
{ 1, 1, 1, 1, 0 },
{ 1, 1, 1, 1, 1 },
{ 1, 0, 1, 1, 1 },
{ 1, 1, 1, 1, 1 }};
bool keepFirstRow = (m[0, 0] == 1);
bool keepFirstColumn = keepFirstRow;
for (int i = 1; i < N; i++)
{
keepFirstRow = keepFirstRow && (m[0, i] == 1);
keepFirstColumn = keepFirstColumn && (m[i, 0] == 1);
}
Print(m); // show initial setup
m[0, 0] = 1; // to protect first row from clearing by "second pass"
// "second pass" is performed over i-1 row/column,
// so we use one more index just to complete "second pass" over the
// last row/column
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
// "first pass" - searcing for zeroes in row/column #i
// when i = N || j == N it is additional pass for clearing
// the previous row/column
// j >= i because cells with j < i may be already modified
// by "second pass" part
if (i < N && j < N && j >= i)
{
m[i, 0] &= m[i, j];
m[0, j] &= m[i, j];
m[0, i] &= m[j, i];
m[j, 0] &= m[j, i];
}
// "second pass" - clearing the row/column scanned
// in the previous iteration
if (m[i - 1, 0] == 0 && j < N)
{
m[i - 1, j] = 0;
}
if (m[0, i - 1] == 0 && j < N)
{
m[j, i - 1] = 0;
}
}
Print(m);
}
// Clear first row/column if needed
if (!keepFirstRow || !keepFirstColumn)
{
for (int i = 0; i < N; i++)
{
if (!keepFirstRow)
{
m[0, i] = 0;
}
if (!keepFirstColumn)
{
m[i, 0] = 0;
}
}
}
Print(m);
Console.ReadLine();
}
private static void Print(int[,] m)
{
for (int i = 0; i < m.GetLength(0); i++)
{
for (int j = 0; j < m.GetLength(1); j++)
{
Console.Write(" " + m[i, j]);
}
Console.WriteLine();
}
Console.WriteLine();
}
誰もバイナリ形式を使用していませんか？1と0しかないので。バイナリベクトルを使用できます。
def set1(M, N):
'''Set 1/0s on M according to the rules.
M is a list of N integers. Each integer represents a binary array, e.g.,
000100'''
ruler = 2**N-1
for i,v in enumerate(M):
ruler = ruler & M[i]
M[i] = M[i] if M[i]==2**N-1 else 0 # set i-th row to all-0 if not all-1s
for i,v in enumerate(M):
if M[i]: M[i] = ruler
return M
テストは次のとおりです。
M = [ 0b10110,
0b01110,
0b11111,
0b10111,
0b11111 ]
print "Before..."
for i in M: print "{:0=5b}".format(i)
M = set1(M, len(M))
print "After..."
for i in M: print "{:0=5b}".format(i)
そして出力：
Before...
10110
01110
11111
10111
11111
After...
00000
00000
00110
00000
00110
さて、私は 4 つのブール値と 2 つのループ カウンターを使用して、単一パスのインプレース (非再帰) ソリューションを思い付きました。2 つの bool と 2 つの int に減らすことはできませんでしたが、それが可能であったとしても驚かないでしょう。各セルの約3回の読み取りと3回の書き込みを行い、O（N ^ 2）である必要があります。配列サイズで線形。
これを理解するのに数時間かかりました - インタビューのプレッシャーの下でそれを考え出す必要はありません! 私がブーブーを作ったら、疲れすぎてそれを見つけることができません...
うーん...各値に 1 回触れるのではなく、マトリックスを 1 回スイープすることを「シングルパス」と定義しています。:-)
#include <stdio.h>
#include <memory.h>
#define SIZE 5
typedef unsigned char u8;
u8 g_Array[ SIZE ][ SIZE ];
void Dump()
{
for ( int nRow = 0; nRow < SIZE; ++nRow )
{
for ( int nColumn = 0; nColumn < SIZE; ++nColumn )
{
printf( "%d ", g_Array[ nRow ][ nColumn ] );
}
printf( "\n" );
}
}
void Process()
{
u8 fCarriedAlpha = true;
u8 fCarriedBeta = true;
for ( int nStep = 0; nStep < SIZE; ++nStep )
{
u8 fAlpha = (nStep > 0) ? g_Array[ nStep-1 ][ nStep ] : true;
u8 fBeta = (nStep > 0) ? g_Array[ nStep ][ nStep - 1 ] : true;
fAlpha &= g_Array[ nStep ][ nStep ];
fBeta &= g_Array[ nStep ][ nStep ];
g_Array[ nStep-1 ][ nStep ] = fCarriedBeta;
g_Array[ nStep ][ nStep-1 ] = fCarriedAlpha;
for ( int nScan = nStep + 1; nScan < SIZE; ++nScan )
{
fBeta &= g_Array[ nStep ][ nScan ];
if ( nStep > 0 )
{
g_Array[ nStep ][ nScan ] &= g_Array[ nStep-1 ][ nScan ];
g_Array[ nStep-1][ nScan ] = fCarriedBeta;
}
fAlpha &= g_Array[ nScan ][ nStep ];
if ( nStep > 0 )
{
g_Array[ nScan ][ nStep ] &= g_Array[ nScan ][ nStep-1 ];
g_Array[ nScan ][ nStep-1] = fCarriedAlpha;
}
}
g_Array[ nStep ][ nStep ] = fAlpha & fBeta;
for ( int nScan = nStep - 1; nScan >= 0; --nScan )
{
g_Array[ nScan ][ nStep ] &= fAlpha;
g_Array[ nStep ][ nScan ] &= fBeta;
}
fCarriedAlpha = fAlpha;
fCarriedBeta = fBeta;
}
}
int main()
{
memset( g_Array, 1, sizeof(g_Array) );
g_Array[0][1] = 0;
g_Array[0][4] = 0;
g_Array[1][0] = 0;
g_Array[1][4] = 0;
g_Array[3][1] = 0;
printf( "Input:\n" );
Dump();
Process();
printf( "\nOutput:\n" );
Dump();
return 0;
}
テストを含めた私の Ruby 実装を次に示します。これには O(MN) スペースが必要です。リアルタイムの更新が必要な場合 (ゼロを見つける最初のループを待つのではなく、ゼロを見つけたときに結果を表示するなど)、別のクラス変数を作成することができ@outputます。@output@input
require "spec_helper"
class Matrix
def initialize(input)
@input = input
@zeros = []
end
def solve
@input.each_with_index do |row, i|
row.each_with_index do |element, j|
@zeros << [i,j] if element == 0
end
end
@zeros.each do |x,y|
set_h_zero(x)
set_v_zero(y)
end
@input
end
private
def set_h_zero(row)
@input[row].map!{0}
end
def set_v_zero(col)
@input.size.times do |r|
@input[r][col] = 0
end
end
end
describe "Matrix" do
it "Should set the row and column of Zero to Zeros" do
input = [[1, 3, 4, 9, 0],
[0, 3, 5, 0, 8],
[1, 9, 6, 1, 9],
[8, 3, 2, 0, 3]]
expected = [[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 9, 6, 0, 0],
[0, 0, 0, 0, 0]]
matrix = Matrix.new(input)
expect(matrix.solve).to eq(expected)
end
end
以下のコードは、サイズ m,n の行列を作成します。最初に行列の次元を決定します。行列 [m][n] を 0..10 の間の数字でランダムに埋めたかったのです。次に、同じ次元の別の行列を作成し、-1 (最終行列) で埋めます。次に、最初のマトリックスを反復して、0 にヒットするかどうかを確認します。location(x,y) にヒットしたら、最終マトリックスに移動し、行 x を 0 で、列 y を 0 で埋めます。最後に最終行列を読み、値が -1 (元の値) の場合、初期行列の同じ場所にある値を最終行列にコピーします。
public static void main(String[] args) {
int m = 5;
int n = 4;
int[][] matrixInitial = initMatrix(m, n); // 5x4 matrix init randomly
int[][] matrixFinal = matrixNull(matrixInitial, m, n);
for (int i = 0; i < m; i++) {
System.out.println(Arrays.toString(matrixFinal[i]));
}
}
public static int[][] matrixNull(int[][] matrixInitial, int m, int n) {
int[][] matrixFinal = initFinal(m, n); // create a matrix with mxn and init it with all -1
for (int i = 0; i < m; i++) { // iterate in initial matrix
for (int j = 0; j < n; j++) {
if(matrixInitial[i][j] == 0){ // if a value is 0 make rows and columns 0
makeZeroX(matrixFinal, i, j, m, n);
}
}
}
for (int i = 0; i < m; i++) { // if value is -1 (original) copy from initial
for (int j = 0; j < n; j++) {
if(matrixFinal[i][j] == -1) {
matrixFinal[i][j] = matrixInitial[i][j];
}
}
}
return matrixFinal;
}
private static void makeZeroX(int[][] matrixFinal, int x, int y, int m, int n) {
for (int j = 0; j < n; j++) { // make all row 0
matrixFinal[x][j] = 0;
}
for(int i = 0; i < m; i++) { // make all column 0
matrixFinal[i][y] = 0;
}
}
private static int[][] initMatrix(int m, int n) {
int[][] matrix = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
Random rn = new Random();
int random = rn.nextInt(10);
matrix[i][j] = random;
}
}
for (int i = 0; i < m; i++) {
System.out.println(Arrays.toString(matrix[i]));
}
System.out.println("******");
return matrix;
}
private static int[][] initFinal(int m, int n) {
int[][] matrix = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = -1;
}
}
return matrix;
}
// another approach
/**
* @param matrixInitial
* @param m
* @param n
* @return
*/
private static int[][] matrixNullNew(int[][] matrixInitial, int m, int n) {
List<Integer> zeroRowList = new ArrayList<>(); // Store rows with 0
List<Integer> zeroColumnList = new ArrayList<>(); // Store columns with 0
for (int i = 0; i < m; i++) { // read through the matrix when you hit 0 add the column to zeroColumnList and add
// the row to zeroRowList
for (int j = 0; j < n; j++) {
if (matrixInitial[i][j] == 0) {
if (!zeroRowList.contains(i)) {
zeroRowList.add(i);
}
if (!zeroColumnList.contains(j)) {
zeroColumnList.add(j);
}
}
}
}
for (int a = 0; a < m; a++) {
if (zeroRowList.contains(a)) { // if the row has 0
for (int b = 0; b < n; b++) {
matrixInitial[a][b] = 0; // replace all row with zero
}
}
}
for (int b = 0; b < n; b++) {
if (zeroColumnList.contains(b)) { // if the column has 0
for (int a = 0; a < m; a++) {
matrixInitial[a][b] = 0; // replace all column with zero
}
}
}
return matrixInitial;
}
追加のスペース要件なしで次のように機能するようです：
最初に、行の要素に要素がある行の要素を掛けると、目的の値が得られることに注意してください。
追加のスペースを使用しないようにする (新しい行列を作成して埋めるのではなく、代わりに直接行列に変更を適用する) には、行列の左上から開始し、任意の ixi 行列 ((0 で「開始」) の計算を実行します。 ,0)) 任意のインデックス > i を持つ要素を考慮する前。
これが機能することを願っています（まだテストしていません）
私の 1 パスの C# ソリューションを楽しんでいただければ幸いです
O(1) で要素を取得でき、行列の 1 行と 1 列のスペースのみが必要です
bool[][] matrix =
{
new[] { true, false, true, true, false }, // 10110
new[] { false, true, true, true, false }, // 01110
new[] { true, true, true, true, true }, // 11111
new[] { true, false, true, true, true }, // 10111
new[] { true, true, true, true, true } // 11111
};
int n = matrix.Length;
bool[] enabledRows = new bool[n];
bool[] enabledColumns = new bool[n];
for (int i = 0; i < n; i++)
{
enabledRows[i] = true;
enabledColumns[i] = true;
}
for (int rowIndex = 0; rowIndex < n; rowIndex++)
{
for (int columnIndex = 0; columnIndex < n; columnIndex++)
{
bool element = matrix[rowIndex][columnIndex];
enabledRows[rowIndex] &= element;
enabledColumns[columnIndex] &= element;
}
}
for (int rowIndex = 0; rowIndex < n; rowIndex++)
{
for (int columnIndex = 0; columnIndex < n; columnIndex++)
{
bool element = enabledRows[rowIndex] & enabledColumns[columnIndex];
Console.Write(Convert.ToInt32(element));
}
Console.WriteLine();
}
/*
00000
00000
00110
00000
00110
*/
1 パス、2 ブール値。繰り返しの整数インデックスはカウントされないと仮定する必要があります。
これは完全な解決策ではありませんが、この点を通過できません。
0 が元の 0 なのか、0 に変換された 1 なのかだけを判断できれば、-1 を使用する必要はなく、これでうまくいきます。
私の出力は次のようになります。
-1 0 -1 -1 0
0 -1 -1 -1 0
-1 -1 1 1 -1
-1 0 -1 -1 -1
-1 -1 1 1 -1
私のアプローチの独創性は、行または列の検査の前半を使用して 0 が含まれているかどうかを判断し、後半を使用して値を設定することです。これは、x と width-x、次に y と height を見て行われます-y 各反復で。反復の前半の結果に基づいて、行または列に 0 が見つかった場合、反復の後半を使用して 1 を -1 に変更します。
これは、ブール値を 1 つだけ残して 1 を ... にするだけで実行できることに気付きました。
誰かが「ああ、これをやって…」と言ってくれることを期待して投稿しています（そして、投稿しないのにあまりにも多くの時間を費やしました. ）
VB のコードは次のとおりです。
Dim D(,) As Integer = {{1, 0, 1, 1, 1}, {0, 1, 1, 0, 1}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}, {0, 0, 1, 1, 1}}
Dim B1, B2 As Boolean
For y As Integer = 0 To UBound(D)
B1 = True : B2 = True
For x As Integer = 0 To UBound(D)
// Scan row for 0's at x and width - x positions. Halfway through I'll konw if there's a 0 in this row.
//If a 0 is found set my first boolean to false.
If x <= (Math.Ceiling((UBound(D) + 1) / 2) - 1) Then
If D(x, y) = 0 Or D(UBound(D) - x, y) = 0 Then B1 = False
End If
//If the boolean is false then a 0 in this row was found. Spend the last half of this loop
//updating the values. This is where I'm stuck. If I change a 1 to a 0 it will cause the column
//scan to fail. So for now I change to a -1. If there was a way to change to 0 yet later tell if
//the value had changed this would work.
If Not B1 Then
If x >= (Math.Ceiling((UBound(D) + 1) / 2) - 1) Then
If D(x, y) = 1 Then D(x, y) = -1
If D(UBound(D) - x, y) = 1 Then D(UBound(D) - x, y) = -1
End If
End If
//These 2 block do the same as the first 2 blocks but I switch x and y to do the column.
If x <= (Math.Ceiling((UBound(D) + 1) / 2) - 1) Then
If D(y, x) = 0 Or D(y, UBound(D) - x) = 0 Then B2 = False
End If
If Not B2 Then
If x >= (Math.Ceiling((UBound(D) + 1) / 2) - 1) Then
If D(y, x) = 1 Then D(y, x) = -1
If D(y, UBound(D) - x) = 1 Then D(y, UBound(D) - x) = -1
End If
End If
Next
Next
ランダムアクセス順序でマトリックスにアクセスすることを数えない場合、最初にシングルパスを実行する利点がなくなります（キャッシュコヒーレンス/メモリ帯域幅）。
[編集: シンプルですが、間違ったソリューションは削除されました]
行/列情報を蓄積するためのパスと、それを適用するためのパスの 2 つのパスで実行することにより、単一パスの方法よりもパフォーマンスが向上するはずです。配列は (行優先順で) コヒーレントにアクセスされます。キャッシュ サイズを超える配列 (ただし、その行はキャッシュに収まる) の場合、データをメモリから 2 回読み取り、1 回格納する必要があります。
void fixmatrix2(int M[][], int rows, int cols) {
bool clearZeroRow= false;
bool clearZeroCol= false;
for(int j=0; j < cols; ++j) {
if( ! M[0][j] ) {
clearZeroRow= true;
}
}
for(int i=1; i < rows; ++i) { // scan/accumulate pass
if( ! M[i][0] ) {
clearZeroCol= true;
}
for(int j=1; j < cols; ++j) {
if( ! M[i][j] ) {
M[0][j]= 0;
M[i][0]= 0;
}
}
}
for(int i=1; i < rows; ++i) { // update pass
if( M[i][0] ) {
for(int j=0; j < cols; ++j) {
if( ! M[j][0] ) {
M[i][j]= 0;
}
}
} else {
for(int j=0; j < cols; ++j) {
M[i][j]= 0;
}
}
if(clearZeroCol) {
M[i][0]= 0;
}
}
if(clearZeroRow) {
for(int j=0; j < cols; ++j) {
M[0][j]= 0;
}
}
}
次のようにして、パスを 1 つだけ使用し、入力マトリックスと出力マトリックスを使用できます。
output(x,y) = col(xy) & row(xy) == 2^n
はcol(xy)ポイントを含む列のビットxyです。row(xy)ポイントを含む行のビットxyです。n行列のサイズです。
次に、入力をループします。スペース効率を高めるために拡張可能か?
わかりました、完全に一致していないことに気づきましたが、2つのブール値ではなく、ブール値とバイトを使用して1つのパスで取得しました...近いです。また、その効率性を保証するものではありませんが、これらのタイプの質問には、最適な解決策が必要ないことがよくあります.
private static void doIt(byte[,] matrix)
{
byte zeroCols = 0;
bool zeroRow = false;
for (int row = 0; row <= matrix.GetUpperBound(0); row++)
{
zeroRow = false;
for (int col = 0; col <= matrix.GetUpperBound(1); col++)
{
if (matrix[row, col] == 0)
{
zeroRow = true;
zeroCols |= (byte)(Math.Pow(2, col));
// reset this column in previous rows
for (int innerRow = 0; innerRow < row; innerRow++)
{
matrix[innerRow, col] = 0;
}
// reset the previous columns in this row
for (int innerCol = 0; innerCol < col; innerCol++)
{
matrix[row, innerCol] = 0;
}
}
else if ((int)(zeroCols & ((byte)Math.Pow(2, col))) > 0)
{
matrix[row, col] = 0;
}
// Force the row to zero
if (zeroRow) { matrix[row, col] = 0; }
}
}
}