一亩三分地论坛

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

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

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

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

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

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

x
本帖最后由 wrj5518 于 2014-6-15 23:19 编辑

1.4 Write a method to replace all spaces in a string with'%20'. You may assume that the string has sufficient space at the end of the string to hold the additional characters, and that you are given the "true" length of the string. (Note: if implementing in Java, please use a character array so that you can perform this operation in place.)   
EXAMPLE
Input: "Mr John Smith       "
Output: "Mr%20Dohn%20Smith"  
         
回复解法可以按照以下格式来
【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------optional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】


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



兰橘清檬 发表于 2014-6-17 02:33:54 | 显示全部楼层

【解题思路】
遍历 char 数组计算新数组的长度;
从后往前copy,并将空格改为 %20
【时间复杂度】
  O(n)
【空间复杂度】
  O(1)
【gist link】
https://gist.github.com/JoyceeLee/60a6d8d88866845f4461
回复 支持 0 反对 1

使用道具 举报

qianhuang 发表于 2014-6-16 10:10:43 | 显示全部楼层
【解题思路】
since the string in c++ STL is mutable, it is very easy to solve this problem.
If we can not use string. First count the number of space in the string, then we assign a new string size of (size(oldstring)+count(space)), and we scan from the end of string, when we meet a space, we replace it by "%20".
【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/qianhuang/8d23c5c0309ea246d470
回复 支持 1 反对 0

使用道具 举报

atlas1017 发表于 2014-6-16 06:36:37 | 显示全部楼层
【解题思路】
先计算需要空间 用char[] 存放 然后转回 String
【时间复杂度】
N
【空间复杂度】
N
【gist link】
https://gist.github.com/atlas1017/d45f5885a83bbfefb800
---------------OPTional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】
回复 支持 反对

使用道具 举报

readman 发表于 2014-6-16 12:06:43 | 显示全部楼层
【解题思路】
go through all elems in String, replace space with %20

first time write this in rec
【时间复杂度】
n
【空间复杂度】
n
【gist link】
https://gist.github.com/gaoyike/9a7198ada98a932e37b7
回复 支持 反对

使用道具 举报

habina 发表于 2014-6-16 13:16:37 | 显示全部楼层
【解题思路】
  Split the whole string by space, save each word in an array.
  Concatenate and put "%20" in between each word
【时间复杂度】
  O(N)
【空间复杂度】
  O(1)
【gist link】
https://gist.github.com/habina/cb4d5c96bc98ac87b26c
回复 支持 反对

使用道具 举报

monkerek 发表于 2014-6-16 21:43:33 | 显示全部楼层
【解题思路】
first find the index where the actual string ends
then calculate the number of spaces to be converted to assure the length of the result string
use two pointers, one pointing to the end of the former string, the other pointing to the end of the result string
then move pointers backwards to convert spaces one by one, and this can be done in-place.
【时间复杂度】
  O(n)
【空间复杂度】
  O(1)
【gist link】
  https://gist.github.com/monkerek/61cbc179c97c5d263beb
回复 支持 反对

使用道具 举报

jing0328 发表于 2014-6-16 22:56:27 | 显示全部楼层
【解题思路】first find the "true length" of the string, then whenever we find a space, we count how many spots for this space and then shift the char[] left/right by corresponding amount of spots and then replace space by %20 (感觉自己写的code很复杂, 求各位大神指点, 小弟第一次刷...)
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/startupjing/65f591967d74c78bc2d4
---------------OPTional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】case when multiple spots in a space, like "Mr    John  Smith           "
回复 支持 反对

使用道具 举报

小柯西 发表于 2014-6-17 02:27:00 | 显示全部楼层
【解题思路】Traverse the array. Move every character into the result array by order. Insert "%20" when encounter a " ".
【时间复杂度】O(n) for traversing array once.
【空间复杂度】O(n) for tripling the size of the original array.
【gist link】https://gist.github.com/a833f1d440a33843c0ad.git

求好的test case
回复 支持 反对

使用道具 举报

