java - 有没有办法在数学上找到正确的节点？

Question

来自：https ://open.kattis.com/problems/numbertree 的问题，来自 KTH Challenge 2014

这就是数字树的样子

我使用了一个 for 循环来遍历由“L”和“R”组成的输入字符串，并使用 curr 来存储当前正在评估的变量，并使用previous 来存储迭代之前的变量。

if (i == 0) { //first 'L' or 'R'
   if (curr == 'L') { count++; }
   if (curr == 'R') { count +=2 ; }
} 

在这里，如果当前字符与前一个字符相同，我将计数增加 2 的循环次数，如果当前字符与前一个字符不同，则从该值中减去 1。

else if (curr == prev) { count += (int) Math.pow(2, h); }
else if (curr != prev) { count += (int) Math.pow(2, h)-1;

在每个循环结束时，我将 prev 等同于 curr 并增加 h。

此逻辑适用于 3 个给定输入 、3 LR和3 RRL，2它们分别返回11、2和7。

但是它没有通过隐藏的测试用例。我尝试过的一个输入是3 LLL 应该返回8，但我的算法返回了3。3 LRR应该返回 5，但我得到了 3。

是否有使用数据结构来获得解决方案的解决方案，因为问题引用了“完美二叉树”。感谢您在整理我的逻辑中的扭结以及其他解决方案方面的任何帮助。谢谢！

标签： java

Answer 1

作为一棵完美的二叉树，层 x 的最低节点大于 2^k 的总和，其中 k 是从层 x+1 到 H 的节点数。路径 5 RL 告诉你你有一个5 层树上第 2 层的节点，因此该节点大于 2^3 + 2^4 + 2^5 = 56。现在我们已经将树简化为 H = h(x)，我们可以观察到到节点的路径只不过是一个二进制代码，其中 L = 0，R = 1。我们将此二进制代码转换为整数，将其与之前获得的数字相加，我们就得到了节点的标签。一条路径 RL 是 10 = 2，然后 5 RL 的标签为 58。

现在，转换此算法非常简单，因为您只需将数组分成两部分，将 RL 路径转换为二进制代码并进行数学运算。