Mac SourceTree免登陆方法

SourceTree是Mac上最好用的git工具,可是最新版本(2.6.3)的SourceTree却需要登录Atlassian账号才能使用,而注册Atlassian账号需要谷歌验证码,由于众所周知的原因,我们无法看到验证码,注册不了,我们似乎只有两个选择,要么各凭本事翻墙,要么放弃使用SourceTree。

上网搜了一下SourceTree的免登陆方法,结果也只搜出Windows下的免登陆方法(未验证),没有Mac的,试着学着Windows的方式在Mac的~/Library/Application Support/SourceTree/目录下新建相应的json文件,无效。

试着折腾了下,无意中发现了一个方法可以绕过mac的登录,方法如下:

打开SourceTree -> 点击菜单栏的 窗口 选项 -> 点击显示托管在远端的仓库 -> 点击登录注册页面右上角的关闭按钮 -> 点击Quit -> 点击确定关闭刷新远端仓库失败的窗口 -> 即可正常使用SourceTree了

虽然此方法可以绕过登录,但是每次打开SourceTree都需要操作一次,略烦,而且指不定哪个版本此bug就给修复了,有需要的最好还是凭本事翻个墙吧。

好玩的shader制作分享

前几天无聊随便写了几个shader来玩,觉得跳动的心和跳动的名字还是挺有趣的,做个代码分享吧。

跳动的心fragment shader:

 

跳动的名字跟跳动的心思路是一样的,不一样的地方是使用了图片来做mask命中判断,并抠掉了原来图片像素所在的颜色。

跳动的名字fragment shader

 

STL揭秘之外覆器integral_constant

首先上代码:

代码很简单,它只做了几件事:

  1. 定义了一个_TP类型的value成员变量并赋值为__v
  2. 用typedef声明了value_type和type
  3. 重载了value_type和()操作符

使用起来就像下面这样:

它其实就是一个常量包装类,看起来它似乎没什么用,比直接使用常量繁琐多了,那么我们究竟可以用它来做啥呢?

实际上对于模板元编程来说,它的用处可大了,在STL里面到处都是它的身影,我们来看一下type_traits里面定义的非常重要的两个integral_constant类型:

true_type即是常量true的包装类,false_type即是常量false的包装类。它们跟原来的常量最大的区别就是它们是类类型,我们可以通过继承来使用它们,例如:

到目前为止还是挺无聊的,但是我们别忘了,模板元编程是拥有编译期选择的特性的,接下来就开始变得有趣起来了:

我们通过简单的几行代码就实现了编译期两个类型是否一致的判断,下面我们就可以来尝试一下:

我们再来看下is_integral的实现:

我们现在可以在编译期判断一个类型是否为数值类型了呢,是不是很有趣!

它的用法还不止这些,还记得我们上一篇STL揭秘之编译期纯虚类判断__is_abstract_imp吗,实际它的完整实现是这样的:

is_abstract继承了__libcpp_abstract,__libcpp_abstract做了一次偏特化,当is_class<_TP>::value为false时它继承的是false_type,为true是它继承的是integral_constant<bool, sizeof(__is_abstract_imp::__test<_Tp>(0)) != 1>类型,并且它通过sizeof(__is_abstract_imp::__test<_Tp>(0)) != 1的编译期判断来动态的选择继承的是integral_constant<bool, false>还是integral_constant<bool, true>,于是,我们就能够使用is_abstract来在编译期判断一个类型是否为纯虚类了:

type_traits在基于integral_constant上还做了非常多的编译期判断实现,例如is_const,is_function,is_enum,is_member_pointer,is_member_function_pointer等等,有兴趣的小伙伴们也可以去看一下:)

 

STL揭秘之编译期纯虚类判断__is_abstract_imp

首先列上代码:

__is_abstract_imp命名空间里声明了两个重载的模板函数,返回值分别为char和__two。声明这两个函数的意义在于,我们可以通过编译期重载函数的匹配来判断传入的模板参数是否符合我们的要求,判断的方式也很简单,只要使用sizeof操作符就行了:

