What is LinkedList? 什么是链表?

LinkedList是一个线性逻辑的结构. 之前有一个国内的朋友要考计算机等级证书, 于是让我给她讲讲什么是链表. 那该怎么给一个非计算机专业的朋友讲清楚呢? 其实现实生活中就有很多链表式的结构, 例如体育老师让一队小朋友重头到尾的报数, 又例如一列火车, 他们都有什么样的特征呢? 链状, 一环扣一环. 那我们下面就用火车来举例:

那我们想想, 一辆火车由什么构成? 是不是一截截的车厢? 那车厢与车厢怎么链接的呢? 是不是由许多链接扣互相扣住的? 那对应的在 LinkedList 里面, 车厢就是 LinkedList 的ListNode 节点, 而链接这些节点的就是每个节点上指向下一个 Node 节点的 Pointer. 车厢里面装了什么东西, 车厢有多少个座位, 或者车厢长宽高有多少, 都对应着 ListNode 的属性, 这个 ListNode 可能有一个 size 的属性, 可能有一个 array 属性表示能放多少东西. 每个 Pointer 则有下一个Node 的地址, 也类似于下一节车厢号, 我们可以顺着这个号码一步一步走到车厢尾. 于是怎么来遍历一个 LinkedList 也就清晰了.

遍历: 每当去坐火车时候, 你到站台后是不是只会站在一个车厢前面, 那你怎么到自己的车厢去呢? 肯定得顺着当前这个车厢一节一节的找下去对吧? 同样的道理, 在 LinkedList 里面, 你往往最开始是站到 LinkedList 的 Header 上面的, 那你怎么找到你要找得 Node 呢, 只有顺着头一步一步, 看看 Pointer 指向的是不是我的Node, 如果是那直接进去就行了, 如果不是呢, 继续穿过这个 Node 找下一个 Node.

增加: 怎么添加车厢呢? 比如 A 车厢指向 B 车厢, 现在你想插一个 C 车厢在 AB 之间, 该怎么做? 是不是第一步要拆开 A-B, 然后把 C的尾巴 跟 B 连在一起, 再把 A 的尾巴跟 C 连在一起. 同样的, 如果给你一个 LinkedList, 第一步是不是得找到 A和 B 节点, 然后按照一样的办法, 把 C 节点插进去.

删除: 好现在 A 在 C 前面, C 在 B 前面, 我想把 C 车厢给推出去, 是不是得把 C 和 B 的扣子解开, 又把 C 和 A 的扣子解开, 然后牵着 A 和 B 的手, 祝福他们爱情恒久.

那有朋友肯定说, 你这样找车厢太慢了呀, 要挨个挨个找, 不能一步就找到吗? 当然有啦, 就像列车员直接告诉你, 车厢在哪你直接去就行了,  我们只需要在雇佣一位 Map 结构”列车员”就行了, 例如 LRU Cache 就能够用这种办法实现.

LinkedList 是一个非常基础却经常用到的数据结构, 那在面试过程中, 往往会有很多题目与之相关, 例如最基本的 Reverse LinkedList, 翻转进阶一点的就是翻转一部分的链表. 还有是 Merge 2 LinkedList 甚至是 Merge K LinkedList.

那除此之外, 在链表题里面, 快慢指针(Fast and Slow pointers)的应用也是非常广泛, 例如下面这道题 LinkedList Cycle,你怎么确定链表里面有一个环呢? 那有环会发生什么? 是不是如果你一直沿着走, 肯定会不断不断绕圈, 那我们利用这个特性, 用很直接的办法, 就是固定一个起点, 然后让另一个朋友一直走, 看到能不能再回到这个起点, 那么就有两个问题了, 一是有可能一直绕呀什么时候是个停呀, 二是固定的起点不一定是在环上呀, 就算我们停了也要重新找一个起点继续绕呀. 这时候快慢指针就派上用场了, 看看下面代码能看出什么鬼吗?

