一亩三分地论坛

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

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

[CareerCup] 【第四轮】3.30- 4.5 Career Cup 1.4

[复制链接] |试试Instant~ |关注本帖
pure0909 发表于 2015-3-30 10:22:15 | 显示全部楼层 |阅读模式

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

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

x
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]
【test case】(optional,如果觉得比较好,欢迎贴出来分享)

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

JamesJi 发表于 2015-3-31 01:56:36 | 显示全部楼层
【解题思路】
first we count the number of space, then in the extended char array, we can do reverse compare.
If we find space, we will add %20 in reverse order
【时间复杂度】
O(n)
【空间复杂度】
in place
【gist link]
https://gist.github.com/JamesJi9277/e8fc2faa560ac2329eac
【test case】

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

laonong15 发表于 2015-4-1 00:17:07 | 显示全部楼层
【解题思路】
1. set lastIndex = trueLength of   str,
2. from the str  end to begin  find the space char (str)
3   move rest elments for two spaces
4, char='%'; char[i+1] = '2' char[i+2]=0;
【时间复杂度】
O(n^2)
【空间复杂度】
O(1)
【gist link]
https://gist.github.com/michaelniu/7a44ceae93a42099d10a
【test case】
https://gist.github.com/michaelniu/7a44ceae93a42099d10a (main)

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

alikewmk 发表于 2015-4-1 13:28:50 | 显示全部楼层
【解题思路】
算出新数组的长度,然后将原数组的值插入新数组,插值过程中两个数组的index值要分开计算
【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/alikewmk ... 4-replaceblank-java

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

lucifer_vent 发表于 2015-4-1 14:01:46 | 显示全部楼层
。。。我想知道拿C++的string的.replace()方法直接替换得出可以么。。
回复 支持 反对

使用道具 举报

slaink 发表于 2015-4-2 13:46:21 | 显示全部楼层
【解题思路】

* First calculate the number of spaces, then set a pointer A
* at the end of your new string. Then use another pointer B
* to reversely traverse your old string, move the non-space
* character that B meet to A, and then move A and B accordingly.
*
* If space is met, move "%20" to A, then discard that space character.
*
* Keep doing this until you reach the start of your old string.

【时间复杂度】O(n) traverse the string twice
【空间复杂度】 O(1) No extra space is allocated
【gist link] https://github.com/bxshi/intervi ... substitue_space.cpp
【test case】(optional,如果觉得比较好,欢迎贴出来分享)https://github.com/bxshi/intervi ... c/test/1_4_test.cpp

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

slaink 发表于 2015-4-2 13:49:43 | 显示全部楼层
lucifer_vent 发表于 2015-4-1 14:01
。。。我想知道拿C++的string的.replace()方法直接替换得出可以么。。

Probably not....
回复 支持 反对

使用道具 举报

slaink 发表于 2015-4-2 13:49:51 | 显示全部楼层
lucifer_vent 发表于 2015-4-1 14:01
。。。我想知道拿C++的string的.replace()方法直接替换得出可以么。。

Probably not... Although it is a correct answer.
回复 支持 反对

使用道具 举报

A30041839 发表于 2015-4-2 14:51:04 | 显示全部楼层
[solution]
count the number of space chars, insert %20 from right to left.
[time]
O(n)
[space]
O(1)
[gist]
https://gist.github.com/A30041839/3537bfb540209975322f

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

chongtianzs 发表于 2015-4-3 09:08:32 | 显示全部楼层
[solution]
不用额外空间,先scan一遍,找到whitespace的数量;再scan一遍,从后往前modify这个str。
[time]
O(n)
[space]
O(1)
[gist]
https://gist.github.com/chongtianzs/476e1682c0c95fbd656b

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

mything 发表于 2015-4-3 12:58:28 | 显示全部楼层
【解题思路】
1. 先数一下有多少个空格,计算变换完的字符串有多长。
2. 让一个指针指向新字符串的最后一个字符,另一个指针指向原字符串最后一个字符
3. 一个个字母拷贝,如果发现空格,则不拷贝,而写02%
4. 两指针相遇时拷贝就完成了
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link]
https://gist.github.com/n2iw/170195065cd5b257e4fd
【test case】(optional,如果觉得比较好,欢迎贴出来分享)

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

