{今天我们思考25}两道精巧的小题目

[pongba]

windstorm说上次一次给的题目太多，抱歉，没有筛选。这次给出两道不错的题目。

第一道是上次转载的阅微堂那里（后者从这里转载的，上面有很多不错的题目，分类也井井有条），silwile说这道题不错，我就做了一下，的确不错，小巧又不失精彩。据说也是微软的经典面试题之一。

1. There is a circular track. There are n gas stations of capacity ci. To go from one station to the next station it takes certain amount of gas gi. For any station the gas available may not be enough to get to the next station. Write a linear time algorithm to find the correct station in which we must start in order to complete one round around the track.

第二道题目是Amazon的面试题，从题目的形式上感觉是道挺不错的题目。
2. Given two arrays A [1..n] and B[1..m], find the smallest window in A that contains all elements of B. That is, find a pair <l,k> such that A[l..k] contains B[1..m] For example, given A = 3,1,5,7,3,5,2 and B = 5,3 then the smallest window is [3,5].

最后顺带一道趣题吧。
3. 有一个01数组，现在要你对它进行重排（即保持0和1的数目不变），使得成为这样的形式：0101..01xxx.. 即01间隔，然后多出来的0或者1放到后面（用xx表示）。例如110110重排为010111。要求O(1)空间复杂度，以及只能遍历一次。

--
刘未鹏(pongba)|C++的罗浮宫
http://blog.csdn.net/pongba
TopLanguage
http://groups.google.com/group/pongba

[windstorm]

第三题有点意思，我有两个思路：

1 用两个变量表示下标，一个表示奇数下标，一个表示偶数下标

奇数下标的动作是：如果在自己位置上的数不是0，就停止，如果是0，就自加2，一直到指得数不为0为止。

偶数下标的动作是：如果在自己位置上的数不是1，就停止，如果是1，就自加2，一直到指得数不为1为止。

等到两方都停止的时候，交换双方值。循环下去，应该一次遍历就可以搞定。

2 设一个临时分量temp，下标分量index，然后用i遍历数组，遇到0，就和index的值交换，此时index+1有两种情况，如果不等于i，index+1所指的值此时肯定为1（因为index比i小，不会存在是0的情况），所以直接index自增2。如果等于i，i指向的值取非，

这种的话会有意外，比如index ==
i，比如一开始就是0001.....这种数组，那么就需要把"用i遍历数组，遇到0，就xxxxxx"这个思路换成"用i遍历数组，遇到1，就xxxxxx"。

两个都是遍历一次就行了，不过第二个思路要比第一个思路复杂很多，纸上画了很久才大概摸清楚。不过我不知道O(1)空间复杂度是什么意思？

2008/6/4 pongba <pon...@gmail.com>:

--
Yours Sincerely
Kun

blog: www.forwind.cn

[pongba]

2008/6/4 windstorm <likunar...@gmail.com>:

第三题有点意思，我有两个思路：

1 用两个变量表示下标，一个表示奇数下标，一个表示偶数下标

奇数下标的动作是：如果在自己位置上的数不是0，就停止，如果是0，就自加2，一直到指得数不为0为止。

偶数下标的动作是：如果在自己位置上的数不是1，就停止，如果是1，就自加2，一直到指得数不为1为止。

等到两方都停止的时候，交换双方值。循环下去，应该一次遍历就可以搞定。

很漂亮的思路，可以说说是怎么想到的吗？

[windstorm]

首先就确定必须交换，因为只能遍历一次

然后因为先想的第二个思路，然后花了很久的时间，觉得不应该这么麻烦的，特别是如何解决"交换"的问题，开专门开辟一个temp变量，简直伤透了脑筋

想到后来干脆就换个思路，搞两个下标来解决交换的问题，然后发现换来换去，就是把0放到偶数位上去，1放到奇数位上去，那干脆就一个下标指奇数位，一个下标指偶数位，大家一起遍历找位置不对的地方，等大家都找到（也就是停止）的时候，一交换，最后肯定位置就对了。

举了几个特例一验证，差不多，就写上来了。

2008/6/4 pongba <pon...@gmail.com>:

--

[pongba]

2008/6/4 windstorm <likunar...@gmail.com>:

首先就确定必须交换，因为只能遍历一次

然后因为先想的第二个思路，然后花了很久的时间，觉得不应该这么麻烦的，特别是如何解决"交换"的问题，开专门开辟一个temp变量，简直伤透了脑筋

想到后来干脆就换个思路，搞两个下标来解决交换的问题，然后发现换来换去，就是把0放到偶数位上去，1放到奇数位上去，那干脆就一个下标指奇数位，一个下标指偶数位，大家一起遍历找位置不对的地方，等大家都找到（也就是停止）的时候，一交换，最后肯定位置就对了。

举了几个特例一验证，差不多，就写上来了。

唉，我也想到奇偶下标，但是就是没想到"双下标遍历"。我想的是挨个看过去，如果位于偶数位上，就看它是不是1，奇数位就看它是不是0。那么问题是，如果出现比如说偶数位上不是1，怎么办呢？我想，不"往前看"是不行的，因为万一后面都是0，那将当前位置1就糟糕了，所以得确信前方还有没有剩余的1了。然而一旦往前看，就不是1pass了。就此卡住。

