UNIX环境高级编程学习笔记(上)

2013年4月19日 没有评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

此文作者:冰镇南瓜汁;mail:munantv@qq.com

文件I/O

常用函数:

<fcntl.h>

int open(const char *pathname, int oflag, ... /* mode_t mode */); 

打开或创建一个文件。第一个参数是文件的名字,第二个参数是选项,在O_RDONLY / O_WRONLY / O_RDWR 中选择一个打开的方式,然后可以用或运算指定额外的一些选项(例如O_APPEND写时追加到文件 尾,O_CREAT若文件不存在则创建,O_TRUNC文件截短为0等),第三个参数是创建新文件的访问权限位。返回值是当前最小的未用文件描述符,用于 该文件,出错返回-1。

int creat(const char *pathname, mode_t mode); 

创建一个新文件,等效于 open(pathname, O_WRONLY | O_CREATE | O_TRUNC, mode);

int fcntl(int filedes, int cmd, ... /* int arg */ ); 

改变一个文件的性质。其中cmd的选项包括:F_DUPFD(复制一个现有的描述符,第三个参数为描述符数值的下限)、F_GETFD(获得文件描述符标 志)、F_SETFD(设置文件描述符标志,值为第三个参数)、F_GETFL(获得文件状态标志,可以与O_ACCMODE进行与运算,然后与三种访问 方式标志比较,可以与其他标志进行与运算判断标志位的存在)、F_SETFL(设置文件状态标志,设置为第三个参数,通常先取得现有的标志,然后用或运算 添加标志,用补码的与运算删除标志)、F_GETOWN、F_SETOWN(异步I/O所有权)、F_GETLK、F_SETLK、F_SETLKW(记 录锁)。出错返回-1。
常见的用法:(错误处理略去)val = fcntl(fd, F_GETFL, 0); val |= flags; fcntl(fd, F_SETFL, val);

<unistd.h>

int close(int filedes); 

根据文件描述符filedes关闭已打开的该文件并释放该进程加在该文件上的所有记录锁,成功返回0,出错返回-1。

off_t lseek(int filedes, off_t offset, int whence); 

为一个打开的文件设置偏移量,whence可以取SEEK_SET(距离文件开始处offset字节)、SEEK_CUR(当前值加offset)、SEEK_END(文件长度加offset),成功时返回新的文件偏移量,出错返回-1。

ssize_t read(int filedes, void *buf, size_t nbytes); 

阅读全文...

网页版必应词典功能改进建议

2013年4月4日 没有评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

一直用的是旧版的必应词典,用起来很顺手,对于新版必应词典的建议,个人觉得在用户体验上更多地应该借鉴一下旧版的思路,有选择性保留一些功能亮点,下面说一下相对于新版词典,我选择用旧版的几个理由,或者说旧版让我用起来比较爽的地方:

建议 1)新版应该借鉴旧版的单词对比功能,如图所示,旧版通过标签的拖拽可以实现同义词的对比,一目了然;而新版的同义词无法实现对比,且加载速度感觉稍微逊色于旧版。

建议 2)之所以喜欢旧版,是因为这个产品的细节做的非常好,有一个细节个人很喜欢,就是旧版词典的“查询框”默认是全选待编辑的,如图所示,默认是全选待编辑状态,大大地方便了下一次的查询,可以直接输入新的查询词,而不需要先手动删除历史查询词,再输入新的查询词。对新版的建议就是对此加以借鉴。

建议 3)还有一个细节,建议新版词典引入,就是对于每次查询,旧版都会提供纠错的机会,如果单词的释义有误或用户觉得有更好的释义,尤其是对于句子的翻译,为用户提供发表建议的机会就显得很用心,如图所示是旧版的功能,新版没有,望借鉴

建议 4)建议新版保留旧版的历史查询词功能,这点个人觉得很好。

建议 5)建议有插件可以让词典嵌入到各个浏览器工具栏中,每次就不用找了,直接查询。

阅读全文...

发帖留念--日访问量突破400 & 毕设结稿

