تعيين كل خلية في المصفوفة إلى 0 إذا كان هذا الصف أو العمود يحتوي على 0
https://stackoverflow.com/questions/339262
-
19-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
نظرا NxN مصفوفة مع 0s 1s.تعيين كل صف يحتوي على 0 إلى كل 0s وتعيين كل عمود يحتوي على 0 إلى كل 0s.
على سبيل المثال
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 مهندس قال لي أن هناك ما هو الحل الذي لا ينطوي على أي ذاكرة إضافية اثنين فقط منطقية المتغيرات مرور واحد ، لذلك أنا أبحث عن هذا الجواب.
راجع للشغل, تخيل أنها قليلا مصفوفة, ولذلك فقط 1s و 0s هل تسمح أن تكون في المصفوفة.
المحلول
وطيب، حتى أنا تعبت كما انها 3:00 هنا، ولكن لدي inplace المحاولة الأولى مع بالضبط 2 كرة على كل رقم في المصفوفة، وذلك في O (NxN) ومن الخطية في حجم المصفوفة.
وأنا استخدم العمود 1rst والصف الأول كعلامات أن تعرف أين هي الصفوف / العواميد مع ل1 فقط. ثم، هناك 2 المتغيرات لتر وج أن نتذكر إذا التوالي 1rst / عمود وتصفح جميع (1) أيضا. حتى مرور الأول يضع علامات ويعيد الباقي ل0.
والممر الثاني يحدد 1 في أماكن الصفوف والعواميد حيث تميز لتكون 1، وإعادة تعيين 1ST خط / عمود تبعا ل ج.
وأشك بقوة أن أستطيع القيام به في 1 تمريرة كمربعات في البداية تعتمد على الساحات في نهاية المطاف. ربما بلدي تمرير 2ND يمكن أن تكون أكثر كفاءة ...
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)
نصائح أخرى
لا يمكن أن يتم ذلك في مرور واحد منذ بت واحد له تأثير على بت قبل وبعد ذلك في أي ترتيب. IOW مهما من أجل أن تجتاز مجموعة في، قد تأتي لاحقا تزوجنا و0 مما يعني أنك يجب أن نعود وتغيير السابق 1 إلى 0.
تحديث
يبدووالناس على الاعتقاد بأن طريق تقييد N إلى قيمة ثابتة (مثلا 8) يمكنك حل هذا مرور واحد. حسنا هذا هو) في عداد المفقودين نقطة وب) لا السؤال الأصلي. أنا لن الرد على سؤال حول الفرز ونتوقع جوابا التي بدأت "على افتراض انك تريد فقط لفرز 8 أشياء ...".
وقال ذلك، انها نهجا معقولا إذا كنت تعرف أن N هو في واقع الأمر يقتصر على 8. جوابي أعلاه يجيب على السؤال الأصلي الذي لا يوجد لديه مثل retriction.
وهكذا فكرتي هي استخدام القيم في الصف الأخير / العمود كما علم لبيان ما إذا كانت كافة القيم في العمود / الصف المقابل هي 1S.
منعرج الزاك مسح من خلال مصفوفة كاملة باستثناء الصف / العمود الأخير. في كل عنصر، يمكنك تعيين قيمة في الصف / العمود الأخير لالمنطقية AND في حد ذاته مع القيمة في العنصر الحالي. وبعبارة أخرى، إذا كنت أصاب 0، سيتم تعيين الصف / العمود الأخير إلى 0. إذا كنت عليه 1، والقيمة في الصف / العمود الأخير سيكون 1 إلا إذا كان بالفعل 1. وعلى أية حال تعيين العنصر الحالي إلى 0.
عند الانتهاء، الصف النهائي الخاص بك / يجب أن يكون العمود 1S المنتدى امتلأت العمود / الصف المقابل مع 1S.
والقيام بمسح الخطي من خلال الصف النهائي والعمود وتبحث عن 1S. تعيين 1S في العناصر المقابلة في الجسم من المصفوفة حيث الصف النهائي والعمود على حد سواء 1S.
والترميز سيكون صعب لتجنب الأخطاء من جانب واحد وغيرها ولكن ينبغي لها أن تعمل في مرور واحد.
ولقد حصلت على الحل هنا، فإنه يعمل في مسار واحد، ويفعل كل التجهيز "في المكان" مع عدم وجود ذاكرة إضافية (باستثناء نموا في كومة).
ويستخدم العودية لتأخير كتابة الأصفار التي بالطبع من شأنه أن يدمر مصفوفة للصفوف من الأعمدة والأخرى:
#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، لم يكن لديك وسيلة لمعرفة ما قيم الساحات الأخرى في نفس الصف والعمود هي. ولذلك عليك أن تحقق تلك وإذا كان هناك صفر، والعودة إلى المربع الأول وتغيير قيمتها إلى الصفر. سوف أوصى به في مرورين - مرور الأول يجمع معلومات حول الصفوف والأعمدة يجب أن ركزت بها (يتم تخزين المعلومات في صفيف، لذلك نحن باستخدام بعض ذاكرة إضافية). الممر الثاني بتغيير القيم. أنا أعلم أن هذا ليس هو الحل الذي تبحث عنه، ولكن اعتقد انها واحدة العملي. القيود التي قدمتموها تجعل المشكلة غير قابلة للحل.
وأستطيع أن أفعل ذلك مع اثنين من المتغيرات عدد صحيح ومرورين (حتى 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));
ويمكن حل المشكلة في مرور واحد
وإنقاذ مصفوفة في مصفوفة ط X ي.
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
one each pass save the values of i and j for an element which is 0 in arrays a and b
when first row is scanned a= 1 b = 2,5
when second row is scanned a=1,2 b= 1,2,5
when third row is scanned no change
when fourth row is scanned a= 1,2,4 and b= 1,2,5
when fifth row is scanned no change .
والآن طباعة كافة القيم ك 0 لقيم i و j المحفوظة في أ و ب باقي القيم هي 1 أي (3،3) (3،4) (5،3) و (5،4)
آخر حل يأخذ مرورين، هو تراكم يستخدم المعامل أفقيا وعموديا:
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
وكنت أعتقد أنني يمكن أن تصميم مثل هذه الخوارزمية باستخدام بت التكافؤ و <لأ href = " http://en.wikipedia.org/wiki/Hamming_code "يختلط =" نوفولو noreferrer "> المبالغة رموز أو <وأ href =" http://en.wikipedia.org/wiki/Dynamic_programming "يختلط =" نوفولو noreferrer "> البرمجة الديناميكية ، ربما باستخدام تلك القيم المنطقية اثنين وعدد 2 بت، ولكن لقد كان هناك نجاح حتى الان.
هل يمكن ان يرجى إعادة التحقق من بيان المشكلة مع مهندس والسماح لنا أن نعرف؟ إذا هناك <م> هو بالفعل حل، وأريد للحفاظ على التقطيع بعيدا في هذه المشكلة.
والحفاظ على متغير واحد لتتبع كل ما من الصفوف ANDed معا ل.
وإذا كان الصف -1 (جميع 1S)، ثم جعل الصف التالي إشارة إلى هذا المتغير
إذا على التوالي ولكن اي شيء، انها 0. يمكن أن تفعل كل شيء في مرور واحد. الزائف رمز:
foreach (my $row) rows {
$andproduct = $andproduct & $row;
if($row != -1) {
zero out the row
} else {
replace row with a reference to andproduct
}
}
وهذا ينبغي أن نفعل ذلك، في مسار واحد - ولكن هناك افتراض هنا أن N هي صغيرة بما يكفي لوحدة المعالجة المركزية للقيام الحساب في صف واحد، وإلا كنت بحاجة الى الذهاب الى حلقة على كل صف لتحديد اذا كان كل 1S أم لا، على ما أعتقد. ولكن نظرا كنت تسأل عن algos وليس تقييد الأجهزة بلدي، وأنا سوف نبدأ جوابي مع "بناء وحدة المعالجة المركزية التي تدعم الحساب N-بت ..."
وهنا واحدة سبيل المثال كيف يمكن القيام به في C. ملاحظة أزعم أن القيم وصول مجتمعة تمثل مجموعة وp و numproduct هي بلدي مكرر ووالمتغيرات استخدام المنتج لتنفيذ هذه المشكلة. (كان يمكن أن يحلق فوق آر مع الحساب المؤشر للتحقق من عملي، ولكن مرة واحدة كانت كافية!)
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);
وأنا شيء مفقود؟
ونيس تحدي دبي. هذا الحل نوعا من يستخدم اثنين فقط من القيم المنطقية التي تم إنشاؤها على المكدس، ولكن يتم إنشاء القيم المنطقية عدة مرات على المكدس لأن وظيفة غير متكررة.
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
ووهلم جرا
وبعد ذلك changeing القيم في هذا النمط على العائد على كل من وظائف المسح الضوئي. (أسفل إلى أعلى):
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
ووهلم جرا
حسنا هذا هو الحل الذي
- يستخدم واحدة فقط إضافية طويلة قيمة العامل التخزين.
- لا يستخدم العودية.
- مرور واحد فقط ن ، حتى ن*ن.
- سوف تعمل من أجل القيم الأخرى N ولكن سوف تحتاج جديد #تعرف.
#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;
}
والواقع. إذا كنت ترغب فقط لتشغيل الخوارزمية وطباعة النتائج (أي ليست استعادتها، ثم وهذا يمكن القيام به بسهولة في مرور واحد. والمشكلة تأتي عندما حاولت تعديل مجموعة كما كنت تقوم بتشغيل الخوارزمية.
وهنا هو بلدي الحل هو فقط ينطوي اندينج الصفوف / الأعمدة القيم لgivein (ط، ي) الصورة عنصر وطباعته.
#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 تمثل البعد
المنطق حاولت هي:
- حساب و الصفوف و العواميد تشارك في كل ساحة مركزية من المصفوفة
- متجر في الزاوية الخلايا (لقد تم تخزينها في مكافحة اتجاه عقارب الساعة)
- اثنين منطقي المتغيرات تستخدم للاحتفاظ القيم من ركنين عند تقييم مربع معين.
- هذه العملية سوف تنتهي عندما الخارجي حلقة (أنا) هو في منتصف الطريق.
- تقييم النتائج من الخلايا الأخرى على أساس الزاوية الخلايا (للراحة من أنا).تخطي الزاوية الخلايا أثناء هذه العملية.
- عندما يصل n, جميع الخلايا لها نتيجة باستثناء الزاوية الخلايا.
- تحديث الزاوية الخلايا.هذا هو إضافي التكرار على طول n/2 غير مرور واحد القيد المذكور في المشكلة.
كود:
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;
}
}
}
}
وعلى الرغم من المستحيل نظرا للقيود، وسيلة فعالة المساحة الأكبر للقيام بذلك هو عن طريق عبور المصفوفة في overlaping، بالتناوب الأزياء صف / عمود، والتي من شأنها أن تجعل وجود نمط مماثل لوضع الطوب بطريقة التعرج:
-----
|----
||---
|||--
||||-
وباستخدام هذا، سوف تذهب في كل صف / عمود، كما هو مبين، وإذا واجهت 0 في أي وقت، وتعيين متغير منطقية، وإعادة السير أن صف / عمود، وتحديد مداخل 0 كما تذهب .
وهذا يتطلب عدم وجود ذاكرة إضافية، وسوف تستخدم فقط متغير منطقية واحدة. لسوء الحظ، إذا تم تعيين الحافة "الآن" لتكون كلها 0، وهذا هو أسوأ الحالات وأنت تمشي في مجموعة كاملة مرتين.
وإنشاء مصفوفة نتيجة وتعيين كافة القيم إلى 1. تذهب من خلال مصفوفة البيانات بمجرد اجه 0، تعيين العمود نتيجة الصف مصفوفة 0
وفي نهاية الممر الأول، فإن مصفوفة نتيجة لديهم الإجابة الصحيحة.
وتبدو بسيطة جدا. هل هناك خدعة أنا في عداد المفقودين؟ هل لا يسمح لاستخدام مجموعة النتيجة؟
وتحرير:
ويبدو وكأنه # ظيفة F، ولكن هذا هو الغش قليلا لأنه حتى لو كنت تفعل مسار واحد، ويمكن أن يكون وظيفة العودية.
ويبدو أن المقابلة هو محاولة لمعرفة ما اذا كنت تعرف البرمجة الوظيفية.
حسنا، خطرت لي بعد مرور واحد، حل في المرتبة (غير متكررة) باستخدام 4 bools و 2 عدادات حلقة. أنا لم تمكن من تقليصه إلى 2 bools و 2 [إينتس]، لكنني لن يفاجأ إذا كان من الممكن. وهو يفعل حوالي 3 يقرأ ويكتب 3 من كل خلية، وأنه ينبغي أن يكون O (N ^ 2) أي. خطية في حجم مجموعة.
وأخذني بضع ساعات للغز هذا واحد - لا أريد أن يكون لتأتي معها تحت ضغط مقابلة! إذا كنت قد قدمت BOOBOO أنا متعب جدا لاكتشاف ذلك ...
وأم ... أنا اختيار لتحديد "تمرير واحد"، كما جعل الاجتياح واحد من خلال مصفوفة، بدلا من لمس كل قيمة مرة واحدة! : -)
#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;
}
وآمل أن تستمتع بلدي 1 تمرير ج # الحل
ويمكنك استرداد عنصر مع O (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 أو 1 التي تم تحويلها إلى 0 ثم انني لن تضطر إلى استخدام -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 و عرض السينية ومن ثم ذ وارتفاع ذ في كل تكرار. وبناء على نتائج النصف الأول من التكرار، إذا تم العثور على 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
لا أحد يستخدم الشكل الثنائي؟ لأنه فقط 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
ويمكنك أن تفعل شيئا من هذا القبيل لاستخدام مرور واحد ولكن على المدخلات والمخرجات مصفوفة:
output(x,y) = col(xy) & row(xy) == 2^n
وحيث col(xy) هو بت في العمود الذي يحتوي على xy نقطة. row(xy) هو بت في الصف الذي يحتوي على xy نقطة. n هو حجم المصفوفة.
وبعد ذلك حلقة فقط على المدخلات. ربما قابلة للتوسيع إلى أن تكون أكثر كفاءة الفضاء؟
واحد مسح مصفوفة، وهما القيم المنطقية، لا العودية.
وكيفية تجنب الممر الثاني؟ وهناك حاجة مسار الثاني لمسح الصفوف أو الأعمدة عندما appeares الصفر في نهايتها.
ولكن هذه المشكلة لا يمكن حلها، لأننا عندما مسح الصف #I نعرفه الوضع الصف للصف # ط 1. لذلك، في حين أننا مسح #I التوالي يمكننا مسح في وقت واحد الصف # ط 1 إذا لزم الأمر.
والحل نفسه يعمل للأعمدة، ولكن نحن بحاجة إلى مسح الصفوف والأعمدة في وقت واحد في حين لم يتم تغيير البيانات عن طريق التكرار التالي.
ويطلب من اثنين من القيم المنطقية لتخزين وضعية الصف الأول والعمود الأول، لأنه سيتم تغيير قيمها أثناء تنفيذ الجزء الرئيسي من الخوارزمية.
لتجنب إضافة المزيد من القيم المنطقية نحن تخزين "واضح" العلم لالصفوف والأعمدة في الصف الأول والعمود المصفوفة.
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();
}
ويبدو أن الأعمال التالية مع عدم وجود متطلبات مساحة إضافية:
والمذكرة الأولى التي ضرب عناصر مرات متتالية عناصر الخط الذي هو عنصر، ويعطي القيمة المطلوبة.
في أجل عدم استخدام أي مساحة إضافية (لا يجعل مصفوفة جديدة وشغل عنه ولكن بدلا من تطبيق التغييرات على مصفوفة مباشرة)، وبدء أعلى اليسار من المصفوفة والقيام حساب لأي مصفوفة مبدعين (أن "يبدأ" في (0،0)) قبل النظر في أي عنصر مع أي مؤشر> ط.
والأمل يعمل هذا (طعاما testet)
هذا هو اختبار مختلفة N C++ و هي:
مرور واحد, اثنين BOOLS, لا العودية, لا ذاكرة إضافية, يحمل ARBITRARLY كبيرة ن
(حتى الآن أيا من الحلول هنا هل كل هذه.)
وبشكل أكثر تحديدا, أنا مسلية اثنين حلقة عدادات حسنا.لدي اثنين من const unsigneds ، والتي توجد فقط بدلا من احتساب كل وقت القراءة.الخارجي الحلقة فاصل [0, N] و الحلقة الداخلية هو فاصل [1, n - 1].بيان التبديل في حلقة معظمها موجود تظهر بشكل واضح جدا أنه حقا هو مرور واحد فقط.
خوارزمية الاستراتيجية:
الحيلة الأولى لنا صف وعمود من المصفوفة نفسها تجميع محتويات المصفوفة ، هذه الذاكرة تصبح متاحة من خلال تفريغ ما نحن حقا بحاجة إلى معرفة من الصف الأول والعمود إلى قسمين القيم المنطقية.الحيلة الثانية هو الحصول على اثنين من يمر من أصل واحد ، باستخدام التماثل الفرعية مصفوفة و المؤشرات.
خوارزمية ملخص الفيلم:
- مسح الصف الأول وتخزين إذا كانت كل منها منطقية ، تفعل الشيء نفسه بالنسبة العمود الأول تخزين النتيجة في الثانية المنطقية.
- الفرعية مصفوفة باستثناء الصف الأول العمود الأول:من خلال تكرار ، اليسار إلى اليمين ومن الأعلى إلى الأسفل ، كما قد قرأت الفقرة.عند زيارة كل عنصر ، أيضا زيارة العنصر المقابل سيكون زار إن زيارة الفرعية مصفوفة في الاتجاه المعاكس.لكل عنصر زار قيمته إلى أين الصف صلبان العمود الأول, و أيضا و قيمته إلى حيث العمود والصلبان الصف الأول.
- مرة واحدة في مركز الفرعية مصفوفة الوصول إلى مواصلة زيارة اثنين من العناصر في وقت واحد على النحو الوارد أعلاه.ولكن الآن تعيين زار عناصر' قيمة من حيث الصف صلبان العمود الأول من حيث عمود يعبر الصف الأول.بعد هذا الفرعية المصفوفة كاملة.
- استخدام اثنين منطقية المتغيرات المحسوبة في التسول لضبط الصف الأول والعمود الأول إلى القيم الصحيحة.
Templatized تنفيذ C++:
template<unsigned n>
void SidewaysAndRowColumn(int((&m)[n])[n]) {
bool fcol = m[0][0] ? true : false;
bool frow = m[0][0] ? true : false;
for (unsigned d = 0; d <= n; ++d) {
for (unsigned i = 1; i < n; ++i) {
switch (d) {
case 0:
frow = frow && m[d][i];
fcol = fcol && m[i][d];
break;
default:
{
unsigned const rd = n - d;
unsigned const ri = n - i;
if (d * n + i < rd * n + ri)
{
m[ d][ 0] &= m[ d][ i];
m[ 0][ d] &= m[ i][ d];
m[ 0][ i] &= m[ d][ i];
m[ i][ 0] &= m[ i][ d];
m[rd][ 0] &= m[rd][ri];
m[ 0][rd] &= m[ri][rd];
m[ 0][ri] &= m[rd][ri];
m[ri][ 0] &= m[ri][rd];
}
else
{
m[ d][ i] = m[ d][0] & m[0][ i];
m[rd][ri] = m[rd][0] & m[0][ri];
}
break;
}
case n:
if (!frow)
m[0][i] = 0;
if (!fcol)
m[i][0] = 0;
};
}
}
m[0][0] = (frow && fcol) ? 1 : 0;
}
وطيب، وأنا أدرك أنه ليس تماما مباراة، ولكن حصلت عليه في مرور واحد باستخدام منطقي وبايت بدلا من اثنين bools ... وثيق. كما أنني لا أود أن يشهدوا على كفاءة ولكن هذه الأنواع من الأسئلة غالبا ما تتطلب أقل من الحلول المثلى.
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; }
}
}
}
وأنت شيء على أن تفعل ذلك في تمريرة واحدة - إذا كنت لا تعول الوصول إلى مصفوفة من أجل الوصول العشوائي، الذي يلغي فوائد القيام به واحد تمرير في المقام الأول (ذاكرة التخزين المؤقت التماسك / ذاكرة النطاق الترددي ).
[عدل: بسيطة، ولكن الخطأ الحل حذف]
ويجب عليك الحصول على أداء أفضل من أي طريقة تمرير واحد من يفعل ذلك في مرورين: واحد لتجميع صف / عمود من المعلومات، واحدة لتطبيقه. يتم الوصول إلى مجموعة (من أجل الصف الرئيسي) متماسك. للصفائف يتجاوز حجم ذاكرة التخزين المؤقت (ولكن الذي يمكن أن يصلح الصفوف في ذاكرة التخزين المؤقت)، وينبغي أن يقرأ البيانات من الذاكرة مرتين، وتخزينها مرة واحدة:
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;
}
}
}
وأبسط حل أستطيع أن أفكر في لصق أدناه. المنطق هو تسجيل التي الصفوف والأعمدة لوضع الصفر في حين بالتكرار.
import java.util.HashSet;
import java.util.Set;
public class MatrixExamples {
public static void zeroOut(int[][] myArray) {
Set<Integer> rowsToZero = new HashSet<>();
Set<Integer> columnsToZero = new HashSet<>();
for (int i = 0; i < myArray.length; i++) {
for (int j = 0; j < myArray.length; j++) {
if (myArray[i][j] == 0) {
rowsToZero.add(i);
columnsToZero.add(j);
}
}
}
for (int i : rowsToZero) {
for (int j = 0; j < myArray.length; j++) {
myArray[i][j] = 0;
}
}
for (int i : columnsToZero) {
for (int j = 0; j < myArray.length; j++) {
myArray[j][i] = 0;
}
}
for (int i = 0; i < myArray.length; i++) { // record which rows and // columns will be zeroed
for (int j = 0; j < myArray.length; j++) {
System.out.print(myArray[i][j] + ",");
if(j == myArray.length-1)
System.out.println();
}
}
}
public static void main(String[] args) {
int[][] a = { { 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 } };
zeroOut(a);
}
}
وهنا هو تنفيذ روبي بلدي مع اختبار المدرجة، هذا سيستغرق 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
وإنشاء التعليمات البرمجية أدناه مصفوفة من حجم م، ن. أولا تحديد أبعاد المصفوفة. كنت أرغب في ملء مصفوفة [م] [ن] مع عشوائيا مع الأرقام بين 0..10. ثم إنشاء مصفوفة آخر من نفس الأبعاد وملء مع -1s (المصفوفة النهائية). ثم تكرار خلال مصفوفة أولية لمعرفة ما اذا كنت سوف تصل 0. عندما ضرب على الموقع (س، ص)، انتقل إلى المصفوفة النهائية وملء الصف العاشر مع 0S والعمود ذ مع 0S. وفي نهاية القراءة من خلال المصفوفة النهائية، إذا كانت القيمة -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;
}
وهنا هو بلدي الحل. وكما ترون من التعليمات البرمجية، نظرا مصفوفة M * N، فإنه يضع الصف بأكمله إلى الصفر بمجرد أن يتفقد صفر في ذلك الوقت row.the تعقيد بلدي الحل هو O (M * N). أنا تقاسم الصف بأكمله التي لديها مجموعة سكانية ثابتة للاختبار وطريقة عرض مجموعة لرؤية النتيجة في وحدة التحكم.
public class EntireRowSetToZero {
static int arr[][] = new int[3][4];
static {
arr[0][0] = 1;
arr[0][1] = 9;
arr[0][2] = 2;
arr[0][3] = 2;
arr[1][0] = 1;
arr[1][1] = 5;
arr[1][2] = 88;
arr[1][3] = 7;
arr[2][0] = 0;
arr[2][1] = 8;
arr[2][2] = 4;
arr[2][3] = 4;
}
public static void main(String[] args) {
displayArr(EntireRowSetToZero.arr, 3, 4);
setRowToZero(EntireRowSetToZero.arr);
System.out.println("--------------");
displayArr(EntireRowSetToZero.arr, 3, 4);
}
static int[][] setRowToZero(int[][] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[i].length; j++) {
if(arr[i][j]==0){
arr[i]=new int[arr[i].length];
}
}
}
return arr;
}
static void displayArr(int[][] arr, int n, int k) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.println("");
}
}
و}
واحد ممر - لقد اجتاز إدخال مرة واحدة فقط ولكنها تستخدم مجموعة جديدة واثنين فقط من المتغيرات المنطقية إضافية
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
sc.nextLine();
boolean rowDel = false, colDel = false;
int arr[][] = new int[n][n];
int res[][] = new int[n][n];
int i, j;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
arr[i][j] = sc.nextInt();
res[i][j] = arr[i][j];
}
}
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (arr[i][j] == 0)
colDel = rowDel = true; //See if we have to delete the
//current row and column
if (rowDel == true){
res[i] = new int[n];
rowDel = false;
}
if(colDel == true){
for (int k = 0; k < n; k++) {
res[k][j] = 0;
}
colDel = false;
}
}
}
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
System.out.print(res[i][j]);
}
System.out.println();
}
sc.close();
}
