notice
...
2015年6月24日 | 分类: 日志 | 标签:

题目:

Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

其实一开始并没有看出来最优解,网上搜索到答案才知道的:

最优解法非常巧妙,利用了常见的”双指针”法, 两个指针一个指向最前,一个指向最后, 然后 “数值小”的指针向里运动, 这里利用了”水桶的容积只取决于最短的那个木板”的原理!,最终把复杂度降到了O(n)

container-with-most-water-400x161

不过我想了半天才明白了为什么如此移动指针的方法可以确保能够遍历到容积最大的组合:

1.整个搜索过程可以理解为遍历水桶的宽度从n-1到1,只要遍历到每个宽度的最大容积组合就可以保证得到正确的结果。

2.假定ax是a1~ax里最大值,ay是ay~an里的最大值,可以推断出宽度为y-x的水桶组合里,x~y的容积是最大。因为水桶的容积只取决于最短的那块木板,宽度确定的情况下,无论这个组合左移或者右移都无法使得最短的那块木板长度增加。

3.假定ax是a1~ax里最大值,ay是ay~an里的最大值,宽度w=y-x (即第x块木板不低于所有左侧的木板高度,第y块木板不低于所有右侧的木板高度)

先假定ax<=ay,i是满足ax+i>ax的最小值,即第x+i块木板是第x块木板右边第一个更高的木板,由水桶原理可推断出所有宽度小于w但大于w-i+1的组合不可能比当前组合的容积更高(因为ax是a1~ax+i-1里的最大值,ay>ax,宽度减小但是较短的那个木板高度不会变的更高),此时x+i~y的容积是有可能超过x~y的容积,需要计算来判断。

同理如果ax>ay则从y往左找到第一块更高的木板。

4.从宽度n开始,根据3即可找到最大的容积。即,每次移动两侧较低的那块木板向另外一侧,直到该木板的高度高于移动前的高度,然后比较是否大于当前找到的最大容积。

 

下面是我的代码供参考:

#define MIN(x, y) ((x) > (y) ? (y) : (x))

int maxArea(int* height, int heightSize) {
	int lh = height[0], rh = height[heightSize - 1];
	int l = 0, r = heightSize - 1;

	int h, max_area;
	max_area = 0;

	while (l < r)
	{
		int area = (r - l) * MIN(height[l], height[r]);
		if (area > max_area)
			max_area = area;

		if (height[l] < height[r])
		{
			h = height[l];
			while ((height[l] <= h) && (l < r))
				l++;
		}
		else
		{
			h = height[r];
			while ((height[r] <= h) && (l < r))
				r--;
		}

	}

	return max_area;
}
2013年7月11日 | 分类: 日志 | 标签:

本文来源于《程序员修炼之道——从小工到专家(评注版)》,文章作者蔡学镛。

务实的哲学

务实的程序员需要具备特定的态度、风格、哲学,特别是以下六点。

(1)有格局的眼光:务实的程序员不只将眼光放在目前的问题与解决方案上,而是会看的更远,了解环境背景,这么一来,便能做出更好、更正确的决策。

(2)富有责任感:务实的程序员负责人,决定要做某件事之前一定会想清楚,并念及自己的能力与事情可能存在的风险。一旦他接受某项任务,就会负责到底。犯了错误之后,他会马上承认,并想办法补救。

(3)愿意改变:务实的程序员能克服不良习惯,察觉恶化的趋势,尽快做出改变,慢慢扭转局面。

(4)可以平衡取舍:务实的程序员不会过度追求完美,因为完美并不存在。他只要做的“够好”就可以了。至于什么样的软件算“够好”,这需要对软件环境背景有足够的了解才能做出判断。

(5)丰富的知识和技能:知识就是程序员的工具。务实的程序员都拥有丰富的工具,且对工具的运用相当熟练、自如。

(6)良好的沟通能力:开发系统的过程需要程序员与许多人沟通甚至协作,因此务实的程序员必须具备良好的沟通能力。

程序员除了要求尽力做好自己手上的事情,对于自己掌控范围以外的事情也要有所关注,从而分析状况与风险。如果评估之后发现风险太大,程序员有权利拒绝为不可预知的状况背书负责——一旦决定要负责,就要“真正”地负责。

