【第三轮】6.16-6.22 CareerCup 1.2

heycinderella 发表于 2014-6-18 11:02
求解释：为什么空间是lgN? 和binary search有什么关系？
评论：
  if (str != str[j]) {

求问，为什么这种优化比较好？ 这样不也增加了 if 里面的比较次数了嘛？ 每次都要比较一下？

jaly50 发表于 2014-6-18 00:51
【解题思路】
用java写的，不是用c++.不知道还有没有意义。
嗯，就是字符串先转成StringBuffer或者char ...

没看到哪里能够点评，只好回复了。。
咱俩都是java写的，但是java的string特性是Immutable的，所以你用的是tochararray最后再用valueof把结果dump出来。但是这样做空间复杂度依旧是O(N)，这里我也写错了。其他没问题。
ps我没法点评，是我等级不够高么。。
pps我是刘奕驰，ebiz、mism面基去打桌游做你旁边

serolins 发表于 2014-6-18 21:12
hmm大概是要分情况吧，如果本身前半段和后半段中相同的字符比较多的情况下，这样能省一点吧。若是大部分 ...

恩有道理

time complexity : O(n)
space complexity : O(1)


https://gist.github.com/daisyang/74f6d92e6968c8a2f5bf

chouclee 发表于 2014-6-17 11:47
【解题思路】two pointers, one points to first char, the other traverses to the end of the string.  S ...

nice work!

【解题思路】: locate begin and end pointer to the string, swap while begin < end         
【时间复杂度】 : O(n)
【空间复杂度】 : O(1)
【gist link】: https://gist.github.com/xun-gong/c7e705a292d725cf98d4

咦之前帖子貌似没发上来
同JAVA党
【解题思路】: Find the middle point of the array, swap each pair of char that is before
         * and after the middle point with the same distance
【时间复杂度】 : O(n)
【空间复杂度】 : O(n)这个空间复杂度想不明白求指导，str变charArray就是要n了吧?
【gist link】: https://gist.github.com/XiaoxiaoLi/fcfc06c648aff4bb6bc4

【解题思路】One pointer from start of string and one pointer from end of string go to the middle and switch chars at the same time.
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/jason51122/28500b1b439e6030fc9d

【解题思路】头尾两个指针，循环交换位置，直到相遇
【时间复杂度】O（n）
【空间复杂度】O（1） （好像空间占用为常量时是O（1）？ 说好的看书我还没好好看，懒死了，毕业各种烂事真多）
【gist link】https://gist.github.com/weazord/f31834b0a814e9834323
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】