验证了一下你的方法，有一个corner case没解决：110101 => 010111。

[Googol Lee]

这个corner，可以在验证完一遍后增加一次对奇数位的扫描来解决吧：
奇数指针不动，另一个指针从后向前扫奇数位，碰到为0的奇数位就与奇数指针交换，且奇数指针按之前的方法递增。直到两个指针相遇。

这个过程应该也是O(n)的。

2008/6/4 pongba <pon...@gmail.com>:

--
新的理论从少数人的主张到一统天下，并不是因为这个理论说服了别人抛弃旧观点，而是因为一代人的逝去。

My blog: http://googollee.blog.163.com

[pongba]

2008/6/4 Googol Lee <goog...@gmail.com>:

这个corner，可以在验证完一遍后增加一次对奇数位的扫描来解决吧：
奇数指针不动，另一个指针从后向前扫奇数位，碰到为0的奇数位就与奇数指针交换，且奇数指针按之前的方法递增。直到两个指针相遇。

这个过程应该也是O(n)的。

这样的话就不是1pass，而是2pass了。

顺便答windstorm，O(1)空间复杂度就是只耗常数规模的空间。

[alai]

题目的要求是一次遍历，只是O(n)并不满足题意啊，不然就容易了。

2008/6/4 Googol Lee <goog...@gmail.com>:

[Googol Lee]

哦……看错了，呵呵

2008/6/4 alai <ala...@gmail.com>:

[Googol Lee]

又想了一下，即便增加这个过程，从总体上来看，每个位依旧只访问了一遍，因为在奇数指针之后的奇数位还没有被访问过。

所以……这样能算一次遍历么？

2008/6/4 alai <ala...@gmail.com>:

[xxmplus]

2008/6/4 pongba <pon...@gmail.com>:

用一个i指向当前下标，用一个e指向第一个出错的位置，当前位置正确时，e随着i一起前进，当前位置不正确时，e停住，i继续前进寻找e位置上需要的那个数字，当i到底时，算法结束。
用pongba的例子110101，x代表空格：
======== 1 ========
i
110101
e
======== 2 ========
xi
110101
e
======== 3-1 ========
xxi
110101
e
======== 3-2 找到了，i和e交换，e前进至i ========
xxi
011101
xxe
======== 4 ========
xxxi
011101
xxe
======== 5-1 ========
xxxxi
011101
xxe
======== 5-2 找到了，i和e交换，e前进至i ========
xxxxi
010111
xxxxe
======== 6 =========
xxxxxi
010111
xxxxe
========= end ==========

另外问一句，如果我凭空构造一个数组出来直接替换原数组，算不算破坏O(1)？
--
Any complex technology which doesn't come with documentation must be the best
available.

[alai]

其实我觉得，"只能遍历一次"这个条件有点模糊，是否要理解为"只能有一个单向迭代器且只能遍历一次"，还是可以理解为"可以有一个以上的单向迭代器，每个只能遍历一次"，抑或是"可以是双向迭代器，遍历的过程中可以回溯"？有许多不确定的地方。

LS几位给出的解法都用了两个迭代器，各遍历一次，这是否符合题意呢？

2008/6/4 xxmplus <xxm...@gmail.com>:

[翁翊成]

这道题目好像还有个要求。。。只能有一个临时变量 = =#

2008/6/4 Googol Lee <goog...@gmail.com>:

[xxmplus]

只要求常数空间复杂度就行了

2008/6/4 翁翊成 <wen...@gmail.com>:

--

[pongba]

2008/6/4 alai <ala...@gmail.com>:

其实我觉得，"只能遍历一次"这个条件有点模糊，是否要理解为"只能有一个单向迭代器且只能遍历一次"，还是可以理解为"可以有一个以上的单向迭代器，每个只能遍历一次"，抑或是"可以是双向迭代器，遍历的过程中可以回溯"？有许多不确定的地方。

LS几位给出的解法都用了两个迭代器，各遍历一次，这是否符合题意呢？

我觉得应该理解为"每个元素只被访问一次" 吧。

[windstorm]

晕了，O(1)到底是常数个，还是1个？

我刚才也想了一下，如果不允许偶数指针回扫，貌似这个问题还很难解决，这个问题实际上是：如何排序本身所在位置的奇偶性正确，只是位置靠后（位置编号不对）的元素。

2008/6/4 翁翊成 <wen...@gmail.com>:

--

[pongba]

2008/6/4 翁翊成 <wen...@gmail.com>:

这道题目好像还有个要求。。。只能有一个临时变量 = =#

O(1)的复杂度不是指只能有一个额外空间。而是常数数目的额外空间。

[xxmplus]

所以我有另外一个思路，但是不知道是不是破坏了空间O(1)。。。
反正最后结果的形式已经知道了，惟一的区别是0101xx最后的x是0还是1，那么只要扫一遍数组，得到0和1之间的差，比如0比1多差就是负数，一样多就是0，1比0多就是正数，然后构造一个数组直接换掉原来的就行了

[Googol Lee]

这个思路好！

2008/6/4 xxmplus <xxm...@gmail.com>:

--

[pongba]

