google 电面

内个，请教LZ第一题，如何不sort涅？想不通了……(⊙﹏⊙)b
我的code如下，大家多指教：

/* wiggle sort
flg=0: a>=b<=c>=d<=e........
flg=1: a<=b>=c<=d>=e........
*/
template<typename T>
void wigglesort( vector<T> &v, int flg ){
        if(v.size()<=2)
                return;
        sort(v.begin(),v.end());
        int first;
        if(flg==0) //
                first=0;
        else if(flg==1)
                first=1;
        int idx=first;
        while(idx<v.size()-1){
                swap(v[idx],v[idx+1]); idx+=2;
        }
};

stochasticer 发表于 2015-4-8 18:23
内个，请教LZ第一题，如何不sort涅？想不通了……(⊙﹏⊙)b
我的code如下，大家多指教：

只要分奇偶一个个往右比较就可以了，35421=>53421=>53421=>53421=>53412.

sunfish 发表于 2015-4-8 12:04
如果矩阵的宽度很大这么办，会overflow吗？

这还真没有考虑过，电面时间比较短。没问这么细。懂的人麻烦解答一下哈！

celtspirit 发表于 2015-4-9 04:22
只要分奇偶一个个往右比较就可以了，35421=>53421=>53421=>53421=>53412.

突然发现确实是想复杂了！这题貌似是个坑啊，不小心就会掉进去。多谢提点！

celtspirit 发表于 2015-4-8 11:15
(100000-1) &100000 = 0;

(101000-1) & 101000 != 0;

good idea~ learn it, thanks~

celtspirit 发表于 2015-4-8 11:15
(100000-1) &100000 = 0;

(101000-1) & 101000 != 0;

楼主楼主，但是
(100001 - 1) & 101000 也是 != 0 呀， 但是是不合理的， 楼主能讲的更详细点吗？

resoy 发表于 2015-4-10 02:24
楼主楼主，但是
(100001 - 1) & 101000 也是 != 0 呀， 但是是不合理的， 楼主能讲的更详细点吗？

你是已经先进行与运算了，现在的问题是判断有几个1啊。 你跳过了一步，你看看前面的回复。

jeager 发表于 2015-4-8 05:43
我也是这么想的
预处理 matrix to bitmap O(n2)
line对比line worst 是O(n2)

想问一下一些细节，预处理是指把每一行存成bitset吗？
如果这么做的话line对比是O(n^2)，但是line和line的and操作是O(n)，所以总的应该是O(n^3)吧。
不知道我理解的对不对

xuchen1m3fd 发表于 2015-4-10 04:54
想问一下一些细节，预处理是指把每一行存成bitset吗？
如果这么做的话line对比是O(n^2)，但是line和line ...

首先 我表示 长见识了 头一次听说BitSet
我的方法是直接处理成一个Integer
这样的话 and操作就是O(1)了

resoy 发表于 2015-4-10 02:24
楼主楼主，但是
(100001 - 1) & 101000 也是 != 0 呀， 但是是不合理的， 楼主能讲的更详细点吗？

我来解释一下吧

1000&0100 = 0，fail;
1000&1000 = 1000 > 0 => (1000-1) = 0111, 0111&1000 = 0, fail;
1001&1010 = 1000 > 0 => (1000-1) = 0111, 0111&1000 = 0, fail;
1010&1010 = 1010 > 0 => (1010-1) = 1001, 1001&1000 > 0, success;
1011&1010 = 1010 > 0 => (1010-1) = 1001, 1001&1000 > 0, success;
1011&1011 = 1011 > 0 => (1011-1) = 1010, 1010&1011 > 0, success;