上行代码的含义也很简单明了,即匹配第一个重载函数时,sizeof的结果为1,匹配第二个重载函数时sizeof的结果为2,所以我们就实现了编译期的类型判断。

那么,我们就需要进一步理解为啥通过这两重载函数可以判断出一个类类型是否为纯虚类,即何时_Tp (*)[1]会匹配成功。

_Tp (*)[1]这写法乍一看会让人感到莫名其妙,也很容易让人联想到是否跟类的虚函数表有关(我就在这卡了很久),实际上并没有那么复杂,我们只要将它换种写法一切就豁然开朗了:

参数p不就是一个指向_TP类型的数组的指针(即数组指针)吗,前面的写法只是省去了参数名而已。。。。理解起来就是下面这样:

后面的[1]代表的是指向一个只拥有一个元素的数组的指针(所以如果你将其改成0,会造成编辑器的警告,因为定义了一个指向0个元素的数组的指针)。

那么接下来就很好理解了,因为纯虚类无法实例化,所以我们无法定义一个纯虚类对象的数组(注意不是纯虚类对象指针的数组,即是TP  a[1],不是TP* a[1]),所以在遇到纯虚类时第一个重载函数匹配会失败,而遇到非纯虚类第一个重载函数却能匹配成功,所以我们现在就能够通过这个模板来判断传入模板参数的类型是否为纯虚类类型了。

到这里,有的人可能还会有疑问,为什么我们需要这样写呢,写成下面这样不行么,不是一样也能判断模板的参数类型么,而且还更好理解:

实际上这并不是stl在故意炫技,我们需要注意的是sizeof的写法:

即sizeof在计算函数返回值大小的时候必须给函数传入一个参数,并且我们需要让sizeof的计算发生在编译期而非运行期,我们是不可能创建一个_TP对象传进去的,也就是说这里__test最理想的参数就是指针了,我们只需要传入0作为参数就可以了,所以这里最好的参数选择就是指针数组了。

最后,感谢同事给的思路启发,摸摸哒:)

面试官心得

最近我负责的项目需要招人,有幸做了公司的首轮技术面试官,从第一次人事突然袭击的毫无准备,到现在面试了十几个人,也渐渐的有了一些自己的思考和心得,遂做个分享。
通过个人简历和短暂的面试来筛选一个合适的人才是个很艰巨的任务,特别对于一个程序技术岗位来说,通过短时间考察出一个人的技术实力和技术潜力也是一件很难的事。

首先,我们需要明确公司想招的岗位需求,薪资定位,岗位缺口情况,以及公司长期的用人需求和人才培养计划,从而在心里上确定对一个候选人的需求和门槛,这样才能避免仅从个人喜好上出发来筛选候选人,过滤掉一些虽然不是很优秀但符合岗位需求的人选,或者招到不是太适合目前岗位的人才,造成高不成低不就或者人员不匹配的情况。

其次就是笔试题的设计了,我觉得一份好的笔试题必须满足以下几个条件:
1. 必须充分结合岗位的需求,包含适量的基础题和部分的难题,能够尽量的对候选人有个彻底的技术摸底,避免全是基础题候选人只要通过适当的准备和背书就能完成,或者难题过多并且难度跨度过大导致没法摸出候选人的真实水平。
2. 尽量贴合实际的岗位需求出题,题目尽量是工作中经常遇到和可能出现的问题,能够考察出候选人实际工程水平和熟练度。
3. 不要剑走偏锋,虽然有时候出一些偏门的题目会获得惊喜,但是面试不是为了考倒别人,而是为了筛选出真正合适的人才,一些偏门的难题最好一题都别出。
4. 最好能结合一两题的思考题和程序基础题,这里最合适的题选就是算法题了,虽然算法在工作中用不到,但是一些不难的算法题有利于考察出候选人对自己职业的态度,能够看出他究竟仅仅把程序当做一份糊口的工作,还是怀有热情愿意去做更深入的学习和研究。
5. 题目来源的问题。网上的题目虽然可靠,考量点一般都比较合适,但是很容易通过短期适当的准备被候选人命中,考量不出候选人真实的水平,所以最好能参入些自己出的题目。
6. 题目类型的考虑。题目类型最好大部分都是问答题,再补充上一到两题的编程题考量下候选人的编程习惯和思维能力。
7. 题量的考虑。题量上完成时间最好在一小时左右,一方面不会太多造成候选人的反感,另一方面也不会因为太少导致筛选困难。在这个基础上我觉得还可以从多个方面出题,题目在岗位需求内覆盖的范围广泛些,让候选人自己选出会做的题来做,然后按照候选人能够答出40%左右的题量来估计时间, 这样的好处是能够更全面的考量候选人的综合技术实力。

再就是阅读简历,我拿到简历的时间一般是在去见面试人的时候,给我阅读简历的时间并不多,一般我会在见到面试人的时候让他做个自我介绍考察一下他的工作经历和表达能力的同时来阅读简历。简历我一般重点考察以下几个方面:
1. 工作年限和相关工作经验,对候选人的能力有个大概的预期。
2. 个人能力和擅长技术,能够大致明白他的能力范围。
3. 公司履历,每家公司的时长以及所在岗位,能够对他以往的工作职责,能力和目前所需职位的匹配度有个预期。
4. 项目经验,所在项目的团队大小以及在项目起到的作用,进一步对候选人的能力和职位匹配度有个预判。

然后就是实际面试了。面试的流程和内容我一般会分成以下几个部分:
1. 自我介绍,考量候选人的表达能力和过往经验,不过这部分的表达能力考量并不是关键,因为候选人同样可以通过背书来完成,所以重点关注的是他过往的公司和项目经历,同时跟简历对照一下看看是否有所出入和没说详细的地方。
2. 过往项目经历的了解。对候选人项目经历做进一步的了解,有带具体项目的可以拿来看看,让候选人介绍下具体功能和哪部分是他做的,以及深究一下简历没有说详细的部分。
3. 笔试题目的审核,看一下候选人的答题情况以及顺便在面试题的基础上提一些深入的问题或者问一些候选人没有回答仔细的问题。
4. 结合候选人的项目经验问一些基础题和项目相关问题,了解候选人具体的项目经验和工程应用能力,以及进一步挖掘候选人实际的项目经验。
5. 结合候选人的实际能力问一些比较难但不偏门的原理性问题,比如对Java和Android熟悉的可能会问Java虚拟机的运行机制或者Java虚拟机的GC机制的问题,UI做得多的会问具体UI框架结构和响应机制等问题,Android方面会问安卓源码相关的问题,这部分考察的是候选人是否对他从事的相关项目有过深入的研究,理解和思考,是否有认真的对待自己的工作,以及进一步考察候选人的思维能力和表达能力。
6. 计算机基础题,主要考察的是数据结构和算法,可能会包含部分的操作系统原理,这部分科班出身的比较有优势,这部分考察的是候选人是否对编程有热情,对计算机有过全面的了解,以及他是否具备这样的能力。
7. 逻辑题,考察候选人解决实际问题的能力,这部分我最喜欢用的是腾讯的一个面试题,”从1亿个整数中找出最大的100个数“,这题看着很吓人,实际上并不难,在候选人回答不上来时还可以一步步的分解成”从1000个整数找出最大的1个数“,”从1亿个整数中找出最大的1个数“,”从1000个整数找出最大的100个数“来引导候选人回答,考察候选人是否有最小堆和最大堆的概念,考察候选人对算法复杂度的理解,考察候选人是否有好的程序思维能力。
8. 开放题,考察候选人思维敏捷程度,候选人的思维习惯,候选人的处理问题的能力,以及候选人是否能清晰表达自己的思维,比如问”在工作中和生活中有遇到过什么难题,你是怎么解决的“,”你工作中有什么好的工作习惯“,”你平常怎么安排你的时间“,”假设你在人烟稀少的山路遭遇暴雨,你会怎么做“等问题。这部分问题还可以进一步的问下去,至于问到什么程度就自己把握啦。
9. 职业规划和发展方向,看候选人是否对自己的职业有比较明确的想法和规划,以及他对目前公司提供给他的岗位是否有更多的想法,还有候选人对自己目前能力和技术的定位和认知。我多多少少也会给他们一些建议。
10. 当然少不了最后的问答环节,我对这部分没什么多的想法,主要只是给候选人一个了解公司和职位的机会,毕竟是双向选择。

