一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1869|回复: 60
收起左侧

[CareerCup] 【第三轮】6.16-6.22 CareerCup 1.2

[复制链接] |试试Instant~ |关注本帖
wrj5518 发表于 2014-6-15 23:20:05 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
1.2 Implement a function void reverse(char* str) in C or C++ which reverses a null-terminated string.

回复解法可以按照以下格式来
【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------optional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】

Notice:
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子,除了贴解法,欢迎讨论,集思广益
4、任何未尽之处,欢迎回报名帖提问,我会进一步作出修改。



readman 发表于 2014-6-16 00:07:32 | 显示全部楼层
【解题思路】
same to binary search ?
【时间复杂度】
n, since  i use char ary
【空间复杂度】
lg, no need to traverse all char in string
【gist link】
https://gist.github.com/gaoyike/50d11d25f2f59deb3150
【test case】

评分

1

查看全部评分

回复 支持 2 反对 0

使用道具 举报

atlas1017 发表于 2014-6-16 05:56:59 | 显示全部楼层
readman 发表于 2014-6-16 00:07
【解题思路】
same to binary search ?
【时间复杂度】

这题目就是想要用 char pointer的吧 虽然差不多= =
回复 支持 反对

使用道具 举报

habina 发表于 2014-6-16 06:10:34 | 显示全部楼层
【解题思路】
  Two pointers, named begin and end, begin points to the begin and towards to the end, end points the last character and towards to the begin.
  Swap characters between these two pointers until they point to the same address or begin pointer is step over by one of end pointer
【时间复杂度】
  O(N)
【空间复杂度】
  O(1)
【gist link】
  https://gist.github.com/habina/d55da65182a6622e64b5
【Test Case】
  null character
回复 支持 反对

使用道具 举报

qianhuang 发表于 2014-6-16 09:50:49 | 显示全部楼层
本帖最后由 qianhuang 于 2014-6-16 10:06 编辑

【解题思路】
two pointers which point the head/tail(not the '\0', but the one before it) of the string. Then swap their value, and update the pointers.
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/qianhuang/96320b980038b7df26cd
回复 支持 反对

使用道具 举报

monkerek 发表于 2014-6-16 11:27:15 | 显示全部楼层
【解题思路】
Using 2 pointers respectively point to the start and the end of the string, swap the value they point to, then move the pointers iteratively.
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/monkerek/100587049a945115f589
回复 支持 反对

使用道具 举报

jing0328 发表于 2014-6-16 13:44:18 | 显示全部楼层
本帖最后由 jing0328 于 2014-6-17 09:39 编辑

【解题思路】traverse the string(code written in java)
【时间复杂度】O(n)
【空间复杂度】O(n)
【gist link】https://gist.github.com/startupjing/8f8a5adc6ed5408923a1

回复 支持 反对

使用道具 举报

wilbert 发表于 2014-6-16 22:47:09 | 显示全部楼层
【解题思路】
得到字符串长度,swap首尾字符直到相遇
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/anonymous/437c05fb726da019ff52
回复 支持 反对

使用道具 举报

小柯西 发表于 2014-6-17 00:13:35 | 显示全部楼层
本帖最后由 小柯西 于 2014-6-19 01:07 编辑

【解题思路】Locate the ending of the string, then swap those previous characters.  
【时间复杂度】n
【空间复杂度】1
【gist link】https://gist.github.com/e63557112ca2253e3d60.git
【test case】Empty string and null pointer.
回复 支持 反对

使用道具 举报

兰橘清檬 发表于 2014-6-17 01:50:20 | 显示全部楼层
【解题思路】
利用两个指针,开始一个指向数组头,一个指向数组尾,然后两两交换,指针同时向中间移动
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/JoyceeLee/4e200d7a93e376415d67
回复 支持 反对

使用道具 举报

林微熙 发表于 2014-6-17 02:01:22 | 显示全部楼层
【解题思路】
traverse the string, find the end.swap from beginning until they meet in the middle
【时间复杂度】
  O(N)
【空间复杂度】
  O(1)
【gist link】https://gist.github.com/hilda8519/83237bb94060d14ab83f
回复 支持 反对

使用道具 举报

zhenzhenanan 发表于 2014-6-17 06:37:17 | 显示全部楼层
【解题思路】
用strlen获取字符串长度。用i和j两个lindex,其中i在0位置;j在len-1位置。i和j相互靠近并调换所指向的字符,直到i和j相遇。这个过程中,'\0'一直在len位置没动,所以程序结束后还是在len位置。
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/seemuch/af64b140e576b6ea73ad#file-1_2-cc
---------------OPTional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】
回复 支持 反对

使用道具 举报

jyh橘子 发表于 2014-6-17 08:47:46 | 显示全部楼层
【解题思路】I use two pointers for the head and tail of the string, swap the two elements , move pointers forward and backward, swap until two pointers meet.
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/jyhjuzi/4f26f7112cf58d9fcd2d
回复 支持 反对

使用道具 举报

RealityPC 发表于 2014-6-17 10:52:08 | 显示全部楼层
【解题思路】two iterator at the begin and end of string, swap chars and move the iterator until begin is equal or greater than end
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/pchong90/e48b4175b82883e62780
回复 支持 反对

使用道具 举报

chouclee 发表于 2014-6-17 11:47:27 | 显示全部楼层
【解题思路】two pointers, one points to first char, the other traverses to the end of the string.  Swap the elements they are pointing to. Then first pointer points to next char while the last one points to previous char. This process repeats until two pointers cross.
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/chouclee/bd4d1f0292c7111bbe74
回复 支持 反对

使用道具 举报

fang_wu 发表于 2014-6-17 17:48:45 | 显示全部楼层
【解题思路】java实现,先把string转换为char数组,然后跟二分法一样,维持left和right两个。一个++,一个--
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/qiangusc/4b705d25103a944d74e1
回复 支持 反对

使用道具 举报

bitcpf 发表于 2014-6-17 23:36:13 | 显示全部楼层
【解题思路】exchange the content of the first 1/2 and the last 1/2
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/bitcpf/4 ... ca0#file-cc1_2-java
回复 支持 反对

使用道具 举报

jaly50 发表于 2014-6-18 00:51:46 | 显示全部楼层
【解题思路】
用java写的,不是用c++.不知道还有没有意义。
嗯,就是字符串先转成StringBuffer或者char[],再将左半部分的字符和右半部分的字符互换..
swap(s[low=0],s[high=length-1]),再low++; high--
【时间复杂度】
o(n)
【空间复杂度】
o(1)
【gist link】
https://gist.github.com/jaly50/a8a7c47a6acfffdc0381
---------------OPTional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】
回复 支持 反对

使用道具 举报

asdw3276 发表于 2014-6-18 01:18:11 | 显示全部楼层

【解题思路】java实现,遍历一遍。新建了一个string,和tochararray的效果应该是一样的吧。因为java没法直接改原string。
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/asdw3276/39b2a443c62773fca357

感谢所有给我code review的小伙伴
回复 支持 反对

使用道具 举报

头像被屏蔽
serolins 发表于 2014-6-18 05:42:43 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 12:34

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表