小柯西 发表于 2014-6-17 02:30:51 | 显示全部楼层
readman 发表于 2014-6-16 12:06
【解题思路】
go through all elems in String, replace space with %20

为什么会想到用recursion来做这道题!
回复 支持 反对

使用道具 举报

zhenzhenanan 发表于 2014-6-17 08:30:59 | 显示全部楼层
【解题思路】
1. 首先遍历一遍字符串,数出空格的个数。如果字符串后面留的空间刚好就是转换后所需要的空间的话,这一步可以省略;
2. 如果第一步没有省略,则找到转换后的字符串最后一个字符所应该在的位置。方法也很简单,那就是原来只有一个字符的空格现在需要3个字符的空间,转换一下即可。如果第一步省略了,则字符转换后,最后一个字符的位置就是整个字符串(包括留白)的最后一个位置。
3. 从后向前遍历字符串,如果是非空格,直接就放在正确的位置;如果是空格,则转换成'%20'。
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/seemuch/af64b140e576b6ea73ad#file-1_4-cc
---------------OPTional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】
None
回复 支持 反对

使用道具 举报

readman 发表于 2014-6-17 10:51:42 | 显示全部楼层
小柯西 发表于 2014-6-17 02:30
为什么会想到用recursion来做这道题!

最近在看算法设计....
回复 支持 反对

使用道具 举报

ryancooper 发表于 2014-6-17 11:36:22 | 显示全部楼层
habina 发表于 2014-6-16 13:16
【解题思路】
  Split the whole string by space, save each word in an array.
  Concatenate and put  ...

I think your space complexity should be O(n)
回复 支持 反对

使用道具 举报

habina 发表于 2014-6-17 11:57:25 | 显示全部楼层
ryancooper 发表于 2014-6-17 11:36
I think your space complexity should be O(n)

Thanks for pointing that out.
I think my code does not satisfy for performing operation in place.
I'll rewrite it.
Thanks again.
回复 支持 反对

使用道具 举报

ryancooper 发表于 2014-6-17 12:05:31 | 显示全部楼层
habina 发表于 2014-6-17 11:57
Thanks for pointing that out.
I think my code does not satisfy for performing operation in place. ...

That's fineActually, maybe you should use another language to write this if you want to do it in place since object string in python is immutable
回复 支持 反对

使用道具 举报

habina 发表于 2014-6-17 12:12:12 | 显示全部楼层
ryancooper 发表于 2014-6-17 12:05
That's fineActually, maybe you should use another language to write this if you want to do ...

Yeah. I totally agree about that. I'll do it in c.
回复 支持 反对

使用道具 举报

fang_wu 发表于 2014-6-17 18:00:00 | 显示全部楼层
【解题思路】
先把index变成最后一个不是空格,然后就是替换。
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/qiangusc/def553c9b31b44560818
回复 支持 反对

使用道具 举报

chouclee 发表于 2014-6-17 19:35:06 | 显示全部楼层
【解题思路】traverse字符串s,统计空格的数量c,new 一个s.length() + c<<1 大小的char[],再次traverse,重组字符串
【时间复杂度】O(n)
【空间复杂度】O(n)
【gist link】https://gist.github.com/chouclee/d111abfd1ff20e41cd01
回复 支持 反对

使用道具 举报

wilbert 发表于 2014-6-18 02:17:21 | 显示全部楼层
【解题思路】
Original string must ends with '\0'. Count the number of spaces to get the length of the new string. Then start from the end of the new string and original string, if meets space in the original string, replace it with "%20", otherwise just move the character.
【时间复杂度】
O(N)
【空间复杂度】
O(1), in-place replace, no additional place
【gist link】
https://gist.github.com/iwilbert/d0efe909f1311c081bc2
回复 支持 反对

使用道具 举报

林微熙 发表于 2014-6-18 11:11:36 | 显示全部楼层
【解题思路】
go through all characters in String, replace space with '%20'
【时间复杂度】
O(N)
【空间复杂度】
o(1)
【gist link】https://gist.github.com/hilda8519/e4f3e5ade2e38224129a
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 10:28

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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