2008/6/4 xxmplus <xxm...@gmail.com>:

所以我有另外一个思路，但是不知道是不是破坏了空间O(1)。。。
反正最后结果的形式已经知道了，惟一的区别是0101xx最后的x是0还是1，那么只要扫一遍数组，得到0和1之间的差，比如0比1多差就是负数，一样多就是0，1比0多就是正数，然后构造一个数组直接换掉原来的就行了

哈哈，我脑袋秀逗了，这个方法才是最简洁的。
BTW. 你不需要构造另一个数组，直接in-place的写入原数组就行了:)

[pongba]

2008/6/4 pongba <pon...@gmail.com>:

2008/6/4 xxmplus <xxm...@gmail.com>:

所以我有另外一个思路，但是不知道是不是破坏了空间O(1)。。。

反正最后结果的形式已经知道了，惟一的区别是0101xx最后的x是0还是1，那么只要扫一遍数组，得到0和1之间的差，比如0比1多差就是负数，一样多就是0，1比0多就是正数，然后构造一个数组直接换掉原来的就行了

照例，说说思考的过程吧:D

[windstorm]

我寒，一开始想到过这个思路，但是我以为重新构造数组算是另外一次遍历......

2008/6/4 pongba <pon...@gmail.com>:

--

[xxmplus]

2008/6/4 pongba <pon...@gmail.com>:

>
>
> 2008/6/4 xxmplus <xxm...@gmail.com>:
>>
>> 所以我有另外一个思路，但是不知道是不是破坏了空间O(1)。。。
>>
>> 反正最后结果的形式已经知道了，惟一的区别是0101xx最后的x是0还是1，那么只要扫一遍数组，得到0和1之间的差，比如0比1多差就是负数，一样多就是0，1比0多就是正数，然后构造一个数组直接换掉原来的就行了
>
> 哈哈，我脑袋秀逗了，这个方法才是最简洁的。
> BTW. 你不需要构造另一个数组，直接in-place的写入原数组就行了:)
>

是啊是啊，也对哦;p

[pongba]

2008/6/4 windstorm <likunar...@gmail.com>:

我寒，一开始想到过这个思路，但是我以为重新构造数组算是另外一次遍历......

我才汗，一道题目居然被你想出三种思路:-D

[windstorm]

其实我的第二个思路，也就是一开始想的那个思路，就是从xxmplus这个思路来的，因为你要确定0多还是1多啊，加和是最好的方法。

只是以为重新写一次数组算一次遍历......所以我才用了条件判断，分情况讨论，导致这个思路如此复杂.....

2008/6/4 pongba <pon...@gmail.com>:

--

[xxmplus]

2008/6/4 pongba <pon...@gmail.com>:

>
>
> 2008/6/4 pongba <pon...@gmail.com>:
>>
>>
>> 2008/6/4 xxmplus <xxm...@gmail.com>:
>>>
>>> 所以我有另外一个思路，但是不知道是不是破坏了空间O(1)。。。
>>>
>>> 反正最后结果的形式已经知道了，惟一的区别是0101xx最后的x是0还是1，那么只要扫一遍数组，得到0和1之间的差，比如0比1多差就是负数，一样多就是0，1比0多就是正数，然后构造一个数组直接换掉原来的就行了
>
> 照例，说说思考的过程吧:D
>

浆糊一样的思考过程：
首先看到01010脑子里想到的是二进制数，然后试图用把它转换成十进制看看能不能用一个数来表达这一串0和1所携带的信息，当时是想只要知道能从那个转换出来的十进制数上看出它有多少个1就行了，试了几次，觉得很麻烦，回头再读题目，原数组和目标数组其实长度一样，0和1的具体数目没有意义，只要知道它们之间的关系就足够了。。。然后就有结果啦。。。

[Googol Lee]

不过，这个方法确实有两次遍历的嫌疑。

能不能在遍历前就知道数组总长度呢？

2008/6/4 xxmplus <xxm...@gmail.com>:

--

[pongba]

@All：

该做第1题啦，也是很好的题目:D

2008/6/4 pongba <pon...@gmail.com>:

windstorm说上次一次给的题目太多，抱歉，没有筛选。这次给出两道不错的题目。

第一道是上次转载的阅微堂那里（后者从这里转载的，上面有很多不错的题目，分类也井井有条），silwile说这道题不错，我就做了一下，的确不错，小巧又不失精彩。据说也是微软的经典面试题之一。

1. There is a circular track. There are n gas stations of capacity ci. To go from one station to the next station it takes certain amount of gas gi. For any station the gas available may not be enough to get to the next station. Write a linear time algorithm to find the correct station in which we must start in order to complete one round around the track.

第二道题目是Amazon的面试题，从题目的形式上感觉是道挺不错的题目。
2. Given two arrays A [1..n] and B[1..m], find the smallest window in A that contains all elements of B. That is, find a pair <l,k> such that A[l..k] contains B[1..m] For example, given A = 3,1,5,7,3,5,2 and B = 5,3 then the smallest window is [3,5].

最后顺带一道趣题吧。
3. 有一个01数组，现在要你对它进行重排（即保持0和1的数目不变），使得成为这样的形式：0101..01xxx.. 即01间隔，然后多出来的0或者1放到后面（用xx表示）。例如110110重排为010111。要求O(1)空间复杂度，以及只能遍历一次。

