遍历

根据题意，对 $n$ 的每一位进行遍历检查。

代码：

###Java

class Solution {
    public boolean hasAlternatingBits(int n) {
        int cur = -1;
        while (n != 0) {
            int u = n & 1;
            if ((cur ^ u) == 0) return false;
            cur = u; n >>= 1;
        }
        return true;
    }
}

• 时间复杂度：$O(\log{n})$
• 空间复杂度：$O(1)$

位运算

另外一种更为巧妙的方式是利用交替位二进制数性质。

当给定值 $n$ 为交替位二进制数时，将 $n$ 右移一位得到的值 $m$ 仍为交替位二进制数，且与原数 $n$ 错开一位，两者异或能够得到形如 $0000...1111$ 的结果 $x$，此时对 $x$ 执行加法（进位操作）能够得到形如 $0000...10000$ 的结果，将该结果与 $x$ 执行按位与后能够得到全 $0$ 结果。

代码：

###Java

class Solution {
    public boolean hasAlternatingBits(int n) {
        int x = n ^ (n >> 1);
        return (x & (x + 1)) == 0;
    }
}

• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$

同类型加餐

今日份加餐：经典「状态压缩 + 位运算」入门题 🎉🎉

或是考虑加练如下「位运算」题目 🍭🍭🍭

注：以上目录整理来自 wiki，任何形式的转载引用请保留出处。

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ ("▔□▔)/

也欢迎你 关注我 和 加入我们的「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。

所有题解已经加入 刷题指南，欢迎 star 哦 ~

线性 DP

为了方便，我们令 poured 为 k，query_row 和 query_glass 分别为 $n$ 和 $m$。

定义 $f[i][j]$ 为第 $i$ 行第 $j$ 列杯子所经过的水的流量（而不是最终剩余的水量）。

起始我们有 $f[0][0] = k$，最终答案为 $\min(f[n][m], 1)$。

不失一般性考虑 $f[i][j]$ 能够更新哪些状态：显然当 $f[i][j]$ 不足 $1$ 的时候，不会有水从杯子里溢出，即 $f[i][j]$ 将不能更新其他状态；当 $f[i][j]$ 大于 $1$ 时，将会有 $f[i][j] - 1$ 的水会等量留到下一行的杯子里，所流向的杯子分别是「第 $i + 1$ 行第 $j$ 列的杯子」和「第 $i + 1$ 行第 $j + 1$ 列的杯子」，增加流量均为 $\frac{f[i][j] - 1}{2}$，即有 $f[i + 1][j] += \frac{f[i][j] - 1}{2}$ 和 $f[i + 1][j + 1] += \frac{f[i][j] - 1}{2}$。

代码：

###Java

class Solution {
    public double champagneTower(int k, int n, int m) {
        double[][] f = new double[n + 10][n + 10];
        f[0][0] = k;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= i; j++) {
                if (f[i][j] <= 1) continue;
                f[i + 1][j] += (f[i][j] - 1) / 2;
                f[i + 1][j + 1] += (f[i][j] - 1) / 2;
            }
        }
        return Math.min(f[n][m], 1);
    }
}

###TypeScript

function champagneTower(k: number, n: number, m: number): number {
    const f = new Array<Array<number>>()
    for (let i = 0; i < n + 10; i++) f.push(new Array<number>(n + 10).fill(0))
    f[0][0] = k
    for (let i = 0; i <= n; i++) {
        for (let j = 0; j <= i; j++) {
            if (f[i][j] <= 1) continue
            f[i + 1][j] += (f[i][j] - 1) / 2
            f[i + 1][j + 1] += (f[i][j] - 1) / 2
        }
    }
    return Math.min(f[n][m], 1)
}

###Python3

class Solution:
    def champagneTower(self, k: int, n: int, m: int) -> float:
        f = [[0] * (n + 10) for _ in range(n + 10)]
        f[0][0] = k
        for i in range(n + 1):
            for j in range(i + 1):
                if f[i][j] <= 1:
                    continue
                f[i + 1][j] += (f[i][j] - 1) / 2
                f[i + 1][j + 1] += (f[i][j] - 1) / 2
        return min(f[n][m], 1)

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(n^2)$

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ ("▔□▔)/

也欢迎你 关注我，提供写「证明」&「思路」的高质量题解。

所有题解已经加入 刷题指南，欢迎 star 哦 ~