2013年3月30日 没有评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

博客现在日访问量稳定在200左右,今天突增到400,不知道是否有什么引起的还是偶然事件,暂时还木有研究,先留帖纪念!(后来发现是利人大师在微博上转发了并查集的文章)

访问柱状图

最近20多天一直在整毕业论文,写了一篇小论文,一篇外文期刊,一篇大论文,刚刚将表格都填完,明天打印,后天交稿;适逢blog访问突增破400,就留帖纪念,吼吼;马上要毕业了!

在论文的致谢词里感谢了很多人,这几年的成长离不开太多朋友的帮助,在这里就不一一列举,谢谢你们了,亲爱的朋友们,我会永远怀念与你们在一起的那种满足感。致谢词的最后放肆了一把,也在这里贴上吧,哈哈

阅读全文...

查找字典中某个公共前缀的所有单词

2013年3月14日 2 条评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

练手,求给定公共前缀的所有单词集合,使用trie树,找到公共前缀后,DFS深搜即可。在Trie树节点中增加一个记录以当前串为前缀的单词个数,可以直接返回公共前缀单词个数。在Trie树类中增加一个存储公共前缀单词的集合指针,存储所求单词集合。

阅读全文...

一个有价值的人

2013年3月6日 4 条评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

人真的是需要经历一些事情才能有所成长,读书、历事、旅行,这些对一个人的视野、心胸真心有帮助,视野开了,心胸阔了,一些事情就能看开了,心也可以静下来去思考一些事了,人也可以慢慢地学着有些许平和了,慢慢学会接受了,学会坦然但不放弃,想明白了,看开了,心情和美。

【2012是成长的一年,2013继续努力吧!】

---------------------------------------------

=> 人的大部分痛苦和不快并不是因为你的境遇,而是因为你的态度。【因为你的态度】

=> 人生是一场与任何人无关的独自修行,这是一条悲喜交加的道路,路的尽头一定有礼物,就看你配不配得到。【一条悲喜交加的路】

=> 有时,我们做出的最艰难的抉择,最终成为我们做过的最漂亮的事。【最终成为最漂亮的事】

=> 人生三大遗憾: 不会选择;不坚持选择;不断地选择。【三大憾事】

=> 爱是点点滴滴,情是一路走过。【爱和情】

=> 我们必须愿意放下头脑中策划好的生活,这样才能拥抱现实中正等待着我们的生活。   ——约瑟夫.坎贝尔【这样才能拥抱现实生活】

=> 如果一个人先从自己的内心开始奋斗,他就是一个有价值的人。     ——白朗宁【一个有价值的人】

==> 1941年,丘吉尔受邀在牛津大学毕业典礼讲话。在校长冗长的介绍后,他悠闲地走上讲台,环视全体学生30秒后,开口说了一句话:“永远,永远,永远不要放弃!” “Never, Never, Never, …give up.” 又重复了一次这句话之后,他就下台了。这是历史上最短的一个毕业演讲。 【Never】

阅读全文...

小米面试题一道:N对括号所有的合法状态

2013年3月6日 15 条评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

给定N对括号,输出其所有的合法的组合状态,例如,N=3,所有的合法状态为:"((()))”, “(()())”, “(())()”, “()(())”, “()()()”

思路:还是深搜DFS的思路,深搜的过程关键在于记录已经用掉的左括号个数和右括号的个数,当用过的左括号个数小于右括号则非法;当二者个数和大于2N则非法;当二者个数相等且数目等于2N则为合法。

代码如下:

#include<iostream>
using namespace std;

#define PAIR 50

char str[PAIR * 2 + 1]; // 设括号对数不超过50, str记录括号组合状态

void DFS_bracket(int n, int left_used, int right_used)
{
	if(left_used == right_used && left_used + right_used == 2*n)
	{
		printf("%s\n",str);
		return;
	}
	if(left_used < right_used || left_used + right_used >= 2*n)
	{
		return ;
	}
	int index = left_used + right_used;
	str[index] = '(';
	DFS_bracket(n, left_used + 1, right_used);

	str[index] = ')';
	DFS_bracket(n, left_used, right_used + 1);
}