程序员是人,人都会犯错。当发生疏忽、错误或开发延迟时,程序员应该直接承认问题,并尽快找出补救的方法,不要编借口或者指责别人,甚至怪到编程语言头上。小孩子没写作业时,会对老师编出很烂的借口,例如“狗吃了我的作业本”,本书则用“猫吃了我的源代码”来比喻程序员编出的烂借口。

为什么不能怪别人?尽管厂商可能会隐瞒某些事实,我们还是得怪自己没有调研清楚;硬盘挂掉,数据全毁,我们还是得怪自己没有备份。负责任的程序员必须注意到这些风险,并提出防范之道。出现问题时,就要马上承认,设法补救。

物理学的特性很少用于软件业,但“Entropy”(熵)是个例外。Entropy原本是一个物理学术语,软件行业却借用这个词来描述软件源代码混乱的状态。随着时间的推移,许多软件的代码会越来越复杂,越来越混乱。导致无法控制。仅有极少数的代码中不存在这样的问题。

为什么大多数软件的源代码会如此混乱?

知名的“破窗理论”告诉我们,如果某地区的建筑老旧、窗户破裂,却不马上去修整,该地区就会被加速破坏。“反正这地方都这样了,没人在乎。我多打破一个窗户,多砸烂一个路牌又如何?”居民是这样的心理。程序员也是这样的心理。

所以,务实的程序员要防微杜渐,时时刻刻防止潜在问题的发生,让项目保持在正确的轨道上前进而不会逐渐失控。对于软件开发来说,哪些东西是“破窗”呢?不好的决策、不好的架构、不好的代码都是“破窗”,都要及时修正。

有的时候,我们知道事情应该怎么做才正确,但大家都有本位主义思想,所以会让事情举步维艰。想让不好的现状逐渐改善,必须有改变的能力。作者讲了一个“石头汤”的故事,或许我们也应该像故事中的士兵一样,用一些巧思,诱发一场正向的变革。

我们可以用现有的资源做出合理的第一版系统,引起大家围观,然后不经意地说,“如果有人能帮我设计画面与交互,这系统一定会更棒”、“如果有人能帮我设计数据库,这系统一定会更棒”……这样,大家会逐渐加入,一同为这件事努力。要大家加入一个正在顺利进行的项目,会比大家加入一个什么都没有的项目更容易,所以,用现有资源做出合理的第一版系统是很关键的一步。

如果不从士兵的角度,而该从村民的角度来读“石头汤”的故事,就会发现我们应该警惕的地方。过度专注于一个小目标,无法顾及全局,最后会导致猪样变色。所以,程序员一定要随时纵观全局。“水煮青蛙”的语言我们都很熟悉,它对我们的警告也是:不要只专心处理自己的事情,要随时观察整个大环境的变化。

完美的代码是不存在的,尽快推出“足够好”的产品比较重要。这里所谓的“足够好”同时指:对使用者足够好,对未来做维护的人足够好,对自己的心理状态也足够好。大家都能接受,就是“足够好”。在互联网时代,这一点很重要——快速地推出“足够好”(但不完美)的产品,收集反馈,持续改进。

大多数使用者的心态是:宁可今天就有基本的产品可以用,然后持续看到产品的改进,也不要等待一年后的一个完美的产品。快速发布“足够好”的产品有一个很大的好处——可以从用户的反馈中得到更多的信息,让后续改进的产品更符合用户的需求。

开发软件的过程需要在许多方面取得平衡,例如使用者的需求、公司的财务状况、营销的角度和进度等,如果把这些都抛诸脑后,只是一味的新增功能、完善代码,那就太不切实际了。系统需求文档中应该明确地给出系统范畴与质量要求。唯有如此,程序员才知道“足够好”是什么意思。

程序员必须持续学习与实践,积累丰富的知识与经验,因为这是程序员最重要的专业资产。不幸的是,这是会贬值的资产——特别是在环境快速变化的现代社会。公司是由人组成的,人的知识与经验一贬值,公司也会随之贬值。那么,应该如何预防这样的状况发生?

