我正在解决来自一个名为Codefights的网站上的一些问题,最后一个解决的问题涉及到一个二叉树,其中包含以下内容:
Consider a special family of Engineers and Doctors. This family has the following rules:
Everybody has two children. The first child of an Engineer is an Engineer and the second child is a Doctor. The first child of a Doctor is a Doctor and the second child is an Engineer. All generations of Doctors and Engineers start with an Engineer.
We can represent the situation using this diagram:
E / \ E D / \ / \ E D D E / \ / \ / \ / \ E D D E D E E D
Given the level and position of a person in the ancestor tree above, find the profession of the person. Note: in this tree first child is considered as left child, second - as right.
由于限制了时间和空间,所以无法实际构建树直到所需的层级并检查所需位置的元素。到目前为止还好。我提出的解决方案使用Python编写:
def findProfession(level, pos):
size = 2**(level-1)
shift = False
while size > 2:
if pos <= size/2:
size /= 2
else:
size /= 2
pos -= size
shift = not shift
if pos == 1 and shift == False:
return 'Engineer'
if pos == 1 and shift == True:
return 'Doctor'
if pos == 2 and shift == False:
return 'Doctor'
if pos == 2 and shift == True:
return 'Engineer'
当问题得到解决后,我获得了其他用户的解决方案,并对其中一项感到惊讶:
def findProfession(level, pos):
return ['Engineer', 'Doctor'][bin(pos-1).count("1")%2]
更重要的是,我不理解它背后的逻辑,所以我们来到了这个问题。有人能向我解释一下这个算法吗?