保罗·巴罗斯（Paulo Barros）的面试挑战
我选择在Python中进行此练习是因为我已经很长时间没有使用该语言了，但是我很喜欢它。 除了我在Python方面的有限经验外，我也从未有过使用PyUnit的机会，因此我认为我可以使用此练习来学习新知识。 测试是使用PyUnit完成的。
该解决方案假定等边三角形的底边之一在底部。
此问题是最长路径问题的一个实例，该图是DAG（有向无环图）。 因此，这可以在线性时间内解决，只需访问每个节点（三角形中的元素）一次即可。
该解决方案使用对数空间。 如果指定更改原始三角形不是问题，那么我们根本不需要多余的空间，但事实并非如此。 因此，需要跟踪三角形的2个“行”，并且在最坏的情况下，行的大小将是最后一行的大小，该大小等于三角形的高度，因此，解决方案使用对数空间。
使用Python 2.7进行了测试。
要测试它，请运行helltriangle
评论0