A decent, clean and in-place solution accepted as best submission in C enclosed with critical comments


  • 0
    #define MIN(a, b) ((a) < (b) ? (a) : (b))
    #define MAX(a, b) ((a) > (b) ? (a) : (b))
    //in-place solution using bit manipulation;
    void gameOfLife(int** board, int rSize, int cSize)
    {
        for(int i = 0; i < rSize; i++)
            for(int j = 0; j < cSize; j++)
            {
                int count = 0;
                for(int rr = MAX(i-1, 0); rr < MIN(i+2, rSize); rr++)
                    for(int cc = MAX(j-1, 0); cc < MIN(j+2, cSize); cc++)
                        count += board[rr][cc]&1; //in-place;
                count -= board[i][j];
                if(count==3 || (board[i][j]&&count==2))
                    board[i][j] |= 2;
            }
        for(int i = 0; i < rSize; i++)
            for(int j = 0; j < cSize; j++)
                board[i][j] >>= 1;
    }

  • 0
    X

    This is not correct....

    1.for(int rr = MAX(i-1, 0); rr < MIN(i+1, rSize); rr++) for(int cc = MAX(j-1, 0); cc < MIN(j+1, cSize); cc++) is ignoring the a row and a line when calculating count.

    1. count -= board[i][j]; shoud be count -= board[i][j]&1; to only count for current state;

    2. if(count==3 || (board[i][j]&&count==2)) should be if(count==3 || ((board[i][j]&1) &&count==2)) for the same reason.


  • 0

    Sorry about your first question -> I really do not understand what you are trying to say;

    As for the second one, the count -= board[i][j] is alright here since here is board[i][j] which will only be handled once in the whole loop before <font color="#0000ff">board[i][j] |= 2; </font> as for board[rr][cc] which will be essential to add board[rr][cc]&1 because this value will be handled several times;


    then the third question, since second one is specified ^^

    Hope this can help you!


  • 0
    #define MIN(a, b) ((a) < (b) ? (a) : (b))
    #define MAX(a, b) ((a) > (b) ? (a) : (b))
    //in-place solution using bit manipulation;
    void gameOfLife(int** board, int rSize, int cSize)
    {
        for(int i = 0; i < rSize; i++)
            for(int j = 0; j < cSize; j++)
            {
                int count = 0;
                for(int rr = MAX(i-1, 0); rr < MIN(i+2, rSize); rr++)
                    for(int cc = MAX(j-1, 0); cc < MIN(j+2, cSize); cc++)
                        count += board[rr][cc]&1; //in-place;
                count -= board[i][j];
                if(count==3 || (board[i][j]&&count==2))
                    board[i][j] |= 2;
            }
        for(int i = 0; i < rSize; i++)
            for(int j = 0; j < cSize; j++)
                board[i][j] >>= 1;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.