void main()
{
	int N;
	scanf("%d", &N);
	DFS_bracket(N,0,0);
}

阅读全文...

微策略笔试题一道:数字序列和为0

2013年3月5日 10 条评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

这道深搜的题目写的我心情好别扭,代码也感觉别扭。希望路过的爱动手的牛牛们指导,不管是代码还是思路方面的建议都行;/握手

题目:序列123...N,N介于3和9之间,在其中加入+、-或者空格,使其和为0。如123456  1-2 3-4 5+6 7 等价于1-23-45+67=0。请问,如何获得所有组合?

我代码的思路就是深搜,处理空格时复杂一些,具体参数见注释。

阅读全文...

兄弟单词 — 两种算法实现

2013年2月28日 2 条评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

兄弟单词这个题目最初见于《编程珠玑》,但是里面给出的方法是最笨的,一般不提倡采用吧;这个题目在之前的百度面试中也遇到过,本文实现两种方法的代码,方法如下:

方案一:使用数据结构 map<key,list>。兄弟单词共用一个签名key,key为单词内部排序后的词条,list存储同一key的单词集合;相对于编程珠玑中的方法,该方法在空间上节省了每个单词一个key的空间;在时间上,不再需要二分查找,O(1)的查找;但是这种方法还可以优化,见方案二

方案二:使用trie树。trie树又称字典树,在面试题中关于“字符串”与“数字串”类型的问题中高频出现,非常实用。对于兄弟单词,兄弟单词公用一个key自不必说,只是trie的节点结构应该多出一个域list,用来存储key对应的兄弟单词;具体节点结构应该为


bool isStr, Node* next[26], vector<const char*> brothers

该方案查询的复杂度为O(L),L为key的平均长度;空间上则有很大的优化,例如单词的key有“abc”、“abcd”、“abcde”之类的形式,则这些key也能达到空间公用,不过数据量大还好,数据量小,trie树开辟的空间还是有些浪费的,不多言,上代码:

【测试用例】


input:

cba acb bc cb b

output:

cba acb

bc cb

b

【方案一:使用哈希map实现兄弟单词】

#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;

#define MAXLEN 100  /* 单词最大长度 */

/* qsort比较函数 */
int charcmp(const void *p, const void *q)
{
	return *(char *)p - *(char *)q;
}

/* 打印输出 & 释放内存 */
void output(map<string,vector<char*>> dic)
{
	for(map<string,vector<char*>>::iterator it = dic.begin(); it != dic.end(); ++it)
	{
		for(vector<char *>::iterator itv = it->second.begin(); itv != it->second.end(); ++itv)
		{
			printf("%s ",*itv);
			free(*itv);
		}
		printf("\n");
	}
}

void main()
{
	map<string,vector<char*>> dic;  /* 存储<key,兄弟单词集> */
	char word[MAXLEN];
	int len = 0;

	while(scanf("%s",word) != EOF) /* ctrl+z结束输入 */
	{
		len = strlen(word);
		if(len > 0)
		{
			char * ptr = (char *) malloc(len+1);
			strcpy(ptr,word);
			qsort(word,len,sizeof(char),charcmp);
			string key(word);
			dic[key].push_back(ptr);
		}
	}
	output(dic);
}

【方案二:使用trie树实现兄弟单词】

阅读全文...

定长线段最多覆盖点的个数

2013年1月5日 2 条评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

来自之前百度一面的题目:给定一系列x轴的点坐标,例如 1,3,7,8,9,11这些坐标升序放在数组中,现在给一根绳子,长度为4,问绳子最多能覆盖的点数有多少,例如绳子放前面只能覆盖两个点,1,3,如果放后面能覆盖4个点。

题目不难,但也不是太容易想出来,两个指针前后跑的思路:两个指针往前走,前面的负责加,后面的负责减,前面的每次都移动,如果点间隔长度大于绳子长度,后面指针移动。

阅读全文...