free website counter

Mushsen's Blog


Ubuntu14.04下搭建配置nginx与FastCGI环境

  Nginx不支持外部程序的调用或者解析,包括php程序、python程序都不行,因此业务处理模块的调用,必须通过FastCGI接口来调用。FastCGI在Linux下是socket,为了调用CGI程序,还需要一个FastCGI的wrapper(启动另一个程序的程序),绑定在某个固定的socket。

Read More

基于数组与链表的归并排序算法实现

  这两天在写链表相关的题目,不少数组操作,将数据结构换成链表之后,都会比较难以处理,主要是单向链表,没有了反向的指针,其实数组,可以将其与双向链表对应上。早上在写一个链表归并排序的题目,一直runtime error,很是头疼。故将数组、链表的归并排序递归以及非递归实现,做一个整理。

Read More

Reverse Nodes in k-Group

  给一个链表,每次反转k个节点,如果节点数不是k的倍数,最后剩下的节点不需要反转,只能操作节点,不能改变节点的值,使用常数空间。

   跟昨天做的Reverse Linked List II是一样的思路,即对于每k个节点,看成一组[m, n],Reverse Linked List II只需要反转一组子链表,而这一题需要反转多组。

Read More

Reverse Linked List II

   即给定一个链表,以及两个位置m,n,将从第m个节点到第n个节点的链表进行反转。要求最好是只扫描一次链表,以及in-place去做。比如,对于1->2->3->4->5->NULL, m = 2 and n = 4,反转后返回1->4->3->2->5->NULL

  开始想到的方法是,使用一个栈,从m到n,将节点的值入栈,然后再扫一遍链表,从m到n,再将值依次出栈,更改节点元素值即可。如此,有两个不好的地方,首先,多开辟了存储空间,最坏情况下,需要浪费O(n)的存储空间;再者,需要遍历两次。

Read More

Largest Rectangle in Histogram/Maximal Rectangle

   Leetcode中求面积的两个相对比较难的题目,其中Largest Rectangle in Histogram给定n个元素的数组,每个元素为柱子的高度,宽度均为1,计算柱子组成的矩形的最大面积;Maximal Rectangle给一个二维数组,元素为0/1,找出包含1的最大的方形区域。

  对于第一道题,穷举的时间复杂度为O(n^2),可以通过减枝满足AC的要求;也可以使用栈来优化算法,达到O(n)的时间复杂度。很多需要进行时间复杂度优化的问题都可以通过栈或者是哈希表加以解决;而对于后者,开始想到了纪录一个矩形块的左右边界的方法,但没有具体想明白,可以通过逐层对每个元素,纪录左右边界以及有效高度的方法,类似DP。

Read More
Load More…
分享按钮