以c的视角来理解c++的多态

2017年3月22日 4,519 人阅读 没有评论

1.概述

c++是一门混合型编程语言,即支持面向对象有支持面向过程,其中又以面向对象为主。c++的三大主要特性:“继承”,“封装”,“多态”中,又以“多态”最难以理解,本文将通过c的视角来诠释c++的多态。

2.动手前的预备知识点

2.1 你知道不同类型的指针意味着什么?

阅读全文…

分类: c/c++ 标签:

分布式内存缓存系统设计

2017年3月19日 2,862 人阅读 没有评论

1.问题

任何平台随着用户规模的扩大、功能不断的添加,持久化数据库层承受的读写压力会越来越大,一旦数据库承压过大会导致读写性能陡然下降,严重时会导致大量的业务请求超时,进而发生“雪崩”引发严重的故障。

2.解决方案

在业务层和数据库持久层之间引入一层内存缓存层,对于复杂且业务逻辑上不会变化的查询结果进行缓存,业务请求再次发起时,每次都先从缓存层中查询,从而大大减少对数据库的查询,减小对数据库的压力。

3.分布式内存缓存、本地单点缓存、应用层缓存对比

类型 稳定性 扩展性 通用性 对代码的侵入性
应用层缓存 应用会频繁重启更新,缓存易丢失,稳定性不佳 差,受限于进程的资源限制 差,不同应用难以复用 代码侵入性小,无网络操作,只需要操作应用进程内存
本地单点缓存 独立的缓存应用(redis、memcached等),不会频繁重启,稳定性一般,但有单点故障问题 一般,受限于单服务器资源限制 一般,业务应用和缓存应用有强耦合 代码侵入性一般,需要引入对应的api通常有网络操作
分布式内存缓存 分布式系统,具备故障恢复功能,无单点故障问题,稳健性佳 好,支持水平扩展 好,对业务层提供通用接口,后端具体的缓存应用对业务透明 代码侵入性一般,需要引入通用的api通常有网络操作

阅读全文…

分类: 通用概念 标签:

手把手教你实现自定义的应用层协议

2017年3月11日 5,731 人阅读 没有评论

1.简述

  • 互联网上充斥着各种各样的网络服务,在对外提供网络服务时,服务端和客户端需要遵循同一套数据通讯协议,才能正常的进行通讯;就好像你跟台湾人沟通用闽南语,跟广东人沟通就用粤语一样。
  • 实现自己的应用功能时,已知的知名协议(http,smtp,ftp等)在安全性、可扩展性等方面不能满足需求,从而需要设计并实现自己的应用层协议。

2.协议分类

2.1按编码方式

  • 二进制协议
    比如网络通信运输层中的tcp协议。
  • 明文的文本协议
    比如应用层的http、redis协议。
  • 混合协议(二进制+明文)
    比如苹果公司早期的APNs推送协议。

阅读全文…

分类: c/c++ 标签:

相比“重要不紧急”的事务什么人们更容易沉溺于游戏之中

2016年8月1日 2,560 人阅读 没有评论

1.为什么会有这样思考

  • 醉心于刷题(最要不紧急)
    前阶段有几天醉心于LeetCode上的面试题,每天下班到家就一直刷题,一直刷到晚上11,12点,这样的状态持续3,4天后,人明显比较疲惫也就没一直坚持下来。
  • 口袋妖怪(游戏)
    Pokemon Go游戏大热,让我这个从来对游戏不太感冒的人,开始玩起了国产的山寨版,并沉溺达10多天,可以起床就玩,即使不再沉溺,也时不时想玩一下。
  • 思考
    有了这两段经历,不禁思考,我们能不能像沉溺于游戏那般去做“重要不紧急”的事。

2.游戏为什么能让人入迷?

阅读全文…

分类: 随想 标签:

LeetCode面试题之删除单链表节点

2016年7月16日 2,842 人阅读 没有评论

1.限制于要求

只给要删除的数据节点的指针,指针不会指向链表尾。

2.思考

正常删除一个链表中的节点我们先要获取要删除节点的前驱节点的指针pre,然后执行pre->next = pre->next->next来把要删除的节点从链表中剔除。其实这里我们可以转换一下思维方式不一定要通过删除节点的方式来删除数据,我们可以通过复制要删除节点的下一个节点的数据到当前要删除的节点中,然后再把要删除节点的下一个节点给删除,就能达到删除指定节点上数据的要求。