实际面试的内容我会根据面试的实际情况做一些调整,有时候适当的让候选人去把控面试的节奏也是可以的,我觉得只有能够让候选人充分展示自己实力的面试才是一场好的面试,而非一板一眼的按照自己的节奏来。另外,我不太喜欢现场考察手写编程,我觉得这部分放在笔试部分才是合理的,面试时候由于时间和气氛的紧张程度,手写编程往往考察不出候选人真正的实力。虽然我作为面试官,尽量缓和面试气氛也是我职责的一部分,但毕竟自己是处于一个心理优势地位,给予过多压力的面试方法我觉得对候选人并不是很公平。

总的来说,面试是为公司筛选人才的过程,这些想法也是通过我自己以往实际的面试经历和以往看过的面试他人的经验总结帖结合自己的思考得出,有什么考虑不周或者错误的地方也欢迎大家提出来:)

个推ios测试步骤

最近被这个整烦了,做个记录。

先是上苹果官网登陆开发者账号,找到APPID,开通Development的Push Notifications

创建Certificate

生成证书请求文件

下载授权文件

导出p12证书文件

登个推官网登记应用上传证书和输入导出时填写的密码

记得开启xcode项目中的Push Notification

编写个推相关代码,并且根据上面个推网站给的数据输入个推的相关配置。

获取ios推送的token并打印。

 

到个推网站的应用配置下输入刚才打印出来的token,点击确认就能收到个推的推送消息了。

红黑树详解

最近在教同事学习红黑树,于是想用自己的语言归纳一篇讲解红黑树的文章,运用下费曼学习法,巩固自己的知识。

闲话少叙,开始吧。

开始前,你需要先了解下二叉树二叉搜索树平衡二叉树的概念,这里就不展开了。

  • 定义

能满足以下5个性质的二叉搜索树才能被称为红黑树:

  1. 每个节点都有一个颜色,要么是红色,要么是黑色。
  2. 根节点为黑色。
  3. 每个叶子节点(为NIL的节点)均为黑色。
  4. 红色节点的左右子节点均为黑色。
  5. 从任一节点出发到其后代任一叶子节点的简单路径上的黑色节点个数均相等。

注意,红黑树的叶子节点均为NIL节点,除去叶子节点的其他节点可称为内部节点

 

一棵红黑树(图画不好,见谅)

  • 证明

我们需要证明下为什么满足了上述条件的红黑树是一棵好的二叉搜索树。

因此,我们需要证明如下定理:

一棵拥有n个内部节点的红黑树的最高高度为 2*lg(n+1)。

要证明这点,我们先来了解下黑高的定义。从任一节点x出发,从x到其后代任一叶子节点的简单路径上的黑色节点个数(不包含x)即是以x为根的子树的黑高(根据性质5可知从x到其后代任一叶子节点的简单路径上的黑色节点个数均相等),可表示为bh(x)。

然后,我们来证明一下,以任一节点x为根的子树至少包含2^bh(x)-1个内部节点。

我们运用数学归纳法,假设x为NIL节点,则它的子树至少包含2^0-1=0个内部节点。假设以x为根的子树高度为1(即x的左右子节点均为NIL),而它的子树至少包含2^1-1=1个内部节点。假设以x为根的子树的黑高为bh(x),则它的左右子树的黑高则为bh(x)(子节点为红色)或bh(x)-1(子节点为黑色)。根据归纳法假设x的左右子树至少包含2^(bh(x)-1)-1个内部节点,则x最少包含的内部节点个数为2*(2^(bh(x)-1)-1)+1 = 2^bh(x)-1个内部节点。得证。

根据性质4得知,从任一节点x出发,从x到其后代任一叶子节点的简单路径上的黑色节点个数最少为所经过的节点个数的一半(不包括x),所以,假设红黑树的高度为h,则红黑树的黑高最少为h/2,于是有:

