一亩三分地论坛

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

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

[CareerCup] 【第三轮】7.24-7.31 CareerCup 5.3

[复制链接] |试试Instant~ |关注本帖
林微熙 发表于 2014-7-25 06:28:50 | 显示全部楼层 |阅读模式

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

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

x
5.3 Given a positive integer, print the next smallest and the next largest number that have the same number of 7 bits in their binary representation.


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



Notice:
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子,除了贴解法,欢迎讨论,集思广益
4、任何未尽之处,欢迎回报名帖提问,我会进一步作出修改
jyh橘子 发表于 2014-7-25 13:11:24 | 显示全部楼层
楼主你是不是把 1 都打成 7 了 ?   这是我发现的第二个~  
回复 支持 反对

使用道具 举报

jyh橘子 发表于 2014-7-25 14:41:30 | 显示全部楼层
【解题思路】
Next:  find the first "01", exchange the position of 0 and 1;  and shift all the 1s on the right of this "01"  to the most right
Previous:  find the first "10", exchange the position of 0 and 1; and then make all the 1s on the right  follow this "01"
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link】https://gist.github.com/jyhjuzi/9c438422bcef5cceadab
回复 支持 反对

使用道具 举报

 楼主| 林微熙 发表于 2014-7-26 00:12:59 | 显示全部楼层
jyh橘子 发表于 2014-7-24 22:11
楼主你是不是把 1 都打成 7 了 ?   这是我发现的第二个~

好像是的
我没找到在哪里修改
回复 支持 反对

使用道具 举报

renli3000 发表于 2014-7-26 04:13:38 | 显示全部楼层
【解题思路】
Solution1: search number that larger or smaller than original number with same count of 1
Solution2: search '01' => '10' search '10' => '01'
Reminder: if n is the power of 2, we have to do special optimization for it
【时间复杂度】O(N) for Solution2
【空间复杂度】O(1)
【gist link】https://gist.github.com/Noahsark/23ad2bde5151fb652e83
回复 支持 反对

使用道具 举报

grassgigi 发表于 2014-7-27 11:30:56 | 显示全部楼层
【解题思路】
参考了书上的解法

【时间复杂度】
O(N)

【空间复杂度】
O(1)

【gist link】
https://gist.github.com/chrislukkk/27d32c76ed3c4b53af80
回复 支持 反对

使用道具 举报

圆梦梦剧场 发表于 2014-7-27 21:14:53 | 显示全部楼层
【解题思路】
next smallest: scan from LSB to MSB to find the first "01", change the "0" to "1" and put all the "1" in the right
next largest:   scan from LSB to MSB to find the first "10", change the "1" to "0" and put all the "0" in the right


【时间复杂度】
O(1)

【空间复杂度】
O(1)

【gist link】
https://gist.github.com/happyWinner/956c1b6a04dc785334ea
回复 支持 反对

使用道具 举报

bearkino 发表于 2014-7-29 13:12:30 | 显示全部楼层
【解题思路】
next smallest: scan to find the 0 which have 1s to its right. change it to 1 and move the right 1s all to the rightmost.
next largest: scan from the right, find the 1 which have 0s to its right. change it to 0, and move the right 1s to this position's right.


【时间复杂度】
O(n)

【空间复杂度】
O(1)

【gist link】
https://gist.github.com/UncleGarden/c77586fa5a7a12bff526
回复 支持 反对

使用道具 举报

ivycheung1208 发表于 2014-7-29 14:38:33 | 显示全部楼层
本帖最后由 ivycheung1208 于 2014-7-29 11:47 编辑

【解题思路】
1.传说中的字典序LOL 参见wiki:Lexicographic order
2.Simplify: shifting the tailing sequence instead of reverse!
3.*Arithmetic trick*:
next = n + (1 << c0) + (1 << (c1 - 1)) - 1
prev = n - (1 << c1) - (1 << (c0 - 1)) + 1
【时间复杂度】
O(1) - 32 bit unsigned int
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/089d3f8a9692c5bd00d9
【test case】
0
0 0

1
2 0

2
4 1

3
5 0

128(1000,0000)
64 256

255(1111,1111)
383 0

2147483648(1000,0000..0000)
0 1073741824(0100,0000..0000)

4294967295(1111...1111)
0 0




回复 支持 反对

使用道具 举报

 楼主| 林微熙 发表于 2014-8-3 07:18:40 | 显示全部楼层
【解题思路】
【时间复杂度】
【空间复杂度】
【gist link]
confusing
回复 支持 反对

使用道具 举报

bitcpf 发表于 2014-8-5 02:01:10 | 显示全部楼层
【解题思路】
next small but closest: find 10 and change to 01, then put all 1s on the 10 right side next to the position of 1 in the 10
next large but closest: find 01 and change to 10, then put all 1s on the 01 right side from the position of 0.

【时间复杂度】
O(n)

【空间复杂度】
O(1)

【gist link】
https://gist.github.com/bitcpf/be3aee6d7a22ddd1a807
回复 支持 反对

使用道具 举报

nibuxing 发表于 2014-10-9 01:32:46 | 显示全部楼层
这道题有个判断条件不是很明白,C1+C0 == 31 为什么是31不是32,求解答,谢谢!
回复 支持 反对

使用道具 举报

水逼一枚 发表于 2015-8-16 01:09:46 | 显示全部楼层
nibuxing 发表于 2014-10-9 01:32
这道题有个判断条件不是很明白,C1+C0 == 31 为什么是31不是32,求解答,谢谢!

个人理解是因为,它是按照LSB是第0位,MSB是第31位来的,这里就是在判断,给定的positive number不能是Integer.MAX_VALUE的情况。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 19:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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