亚麻新鲜面筋附最近三周bq整理

xxxxx

454400098 发表于 2019-3-14 01:00
请问楼主这道题二分法应该怎么做呀不是太懂

我的思路是在单独出现的字符之前偶数位=奇数位，从单独字符之后，偶数位！=奇数位，即使是后面成对出现的字符两个相同字符也是先奇数再偶数，所以用二分去找第一个偶数位！=奇数位的地方就行了~

xxxxx

三班长发表于 2019-3-14 01:57
XOR，之前看到一个面经里提到过

唔对之前地里有XOR的做法但是我没看到233 不过借问一句xor的复杂度是多少啊

xxxxx

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

xxxxx

sundance1 发表于 2019-3-13 22:02
查了分治复杂度也是o(n)...

不需要sorted就可以二分二分的思路我已经在前面回答啦供参考

三班长

xxxxx 发表于 2019/03/14 03:36:47

唔对之前地里有XOR的做法但是我没看到233 不过借问一句xor的复杂度是多少啊

每次xor是O(1), 总的应该还是要O(n). 好处就是逻辑简单代码短吧，也不需要考虑corner case

Wu_kong

xxxxx 发表于 2019-3-14 03:33
我的思路是在单独出现的字符之前偶数位=奇数位，从单独字符之后，偶数位！=奇数位，即使是后面成对出现的 ...

楼主, 你的思路是基于字符串已经是sorted, 如果字符串是这样, [A,E,D,A,D], 还怎么二分

xxxxx

gui59106375 发表于 2019-3-17 00:17
楼主, 你的思路是基于字符串已经是sorted, 如果字符串是这样, [A,E,D,A,D], 还怎么二分

emmm我没有基于sorted啊…我只用到了位置的奇偶性，不需要比较字符大小

Wu_kong

xxxxx 发表于 2019/03/17 02:59:55

emmm我没有基于sorted啊…我只用到了位置的奇偶性，不需要比较字符大小

楼主能否说的稍微详细一点，看了你之前的解法，单独字符之前偶数位等于基数位，但是这个解法对于字符串[ a,b,a,b,c] 并不适用啊

tianyiwu

楼主leadership 准则是指什么呀？

sanyuzhang

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

亚麻新鲜面筋 附最近三周bq整理