题目引用
Given k - which is the number of bits, print all possible combinations of numbers formed by printing all numbers with one bit set, followed by two bits set... upto the point when all k-bits are set. They must be sorted according to the number of bits set, if two numbers have the same number of bits set then they should be placed as per their value.
For example, if k = 3, output:
000, 001, 010, 100, 101, 110, 011, 111.
给一个非负整数k，返回从0到二进制k个1的比特组，以含有1的个数升序排列，如果1的个数一样的话就按照实际大小排列。
补全问题
返回的是字符串还是数字？假设是字符串。
另外对于比特相同的数字，好像给出的例子不是很对，前面001, 010, 100是升序，到了101, 110, 011就不知道是什么顺序了。假设是升序。
思路解析
从0到k个1，其实就是2k个数。也就是说返回的数其实是从0到2k-1，只不过其中的顺序有一些改变。
暴力破解
很自然的，先生成0 ~ 2^k-1，然后再加上一遍对于1的个数的排序即可。
前者的时间复杂度是O(2k)，后者是O(2klog(2^k)) = O(k2^k)，总体就是O(k2^k)。
如何改进
从排序方法的角度而言，暴力破解方法已经做得不错了。
其他方法
字符串的角度
可以考虑将这些数按照1的个数分为一组组，然后后一组在前一组的基础上产生。
那么就要牵扯到具体怎么实现了，因为组与组之间的个数可能不会一样。
还有一个就是怎么避免重复的问题。
例如从001,010,100来生成101, 110, 011。可能set在这里会起作用。不过如果是这样，这个方法的效率也必然不会太高。
因为含有i个1的数有C(i, k)个，这样的数每个要试其0的个数，也就是k-i次，乘起来求和就是复杂度了。我不会算，很多阶乘。
总体而言，这个方法实现比上一个复杂，效率看起来也没好到哪去。
代码：
class Solution:
def generateKList(self, k):
L = []
for i in range(2 ** k):
L.append(i)
L.sort(key=lambda n: self.getOnes(n))
return [str(bin(x)[2:]).rjust(k, "0") for x in L]
def getOnes(self, n):
return str(bin(n)[2:]).count("1")
if __name__ == "__main__":
print(Solution().generateKList(3))
其实获取二进制1的数目这个函数可以更高效。
总结
由于Career cup上的题也没有正式答案，有些题还是面试者凭借记忆写的，所以可能有些地方不太对劲。