3.算法图解

分类: c/c++, LeetCode, 面试 标签:

LeetCode面试题之回文单链表

2016年7月15日 2,148 人阅读 没有评论

1.限制与要求

  • 时间复杂度O(n),空间复杂度O(1)

2.思考

回文最初的概念是应用在字符串上的,比如”abccba”和“abcdcba”都是回文字符串。判断是否是回文字符串的算法也很简单,使用两个下标i、j,i从头开始向后遍历,j从尾开始向前遍历,只要i < j就一直遍历,在遍历过程中如果i和j位置上的字符不相同,则该字符串必然不是回文的并立即停止遍历,如果遍历结束后都没遇到不相同的字符,则该字符串是回文的。

  • 单链表回文难点
    • 我们无法像遍历连续空间那样,直接从尾部向前遍历。
    • 即使解决了逆向遍历的问题,那么如何判断结束遍历也同样是个问题。
  • 一个巧妙的解法
    • 第一个问题:我们把单链表逆序然后再遍历就可以实现从尾部(逆序前的单链表)向前遍历了。
    • 第二个问题:把链表先拆分成left和right两部分,然后只对right部分进行逆序。
    • 最后我们从left头节点和逆序后的right头节点开始遍历,一直往后遍历直到链表尾。
    • 遍历过程中出现不相同的数据则不是回文的单链表,否则就是回文的单链表。

3.算法图解

分类: c/c++, LeetCode, 面试 标签:

LeetCode面试题之删除单链表中倒数第n个节点

2016年7月15日 2,129 人阅读 没有评论

1. 限制于要求

  • 空间复杂度O(1),时间复杂度度O(n)

2.思考

可以使用两个指针来实现,一个cur指针先从链表头往后遍历n个节点,然后一个pre指针(初始为NULL)和cur指针一起在链表中往后遍历直到cur指向NULL,而此时pre指向的就是要被删除的倒数第n个节点的前驱,如果pre为空,则说明要删除的是链表头节点,否则更新一下pre的next指针即可,即pre->next = pre->next->next。

2.1删除链表尾节点

分类: c/c++, LeetCode, 面试 标签:

LeetCode面试题之单链表是否有环

2016年7月13日 2,078 人阅读 没有评论

1.限制与要求

  • 不允许修改链表结构。
  • 时间复杂度O(n),空间复杂度O(1)。

2.思考

2.1判断是否有环

如果链表有环,那么在遍历链表时则会陷入死循环,利用这个特征,我们可以设计这样的算法。

  • 使用一个slow指针,一个fast指针。
  • slow指针一次往后遍历以1个节点,fast指针一次往后遍历2个节点,一直做这样的操作。

    阅读全文…
分类: c/c++, LeetCode, 面试 标签:

LeetCode面试题之两个单链表相交

2016年7月13日 2,029 人阅读 没有评论

1.限制和要求

  • 如果两个链表没有交叉返回NULL,有相交返回相交的点。
  • 两个链表的原始结构不能被修改。
  • 两个链表中都没有环。
  • 算法的时间复杂度要求是O(n),空间复杂度是O(1)。

2.思考

  • 算法1
    • 分别遍历两个链表,记录遍历的节点。
    • 出现重复的节点,就说明两条链表相交。
    • 第一个重复出现的节点就是交点。
  • 算法2
    算法1不能满足空间复杂为O(1)的要求,因为你需要记录遍历过的节点,认真分析后发现如果两个链表有相交那么它们的尾节点必定是相同的。

    • 分别遍历两个链表,记录遍历的尾节点和链表长度,如果两个链表的尾节点相同则说明链表相交。
    • 在两边相交的情况下,如果两个链表的长度不一致,则较长的链表先从链表头遍历n步,n为两个链表的长度差。
    • 长度短的链表从链表头往后遍历,长度长的链表继续往后遍历,直到遍历到相同的节点,而这个节点就是这两个链表的交点。

3.算法图解

分类: c/c++, LeetCode, 面试 标签:

LeetCode面试题之单链表逆序

2016年7月12日 2,471 人阅读 没有评论

1.算法概述

遍历链表,并在遍历的过程中修改当前节点cur的next指针,使当前节点cur的next指针指向当前节点的前驱节点pre,遍历完之后pre指针就是逆序后链表的头指针。

2.图解

分类: c/c++, LeetCode, 算法, 面试 标签: