追忆似水流年

=================================================================

 

I think the following is O(nlogn).

Given an array A in which we need to find the contiguous sub-array of sum k, create a new Array B such that

B[i] = Sum j = 1 to i A[i]

i.e B[m] = A[1] + A[2] + ...  A[m] is the prefix sum array of A.

Now create a third array C such that C[i] = (B[i], i) (ordered pairs)

Now sort array C using the values B only (i.e ignore the second co-ordinate of the ordered pair).

Now for each element C[p] =  (B[q],q) do a binary search for B[q] + K in C. Say you find the element(s) C[r] = (B[s], s)

if q < s, then we are done, else continue.

(Note, we might have to create a new array C' by merging sub-arrays with same value of B and also store the set of indices of B which take that value i.e. instead of just using the ordered pair (B,i) we use (B, {i1, i2, ..., ik}) and do a binary search on C')

+++++++++++++++++++++++++++++++++++++++++++++++++++

这个题目不同于找最大之和，最大之和的解能在O(1)空间下,在O(n)时间内完成

Digest from http://discuss.techinterview.org/?interview

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

I have an array consisting of 2n+1 elements. n elements in it are
married, i.e they occur twice in the array, however there is one element
which only appears once in the array. I need to find that number in a
single pass using constant memory. {assume all are positive numbers}
Eg : 3 4 1 3 1 7 2 2 4
Ans: 7

===============================================

var array = [3, 4, 1, 3, 1, 7, 2, 2, 4]
var remaining = 0;

for(var i = 0; i < array.length; i++)
{
  remaining ^= array[i];
}

return remaining;

 

==========================================================

首先，应该用原地置换的思想。2，用两个指针，分别指向0和k＋1位置。两个比较，

小的换到0的那个指针(表示全局的较小)，后面那个指针得到的换过来的元素要和它的后续比较一下，

要确定这个指针所指是后半部分的最小。这样两指针一直从左到右移动，就排序完了。

最近在公司忙里偷闲，装了python，开始玩了。批评一句，那个shell太不友好了，虽然能调颜色。但是它也是很好玩的，现在基本上是语法和语言特性的体验阶段。公司一天要损失20%的劳动力了，哈哈。

从小就没有什么像样人生观。小学的六年太漫长，时间好像停滞了一样。中学的时候，高考就好像一个终点。我也老给人灌输，看，状元，怎样怎样。似乎那样就成仙成佛了。没看过西游封神啊？成仙成佛之后也有艰苦的斗争在等着你呢。大学四年，不长不短，终点就是毕业。下一个？当然是结婚了，不出意外的话，或者出了意外的话。And then？离婚？还是孩子出生成长然后结婚？终于迷失自己。忽然想到某电台主持人所说，你不能同时得到幸福和精彩。

发信人: Puma (彪马), 信区: Marvel
标  题: 转, 因为女朋友诡异而分手
发信站: 水木社区 (Sat Apr  5 16:25:47 2008), 站内

首先申明，我下面说的这个事情绝对是我亲身经历的事情．绝对没有半点虚假．因为我不是专业写作的作家，所以文笔不好，请大家见谅．

事情要从半年前我跟前任女友分手开始说起．

实话实说，她确实是个有魅力的女人，长的漂亮，身材也好，而且很懂事．知道孝顺双方的父母．

但在我们相识一年零四个月的时候，我还是决定跟她分手了．

原因是她身上真的有太多太多我看不透的东西．是诡异．

下面我先跟大家说说她都有些什么地方跟别人不一样

１：她从来不会跟我提她的家庭情况，她的朋友，她的社交，而且也从来没有见过她有其他的朋友，她手机的电话本里除了我的，一个号码也没有．更不要说有人给她打电话了．一年零四个月里，我从来没听到她的手机响过．

２：每隔一个月她都会失踪一天，直到第二天的早上８点准时给我打电话．