n >= 2^bh(x)-1 >= 2^(h/2) – 1

方程式转移后可得:

h <= 2 *  lg(n + 1)

得证。

所以,通过此定理结合二叉搜索树的时间复杂度计算可得,红黑树的增、删、查均可在o(lgn)时间内执行。所以它是一棵好的二叉搜索树。

好了,目前理论证明已经有了,接下来我们就需要来构建这样一棵红黑树,并保证在增、删的时间复杂度在o(lgn)的同时,红黑树的性质不会被破坏。

  • 旋转

    在继续学习红黑树之前,我们需要先来学习一下旋转的概念。旋转分为左旋和右旋,如下图所示:

(a)

(b)

我们先来回顾一下二叉搜索树的性质,二叉搜索树的性质可以描述为:二叉搜索树是一棵二叉树,并且对于二叉搜索树的任一节点x来说,位于x左子树上的所有节点的关键字的值均比x节点的关键字的值小,位于x右子树上的所有节点的关键字的值均比x节点关键字的值大。

左旋或右旋操作并不会破坏二叉搜索树的性质,我们来考虑左旋操作。观察图(a),我们用圆形和小写字母表示节点,用三角形和大写字母表示子树。我们可以观察到以下几个变化:

  1. b从a的子节点变成了a的父节点的子节点。
  2. a从b的父节点变成了b的左子节点。
  3. B子树从b的左子树变成了a的右子树。

接下来我们来分析下左旋对二叉搜索树的性质的影响。从二叉搜索树的性质我们可以得知,对于任一节点x,位于x左子树上的所有非空节点的大小均比x小,位于x右子树上的所有非空节点的大小均比x大。从左旋操作引起的变化上来看,变化1对二叉搜索树的性质无影响;变化2由于节点a大小比节点b小,所以也不会引起二叉搜索树的性质的变化;变化3由于B子树上的节点大小均比节点a大,也不会引起二叉搜索树的性质的变化;所以综上所述,左旋操作对二叉搜索树的性质无影响。

通过类似的推理,我们同样可以得到右旋操作对二叉搜索树的性质无影响的结论,这里就再不叙述了。

以下是代码实现:

不难看出,旋转过程的时间复杂度为o(1)。

  • 插入

    红黑树的插入操作的过程跟二叉搜索树的插入操作是类似的,只不过在插入之后我们需要考虑红黑树的性质是否被破坏以及对红黑树性质的修复过程。

首先是插入过程,插入过程即是新元素循环下降的过程。通过对新增元素关键字跟当前节点关键字的比较,决定是将新增元素向当前节点的左子树还是右子树插入(左小右大),并从根节点一直循环下降到叶节点(即NIL节点),最后查找到的叶节点即是我们需要插入的位置。

 

代码解释:root为RBTree的成员变量,指向红黑树的根节点,当树为空时root指向nullptr。

插入过程完成后,我们再来考虑性质修复的过程。首先我们默认将新建节点标为红色。这么做的好处是,排除掉根节点为空的情况(该情况下直接创建黑色节点并将根节点指针指向该节点就完成了),我们只可能会破坏的红黑树的性质只有性质4,即红色节点的左右子节点均为黑色。并且我们只需要考虑新增节点的父节点为红色的情况(父节点为黑色时新增节点并不会引起红黑树的性质被破坏)。所以,在一开始,我们需要修复的位置就是该新增的节点位置。

我们需要理解的是,红黑树修复的过程是一个循环向上的过程,在每次循环的开头,我们都需要保证当前需要修复的节点x的左右子树均能满足红黑树的性质,并且只有节点x破坏了红黑树的性质。即该while的循环不变式为(即在while循环的条件成立时开始的状态):

  1. x节点为红色。
  2. x节点拥有父节点并且父节点为红色(即破坏了性质4)。

注意该循环递归式还有可能造成性质2的破坏,然而我们并没有考虑性质2被破坏的情况,我们可以直接在修复函数的末尾将根节点标记为黑色来防止性质2被破坏的可能性。