--
刘未鹏(pongba)|C++的罗浮宫
http://blog.csdn.net/pongba
TopLanguage
http://groups.google.com/group/pongba

[rmq]

第1题：
假设共有n个station，编号一次为 1,2,3,...,n， 其中1和n是相邻的，这样构成一个环。
任意选择一个station作为其实点，假设其实点为i，我们考虑顺时针方向（逆时针同理），然后让汽车尽可能的开，如果能开会到i，则i为所求，否则
假设车经历了
i,i+1,i+2,...,j， 而从j无法再到j+1， 那么一个结论是i+1,i+2,...,j这些点都不可能是起始点，因为i到i+1时，邮
箱中的油量是>=0的。
这样再考虑j+1作为起始点即可，重复。最终是线性的。

第2题：
题目中没说是否必须按顺序包含，看例子好像是要求顺序的，我就按这个意思来吧。
还没想到最优的算法，先给一个n^3的dp吧，抛砖引玉了

memo[i][j][k]表示A[i],A[i+1],...,A[k] 是否能包含B[j],B[j+1],...,B[len(B)-1]
状态转移 ： 如果A[i]==B[j], 则memo[i][j][k]=memo[i+1][j+1][k] 否则 memo[i][j]
[k]=memo[i+1][j][k];
左右解只需遍历memo[i][0][k]，知道可以的且k-i最小的。

On 6月4日, 下午6时24分, pongba <pon...@gmail.com> wrote:
> @All：
>
> 该做第1题啦，也是很好的题目:D
>
> 2008/6/4 pongba <pon...@gmail.com>:
>
>
>
> > windstorm说上次一次给的题目太多，抱歉，没有筛选。这次给出两道不错的题目。
>

> > 第一道是上次转载的阅微堂 <http://zhiqiang.org>那里（后者从这里 <http://www.careercup.com/>

[Eric]

我的疑问是难道这个不等于两次遍历? 写入也要迭代器的吧? 那么就至少需要两个迭代器了

我复述一下xxmplus 的思路：

有两个头，一个负责在前面读，一个负责在后面写，等价于生产者消费者模型。同时有两个计数器。 前面的读的东西是生产者，读到1 就给 1的计数器
+1 读到0 就给0 的计数器 +1。 后面的写头 轮流写0/1 如果0/1计数器里面是空的，又正好要写0/1 就 block 住 直到有新的
0/1进来，或者读头读完。

[rmq]

第2题：
暴力的方法也能做到n^2，上面给了一个n^3的，惭愧啊。
首先枚举A中一个元素A[i]，使得A[i]==B[0]，然后以i为起始点，通过贪心的方法，找出能包含B所有元素的最短窗口。
这个方式n^2的。

[pongba]

2008/6/5 rmq <zhan...@gmail.com>:

第2题：
 暴力的方法也能做到n^2，上面给了一个n^3的，惭愧啊。
 首先枚举A中一个元素A[i]，使得A[i]==B[0]，然后以i为起始点，通过贪心的方法，找出能包含B所有元素的最短窗口。
 这个方式n^2的。

呃，我在上个帖子里面给的也是这个方法，但是..它的复杂度为什么是O(n^2)的？详细分析一下？

[rmq]

第2题的pongba说的那个复杂度分析。
代码如下：
int [] A=...;
int [] B=...;
int res=10000000;
for(int i=0;i<A.length;i++) {
if(A[i]==B[0]) {
int x=i,y=0;
while(y<B.length) {
while(x<A.length && A[x]!=B[y])x++;
if(x==A.length)break;
x++;
y++;
}
if(y==B.length) {
res=Math.min(res, x-i);
}
}
}

偷懒了，代码中只求区间的最小长度。
外层循环是n次，内层两个循环的总次数<2n， 因为每次循环x或者y都在增加。
因此总的复杂度是n^2的

On 6月5日, 下午1时05分, pongba <pon...@gmail.com> wrote:
> 2008/6/5 rmq <zhangf...@gmail.com>:

[pongba]

2008/6/5 rmq <zhan...@gmail.com>:

第2题的pongba说的那个复杂度分析。
代码如下：
       int [] A=...;
       int [] B=...;
       int res=10000000;
       for(int i=0;i<A.length;i++) {
           if(A[i]==B[0]) {
               int x=i,y=0;
               while(y<B.length) {
                   while(x<A.length && A[x]!=B[y])x++;
                   if(x==A.length)break;
                   x++;
                   y++;
               }
               if(y==B.length) {
                   res=Math.min(res, x-i);
               }
           }
       }

偷懒了，代码中只求区间的最小长度。
外层循环是n次，内层两个循环的总次数<2n， 因为每次循环x或者y都在增加。
因此总的复杂度是n^2的

我忽然发现，我不记得当时怎么想的了，这的确明显是n^2啊.. 为什么我当时不这么认为呢？奇怪..

[rmq]

可是我感觉n^2的也不是最优的，直觉还有更优的算法， 呼唤大牛

On 6月5日, 下午7时17分, pongba <pon...@gmail.com> wrote:
> 2008/6/5 rmq <zhangf...@gmail.com>:
>
>
>

