月度归档:2018年08月

# Difference between map & unordered_map

点击量:9

目前有三个容器我不太了解其内部实现,打算通过 <c++ primer> 进行学习

  1. map
  2. multimap
  3. unordered_map

map

map 是目前最简单的结构,实现的方法是 BST(binary search tree)。因此,其时间复杂度等都与 BST 相同,搜索,增加,删除基本时间都是 log(n)。

use map when

  1. 数据有序
  2. 需要按照有序的顺序获得元素


unordered_map

unordered_map 则是通常所说的 hash table,哈希表,搜索,增加,删除都是以hash表为主,较好的情况是o(1),也就是hash函数可以较好的把元素分布到表中,如果 hash 函数比较糟糕,则每一次添加删除查找,都是完整遍历一个表。

use unordered_map when

  1. 对数据计数
  2. 只需要根据 key 访问 value

简单来讲,就是当你需要使用 vector 来计数的时候,可以用 unordered_map 来代替。

                  | map             | unordered_map
---------------------------------------------------------
Ordering        | increasing  order   | no ordering
                | (by default)        |

Implementation  | Self balancing BST  | Hash Table
                | like Red-Black Tree |  

search time     | log(n)              | O(1) -> Average 
                |                     | O(n) -> Worst Case

Insertion time  | log(n) + Rebalance  | Same as search
                      
Deletion time   | log(n) + Rebalance  | Same as search

multimap

multimap containers are generally slower than unordered_multimap containers to access individual elements by their key, but they allow the direct iteration on subsets based on their order.

Multimaps are typically implemented as binary search trees.

multiple 也是用 bst 实现的,相比 map,允许按照顺序遍历元素。

Reference

https://www.geeksforgeeks.org/map-vs-unordered_map-c/

# leetcode 相交链表

点击量:12

这是leetcode的解题报告。ARTS很想加入,但是因为自己懒,本身也做了这些事情,因此就一直都在拖,希望这周能够搞定。

origin

from leetcode

road

相交链表,两个指针分别遍历两个链表即可,具体可以画图来表示,两个链表,一个长度为 a+c,另一个长度为 b+c,两个指针势必会在 a+b+c 的位置相遇。

solution

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *w1, *w2;
        w1 = headA;
        w2 = headB;
        if (!w1 || !w2) {
            return NULL;
        }
        while (w1 != w2) {
            if (!w1)
                w1 = headB;
            else
                w1 = w1->next;
            if (!w2)
                w2 = headA;
            else
                w2 = w2->next;
        }
        return w1;
    }
};

# 找房启示

点击量:12

安居客是不太行,所有的看起来不错的房源,没有一个能联系上,联系上的全都是没有了,建议别用安居客。

找房几个关键因素:

  1. 阳光好,(朝南)
  2. 床板硬,不凹陷
  3. 淋浴头水力充足
  4. 独立卫浴,
  5. 地铁口附近,
  6. 没有汽车声音
  7. 没有蟑螂老鼠,
  8. 隔音好,
  9. 马桶,是否正常使用
  10. 热水器,是否正常使用
  11. 冬天供暖多少度(集体供暖还是)
  12. 空调制冷情况,
  13. 房产证(是否和房东签合同)
  14. 水电如何收费,怎么缴费(商电民电等,差距比较大)
  15. 暖气费(一般是房东或者中介交)
  16. 天花板是否漏水,这个不要因为不是顶楼就不看,不是顶楼照样漏水!
  17. 设施损坏维修问题
  18. Wi-Fi,空调

根据这几个关键因素,找了两天的房子,终于有点收获,但是前期看房没有效率,耗费了不少的时间。此外,房子的地点需要额外精心挑选,离地铁近能省好多好多事情。。

自如贵一些,服务质量高,但是个人感觉是有溢价的,因此如果自己懂的套路多,又不是很懒,就可以避免。

链家和我爱我家,两大巨头,处理事情方便,房子相对小中介来言靠谱许多。

一些公寓的评论——来自微博和知乎,许多都在讲存在管家态度不好,以及隔音差,维修慢等问题。我感觉这个还是要看付了多少钱。一分价钱一分货,如果价格低,不要奢求太多。