提问人:userNotFound 提问时间:3/9/2019 最后编辑:Dillon DavisuserNotFound 更新时间:3/10/2019 访问量:55
该算法如何按预期工作?尽管溢出
How is this algorithm working as expected? Despite the overflow
问:
我正在尝试解决这个问题:
给定一个非空的二叉搜索树和一个目标值,找到 BST 中最接近目标的值。
注意:给定的目标值是一个浮点数。您保证 BST 中只有一个最接近目标的唯一值。
这是我在网上看到的一个解决方案:
public int closestValue(TreeNode root, double target) {
int ret = root.val;
while(root!=null) {
if(Math.abs(target - root.val) > Integer.MAX_VALUE){
System.out.println( " Underflow!");
}
if(Math.abs(target - root.val) < Math.abs(target -ret)){
ret = root.val;
}
root = (target < root.val)? root.left : root.right;
}
return ret;
}
我正在考虑测试用例:
[1500000000,1400000000]
-1500000000.0
其中 是父节点,是左子节点,是目标节点。Id 期望代码在 Math.abs 子句中下溢(确实如此),因为它大于 Int.MIN_VALUE。但是我不明白算法怎么还能返回.下溢不应该导致比较失败吗?1500000000
1400000000
-1500000000.0
-1500000000 - 1500000000
1400000000
答: 暂无答案
上一个:将地图区域划分为给定半径的重叠圆
评论
target
是 ,因此任何涉及它和 an 的表达式都将导致 被提升为 .此表达式在循环的第一次迭代中不成立:double
int
int
double
Math.abs(target - root.val) > Integer.MAX_VALUE