[Eric]

第一题很简单的, 用推箱子方法. 把油反向往前推.

先假设顺时针可以有解的话, 从任意一点开始, 逆时针往前走, 遇路减路, 遇油加油. 在油站如果结果为正, 把当前的和记下, 把和刷成0, 然
后从下条路开始, 继续同样的方法往前推, 推的结果是所有局部和为负的都往前推, 直到在某个点和某个正的值合并. 这样, 如果有可行解, 最后环
上就没有负的元素, 有些油站是0或者正的, 从任意一个正的开始, 顺时针走, 肯定有解.
O(N) [最多往前推积木推2N个点]

[pongba]

2008/6/7 Eric <xu.ma...@gmail.com>:

第一题很简单的, 用推箱子方法. 把油反向往前推.

先假设顺时针可以有解的话, 从任意一点开始, 逆时针往前走, 遇路减路, 遇油加油. 在油站如果结果为正, 把当前的和记下, 把和刷成0, 然
后从下条路开始, 继续同样的方法往前推, 推的结果是所有局部和为负的都往前推, 直到在某个点和某个正的值合并. 这样, 如果有可行解, 最后环
上就没有负的元素, 有些油站是0或者正的, 从任意一个正的开始, 顺时针走, 肯定有解.
O(N) [最多往前推积木推2N个点]

那么，这个思路是通过什么过程得到的呢？看起来是通过对以前做过类似题目的类比？

我发现考察人们得到答案之前经历的思考过程是很有意思的：一个题目的答案往往只有一种，然而不同的人通过不同的思路达到这个答案。比如这道题我做的时候就是首先将问题转化为"每个前缀和都>=0"，然后再试着从任意一个节点往前迭代并观察条件的变化，讨论不同case下蕴含的结论。其中转化问题这一步是用的倒推。但第二步则是用的顺序性思路，大家都知道顺序性思路往往很多时候是试错性质的，不属于最佳思路。所以我总觉得也许这道题还有更好的思维方法。

[pongba]

2008/6/5 rmq <zhan...@gmail.com>:

可是我感觉n^2的也不是最优的，直觉还有更优的算法， 呼唤大牛

我也有此感觉。哪位牛做一下？

[Eric]

其实我的思路是, 先把油站减去路 然后每个油站有正有负. 如果非要理论的话, 就是考察一下是不是有可行解, 看看问题出在哪儿.

油站有正有负的话, 正的可以直接经过, 负的就需要之前油站的油, 因此往前走, 找正的补充

思路应该比较自然.

On Jun 6, 11:36 pm, pongba <pon...@gmail.com> wrote:
> 2008/6/5 rmq <zhangf...@gmail.com>:
>

[Wang Xin]

我来公布第一题的最佳答案吧，是我在7年前从一北大朋友那听来的，他的解答是他的数学老师给的：

假设汽车带有0油从任意一点出发，遇油加，遇路减，即便油量为负数也无所谓，循环一圈后，找到值最小的那个点，从那个点出发就肯定可以跑完（只需要进行n次计算）

2008/6/7 Eric <xu.ma...@gmail.com>:

--
Everything is possible and available if we trust ourselves!

[pongba]

2008/6/12 Wang Xin <cber.w...@gmail.com>:

我来公布第一题的最佳答案吧，是我在7年前从一北大朋友那听来的，他的解答是他的数学老师给的：

假设汽车带有0油从任意一点出发，遇油加，遇路减，即便油量为负数也无所谓，循环一圈后，找到值最小的那个点，从那个点出发就肯定可以跑完（只需要进行n次计算）

漂亮！:)

[hayate]

nice!

要是有思路就更好了。知道了这个答案，倒是可以证明这个结论。

2008/6/12 Wang Xin <cber.w...@gmail.com>:

[Wang Xin]