３：她的饭量非常的小，准确的说．是几乎不吃东西，我们交往的那么长时间里，从来没有一起吃过饭．如果我们在一起到吃饭的时候，我说吃饭去吧，她就说她不饿．我们不在一起，打电话约她吃饭，她会说她已经吃过了．除非我买了小零食，拿到她租住的地方，才能象征性的见到她吃一点．

４：她的皮肤非常的好，全身上下都是白皙透亮的，脸上没有任何的斑纹．但是她从来没有做过皮肤护理．记得有一次．我不小心打烂了一瓶啤酒，碎玻璃溅到她的腿上，当时流了很多血．可她坚持没去医院，还说不要紧，只是擦伤而已，过几天就好了．结果后来她的腿上竟然没有留下任何伤疤．

５：她不工作，不上网，不娱乐，街都很少逛．每天都呆在家里．不知道都做些什么．．有次晚上我去找她，到她家门口的时候发现，屋子里没有开灯，以为她不在家．于是打她的手机．结果她竟然在屋子里．我问为什么不开灯，她说她睡着了．可我根本没有发现她有睡意

关于她的诡异还有很多很多，在这里我也不多说了．因为今天我写这个帖子的本意是发泄，而不是要吓人．

总之，因为她的诡异，我最后终于跟她分手了．她不愿意，但是我主意以决．

只记得最后她说了一句，你会后悔的．

变成了人形，还是没人爱我

发信人: wannasoft (天使大哥), 信区: Joke
标  题: 变成了人形，还是没人爱我
发信站: 水木社区 (Sat Apr  5 17:21:39 2008), 站内

我是一只小小的青狐，因为毛色难看，在我们这片林子里，没有一个同类喜欢我，我自卑得要死，整天在家里不愿出门，茶饭不思，粒米不进。

妈妈看在眼里，疼在心上，对我说，孩子别愁，好好修炼吧，修炼800年，你就可以变成人形了，那时候你想变成什么样的美人就变成什么样的美人。

于是，我充满阴霾的心灵豁然有了一缕阳光，我开始刻苦修炼，我要用八百年的寂寞来换得众人的眼球。这，值了。

当我变成人形的那一天，天是灰蒙蒙的，就和我当时的心情一样，人间的险恶、人性的自私、人类的世故，真的让我疲于应付。但我知道，只要找到我心中的那个“他”，我就可以只和他在一起了，不去管旁人了。

老天的眼睛一定是1.5的，没多久我就找到了他。他虽然不帅，但笑起来很好看，对我也很好。就这样，我们相爱了，我对他好，对他的父母好，对他全家都好，因为我知道用八百年修来的缘分是多么的不易。

后来，后来，后来的一天，他居然提出与我分手。。。。。泪水再也止不住了。

他说我皮肤没有伤疤（难道我这八百年是玩着过来吗？），他说我每个月要失踪一次（难道如果我不找个时间来修行一番，我能维持功力吗？），他说我吃得很少（八百多年的饮食习惯是一朝一夕就能改掉的吗？），他说我手机上只有他一个号码（除了他我还会认识谁呢？），他说我不告诉他我的过去（难道我真的说出来他会相信我吗？）

太多的不堪，太多的难舍，太多的不忍相诉，让我心痛不已，痛化为悔，俾余泣不成声。

我对他说，你会后悔的，你会后悔的。可这样的挽留又有什么意义呢？

也许喧闹的人界本就不属于我，思来想去，我决定离开，在一个阳光刺眼的早上，我把自己浇上汽油，让赤焰的红色逼我忘却红尘的一切，而我也在这时显现了我狐狸的真身。

这时，一个人走了过来，惊呼Firefox!!!!!！于是成为了那款浏览器的代言人。