在循环的开头,我们将我们可能遇到的情况分为6种,并对它们分别处理。并且我们将x处于x的爷节点的左子树还是右子树上将6种情况分为左右对称的两个类别(注意x的父节点为红色,故x的爷节点必定存在)分别进行分析,我们先来看x处于爷节点左边的情形:

  1. x的叔节点y为红色(注意该情况下左右两类别的处理方式相同,故可合并处理)。
  2. x的叔节点为黑色并且x为x的父节点的右孩子。
  3. x的叔节点为黑色并且x为x的父节点的左孩子。

具体情形和处理方式如下图:

(1)

(2)

(3)

下面我们来具体分析。

对于情况1,我们将x的父节点b和叔节点c均变为黑色,将x的爷节点d变为红色,并且把x指向爷节点d。

经过该轮处理我们可以看出,该子树的性质被修正了,并且经过该子树到根节点的简单路径上的黑色节点个数没有被改变。并且我们可以看出,此时红黑树的性质要么被修复了(x的父节点为黑色),要么破坏了性质2(x为根节点),要么进入了下轮循环不变式的6种情形(x的父节点为红色)从而进入了下一个循环。

对于情况2,我们对x的父节点b做了一次左旋,并把x指向了b。

经过该轮处理,我们将情况2变成了情况3,我们可以直接进入情况3的处理。

对于情况3,我们把x的父节点a变成黑色,x的爷节点d变为红色,并对x的爷节点做了一次右旋。

经过该轮处理我们可以看出,该子树的性质被修正了,并且经过该子树到根节点的简单路径上的黑色节点个数同样没有被改变。同时,我们将该子树的根节点变成了黑色,故该红黑树的性质被修正了,此时我们可以放心的跳出循环了。

左边的3种情况至此就处理完毕了,右边的3种情况可以根据左边的处理方式做镜像处理,就不再一一分析了。

代码如下:

修复过程的时间复杂度是o(lgn),并且一般都能在3次循环以内完成性质的修复,这里就不展开分析了。

最后我们来回顾一下红黑树插入过程的思想。首先是按照平衡二叉树的插入方式进行插入,然后对红黑树可能被破坏的性质以及可能被破坏性质的位置进行分析,最后通过从底向上的方式一步步修复红黑树的性质。同样我们可以将该思想运用在节点的删除上,具体请参考下一节内容。

  • 删除

红黑树的删除过程同样跟二叉搜索树的删除过程是类似的,但同样也需要考虑修复过程。

删除首先需要查找到需要删除的节点,查找的过程很简单,根据二叉搜索树左小右大的过程依次向下查找就行了。

删除的过程需要分成四种情形,将要删除的节点没有孩子的,只有左孩子或者只有右孩子的,以及同时拥有左右两孩子的。

没有孩子的节点直接删除掉就可以了;只有一个孩子的,在删除掉该节点后,将该节点的孩子连到该节点的父节点下;同时拥有两个孩子的会比较麻烦些,需要找到大于该节点的最小关键字的节点y,用节点y替换该节点,同时还需要将y的右孩子连接到y的父节点的左孩子上(y没有左孩子)。如下图所示:

删除节点22的过程

接下来,我们需要分析下删除操作对红黑树性质的影响。

在删除没有孩子的节点n时,如果n是红色,删除后对红黑树性质无影响;如果n为黑色,则在经过n原先所在位置的NIL节点的简单路径上比其他简单路径少了一个黑色的节点,即性质5被破坏了。

在删除只有左孩子或右孩子的节点n时,如果n为红色,同样对红黑树性质无影响。如果为黑色,则在经过n原先所在位置的节点的简单路径上比其他简单路径少了一个黑色的节点,同样性质5被破坏了。

在删除两个孩子的节点n时,我们可以采取这样的策略:将移上去的y节点改为节点n的颜色,这样我们缺少的就是y原先所在位置的节点的颜色(即y原本的颜色),即当y原本为红色时,删除后对红黑树性质无影响;如果y原本为黑色,则在经过y原先所在位置的NIL节点的简单路径上比其他简单路径少了一个黑色的节点,同样也是性质5被破坏了。