这就是快慢指针的奇妙地方, 那进阶一点的问题, 假如这个链表有环了, 怎么找到环从哪开始的呢?

除此之外, 还有一个解题技巧就是加 Dummy Node, 什么是 Dummy Node 呢? 就是派一个哨兵站岗立一个标杆, 让我每次想对这个链表操作时候我有一个明确的坐标, 例如下面这道题 Remove Duplicates from Sorted List II.

这些小技巧只是帮助你解题更加方便, 或者说提供另一种思路, 但是解决链表题的核心还是在于搞懂链表的构成, 节点与节点之间的链接, 保持增删节点之后链表的一致性.多加练习, 熟能生巧.

各行皆不宜,且行且珍惜 – 知乎问题《有哪些表面光鲜,实际苦逼的职业?》背后的数据

前言

有哪些表面光鲜,实际苦逼的职业?》这个问题在我的知乎 timeline 上面火了几天了,截止该文发出时该问题已经达到 4,100,000 次点击量,7844 人关注,同时共 1307 个回答。作为即将毕业的应届生,家中又有即将高考的妹妹,如何选择职业,如何选择专业,都成了心头萦绕的问题。再将每个答案都细细阅读后,作为码农想对所有答案做一个较为科学的统计,于是对该问题所有答案进行了一次爬取,截止至 8 月 15 日 10:48AM PDT 总共爬取 1058 份答案,以下所有分析数据均来自于该样本。

过程

  1. 因为数据量不大也不需要协调过程需要登录,所以直接用 phantomjs 写了个脚本,数据输出到文本文件。
  2. 写了个 Python 脚本,将每个答案分别分割成句,tokenize,POS Tagging,去掉punctuation,最后去掉 stop words。tokenize 和 POS Tagging 使用了 Jieba 库,stop words 使用了中科院语言所的表
  3. 在此基础上去掉了形容词、状语、动词、以及长度小于等于 1 的词语。
  4. 又写个 Python 脚本 word count 了一下,然后 quick sort 结束。

结果

为了简单直接,我直接采用“如果单词被提及越多次则表示越多人有此答案”的直接原则对数据进行分析,所以以下分析结果的数值均为单词 TF 值。

总体职业抱怨次数饼状图

pie_chart_1024_1024

前20名苦逼职业柱状图

top20_line_1024_102420-50名苦逼职业柱状图

20to50_line_1024_1024

 

总结

冠亚季军的角逐结果倒是很让人吃惊,像银行这种外行人看来“坐着收钱”的,以及老师这种“一年两个假期”的职业能入围前三,看来背后的辛酸估计只有他们自己知道。但是设计师普遍加班熬夜严重早已广为诟病了。排在之后的医护人员、公务员以及警察等作为最广大的与一线老百姓打交道最广的职业,也纷纷表示鸭梨山大,背后的原因值得思考。而学生、皇帝等能排在较高位置估计是灌水比较多吧,而作为程序猿的我看了看程序猿的排名,表示笑而不语,估计各位同行们正熬夜改 Bug 呢,也不会跟轮子哥一样刷知乎。

虽然有些数据结果差强人意,例如一些同职业不同名称的词语应该分为一类,由于需要 NLP 做语意分析或者需要训练模型来分类,所以暂时没有处理;以及点赞数也应该纳入 impact factor 考虑。以上坑后续慢慢再填。总的来说还是能说明一些问题,各行皆不宜,且行且珍惜。总共 3 个小时搞定,撒花!顺便求个美帝地区的码农 full-time job,码农再苦逼也不能阻止我当码农的心!

以上所有工具、数据,若侵犯使用权请予以联系删除。

欢迎转载,转载请注明出处与作者,侵权必纠。

 

 

 

Add watermark with Fresco

Picasso can use transform method to add watermark on the layer of another picture, and in Fresco, there is a class called Processor to handle. But Fresco way is not convenient as Picasso, the transform of Picasso can support chain,but Fresco can not support this chain method,so in there we package the official Processor: