递归

容易想到「递归」进行求解，在 DFS 过程中记录下当前的值为多少，假设遍历到当前节点 $x$ 前，记录的值为 $cur$，那么根据题意，我们需要先将 $cur$ 进行整体左移（腾出最后一位），然后将节点 $x$ 的值放置最低位来得到新的值，并继续进行递归。

递归有使用「函数返回值」和「全局变量」两种实现方式。

代码：

###Java

class Solution {
    public int sumRootToLeaf(TreeNode root) {
        return dfs(root, 0);
    }
    int dfs(TreeNode root, int cur) {
        int ans = 0, ncur = (cur << 1) + root.val;
        if (root.left != null) ans += dfs(root.left, ncur);
        if (root.right != null) ans += dfs(root.right, ncur);
        return root.left == null && root.right == null ? ncur : ans;
    }
}

###Java

class Solution {
    int ans = 0;
    public int sumRootToLeaf(TreeNode root) {
        dfs(root, 0);
        return ans;
    }
    void dfs(TreeNode root, int cur) {
        int ncur = (cur << 1) + root.val;
        if (root.left != null) dfs(root.left, ncur);
        if (root.right != null) dfs(root.right, ncur);
        if (root.left == null && root.right == null) ans += ncur;
    }
}

• 时间复杂度：$O(n)$
• 空间复杂度：忽略递归带来的额外空间开销，复杂度为 $O(1)$

---

迭代

自然也可以使用「迭代」进行求解。

为了不引入除「队列」以外的其他数据结构，当我们可以把某个节点 $x$ 放出队列时，先将其的值修改为当前遍历路径对应的二进制数。

代码：

###Java

class Solution {
    public int sumRootToLeaf(TreeNode root) {
        int ans = 0;
        Deque<TreeNode> d = new ArrayDeque<>();
        d.addLast(root);
        while (!d.isEmpty()) {
            TreeNode poll = d.pollFirst();
            if (poll.left != null) {
                poll.left.val = (poll.val << 1) + poll.left.val;
                d.addLast(poll.left);
            }
            if (poll.right != null) {
                poll.right.val = (poll.val << 1) + poll.right.val;
                d.addLast(poll.right);
            }
            if (poll.left == null && poll.right == null) ans += poll.val;
        }
        return ans;
    }
}

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

---

最后

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

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

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

模拟

根据题意进行模拟即可，遍历 $n$ 的二进制中的每一位 $i$，同时记录上一位 $1$ 的位置 $j$，即可得到所有相邻 $1$ 的间距，所有间距取 $\max$ 即是答案。

代码：

###Java

class Solution {
    public int binaryGap(int n) {
        int ans = 0;
        for (int i = 31, j = -1; i >= 0; i--) {
            if (((n >> i) & 1) == 1) {
                if (j != -1) ans = Math.max(ans, j - i);
                j = i;
            }
        }
        return ans;
    }
}

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

---

加餐 & 加练

今日份加餐：【面试高频题】难度 1.5/5，脑筋急转弯类模拟题 🎉🎉🎉

或是考虑加练如下「模拟」题 🍭🍭🍭

题目	题解	难度	推荐指数
6. Z 字形变换	LeetCode 题解链接	中等	🤩🤩🤩
8. 字符串转换整数 (atoi)	LeetCode 题解链接	中等	🤩🤩🤩
12. 整数转罗马数字	LeetCode 题解链接	中等	🤩🤩
59. 螺旋矩阵 II	LeetCode 题解链接	中等	🤩🤩🤩🤩
65. 有效数字	LeetCode 题解链接	困难	🤩🤩🤩
73. 矩阵置零	LeetCode 题解链接	中等	🤩🤩🤩🤩
89. 格雷编码	LeetCode 题解链接	中等	🤩🤩🤩🤩
166. 分数到小数	LeetCode 题解链接	中等	🤩🤩🤩🤩
260. 只出现一次的数字 III	LeetCode 题解链接	中等	🤩🤩🤩🤩
414. 第三大的数	LeetCode 题解链接	中等	🤩🤩🤩🤩
419. 甲板上的战舰	LeetCode 题解链接	中等	🤩🤩🤩🤩
443. 压缩字符串	LeetCode 题解链接	中等	🤩🤩🤩🤩
457. 环形数组是否存在循环	LeetCode 题解链接	中等	🤩🤩🤩🤩
528. 按权重随机选择	LeetCode 题解链接	中等	🤩🤩🤩🤩
539. 最小时间差	LeetCode 题解链接	中等	🤩🤩🤩🤩
726. 原子的数量	LeetCode 题解链接	困难	🤩🤩🤩🤩

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

---

最后

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

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

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

模拟 + lowbit

利用一个 int 的二进制表示不超过 $32$，我们可以先将 $32$ 以内的质数进行打表。

从前往后处理 $[left, right]$ 中的每个数 $x$，利用 lowbit 操作统计 $x$ 共有多少位 $1$，记为 $cnt$，若 $cnt$ 为质数，则对答案进行加一操作。

代码：

###Java

class Solution {
    static boolean[] hash = new boolean[40];
    static {
        int[] nums = new int[]{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
        for (int x : nums) hash[x] = true;
    }
    public int countPrimeSetBits(int left, int right) {
        int ans = 0;
        for (int i = left; i <= right; i++) {
            int x = i, cnt = 0;
            while (x != 0 && ++cnt >= 0) x -= (x & -x);
            if (hash[cnt]) ans++;
        }
        return ans;
    }
}

• 时间复杂度：$O((right - left) * \log{right})$
• 空间复杂度：$O(C)$

---

模拟 + 分治

枚举 $[left, right]$ 范围内的数总是不可避免，上述解法的复杂度取决于复杂度为 $O(\log{x})$ 的 lowbit 操作。

而比 lowbit 更加优秀的统计「二进制 $1$ 的数量」的做法最早在 (题解) 191. 位1的个数 讲过，采用「分治」思路对二进制进行成组统计，复杂度为 $O(\log{\log{x}})$。

代码：

###Java

class Solution {
    static boolean[] hash = new boolean[40];
    static {
        int[] nums = new int[]{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
        for (int x : nums) hash[x] = true;
    }
    public int countPrimeSetBits(int left, int right) {
        int ans = 0;
        for (int i = left; i <= right; i++) {
            int x = i;
            x = (x & 0x55555555) + ((x >>> 1)  & 0x55555555);
            x = (x & 0x33333333) + ((x >>> 2)  & 0x33333333);
            x = (x & 0x0f0f0f0f) + ((x >>> 4)  & 0x0f0f0f0f);
            x = (x & 0x00ff00ff) + ((x >>> 8)  & 0x00ff00ff);
            x = (x & 0x0000ffff) + ((x >>> 16) & 0x0000ffff);
            if (hash[x]) ans++;
        }
        return ans;
    }
}

• 时间复杂度：$O((right - left) * \log{\log{right}})$
• 空间复杂度：$O(C)$

---

其他「位运算」相关内容

考虑加练其他「位运算」相关内容 🍭🍭🍭

题目	题解	难度	推荐指数
137. 只出现一次的数字 II	LeetCode 题解链接	中等	🤩🤩🤩
190. 颠倒二进制位	LeetCode 题解链接	简单	🤩🤩🤩
191. 位1的个数	LeetCode 题解链接	简单	🤩🤩🤩
231. 2 的幂	LeetCode 题解链接	简单	🤩🤩🤩
338. 比特位计数	LeetCode 题解链接	简单	🤩🤩🤩
342. 4的幂	LeetCode 题解链接	简单	🤩🤩🤩
461. 汉明距离	LeetCode 题解链接	简单	🤩🤩🤩🤩
477. 汉明距离总和	LeetCode 题解链接	简单	🤩🤩🤩🤩
1178. 猜字谜	LeetCode 题解链接	困难	🤩🤩🤩🤩
剑指 Offer 15. 二进制中1的个数	LeetCode 题解链接	简单	🤩🤩🤩

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

---

最后

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

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

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

构造

我们可以定义每个字符的得分：字符 1 得分为 $1$ 分，字符 0 得分为 $-1$ 分。

根据题目对「特殊字符串」的定义可知，给定字符串 s 的总得分为 $0$，且任意前缀串不会出现得分为负数的情况。

考虑将 s 进行划分为多个足够小特殊字符串 item（足够小的含义为每个 item 无法再进行划分），每个 item 的总得分为 $0$。根据 s 定义，必然可恰好划分为多个 item。

每次操作可以将相邻特殊字符串进行交换，于是问题转换为将 s 进行重排，求其重排后字典序最大的方案。

首先可以证明一个合法 item 必然满足 1...0 的形式，可通过「反证法」进行进行证明：定义了 item 总得分为 $0$，且长度不为 $0$，因此必然有 1 有 0。若第一位字符为 0，则必然能够从第一位字符作为起点，找到一个得分为负数的子串，这与 s 本身的定义冲突（s 中不存在得分为负数的前缀串）；若最后一位为 1，根据 item 总得分为 $0$，可知当前 item 去掉最后一位后得分为负，也与 s 本身定义冲突（s 中不存在得分为负数的前缀串）。

因此可将构造分两步进行：

1. 对于每个 item 进行重排，使其调整为字典序最大
2. 对于 item 之间的位置进行重排，使其整体字典序最大

由于题目没有规定重排后的性质，为第一步调整和第二步调整的保持相对独立，我们只能对 item 中的 1...0 中的非边缘部分进行调整（递归处理子串部分）。

假设所有 item 均被处理后，考虑如何进行重排能够使得最终方案字典序最大。

若有两个 item，分别为 a 和 b，我们可以根据拼接结果 ab 和 ba 的字典序大小来决定将谁放在前面。

这样根据「排序比较逻辑」需要证明在集合上具有「全序关系」:

我们使用符号 $@$ 来代指我们的「排序」逻辑：

• 如果 $a$ 必须排在 $b$ 的前面，我们记作 $a @ b$；
• 如果 $a$ 必须排在 $b$ 的后面，我们记作 $b @ a$；
• 如果 $a$ 既可以排在 $b$ 的前面，也可以排在 $b$ 的后面，我们记作 $a#b$；

2.1 完全性

具有完全性是指从集合 items 中任意取出两个元素 $a$ 和 $b$，必然满足 $a @ b$、$b @ a$ 和 $a#b$ 三者之一。

这点其实不需要额外证明，因为由 $a$ 和 $b$ 拼接的字符串 $ab$ 和 $ba$ 所在「字典序大小关系中」要么完全相等，要么具有明确的字典序大小关系，导致 $a$ 必须排在前面或者后面。

2.2 反对称性

具有反对称性是指由 $a@b$ 和 $b@a$ 能够推导出 $a#b$。

$a@b$ 说明字符串 $ab$ 的字典序大小数值要比字符串 $ba$ 字典序大小数值大。

$b@a$ 说明字符串 $ab$ 的字典序大小数值要比字符串 $ba$ 字典序大小数值小。

这样，基于「字典序本身满足全序关系」和「数学上的 $a \geqslant b$ 和 $a \leqslant b$ 可推导出 $a = b$」。

得证 $a@b$ 和 $b@a$ 能够推导出 $a#b$。

2.3 传递性

具有传递性是指由 $a@b$ 和 $b@c$ 能够推导出 $a@c$。

我们可以利用「两个等长的拼接字符串，字典序大小关系与数值大小关系一致」这一性质来证明，因为字符串 $ac$ 和 $ca$ 必然是等长的。

接下来，让我们从「自定义排序逻辑」出发，换个思路来证明 $a@c$：

然后我们只需要证明在不同的 $i$ $j$ 关系之间（共三种情况），$a@c$ 恒成立即可：

1. 当 $i == j$ 的时候：

2. 当 $i > j$ 的时候：

3. 当 $i < j$ 的时候：

综上，我们证明了无论在何种情况下，只要有 $a@b$ 和 $b@c$ 的话，那么 $a@c$ 恒成立。

我们之所以能这样证明「传递性」，本质是利用了自定义排序逻辑中「对于确定任意元素 $a$ 和 $b$ 之间的排序关系只依赖于 $a$ 和 $b$ 的第一个不同元素之间的大小关系」这一性质。

最终，我们证明了该「排序比较逻辑」必然能排序出字典序最大的方案。

代码：

###Java

class Solution {
    public String makeLargestSpecial(String s) {
        if (s.length() == 0) return s;
        List<String> list = new ArrayList<>();
        char[] cs = s.toCharArray();
        for (int i = 0, j = 0, k = 0; i < cs.length; i++) {
            k += cs[i] == '1' ? 1 : -1;
            if (k == 0) {
                list.add("1" + makeLargestSpecial(s.substring(j + 1, i)) + "0");
                j = i + 1;
            }
        }
        Collections.sort(list, (a, b)->(b + a).compareTo(a + b));
        StringBuilder sb = new StringBuilder();
        for (String str : list) sb.append(str);
        return sb.toString();
    }
}

###TypeScript

function makeLargestSpecial(s: string): string {
    const list = new Array<string>()
    for (let i = 0, j = 0, k = 0; i < s.length; i++) {
        k += s[i] == '1' ? 1 : -1
        if (k == 0) {
            list.push('1' + makeLargestSpecial(s.substring(j + 1, i)) + '0')
            j = i + 1
        }
    }
    list.sort((a, b)=>(b + a).localeCompare(a + b));
    return [...list].join("")
};

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

---

最后

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

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

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

遍历

根据题意，对 $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)$

---

同类型加餐

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

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

题目	题解	难度	推荐指数
137. 只出现一次的数字 II	LeetCode 题解链接	中等	🤩🤩🤩
190. 颠倒二进制位	LeetCode 题解链接	简单	🤩🤩🤩
191. 位1的个数	LeetCode 题解链接	简单	🤩🤩🤩
260. 只出现一次的数字 III	LeetCode 题解链接	中等	🤩🤩🤩🤩
405. 数字转换为十六进制数	LeetCode 题解链接	简单	🤩🤩🤩🤩
461. 汉明距离	LeetCode 题解链接	简单	🤩🤩🤩🤩
477. 汉明距离总和	LeetCode 题解链接	简单	🤩🤩🤩🤩
526. 优美的排列	LeetCode 题解链接	中等	🤩🤩🤩

注：以上目录整理来自 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 哦 ~