呵呵，可惜我是刚刚听到这个问题时就顺便听到的答案，而这个答案偏偏又很容易被证明且又很精巧
然后，偶就不知道那个数学教授的思路是怎么来的了:(

2008/6/12 hayate <haya...@gmail.com>:

[pongba]

2008/6/12 Wang Xin <cber.w...@gmail.com>:

呵呵，可惜我是刚刚听到这个问题时就顺便听到的答案，而这个答案偏偏又很容易被证明且又很精巧
然后，偶就不知道那个数学教授的思路是怎么来的了:(

可以试着重建思路：

要寻找满足条件P的加油站，那么试探路径有：

P=>__
~P=>__
__=>P
__=>~P

从这四个方向上去探索题目条件中蕴含的结论总是有意义的。

cber给出的答案貌似就是第二个探索：~P=>__。即，如果从一个加油站S开始无法跑完全程，那么必然跑到某一点之后就跑不下去了，这就意味着从S到那个点的Ci（油量）的和小于Gi（路程）的和，于是就使得Sigma(Ci-Gi)变小。

把这个逻辑反一下：~__=>P。即，只要从某个点S开始之后Sigma(Ci-Gi)再也不变小了，那么必然P成立（即从S必然能跑完全程）。

[Wang Xin]

呵呵，当时从朋友口中得知的是，他的教授对于此题不屑一顾，完全是即时给出该解

估计对于他来说，这种思维方式已经成了一种本能了吧

2008/6/12 pongba <pon...@gmail.com>:

[pongba]

2008/6/12 Wang Xin <cber.w...@gmail.com>:

呵呵，当时从朋友口中得知的是，他的教授对于此题不屑一顾，完全是即时给出该解

估计对于他来说，这种思维方式已经成了一种本能了吧

对，正是如此！:) 练得多了，变成了内隐记忆，根本意识不到在以这种方式思考的~

[hayate]

嗯 不错 考察逆否命题
但是实际思考的时候，有时会在某一点有很多可能，必须抽象出确切的概念才能恰好达到目标。比如这里我觉得核心是意识到sigma再也不能小了这个概念，而通常的思路是由于sigma是负数了，所以就此打住，然后考虑从下一个点开始。因此错过了一次走完，统计全部信息的机会。

2008/6/12 pongba <pon...@gmail.com>:

[pongba]

2008/6/12 hayate <haya...@gmail.com>:

嗯 不错 考察逆否命题
但是实际思考的时候，有时会在某一点有很多可能，必须抽象出确切的概念才能恰好达到目标。比如这里我觉得核心是意识到sigma再也不能小了这个概念，而通常的思路是由于sigma是负数了，所以就此打住，然后考虑从下一个点开始。因此错过了一次走完，统计全部信息的机会。

对，思维定势，问题解决的最大敌人..
然而，其实没有思维定势人类是根本无法思考的，因为没有思维定势就是每一步都将所有可能性考虑进去，那样的话可能性就太巨大了..绝对是指数级的..

[rmq]

一次走完，再次统计最小，复杂度仍然是2n

试探那个也是2n

On 6月12日, 下午11时22分, hayate <hayate...@gmail.com> wrote:
> 嗯 不错 考察逆否命题

> 但是实际思考的时候，有时会在某一点有很多可能，必须抽象出确切的概念才能恰好达到目标。比如这里我觉得核心是意识到sigma*再也不能小了*

> 这个概念，而通常的思路是由于sigma是负数了，所以就此打住，然后考虑从下一个点开始。因此错过了一次走完，统计全部信息的机会。
> 2008/6/12 pongba <pon...@gmail.com>:
>
>
>

> > 2008/6/12 Wang Xin <cber.wang...@gmail.com>:

[Wang Xin]

2n吗？给3个临时变量，n就OK了

2008/6/13 rmq <zhan...@gmail.com>:

[pongba]

2008/6/13 rmq <zhan...@gmail.com>:

一次走完，再次统计最小，复杂度仍然是2n

试探那个也是2n

其实关键不是复杂度啦，而是这种方法背后蕴含的思维。比如一个可能有环的单链表，如何线性地探测出它是否有环：

一个甚为精巧的思路是用两个迭代器，后者是前者速度的两倍，如果n步内后者能追上前者，则有环。

而其实这道题目还有一个朴素的解法，没有这么巧妙，但复杂度也是线性的。

还有另一个题目，单链表，线性时间找到倒数第K个节点。

一个精巧的做法是用两个迭代器，相隔K。同步递增到结尾，前一个迭代器就指向倒数第K个元素。

而其实这个题目也还有一个朴素的解法：数一数链表长度N，将N减去K，然后重新遍历(N-K)个节点。

[Eric]

正巧pangba提到了这两个关于单链表的题 请大家基于这两道题，基于启发式思维的方法 想这一题：

一个有环的单链表，如何线性地打开他的环（即找到指回环的那个元素 让他的Next 指针变成NULL）

基于上两题，这个题目就不难了。


On 6月13日, 上午6时43分, pongba <pon...@gmail.com> wrote:
> 2008/6/13 rmq <zhangf...@gmail.com>:

[hayate]

一次走完是n啊，边走边记录就知道哪里是最小了。

2008/6/13 rmq <zhan...@gmail.com>:

[pongba]

2008/6/14 Eric <xu.ma...@gmail.com>:

正巧pangba提到了这两个关于单链表的题  请大家基于这两道题，基于启发式思维的方法 想这一题：

一个有环的单链表，如何线性地打开他的环（即找到指回环的那个元素 让他的Next 指针变成NULL）

基于上两题，这个题目就不难了。

Eric，这道题目真巧妙，多谢！:)
最巧妙的是它完美体现了Polya的"考虑一个与此相关的问题"的思路。
真是个好题目。

[hayate]

"一个精巧的做法是用两个迭代器，相隔K。同步递增到结尾，前一个迭代器就指向倒数第K个元素。
而其实这个题目也还有一个朴素的解法：数一数链表长度N，将N减去K，然后重新遍历(N-K)个节点。"

窃以为这两种方法没有本质区别，都是两个迭代器，执行步数也一样。但是前一种使人显得smart，所以更受面试官的青睐 :D

2008/6/13 pongba <pon...@gmail.com>:

[pongba]

2008/6/13 pongba <pon...@gmail.com>:

比如一个可能有环的单链表，如何线性地探测出它是否有环：

一个甚为精巧的思路是用两个迭代器，后者是前者速度的两倍，如果n步内后者能追上前者，则有环。

