【第三轮】7.24-7.31 CareerCup 5.3

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、任何未尽之处，欢迎回报名帖提问，我会进一步作出修改

【解题思路】
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

【解题思路】
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

【解题思路】
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

楼主你是不是把 1 都打成 7 了 ？   这是我发现的第二个~  

jyh橘子 发表于 2014-7-24 22:11
楼主你是不是把 1 都打成 7 了 ？   这是我发现的第二个~

好像是的
我没找到在哪里修改

【解题思路】
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

【解题思路】
参考了书上的解法

【时间复杂度】
O(N)

【空间复杂度】
O(1)

【gist link】
https://gist.github.com/chrislukkk/27d32c76ed3c4b53af80

【解题思路】
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

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link]
confusing