C solution using self-implement hash table


  • 0
    C
    typedef struct xy_s {
        int     x;
        int     y;
        struct xy_s *next;
    } xy_t;
    
    typedef struct xbucket_s {
        void                *key;
        void                *data_ptr;
        struct xbucket_s   *next;
    } xbucket_t;
    
    typedef struct xhash_s {
        xbucket_t   **buckets;
        int         size;
    } xhash_t;
    
    int xhash_init(xhash_t **hash, int size)
    {
        if (!hash) return -1;
    
        /* TODO Get next prime bigger than *size* */
        /* size = next_prime(size);*/
    
        *hash = calloc(1, sizeof **hash);
        if (! *hash)
            return -1;
    
        (*hash)->buckets = calloc(size, sizeof (*hash)->buckets);
        if (! (*hash)->buckets)
            return -1;
    
        (*hash)->size = size;
    
        return 0;
    }
    
    int xhash_int_insert(xhash_t *hash, void *key, void *data)
    {
        int         idx;
        xbucket_t   *bucket;
    
        /* If exists, return ok */
        if (!xhash_int_find(hash, key, NULL))
            return -2;
    
        idx = ((int)key) % hash->size;
    
        bucket = calloc(1, sizeof *bucket);
        if (!bucket)
            return -1;
    
        bucket->key = key;
        bucket->data_ptr = data;
    
        if (hash->buckets[idx])
            bucket->next = hash->buckets[idx];
    
        hash->buckets[idx] = bucket;
    
        return 0;
    }
    
    int xhash_int_find(xhash_t *hash, void *key, void **data)
    {
        int         idx;
        xbucket_t   *bucket;
    
        idx = ((int)key) % hash->size;
        bucket = hash->buckets[idx];
        while (bucket) {
            if ((int)key == (int)(bucket->key)) {
                if (data) *data = bucket->data_ptr;
                return 0;
            }
            bucket = bucket->next;
        }
    
        return -1;
    }
    
    int xhash_int_remove(xhash_t *hash, void *key)
    {
        int         idx;
        xbucket_t   *bucket, **pre;
    
        idx = ((int)key) % hash->size;
        pre = &hash->buckets[idx];
        bucket = hash->buckets[idx];
    
        while (bucket) {
            if ((int)key == (int)(bucket->key)) {
                *pre = bucket->next;
                free(bucket);
                return 0;
            }
    
            pre = &bucket->next;
            bucket = bucket->next;
        }
    
        /* not found */
        return 0;
    }
    
    int xhash_print(xhash_t *hash)
    {
        int         idx;
        xbucket_t   *bucket;
    
        if (!hash) return -1;
    
        for (idx = 0 ; idx < hash->size ; ++idx) {
            bucket = hash->buckets[idx];
            printf("bucket[%d]: ", idx);
    
            while (bucket) {
                if (bucket->next)
                    printf("%d, ", (int)(bucket->key));
                else
                    printf("%d", (int)(bucket->key));
    
                bucket = bucket->next;
            }
    
            printf("\n");
        }
    
        return 0;
    }
    
    int xhash_uninit(xhash_t *hash)
    {
        int         idx;
        xbucket_t   *bucket, *next;
    
        if (!hash) return 0;
    
        for (idx = 0 ; idx < hash->size ; ++idx) {
            bucket = hash->buckets[idx];
    
            while (bucket) {
                next = bucket->next;
                free(bucket);
                bucket = next;
            }
        }
    
        free(hash->buckets);
        free(hash);
    
        return 0;
    }
    
    bool isValidSudoku(char** board, int boardRowSize, int boardColSize) {
        xhash_t     *hash;
        int         i, j;
        xy_t        *xy, *pre;
        
        xhash_init(&hash, boardRowSize * boardColSize);
        
        for (i = 0 ; i < boardRowSize ; ++i) {
            for (j = 0 ; j < boardColSize ; ++j) {
                if (board[i][j] == '.') continue;
                
                if (!xhash_int_find(hash, board[i][j], &xy)) {
                    while (xy) {
                        if (xy->x == i || xy->y == j
                            || ((i / 3 == xy->x / 3 && i - xy->x < 3 && i - xy->x > -3) && (j / 3 == xy->y / 3 && j - xy->y < 3 && j - xy->y > -3))) {
                            return 0;
                        }
                        pre = xy;
                        xy = xy->next;
                    }
                    
                    xy = calloc(1, sizeof *xy);
                    xy->x = i;
                    xy->y = j;
                    pre->next = xy;
                } else {
                    xy = calloc(1, sizeof *xy);
                    xy->x = i;
                    xy->y = j;
                    xhash_int_insert(hash, board[i][j], xy);
                }
            }
        }
        
        return 1;
    }
    
    

Log in to reply
 

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