Godbless 发表于 2015-4-4 22:31:09 | 显示全部楼层
本帖最后由 Godbless 于 2015-4-4 09:33 编辑
mything 发表于 2015-4-2 23:58
【解题思路】
1. 先数一下有多少个空格,计算变换完的字符串有多长。
2. 让一个指针指向新字符串的最后一 ...

How to guarantee that the string will have enough space for the extension?
回复 支持 反对

使用道具 举报

Godbless 发表于 2015-4-4 22:33:49 | 显示全部楼层
【解题思路】First round to traverse the string and find all whitespace. Compute the length of new string if all whitespace are changed into "%20". For the new string, traversal from the end to the begining by copying the characters of the original string, and copy "%20" when encountering the whitespace in the original string.
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link]
https://github.com/StephenWeiXu/ ... blob/master/1_4.cpp
【test case】(optional,如果觉得比较好,欢迎贴出来分享)
https://github.com/StephenWeiXu/ ... blob/master/1_4.cpp

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

mything 发表于 2015-4-5 09:43:26 | 显示全部楼层
Godbless 发表于 2015-4-4 22:31
How to guarantee that the string will have enough space for the extension?

因为题目里说了!
回复 支持 反对

使用道具 举报

beer 发表于 2015-4-5 19:51:32 | 显示全部楼层
【解题思路】
Tips:
* 1. use a new char array to transfer chars from old array
* 2. use a new String array to transfer Strings from old array
* 3. use internal API: String.replaceAll()
【时间复杂度】1. O(N)     2. O(N)     3. O(N)
【空间复杂度】1. O(N)    2. O(N)     3. O(1)
【gist link】https://github.com/drinkbeer/Cod ... er/src/CC150_4.java
【test case】

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

Fiona杀G 发表于 2015-4-5 22:16:44 | 显示全部楼层
[question]


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.)

[solution]
1. caculate the string len after inserting these 20% as newLen
2. add a end symbol '/0' in the tail
3. start from the tail of the string, there will be two pointer, one
        points to the newTail another points to the original_tail, if the
        original tail points to a space, we will add 20% in the newTail position
    else just copy the char
4. until we reach the 0 index

[time complexity]
O(n)
scan all chars in the string

[space complexity]
O(1)
do this in place

[gist link]
https://gist.github.com/FionaT/369f955a7f70aae3d284

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

daphne_ying 发表于 2015-4-6 04:12:33 | 显示全部楼层
[solution]
1. iterate through the string to calculate the new length of the string after replacing all the spaces
2. Use two pointers, one indicates the old tail, another indicates the new tail, if the char is a space, replace it with %20, otherwise just copy the old char.

[time complexity]
O(n)

[space complexity]
O(1)

[gist link]
https://gist.github.com/kelly-us/a0df33b04130161de1b6

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

窗外一棵树 发表于 2015-4-6 06:55:44 | 显示全部楼层
【解题思路】
* The core condition is that we have sufficient space at the end.
* if we don't care about space, we can just create a new space for new char array.
* In our case, we want to minimize the pace usage, so we start to assign values from the end of the char array
* first, calculate how much space we need according to the number of space
* second, assign new value to the same string from the end, becasue we have many space at the end and we only need
* this one char array in this case.

【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link]
https://gist.github.com/leonw007/ca1cbd10288a9facf2c6
【test case】included in the above link

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

sevenwonder 发表于 2015-4-6 10:22:04 | 显示全部楼层
【解题思路】
先遍历一次字符串,得到空格个数,进而得到将空格转换成%20后的串长度 (每个空格替换为%20需要增加2个字符,x个空格增加2x个字符)。 然后从后向前依次对空格进行替换,非空格原样拷贝

【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link]
https://gist.github.com/songpu2015617/7db42adbff6c83f12b3b

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

Howie 发表于 2015-4-9 14:40:52 | 显示全部楼层
【解题思路】
Count the space, get the new length.
Use two pointers, one points the last item in the array and the other points the last item in the new array.
Because we insert items from  the end of the array, we can use the same array for all operations.

【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link]
https://gist.github.com/Howiezhang226/892a5fc3b7bd9d2980a9
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 08:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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