Browsed by
Category: 未分类

组合与全排列非递归算法

组合与全排列非递归算法

二进制组合算法: 思路是开一个数组,其下标表示1到m个数,数组元素的值为1表示其下标 代表的数被选中,为0则没选中。 首先初始化,将数组前n个元素置1,表示第一个组合为前n个数。 然后从左到右扫描数组元素值的“10”组合,找到第一个“10”组合后将其变为 “01”组合,同时将其左边的所有“1”全部移动到数组的最左端。 当第一个“1”移动到数组的m-n的位置,即n个“1”全部移动到最右端时,就得 到了最后一个组合。 例如求5中选3的组合: 1 1 1 0 0 //1,2,3 1 1 0 1 0 //1,2,4 1 0 1 1 0 //1,3,4 0 1 1 1 0 //2,3,4 1 1 0 0 1 //1,2,5 1 0 1 0 1 //1,3,5 0 1 1 0 1 //2,3,5 1 0 0 1 1 //1,4,5 0 1 0 1 1 //2,4,5 0 0 1 1 1 //3,4,5 全排列N进制算法: 从1到N,输出全排列,共N!条。 分析:用N进制的方法。设一个N个单元的数组a用来存放待全排列的数组的下标,对第一个单元做加一操作,满N进一。每加一次一就判断一下各位数组单元有无重复,有则再转回去做加一操作,没有(且数组a中没有值为N的元素)则说明得到了一个排列方案。 例如:求1-3的全排列,共3!条 设数组初始状态为0 0 0,以下为计算全排列的步骤: 0 0 0 +1…

Read More Read More

Longest Substring Without Repeating Characters

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1. 做这道题时,脑袋里面不停的想起DP的声音,无奈,当时学算法时,DP就是一个弱项,而自己做这题时,又不停的往这个方向去想,所以一直都没有解答出来,最后还是靠这篇文章才找到解决方法而过关。 基本上,第一个直观到思路就是从第一个字符开始向后找,如果不是重复的,就加入到hash表中,然后向后继续找,直到重复时,比较是否是最长的,然后纪录下长度,清空hash表,继续找到最后一个字符为止;接着从第二个字符开始,依次找到每个字符到最后一个字符中所有的不重复字串,这个就是暴力法了。 第二个思路是,其实不需要每个字符都一遍遍寻找,比如abcabc,那么找到abc后,下一个字符a就跟abc中到a重复,然后记下长度,接着从bca组成到新字符串开始向后寻找,也就是从index为1的字符串重新开始找,这样就比第一个方法节省一些时间了。 可是还是不够快,因为从上次重复的下一个字符开始找,还是需要清除map并且重新找,其实可以上一次重复的位置纪录下来,然后只要清除那之前的字符就可以了。 代码如下 int lengthOfLongestSubstring(string s) { int maxLength = 0; int lastRepeatCharIndex = 0; unordered_set uniqueSubStrings; for( int i = 0; i < s.length(); i++ ) { char c = s[i]; if(uniqueSubStrings.find(c) == uniqueSubStrings.end()) {…

Read More Read More

[zt]Guide for Technical Development

[zt]Guide for Technical Development

Guide for Technical Development Having a solid foundation in Computer Science is important in being a successful Software Engineer. This guide is a suggested path for University students to develop their technical skills academically and non-academically through self paced hands-on learning. You may use this guide to determine courses to take but please make sure you are taking courses required for your major or faculty in order to graduate. The online resources provided in this guide are not meant to…

Read More Read More

不思进取

不思进取

好久都没有学习新的东西了。接下来有时间要充充电了。 Real World Haskell http://www.amazon.com/Real-World-Haskell-Bryan-OSullivan/dp/0596514980

亚基拉

亚基拉

超过廿年的年品,却是无人能达到其境界的作品,影响一代动漫迷使其投身动漫事业,大友克洋的代表作,日系动漫迷们应该不会陌生。 有空找来看看。

linode惊魂记

linode惊魂记

好吧。我承认我的站点已经好久没有更新了。 昨天下班前突然想到一个困扰自己多年的问题,问题是:当你开车时,如果副驾驶的人没有系上安全带,这个时候安全带的提示灯就会亮起,提醒乘客系上安全带,这个从技术上是如何实现的。 我自己愚笨的想法是,加一个红外线探测仪,加一个重量检测仪等等,主要目的都是确定那个位置上面有没有人。 在搜索到这个问题的答案后,才恍然大悟,原来我忽略了一个重要的步骤,就是一般情况,要进入副驾驶,那么就得先开副驾驶的门,然后再关上副驾驶的门,所以最简单的实现办法就是:判断如果副驾驶门打开并且关上,然后可以确定副驾驶有人,这个时候才开启安全带的检测。当然会有一些细节问题,例如有人打开关上之后并没有进入等等。 当我知道这个答案后,立马就准备到博客记录下来,没有想到的是,居然进不去了。于是乎我就登录linode站点,发现我的linode不在dashboard了,这时候脑袋突然发白,不会吧,怎么会怎样。跑到了support页面才发现原来我信用卡缴费失败了,我换了张信用卡,但是却没有更新linode,导致他们扣款失败,他们最后的一封信是告诉我如果我在Apr 28还没有缴钱的话,我的linode就会被删除了。昨天正好就是28号啊,幸好我准备更新博客,才发现了这个问题,不然辛苦弄了半天的site被停掉了岂不是很可惜啊。

得到和得不到

得到和得不到

想到一个问题的:如果A和B同事争取一个东西,而两个人都针锋相对,那么结果会是如何? A得到了,B得不到 B得到了,A得不到 A和B都得到了。(这个东西具有分享的特质) A和B都没有得到 现在开始试图去分析各个状态下可能的情况 A觉得胜利了,B觉得失败了 B觉得胜利了,A觉得失败了 A和B都觉得胜利了 A和B都觉得失败了(或者胜利了),或者一方觉得胜利了,另一方觉得失败了。  

恋空

恋空

网上评价特好、特坏都有的一个片子。今天终于把它看完了。 这是一个讲述高中生的爱情故事,之前宣称上讲是纯爱电影,显然有点名过其实,开篇就涉及到高中生偷尝禁果,甚至还有强奸的内容,但是不可否认的是,导游并不想把过的笔墨花费在这些内容上,而是为了铺陈男主角宏树招惹麻烦的特质。 剧情到后面狗血的堕入了生死离别,不得不让人遗憾。不过话由说回来,如果没有这个剧情,电影也不会这么长了,大概半个小时就演完了。 总之看完这部电影,绝对得不会是投入过度赞扬得那一派,大概这也是我理性的部分,觉得剧情实在是不太合理,另外也许同类剧情看过太多,也勾不起感动的部分。