问题3: 给你一个长度为 n 的整数数组 nums 和一个相同长度的二进制字符串 s。 一开始，...

先直接给代码，然后简单讲思路 😄

问题 3：最大得分

思路大纲

• 初始得分 = 目前所有 '1' 所在位置的 nums[i] 之和，但是我们要找的是交换之后的最大得分。
• 操作允许把 '1' 不断往左移动（通过 01 -> 10 的交换），但不能往右移动。
• 最终，相当于我们要选出若干下标集合 $T$，这些位置放 '1'，使得：
  • 选的位置个数 = 初始 '1' 的个数 = m；
  • 对于每个后缀 [i..n-1]，这个后缀中最终放的 '1' 个数，不能超过原串中这个后缀里本来就有的 '1' 个数（因为 '1' 不能向右跑到比自己原来更靠右的位置）。
• 记 suf[i] = 原串中从 i 到末尾 '1' 的个数，那么对每个后缀 [i..n-1]，我们最多可以选择 suf[i] 个位置放 '1'。
• 从右往左扫描：
  • 把当前位置 i 当成一个“候选位置”，放入一个小根堆（只存 nums[i]），表示“如果将来要在后缀 [i..n-1] 放 '1'，可以考虑这个位置”。
  • 当前后缀容量是 suf[i]；如果堆里元素个数 > suf[i]，说明选的位置超了，只好把堆中 最小的那个 nums 丢掉（这样总和最大）。
• 遍历结束时，堆中留下的就是应该放 '1' 的那些位置，堆中元素之和就是最大得分。

复杂度：每个位置进堆一次、最多被弹出一次，O(n log n)，n ≤ 1e5 完全没问题。

代码实现

java
import java.util.PriorityQueue;

class Solution {
    public long maximumScore(int[] nums, String s) {
        int n = nums.length;
        // suf[i] 表示从 i 到末尾的 '1' 的个数
        int[] suf = new int[n + 1];
        int cnt = 0;
        for (int i = n - 1; i >= 0; --i) {
            if (s.charAt(i) == '1') cnt++;
            suf[i] = cnt;
        }

        PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // 存当前后缀选择的位置的 nums 值，维护最大和
        long sum = 0L;

        // 从右往左扫
        for (int i = n - 1; i >= 0; --i) {
            // 把位置 i 作为候选放进来
            minHeap.offer(nums[i]);
            sum += nums[i];

            int cap = suf[i]; // 这个后缀最多可以有 cap 个 '1'

            // 超出容量，则删掉最小的一个位置（不在这里放 1）
            while (minHeap.size() > cap) {
                sum -= minHeap.poll();
            }
        }

        return sum;
    }
}

问题 4：最后剩下的整数

规则总结一下：

• 初始序列为 [1, 2, 3, ..., n]。
• 操作 1（从左）：保留第 1、3、5、... 个数（从左数），删掉第 2、4、6、... 个数。
• 操作 2（从右）：从右往左看，保留从右数第 1、3、5、... 个数，删掉第 2、4、6、... 个数。
• 然后左右交替，直到剩一个数。

直接模拟肯定超时（n 到 1e15）。我们用“等差数列 + 头、步长”的经典写法来做：

用三个变量描述当前序列（不真的存数组）：

• head：当前序列的第一个数；
• step：相邻两个数之间的间隔（公差）；
• remain：当前还剩多少个数；
• left：下一次从左还是从右执行。

初始：

• head = 1, step = 1, remain = n, left = true。

从左删除（操作 1）

当前序列：head, head+step, head+2*step, ... 共 remain 个。

• 从左保留第 1、3、5、... 个：保留下来的索引是 0,2,4,...（0-based）。
• 新的首元素仍然是旧的 head。
• 新的元素个数变成 ceil(remain / 2)。
• 相邻元素间隔变成原来的两倍：step *= 2。

从右删除（操作 2）

当前还有 remain 个数。

从右保留从右数第 1、3、5、... 个。用索引分析：

• 如果 remain 是奇数：保留下来的索引是 0,2,4,...（与从左类似），所以 head 不变。
• 如果 remain 是偶数：保留下来的是 1,3,5,...，所以新的 head = head + step。
• 新序列长度都是 ceil(remain / 2)，步长同样乘 2。

每轮操作后，remain 至少减半，所以循环次数是 O(log n)。对于 n <= 1e15 非常轻松。

代码实现

java
class Solution {
    public long lastInteger(long n) {
        long head = 1L;    // 当前序列的第一个数
        long step = 1L;    // 相邻数字的间隔
        long remain = n;   // 当前还剩多少个数
        boolean left = true; // 下一轮是否从左开始

        while (remain > 1) {
            if (left) {
                // 从左边开始：保留索引 0,2,4,...
                remain = (remain + 1) / 2;  // ceil(remain / 2)
                step <<= 1;                 // step *= 2
                left = false;
            } else {
                // 从右边开始
                if ((remain & 1L) == 1L) {
                    // remain 为奇数，保留索引 0,2,4,... => head 不变
                    remain = remain / 2 + 1;
                } else {
                    // remain 为偶数，保留索引 1,3,5,... => head 向右移一个 step
                    head += step;
                    remain /= 2;
                }
                step <<= 1; // step *= 2
                left = true;
            }
        }

        return head;
    }
}

这两个解法：

• 问题 3：O(n log n)，n <= 1e5 不会超时；
• 问题 4：O(log n)，n <= 1e15 完全没压力。

如果你想，我也可以把两个题都写在一个文件里，或者再给你推几组随机样例验证一下。