美柑の部屋

涙は見せないと誓った。

Loading…

面试常见问题盘点:第k大元素

数组本身结构简单,但是对数组进行操作会涉及到很多经典算法,这使得数组成为了面试中最热门的考点之一。这篇文章就总结一下求数组的第k小/第k大元素,或者中位数的问题。

面试常见问题盘点:链表

链表是面试中经常被问到的一种数据结构,一是因为它实现简单,二是因为它的实现中涉及到指针操作,而一个人对指针操作的熟练程度很能够体现他的C++程序设计水平。这篇文章就来简单地盘点一下面试中经常会被问到的一些链表方面的问题。

Octopress插件:表格

很多Markdown语法都支持在文章中嵌入表格,但是Octopress竟然不支持。为了使得在文章中插入表格更加方便,我开发了一个插件table。在这篇文章中我简要介绍一下该插件的开发流程。

随机查询(三):树状数组

这篇文章介绍了一种叫做树状数组(Binary Indexed Tree)的数据结构,与之前提到的线段树一样,这种数据结构可以解决“求区间内元素之和”的Random Query问题,并且其初始化的时间复杂度是O(n)、更新和查询的时间复杂度都是O(logn)

随机查询(二):线段树

在上一篇文章中,我介绍了解决RMQ问题的ST算法,这篇文章我再介绍一种名为“线段树”的数据结构。所谓线段树,其实就是在求解一个区间所有元素的最大值、最小值或所有元素的和之类问题的时候,用一棵树来维护这段区间及其子区间对应的值。在输入数组经常变化的情况下,线段树比起ST算法更加高效。每当原数组变化后,线段树可以在O(logn)的时间内进行更新(ST算法要进行更新,相当于重新生成一遍Sparse Table,其时间复杂度为O(nlogn)),并且对于每次查询,也可以在O(logn)的时间内给出答案。

随机查询(一):RMQ-ST算法

这篇文章中,我以RMQ问题为例,来介绍随机查询类问题。RMQ是Random Maximum/ Minimum Query的简称,顾名思义,是求解区间最值的问题。假设有一个无序的数组arr(大小为n),给定两个下标lr,让我们求出arr[l]arr[r]之间元素的最大值或最小值(我们称之为一次查询,即query),我们当然可以直接遍历这些元素,然后将结果输出。但是如果query的次数不是仅仅只有一次,而是成百上千次,难道我们每次输出对应结果的时候都需要遍历一遍相应的区间吗?

在自己的博客中加入歌词栏

很久之前我就有将自己喜欢的歌曲分享给别人的梦想,而现在正值我的博客搭建完成,我终于可以通过在博客中加入歌词栏实现我的梦想了。这篇文章就来简单介绍一下在博客中添加歌词栏的流程。

位运算的Tricks

很多初学程序设计的人不熟悉位运算,或者只是听说过名字,没有真正在程序中使用过。实际上,位运算不仅可以大大提升程序的执行速度,而且可以很巧妙地解决一些普通方法无法解决的问题。这篇文章就来盘点几个常见的位运算tricks。