微软经典面试题，毒药和老鼠。。。

猿大侠 · 公众号 · · 2024-07-30 12:08

正文

有 1000 个酒瓶，其中一个瓶子里装着有毒的酒，如果老鼠喝了有毒的酒一小时就会死掉。给你一小时至少需要多少只老鼠才能找出哪个瓶子里有毒？

思考半分钟再来看答案：

其实这题很简单，我们只需要把所有的酒瓶编上号，用二进制表示， 1000 个酒瓶只需要 10 个二进制位就够了，因为 2^10=1024，大于 1000 了，所以至少需要 10 只老鼠。

任何一个酒瓶的二进制位中如果右边第 1 位是 1 ，就让第 1 只老鼠尝，如果右边第 2 位是 1 ，就让第 2 只老鼠尝，如果右边第 n 位是 1 ，就让第 n 只老鼠尝。。。

假如一个小时之后第 1 ，3，5 这三只老鼠死了，说明二进制位中右边第 1 ， 3，5 位肯定是 1 ，也就是 0000010101(总共 10 位)，转化为二进制就是 21 ，也就是第 21 个酒瓶肯定是有毒的。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第543题：二叉树的直径。

问题描述

来源：LeetCode第543题

难度：简单

给你一棵二叉树的根节点，返回该树的直径。二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点 root 。两节点之间路径的长度由它们之间边数表示。

示例1：

输入：root = [1,2,3,4,5]

输出：3

解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。

树中节点数目在范围 [1, 10^4] 内
-100 <= Node.val <= 100

问题分析

这题让计算二叉树的直径，实际上就是让计算二叉树中任意节点两个子树的高度和，保存最大值即可。

比如示例 1 中，根节点左子树的高度是 2 ，根节点右子树的高度是 1 ，它们的和是 3 ，这个就是该二叉树的最大直径。

二叉树的最大直径不一定会经过根节点，我们需要计算每一个节点左右子树的高度和，可以参考二叉树的后续遍历，从下往上的方式计算。

JAVA：

int ans = 0;

public int diameterOfBinaryTree(TreeNode root) {
    maxDepth(root);
    return ans;
}

// 计算当前节点的高度
private int maxDepth(TreeNode root) {
    if (root == null)
        return 0;
    int left = maxDepth(root.left);// 左子树高度
    int right = maxDepth(root.right);// 右子树高度
    ans = Math.max(ans, left + right);// 保存最大值
    return Math.max(left, right) + 1;// 返回子树的高度
}