获取新知识是程序员对自己的一种投资,就如同公司在财务上的投资一样。常见的财务投资方式有五种,而这些方式恰巧也适合用于对知识的投资上(需要发挥一点想象力)。

  • 经常投资,并使投资成为一种习惯。
  • 多元化投资,这是长期成功的关键。
  • 在保守、高风险、高回报之间巧妙地平衡。
  • 低买高卖。
  • 定期审视投资组合,并改进组合方式。

程序员最好每年学习一种编程语言,以拓宽视野(而非为了工作需要)。在挑选编程语言时,最好选择与自己习惯使用的编程语言具有不同编程范式(Paradigm)的语言,而且差异越大越好。程序员最好每季读一本技术书,书的内容可以是与项目相关的,或者无关的。除了读技术书,也要读非技术书,这很重要,因为技术人很容易和社会脱节。我鼓励程序员们多多上课,上个各种课。但我要特别提醒程序员们的是:好的课程很少,要慎选课程。大多数的课程通常不是讲师不好,就是内容不好,或者两者都不好。

技术与技能是否在实际工作中派上用场、能否真正为我们的简历加分,都不是最重要的。最重要的是学习的过程活化了我们的大脑,改变了我们的行为。比如,在我们学习面向对象之前与之后,我们写的C语言代码肯定会有不小的差异,这是因为我们的思维被面向对象影响了。

想活化大脑,除了采用上述方法之外,我们还可以积极参加本地的技术组织。幸好有网络,让这一点很容易实现。我们也可以体验不同的开发环境,例如,习惯用Windows的人改用UNIX,习惯用IDE的人改用Makefile。

还有什么方法可以活化大脑呢?那就是“随时接招”。如果有人问我们一个问题,我们却答不出来,就要找机会把这个问题搞懂。上网搜索、问专家、写代码、做实验等都是寻找答案的方法。阅读、学习、研究、思考、实验都要花时间,但我们哪有这么多时间?其实时间是有的——等公车的时候、等朋友的时候、等开会的时候、等牙医的时候,这些碎片时间都可以好好利用。

阅读与学习固然是件好事,但一定要思考,尤其是批判性地思考,才能避免自己在这个过度包装与夸大的社会中被欺骗。

项目不是一个人能完成的。程序员除了写代码,也要懂得如何与项目其他参与者沟通,甚至与客户沟通。沟通的方式有很多,包括开会、写文档、写邮件、做演示、写代码等。技术人员的沟通技巧通常很差,要好好加强。本书整理出了一些实用的方法,值得我们参考。但有一点一定要特别注意:说什么固然重要,说的方式也很重要。

//敲了一个多小时才敲完,有错误请指正……

2013年5月4日 | 分类: 日志 | 标签:

原理与cygwin的修改方法一致,假定MingGW安装路径为D:\MinGW,在文件夹右键菜单里添加MinGW直接转到该文件夹路径方法如下:
1.复制D:\MinGW\msys\1.0\msys.bat文件到D:\MinGW\msys\1.0\msys2.bat,然后把msys2.bat里:EOF那行下面加上一个exit (为了解决一个蛋疼的bug)
2.修改D:\MinGW\msys\1.0\etc\profile文件,将cd “$HOME”那行替换为下面内容

#cd "$HOME"
if [ ! -z "${MHERE_INVOKING}" ]; then
  unset MHERE_INVOKING
else
  cd "${HOME}" || echo "WARNING: Failed attempt to cd into ${HOME}!"
fi

3.修改注册表regedit,将下面内容存为a.reg并打开导入到注册表:

Windows Registry Editor Version 5.00

[HKEY_CLASSES_ROOT\Directory\shell\MinGW]
@="MSYS"

[HKEY_CLASSES_ROOT\Directory\shell\MinGW\command]
@="cmd.exe /k cd /d \"%1\" & set MHERE_INVOKING=1 & D:\\MinGW\\msys\\1.0\\msys2.bat"

或者手动修改:在HKEY_CLASSES_ROOT\Directory\shell\添加项MinGW(名字不重要),默认值为菜单里显示的文本MSYS,在此项里添加command项,默认值为cmd.exe /k cd /d "%1" & set MHERE_INVOKING=1 & D:\MinGW\msys\1.0\msys2.bat

此方法有个缺点,打开MSYS窗口过程中会另外有个cmd窗口闪一下。