上次发现了这个问题的另一个做法，今天又想起来，也贴上来吧：

是从链表求逆想到的，将这个链表求逆。如果是有环的链表，你会发现求逆求到最后一定会回到原来的头节点。如果无环则不会。

[nextRainbow]

第三题

遍历数组，index记录下标号（从零开始），如果index是奇数，则检查该元素是否为0，是则index++，否则在index后找值为0的
元素，与之互换然后index++，如果没有找到值为0的元素，则结束。如果index为偶数，则检查该元素是否为1，是则index++，否则在
index后找值为1的元素，与之互换然后index++，如果没有找到值为1的元素，则结束。如果index达到最大，结束。

大家看看行不行呢？

On 6月4日, 下午4时13分, windstorm <likunarmstr...@gmail.com> wrote:
> 第三题有点意思，我有两个思路：
>
> 1 用两个变量表示下标，一个表示奇数下标，一个表示偶数下标
>
> 奇数下标的动作是：如果在自己位置上的数不是0，就停止，如果是0，就自加2，一直到指得数不为0为止。
>
> 偶数下标的动作是：如果在自己位置上的数不是1，就停止，如果是1，就自加2，一直到指得数不为1为止。
>
> 等到两方都停止的时候，交换双方值。循环下去，应该一次遍历就可以搞定。
>
> 2 设一个临时分量temp，下标分量index，然后用i遍历数组，遇到0，就和index的值交换，此时index+1有两种情况，如果不等于i，index+-1所指的值此时肯定为1（因为index比i小，不会存在是0的情况），所以直接index自增2。如果等于i，i指向的值取非，
>
> 这种的话会有意外，比如index ==
> i，比如一开始就是0001.....这种数组，那么就需要把"用i遍历数组，遇到0，就xxxxxx"这个思路换成"用i遍历数组，遇到1，就xxxxxx"-。
>
> 两个都是遍历一次就行了，不过第二个思路要比第一个思路复杂很多，纸上画了很久才大概摸清楚。不过我不知道O(1)空间复杂度是什么意思？
>
> 2008/6/4 pongba <pon...@gmail.com>:
>
>
>
>
>
> > windstorm说上次一次给的题目太多，抱歉，没有筛选。这次给出两道不错的题目。
>
> > 第一道是上次转载的阅微堂那里（后者从这里转载的，上面有很多不错的题目，分类也井井有条），silwile说这道题不错，我就做了一下，的确不错，小巧又不失-精彩。据说也是微软的经典面试题之一。
>
> > 1. There is a circular track. There are n gas stations of capacity ci. To go
> > from one station to the next station it takes certain amount of gas gi. For
> > any station the gas available may not be enough to get to the next station.
> > Write a linear time algorithm to find the correct station in which we must
> > start in order to complete one round around the track.
>
> > 第二道题目是Amazon的面试题，从题目的形式上感觉是道挺不错的题目。
> > 2. Given two arrays A [1..n] and B[1..m], find the smallest window in A that
> > contains all elements of B. That is, find a pair <l,k> such that A[l..k]
> > contains B[1..m] For example, given A = 3,1,5,7,3,5,2 and B = 5,3 then the
> > smallest window is [3,5].
>
> > 最后顺带一道趣题吧。
> > 3. 有一个01数组，现在要你对它进行重排（即保持0和1的数目不变），使得成为这样的形式：0101..01xxx..
> > 即01间隔，然后多出来的0或者1放到后面（用xx表示）。例如110110重排为010111。要求O(1)空间复杂度，以及只能遍历一次。

>
> > --
> > 刘未鹏(pongba)|C++的罗浮宫
> >http://blog.csdn.net/pongba
> > TopLanguage
> >http://groups.google.com/group/pongba
>

> --
> Yours Sincerely
> Kun
>
> blog:www.forwind.cn

[windstorm]

这个想法貌似是我第二个思路的改进版，应该可行，但是没有第一个思路速度快

第一个思路有点bug，但是后面朋友patch了。

----------------------------------------------------------------------------------
Yours Sincerely
Kun

blog: www.forwind.cn

2008/7/13 nextRainbow <wangwe...@gmail.com>:

[dnpg]

一个变量(count)即可

(遇到'1' 而且 count < 0) 或者 (遇到'0' 而且 计数器 > 0), 则输出 '0', '1'
遇到的是1:
count += 1
否则
count -= 1

如果count != 0:
如果 count>0 , 输出 '1' * count
否则 '0' * (0-count)

def o(s):
count = 0
for i in s:
if (i == '1' and count < 0) or (i == '0' and count > 0):
print '0', '1',
count += 1 if i == '1' else -1
print '1' * count if count >0 else '0' * (0-count)

[windstorm]

输出？如果是输出，很明显xxmplus的方法是最简单的

----------------------------------------------------------------------------------
Yours Sincerely
Kun

blog: www.forwind.cn

2008/7/13 dnpg <dnpg...@gmail.com>:

[dnpg]

那就c好了:

void o(char * s)
{
int count = 0;
char * p = s;
while(*s) {
if ((*s == '0' && count > 0) || (*s == '1' && count < 0)) {
*p++ = '0';
*p++ = '1';
}
count += *s == '1' ? 1 : -1;
++s;
}
if (count > 0)
while(*p) *p++ = '1';
if (count < 0)
while(*p) *p++ = '0';

}


