Why not C? 3ms C with length-changeable array


  • 0
    8

    For the unkwon length of result, i try to code a simple length-changeable array by myself.
    The more important thing is i use the bitwise operator to accelerate search.
    It's usually used in many contest.

    /**
     * Return an array of arrays of size *returnSize.
     * Note: The returned array must be malloced, assume caller calls free().
     */
    
    int **g_ppiAnswer;
    int iAnswerCnt, iAnswerCap;
    int g_aiAnswer[32];
    int g_n;
    int g_iMask;
    
    void search(int iDep, int iColTabu, int iLeftTabu, int iRightTabu) {
        if (iDep == g_n) {
            if (iAnswerCnt == iAnswerCap) {
                int **ppiNewBuffer = malloc(sizeof(int*) * iAnswerCap * 2);
                memcpy(ppiNewBuffer, g_ppiAnswer, sizeof(int*) * iAnswerCap);
                free(g_ppiAnswer);
                g_ppiAnswer = ppiNewBuffer;
                iAnswerCap *= 2;
            }
            g_ppiAnswer[iAnswerCnt] = malloc(sizeof(int) * g_n);
            memcpy(g_ppiAnswer[iAnswerCnt], g_aiAnswer, sizeof(int) * g_n);
            iAnswerCnt++;
            return;
        }
        iLeftTabu = iLeftTabu >> 1;
        iRightTabu = (iRightTabu << 1) & g_iMask;
        int iAvailables = g_iMask ^ (iColTabu | iLeftTabu | iRightTabu);
        
        while (iAvailables > 0) {
            int iAvailable = iAvailables - (iAvailables & (iAvailables - 1));
            iAvailables -= iAvailable;
            int iPos = lrint(log(iAvailable) / log(2));
            g_aiAnswer[iDep] = iPos;
            search(iDep + 1, iColTabu | iAvailable, iLeftTabu | iAvailable, iRightTabu | iAvailable);
        }
    }
    
    char*** solveNQueens(int n, int* returnSize) {
        assert(n < 32);
        g_n = n;
        g_iMask = (1 << g_n) - 1;
        iAnswerCnt = 0;
        iAnswerCap = 64;
        g_ppiAnswer = malloc(sizeof(int*) * iAnswerCap);
        
        search(0, 0, 0, 0);
        
        *returnSize = iAnswerCnt;
        
        char ***pppcRet = malloc(sizeof(char**) * iAnswerCnt);
        for (int iIndex = 0; iIndex < iAnswerCnt; iIndex++) {
            pppcRet[iIndex] = malloc(sizeof(char*) * g_n);
            for (int iRow = 0; iRow < g_n; iRow++) {
                pppcRet[iIndex][iRow] = malloc(sizeof(char) * (g_n + 1));
                memset(pppcRet[iIndex][iRow], '.', sizeof(char) * g_n);
                pppcRet[iIndex][iRow][g_ppiAnswer[iIndex][iRow]] = 'Q';
                pppcRet[iIndex][iRow][g_n] = 0;
            }
        }
        
        return pppcRet;
    }
    

Log in to reply
 

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