综上所述,我们只需要按上面的分析确定需要修正的位置以及需要修正位置的原本的颜色是否为黑色就可以开始我们的修复过程了。需要注意的是,修正的位置可能为NIL节点,如果我们没有使用特殊节点来表示NIL节点的话,我们需要在此位置为NIL时补上一个辅助的NIL节点来执行修正过程,因为该辅助节点始终都处于叶节点位置,我们只要在修正结束后将该节点删除就可以了。

删除函数的代码实现如下(其中Transparent函数的作用为用后一个节点的子树替换掉前一个节点的子树所在位置,FindMin函数的作用为找到传入节点的子树的最小节点):

接下来我们来分析下修复的过程。

由于经过待修复x节点到达叶节点的简单路径上均少了一个黑色节点(性质5被破坏),我们的修复策略就可以制定为:要么我们在经过x节点的位置上补充上一个黑色节点恢复红黑树的性质,要么我们把x的兄弟节点为根的子树上减去一个黑色节点,并把修复位置往上移,直到待修复节点循环向上推到根节点为止(这样该红黑树的黑高减少了1)。

那么当x为红色时,我们就可以将x上色为黑色来补充缺失的黑色节点来恢复红黑树的性质,当x为黑色时,我们才需要考虑如何循环向上去修复它。因此我们的循环不定式为:

  1. x节点为黑色并且存在父节点。
  2. 经过x节点的简单路径上缺少了一个黑色节点(即破坏了性质5)。

我们可以将待修复的子树状态分为8种情况,根据x为其父节点的左右孩子分为两个对称的类别,同样我们来考虑x为其父节点左孩子时的4种情形:

  1. x的兄弟节点w为红色(这里的隐含条件为,x的父节点以及w的左右子节点均为黑色)。
  2. x的兄弟节点w为黑色并且w左右子节点均为黑色。
  3. x的兄弟节点w为黑色并且w的左节点为红色,右节点为黑色。
  4. x的兄弟节点w为黑色并且w的右节点为红色。

注意,由于在循环不定式中,x为黑色并且经过x节点的简单路径上缺少了一个黑色节点,可以得知,x的兄弟节点不可能为空。

4种情形和处理方式如下图所示。

(1)

(2)

(3)

(4)

下面来具体分析:

对于情况1,我们将x的父节b点标为红色,兄弟节点c标为黑色,然后对节点b做一次左旋。

该操作没有更改相应子树上的黑色节点个数,只是将x的兄弟节点变成了黑色,转换成了2,3,4情形中的一种进入下一次循环。

对于情况2,我们把x的兄弟节点w标红,并把x指向其父节点。

该操作减少了x的兄弟w子树上的一个黑色节点,从而使x和w在该层的性质被修复了,于是将x的位置上移,根据x的颜色进入下次循环(黑色)或者结束循环(红色)。

对于情况3,我们把x的兄弟节点w标红,把w的左孩子标黑,并对w节点做一次右旋。

该操作没有更改相应子树上的黑色节点个数,只是把x的兄弟节点的右孩子变成了红色,转换成了情况4进入下一次循环。

对于情况4,我们把x的兄弟节点c变为x的父节点b的颜色,把节点b染黑,节点e染黑。

该操作往该子树c的右子树的节点a上添加了一个额外的黑色节点,从而恢复了红黑树的性质,跳出循环。

至此4种情况都分析完毕,右边的4种情况同样为左边的镜像,所以就不分析了。

删除修复代码如下:

删除修复操作的时间复杂度同样为o(lgn)。

  • 代码

最后献上我个人的红黑树实现代码:

https://github.com/boyu0/ACM/blob/master/ACM/redblacktree.cpp

费曼方法

偶然的机会通过scotthyoung大神了解到了费曼方法,感觉挺有用的,同时也了解了下Richard Feynman的生平,以及那本耳熟能详的《别闹了,费曼先生!》,真是个风趣幽默的物理学家呀。不过我没有找到Richard Feynman提出费曼方法的可信来源。