On Jul 13, 9:02 pm, windstorm <likunarmstr...@gmail.com> wrote:
> 输出？如果是输出，很明显xxmplus的方法是最简单的
>
> ----------------------------------------------------------------------------------
> Yours Sincerely
> Kun
>
> blog:www.forwind.cn
>

> 2008/7/13 dnpg <dnpg1...@gmail.com>:

[LiBUDI]

看第三题时直接就想到了xxmplus的算法，比较直白，后来再看dnpg的代码，又有了一些新的启发，dnpg的算法效率和适应能力要更高一些，比如
在处理未知长度的流和生成器时候。我用 lysee 翻译一下，结果都是正确的

const string _01 = "01010010010110101010";

// xxmplus

public void listA(string bitlist)
{
int o, z;
bitlist.each {|char c| if (c == '0') ++ z; else ++ o };
z.times {|int x| = "0"; if (x < o) = "1" };
(o - z).times { = "1" };
}

// dnpg

public void listB(string bitlist)
{
int count;
bitlist.each {|char c|
if ((c == '1' and count < 0) or (c == '0' and count > 0)) = "01";
if (c == '0') -- count; else ++ count;
};
if (count > 0) = "1".repeat( count); else
if (count < 0) = "0".repeat(- count);
}

main:

listA(_01);
= eol;

listB(_01);
= eol;

= dumpc();
sys::readln();

----------------------------------------------------
01010101010101010100
01010101010101010100
module main
{
import main, sys;

public const string _01;

void listA(string bitlist)
{
VARB o: int
VARB z: int
STMT
PUSH_VARB bitlist
CAST sys::string.each METHOD [1]
PUSH_SUBF main::listA.1
CALL [2]
STMT
PUSH_VARB z
CAST sys::int.times METHOD [1]
PUSH_SUBF main::listA.2
CALL [2]
STMT
PUSH_VARB o
PUSH_VARB z
CALC -
CAST sys::int.times METHOD [1]
PUSH_SUBF main::listA.3
CALL [2]
STMT
RETURN
}

variant listA.1(char c)
{
STMT
PUSH_VARB c
PUSH_CHAR '0'
CALC ==
GOFP 0002
STMT
INC z
STMT
GOTO 0001
[0002]
STMT
INC o
STMT
[0001]
STMT
}

variant listA.2(int x)
{
STMT
PUSH_STR 0
PRINT [1]
STMT
PUSH_VARB x
PUSH_VARB o
CALC <
GOFP 0004
STMT
PUSH_STR 1
PRINT [1]
STMT
GOTO 0003
[0004]
[0003]
STMT
}

variant listA.3()
{
STMT
PUSH_STR 1
PRINT [1]
STMT
}

void listB(string bitlist)
{
VARB count: int
STMT
PUSH_VARB bitlist
CAST sys::string.each METHOD [1]
PUSH_SUBF main::listB.4
CALL [2]
STMT
PUSH_VARB count
PUSH_INT 0
CALC >
GOFP 0010
STMT
PUSH_STR 1
CAST sys::string.repeat METHOD [1
PUSH_VARB count
CALL [2]
PRINT [1]
STMT
GOTO 0009
[0010]
STMT
PUSH_VARB count
PUSH_INT 0
CALC <
GOFP 0012
STMT
PUSH_STR 0
CAST sys::string.repeat METHOD [1
PUSH_VARB count
CALC NEG
CALL [2]
PRINT [1]
STMT
GOTO 0011
[0012]
[0011]
STMT
[0009]
STMT
RETURN
}

variant listB.4(char c)
{
STMT
PUSH_VARB c
PUSH_CHAR '1'
CALC ==
CAST TOP BOOL
JMPF 0011:
PUSH_VARB count
PUSH_INT 0
CALC <
CAST TOP BOOL
CALC AND
0011:CAST TOP BOOL
JMPT 0025:
PUSH_VARB c
PUSH_CHAR '0'
CALC ==
CAST TOP BOOL
JMPF 0023:
PUSH_VARB count
PUSH_INT 0
CALC >
CAST TOP BOOL
CALC AND
0023:CAST TOP BOOL
CALC OR
0025:GOFP 0006
STMT
PUSH_STR 01
PRINT [1]
STMT
GOTO 0005
[0006]
[0005]
STMT
PUSH_VARB c
PUSH_CHAR '0'
CALC ==
GOFP 0008
STMT
DEC count
STMT
GOTO 0007
[0008]
STMT
INC count
STMT
[0007]
STMT
}

variant main(variant ARGS)
{
STMT
PUSH_STR 01010010010110101010
SAVE_TO main::_01
STMT
PUSH_FUNC main::listA
PUSH_VARB main::_01
CALL [2]
STMT
PUSH EOL
PRINT [1]
STMT
PUSH_FUNC main::listB
PUSH_VARB main::_01
CALL [2]
STMT
PUSH EOL
PRINT [1]
STMT
PUSH_FUNC sys::dumpc
CALL [1]
PRINT [1]
STMT
PUSH_FUNC sys::readln
CALL [1]
STMT
RETURN
}
}