2013年5月4日 | 分类: 日志 | 标签:

假定cygwin安装目录为C:\cygwin,在文件夹右键菜单里添加cygwin直接转到该文件夹路径方法如下:
1.在c:\cygwin目录下新建文件cygwin2.bat,内容如下

@echo off
@cd /d %1
set CHERE_INVOKING=1
C:\cygwin\bin\bash --login -i
exit

2.修改注册表,把下面内容保存为a.reg然后打开导入注册表即可

Windows Registry Editor Version 5.00

[HKEY_CLASSES_ROOT\Directory\shell\cygwin]
@="cygwin"

[HKEY_CLASSES_ROOT\Directory\shell\cygwin\command]
@="C:\\cygwin\\cygwin2.bat \"%1\""

或者手动修改:在HKEY_CLASSES_ROOT\Directory\shell\添加项cygwin(名字不重要),默认值为菜单里显示的文本cygwin(tip:加一个&在c前面可以用c键快速定位),在此项里添加command项,默认值为C:\cygwin\cygwin2.bat "%1"

3.使用mintty

推荐使用mintty替换cmd窗口,mintty下载地址:https://code.google.com/p/mintty/downloads/list

修改cygwin2.bat里的

C:\cygwin\bin\bash --login -i

start C:\cygwin\bin\mintty.exe -

把对应版本的mintty.exe拷到C:\cygwin\bin\目录中即可。

2013年4月20日 | 分类: 日志 | 标签:

在cnbeta上看到这样一篇文章 [评论]GB18030 – 想说爱你不容易,看完此文再次见识到CB喷子们的智商。这样一篇没有水准的文章,我觉得有必要再写点东西留给有需要的人,虽然之前已经写过一点相关的东西了。

注:本文名词较多,需要对字符编码有一定了解才可以看明白,本文不是科普文章抱歉。在此推荐一篇比较详细的编码知识讲解文章http://www.luanxiang.org/blog/archives/1271.html。

首先要明确的是:
1.没有所谓的ANSI字符集或者ANSI编码,所谓的ANSI编码正确的叫法是windows代码页(内码表),简体中文的Windows使用936代码页,基本等同于GBK字符集。(作者开头就说“疑惑一:GB18030到底是一种ANSI编码还是Unicode编码?”真是莫名其妙的很,能提出这种问题足见其水准之低)
2.早期的Windows(NT之前)是原生的单字符操作系统,并非原生支持Unicode,东亚版本的Windows系统则使用多字节字符集,具体而言就是双字节字符集(DBCS),原理是使用一个前导字节和尾字节,DBCS是不可能同时支持所有现有的字符集(由UCS-2与UTF-8转换关系很容易看出)所以不同语言地区会使用不同的代码页,如简体中文的Windows使用的是936代码页,繁体中文的使用950代码页。
3.Windows NT则是原生支持Unicode的,使用的是UCS-2编码(UTF-16的子集,在UNICODE辅助平面字符出来前与UTF-16一样),但是为了兼容以前的MBCS程序还是加上了代码页的功能。WIN32 API所有文本参数的函数接口都包括2个版本:一个基于代码页(ANSI)的版本,一个宽版本(称为’W’)处理Unicode。前者的实现其实就是先调用MultiByteToWideChar将基于代码页编码转化为UCS-2然后再调用后者,另外还有一个WideCharToMultiByte接口将UCS-2编码转换为基于代码页的版本。
4.GB18030与UTF-8一致,采用多字节编码,是ASCII的超集。(作者居然说“这就是说微软确实是把GB18030当作一种多字节的ANSI编码来看待的。”,我已经不知道说什么好了)

知道了这些, 就容易理解Microsoft GB18030 支持工具包的原理了。正如Windows提供对GBK编码的支持一样,通过提供MultiByteToWideChar/WideCharToMultiByte接口实现对GBK与UCS-2编码的互相转换以支持,Microsoft GB18030 支持工具包提供了一个动态链接库ms4bsp.dll来实现GB18030-2000与UCS-2编码之间的互相转换。我只能说并非Windows不支持这些编码标准,而是作者根本不懂这个工具怎么用。把责任推倒有关部门的头上更是莫名其妙……

第 1 页,共 3 页123