Other articles


  1. 加法和乘法问题

    两个字符串表示的大数相乘问题

    Tag: leetcode 43

    Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.

    Note:

    The length of both num1 and num2 is < 110. Both num1 and num2 contains only digits 0-9. Both num1 and num2 does not contain any leading zero. You …

    read more

    There are comments.

  2. 选择问题的解决方法 (最大第 K 个元素问题)

    Tag: leetcode 215, 414

    求一个无序数组中第 k 大元素的问题, 是个很经典的问题, 已经被提出来了很多解法, 这些解法一个比一个精彩. 下面我们来从时间和空间复杂度上综合考虑一下各种解法.

    排序

    首先最容易想到的大概就是排序了, 将数组降序排序, 然后直接取索引 k - 1 的元素就是第 k 大的元素. 这种方法因采取的排序算法不同而不同, 最好的情况是采用快排, 这样平均而言能够达到一个时间复杂度 O(NlogN) + 空间复杂度 O(1) 的结果. 不过在最坏的情况下, 快排也是有可能达到 O(N2) 的时间复杂度.

    归并总是能够达到 O(NlogN) 的时间复杂度, 但是其空间复杂度却是 O(N), 这在当数据量比较大内存资源有限时往往也不是最好的方案.

    最小堆

    第二种方式就是建立最小堆

    Quick Select

    第三种方式是参考快排的思想, 不断的将数组分区, 与快速排序不同的时我们不需要每次都对两个子分区再分区, 而是只对其中一个子分区再分区即可 …

    read more

    There are comments.

  3. 二叉树的序列化与反序列化

    /*
     * A very crude queue implementation
     */
    typedef
    struct queue {
        struct TreeNode *val;
        struct queue    *next;
    } Queue;
    
    void queueCreate(Queue **queue)
    {
        *queue = NULL;
    }
    
    void enqueue(Queue **queue, struct TreeNode *c)
    {
        Queue       *tmp, *p;
    
        tmp = malloc(sizeof *tmp);
        tmp->val = c;
        tmp->next= NULL;
    
        if (! *queue) {
            *queue = tmp;
            return;
        }
    
        for (p = *queue ; p …
    read more

    There are comments.

  4. 嵌入式哈系表的实现

    这篇文章是一个例子, 重点在于阐述嵌入式哈系表结构, 而不是针对不同键类型进行哈希的方法.

    关于哈希冲突的解决, 我们使用链表存储冲突的节点, 这在一些书里被称为 "Separate Chaning" 方法.

    由于在链表中插入以及删除节点需要更新节点的前继和后继的指针, 所以为了方便的从链表中插入以及删除节点, hlist_node_t 结构中定义两个指针, 分别指向前继和后继.

    typedef struct hlist_node_s {
        struct hlist_node_s *prev;
        struct hlist_node_s *next;
    } hlist_node_t;
    

    hlist_t 结构中的 heads 是一个数组, 每个数组元素都只是一个头节点, 头节点不会嵌入到别的结构体中.

    typedef struct xhash {
        hlist_node_t    *heads;
        int             size;
    } xhash_t;
    
    void hlist_node_init(hlist_node_t *node)
    {
        node->next = node->prev = node;
    }
    
    xhash_t *xhash_create(int …
    read more

    There are comments.

Page 1 / 8 »

social