贴一个我一朋友的经验介绍，华工牛人哇，四五阶魔方国内最快呀。             

       三阶魔方顶层基本解法（更新版）

                ――四个步骤解决三阶魔方顶层 

              

   解魔方，对一般的初学者，觉得最复杂的就是顶层。急于想学会全部还原，不想多记公式，厌倦步骤多的公式，公式记得不牢固是大多数初学者的心态。为了照顾大多数的初学者，所以在此就给了一种公式少的解法，当然步骤是会多了点，而且每步的情况分析也有点烦，但只要 用心＋耐心＝成功，一天就足以学会啦！！！

     首先给出这种方法的四个步骤，当然前提还原了第一，二层，步骤如下：

     十字        角反色         换角       换棱（完成）

     下面对每个步骤作具体的介绍。

     十字：

所谓十字，就是将顶层做成一个十字架。

           公式：R’U’F’UFR（公式字符说明在后面）

           在没做成十字前，将会遇到多种情况，但都可以分成以下三大类情况：

            （1）   （2）  （3）

        第一种情况用一次公式就可以做成十字；

        第二种情况用二次公式就可以做成十字；

        第三种情况用三次公式就可以做成十字。

 

     角反色：

将顶层所有角的颜色反成和中心块一样的颜色。

             公式分A,B两种基本情况

             公式：(A)角顺时反色：RUR’URU2R’

                   (B)角逆时反色：R’U’RU’R’U2R

             用法：如图： 

角顺时反色(A)                     角逆时反色(B)

除了以上两种情况外，还有以下种5种，但者几种都是用上面的公式将其转化成“一个颜色已好，其余三个还没反好”这种情况。

          

   （1）    （2）     （3）     （4）     （5）

下面来分析以上五种情况的解法：

（1）       连续用两次“角顺时反色公式”就可以把颜色反好

（2）       用一次“角逆时反色公式”就变成情况B

（3）       用一次“角逆时反色公式”就变成情况A

（4）       先将顶层逆时转过90度（即U’），接着用“角逆时反色公式”就变成情况A

（5）       用一次“角顺时反色公式”就变成情况A

 

换角：

根据角的颜色将顶层的四个角的位置换好

      公式：(lU'R)D2(R'UR)D2R’L’

      公式用途：将其中一个角的颜色对好，并把这个对好的角放在左上角，用一次这个公式就是将左下，右上，右下三个角顺时针转动一次。例如：

（对好颜色的角放在左上角）     

换角会碰到以下几种情况：

 一角对好颜色，三个角错位（又分成以下两种情况）：

1.其它三个角顺时转就可换好，用一次公式。

        2其它三个角逆时转就可换好，用两次公式。

两角对好颜色，两个角错位（又分成以下两种情况）：

        1．邻角错位（如图）

                 用一次公式就可以转化成“一角对好颜色，三个角错位”的情况‘

             2．对角错位（如图）

               用一次公式就可以转化成“邻角错位”的情况。

 

      换棱：