闲话少说,现在我就通过费曼方法来向大家介绍一下费曼方法是什么。

以费曼方法学习,你需要遵循以下几个步骤:

  1. 你想学习一个概念,首先你需要将这个概念写在纸上,然后认真的学习并理解它。
  2. 假想你需要向一个不懂该概念的人来介绍这个概念,尽量运用通俗易懂的语言以及你以往学过的学识来介绍它,并写到纸上。
  3. 当你在介绍的过程中卡壳的时候,再回到书上,找到你卡壳的地方再认真的学习理解一遍,直到你能够运用你的语言介绍它为止。
  4. 简化你的语言,使你的语言更加的通俗易懂。

我觉得这个方法高效的地方在于,它让我们能够摆脱对新学知识似懂非懂的状态,虽然看起来是更繁琐了,然而这样却能够帮助我们更加熟练和牢靠的掌握一门技能,摆脱学了忘,忘了学的恶性循环,所以最近我也很热衷于教别人一些我掌握了的程序知识,帮助他人的同时巩固自己。

USACO rockers

描述

你刚刚继承了流行的“破锣摇滚”乐队录制的尚未发表的N(1 <= N <= 20)首歌的版权。你打算从中精选一些歌曲,发行M(1 <= M <= 20)张CD。每一张CD最多可以容纳T(1 <= T <= 20)分钟的音乐,一首歌不能分装在两张CD中。

不巧你是一位古典音乐迷,不懂如何判定这些歌的艺术价值。于是你决定根据以下标准进行选择:

1.歌曲必须按照创作的时间顺序在所有的CD盘上出现。(注:第i张盘的最后一首的创作时间要早于第i+1张盘的第一首)

2.选中的歌曲数目尽可能地多。

格式

PROGRAM NAME: rockers

INPUT FORMAT:

(file rockers.in)

第一行: 三个整数:N, T, M.

第二行: N个整数,分别表示每首歌的长度,按创作时间顺序排列。

OUTPUT FORMAT:

(file rockers.out)

一个整数,表示可以装进M张CD盘的乐曲的最大数目。

SAMPLE INPUT

SAMPLE OUTPUT

翻译来源:http://www.nocow.cn/index.php/Translate:USACO/rockers

 

解析:

此题是很经典的01背包问题变种,需要你对01背包解法做一些变通,这类型的题目有很多,比如有N个抽屉,需要放入M个物品等等,以后遇到这种题目就不怕不怕啦。。。。

具体思路代码注释里写了,具体参考我的代码吧。

 

 

Lua源码解析

用Lua也有3年多时间了,对这门语言感情挺深的,特别最近一年时间基本都在用Lua,对Lua这门语言也算了解得比较深了,喜欢它的简洁高效,虽然有一些瑕疵,比如没有好的编辑器,调试困难,没有continue等等等等,但瑕不掩瑜,Lua作为一个简洁高效,易学易用的脚本语言,在语言流行排行榜上时不时还是会出现它的小身影的。

记得我第一次接触Lua,就被它的简洁高效给震惊到了,仅仅几千行的代码,几百k的大小,是如何完成这么复杂的Lua虚拟机系统的呢?相比其他语言动辄几十上百m的大小,复杂的环境配置,Lua简直简单得不能再简单了,从那时起,我就萌生了一探究竟的想法。

由于懒癌发作,直到最近才认真的啃下了编译原理这本书跟Lua的源代码,它的优雅与简洁一如所料,让我有点欣喜若狂,于是我新建了一个github目录,陆续给Lua源码做一些中文注释,一来加深学习,二来也给有心阅读Lua源码的一些小伙伴们一些帮助,也欢迎大家来和我一起学习交流。

github的地址为:https://github.com/boyu0/LuaLearn

代码是基于目前Lua最新版本5.2.3的,目前也只有lstring,ltable,llex等少数几个文件的注释,我还会陆陆续续添加的。另外后续我也会考虑写一些相关解析的文章,不过我对编译原理的了解很浅,写得不好就请大家多多包涵了~