就是把中间的四条棱换好

           公式：顺时换棱：(R2' URU)(R'U'R'U')(R'UR')

                 逆时换棱：(R U')（RURU）（RU'R'U'R2'）

           用法：一条棱已经对好位置，另外三条棱错位。如下图：

              

 顺时换棱            逆时换棱

还有一种情况：就是四条棱都是错位的，这时只要随便用顺或逆时换棱种任一条公式就可以转化为以上两种情况。即一条棱已经对好位置，另外三条棱错位。

附：四条棱都是错位的两种情况：

                                 

r2 (R2 U) r2 (R2 U) U r2 (R2 U) R2 r2        .( R'U') (RU')(RURU' R'URU)(R2U')R'U2

 

转载啊

================================================

其实，对一些如树的递归结构，递归算法是又自然又好用。
如果看看一些用来代替递归的技术，（汉诺塔的迭代算法不去说它，那是真正的算法的革命，除了佩服没啥好说的），一般来说只不过是自己模拟堆栈，编起来费劲，读起来费劲，维护起来更费劲。而模拟堆栈的效果，相比于简单的递归，好处在哪里呢？
1。不使用进程堆栈，不会耗尽堆栈空间（虽然可能耗尽堆空间）
2。可以有选择地把真正有用的东西压栈，而不用什么pc, sp, 所有的局部变量都压栈。这样节省了一些内存（不过，仍然在一个数量级，递归是O(N)，模拟递归仍然是O(N))。不过这也不绝对，编译器的优化可以识别一些不需要保存的局部变量的。（这叫变量生存期分析） 那么这样做又没有坏处呢？除了上面的代码复杂度的问题（我想很多搞嵌入式系统，实时系统的C高手都对此不屑一顾），还有一个效率上的缺点： 模拟的递归使用堆空间，它的new/delete都比直接在堆栈上分配空间慢得多。而且很容易产生内存碎片。 所以说，模拟堆栈只不过是牺牲了一定的效率来换取了一部分空间而已。是否值得，嘿嘿，就得看具体应用了。 好，闲话说完，下面言归正传。

话说大家都知道函数调用要压栈。不过这是有几个例外的。
1。函数是inline的。
2。语言采用的函数调用方式是continuation, 而不是activation record. 这种模式中语言可以使用堆而不是栈来完成函数调用。
3。尾调用。也就是说，函数调用出现在调用者函数的尾部，因为是尾部，所以根本没有必要去保存任何局部变量，sp, pc的信息。直接让被调用的函数返回时越过调用者，返回到调用者的调用者去。
尾调用优化不是什么很复杂的优化，实际上几乎所有的现代的高级语言编译器都支持尾调用这个很基本的优化。
实现层面上，只需要把汇编代码call改成jmp, 并放弃所有局部变量压栈处理，就可以了。所以，很简单。

于是，就剩下递三条：尾调用。而一个对自己本身的递归尾调用，就叫做尾递归。

那么，当尾递归时，我们就没有前面分析的递归调用的占用堆栈的缺点，因为每次调用都是尾调用，所以堆栈根本就没有被占用，每次调用都是重新使用调用者的堆栈。

这个好玩的东西出自百度moe贴吧，版权不归我。不过从图片出处来看，好像是猫扑的。

 

封面：《怎样打飞机》广州军区司令部编印 一九六五年二月十五日出版

前言　
帝国主义、社会帝国主义都是“唯武器论”者，迷信所谓“空中优势”。因此，与敌人飞机和空降兵作斗争，，是对付敌人突然袭击，进行反侵略战争的一项重要任务。我们必须遵照毛主席关于“备战、备荒、为人民”，“深挖洞、广积粮、不称霸”的教导，充分做好精神上和物质上的准备，发扬一不怕苦、二不怕死的彻底革命精神，“全力以赴。务歼入侵之敌”。这个画页介绍用民兵常用的轻武器－－步枪、冲锋枪对空射击的方法。

 

射击水平飞行的敌机时，应根据飞机的大小和距离的远近，提前一定的机身倍数。计算提前倍数的方法：飞机速度乘子弹到达飞机的时间，除机身长度。所得到的数字，就是再瞄准时应当考虑的提前量对侧方俯冲的敌机射击时，瞄准点应选在敌机的俯冲方向或俯冲后离去的方向；在俯冲阶段，射击时，应比水平飞行时的提前量增大四分之一。这是因为敌机俯冲速度比水平速度通常要大四分之一。对俯冲的敌机射击时，瞄准要领应根据不同的情况来确定。

 

对向着射手俯冲的敌机，可直接对着机头射击；对背着射手俯冲后离去的敌机，可直接瞄准敌机机尾射击。在这两种情况下，因为敌机的航向与航线与射线概略重合，所以都不必选取提前量。根据步枪、冲锋枪的特点，对敌机射击时，距离五百米以内比较有效。 这是利用土堆，采用仰卧姿势对空射击。如果平时修筑适当的对空射击工事，敌机来犯时就能更有效地消灭它。