标签： 双指针

目标

你有 n 个工作和 m 个工人。给定三个数组： difficulty, profit 和 worker ，其中:

• difficulty[i] 表示第 i 个工作的难度，profit[i] 表示第 i 个工作的收益。
• worker[i] 是第 i 个工人的能力，即该工人只能完成难度小于等于 worker[i] 的工作。

每个工人 最多 只能安排 一个 工作，但是一个工作可以 完成多次 。

• 举个例子，如果 3 个工人都尝试完成一份报酬为 $1 的同样工作，那么总收益为 $3 。如果一个工人不能完成任何工作，他的收益为 $0 。

返回 在把工人分配到工作岗位后，我们所能获得的最大利润 。

示例 1：

输入: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
输出: 100 
解释: 工人被分配的工作难度是 [4,4,6,6] ，分别获得 [20,20,30,30] 的收益。

示例 2:

输入: difficulty = [85,47,57], profit = [24,66,99], worker = [40,25,25]
输出: 0

说明:

• n == difficulty.length
• n == profit.length
• m == worker.length
• 1 <= n, m <= 10^4
• 1 <= difficulty[i], profit[i], worker[i] <= 10^5

思路

现在有一组任务，其难度与收益分别使用两个数组 difficulty 与 profit 表示，还有一个数组表示一组工人的能力。现在需要给工人分配工作，如果分配的工作难度大于工人的能力则无法获取收益，求把工人分配到岗后能够获得的最大收益。

我们只需为每个工人分配其能力范围内的收益最高的工作即可。需要注意的是，题目中没有说难度越高收益越高，并且相同难度的收益也会不同。

难度与收益是通过下标关联的，并且是无序的。

一个很自然的想法是维护一个难度与最大收益的映射，然后直接根据工人的能力二分查找相应的收益并累加。

那么如何同时对两个相关联的数组进行排序就是解题的关键。这里直接将 difficulty 与 profit 的映射通过 hashmap 保存起来，然后对 difficulty 从小到大排序。遍历排序后的 difficulty 数组，计算小于该难度的最大收益并更新到profit 中。根据工人的能力二分查找 profit 并累加即可。

容易出错的点是忘记处理相同难度收益不同的情况，二分查找结果为-1时表示无法完成任务任务，不应取难度最低的任务。

官网题解使用的是 javafx.util.Pair/awt包的Point/ 二维数组来保存映射关系。后面收益最高工作的计算，先对 worker 从小到大排序，使用双指针一个指向worker，一个指向难度，后面工人只需从前一个工人的难度开找即可，没用二分查找。

代码

/**
 * @date 2024-05-17 9:20
 */
public class MaxProfitAssignment826 {

    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        int res = 0;
        int n = difficulty.length;
        int m = worker.length;
        Map<Integer, Integer> profitMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            // 存在难度相同的，取最大的
            if (profitMap.get(difficulty[i]) == null) {
                profitMap.put(difficulty[i], profit[i]);
            } else {
                profitMap.put(difficulty[i], Math.max(profitMap.get(difficulty[i]), profit[i]));
            }
        }
        Arrays.sort(difficulty);
        // 难度从小到大排，更新对应难度可以获得的最大收益
        profit[0] = profitMap.get(difficulty[0]);
        for (int i = 1; i < n; i++) {
            profit[i] = Math.max(profit[i - 1], profitMap.get(difficulty[i]));
        }
        for (int i = 0; i < m; i++) {
            int index = Arrays.binarySearch(difficulty, worker[i]);
            if (index >= 0) {
                res += profit[index];
            } else {
                index = -index - 2;
                if (index >= 0) {
                    // 说明没有能力完成
                    res += profit[index];
                }
            }
        }
        return res;
    }

    // 参考官网题解的答案
    public static class Point{
        public int x;
        public int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public int maxProfitAssignment_v1(int[] difficulty, int[] profit, int[] worker) {
        int res = 0;
        int n = difficulty.length;
        Point[] jobs = new Point[n];
        for (int i = 0; i < n; i++) {
            jobs[i] = new Point(difficulty[i], profit[i]);
        }
        Arrays.sort(jobs, (a, b) -> a.x - b.x);
        // 根据工人技能排序
        // 越往后能力越高，可以直接接着上一次难度位置向后遍历
        Arrays.sort(worker);
        int index = 0;
        int best = 0;
        for (int capability : worker) {
            while (index < n && capability >= jobs[index].x) {
                best = Math.max(best, jobs[index++].y);
            }
            res += best;
        }
        return res;
    }
}

性能

最后计算最大收益时在循环中使用二分查找，时间复杂度为O(mlogn)，而使用双指针 difficulty 最多遍历一遍，时间复杂度是O(m + n)应该更快一点。另外使用hashMap效率不高，因为需要计算hashcode，不如直接访问。

改进后

目标

给你一个二进制字符串 binary ，它仅有 0 或者 1 组成。你可以使用下面的操作任意次对它进行修改：

• 操作 1 ：如果二进制串包含子字符串 "00" ，你可以用 "10" 将其替换。

  比方说， "00010" -> "10010"

• 操作 2 ：如果二进制串包含子字符串 "10" ，你可以用 "01" 将其替换。

  比方说， "00010" -> "00001"

请你返回执行上述操作任意次以后能得到的 最大二进制字符串 。如果二进制字符串 x 对应的十进制数字大于二进制字符串 y 对应的十进制数字，那么我们称二进制字符串 x 大于二进制字符串 y 。

示例 1：

输入：binary = "000110"
输出："111011"
解释：一个可行的转换为：
"000110" -> "000101" 
"000101" -> "100101" 
"100101" -> "110101" 
"110101" -> "110011" 
"110011" -> "111011"

示例 2：

输入：binary = "01"
输出："01"
解释："01" 没办法进行任何转换。

说明：

• 1 <= binary.length <= 10^5
• binary 仅包含 '0' 和 '1'

思路

看到这道题我最先想到的是使用字符串替换，先把00的都替换为10，直到不能替换为止。然后再替换10为01，直到不能替换为止。然后再从头替换，相当于是一个while里面套两个while。

通过对具体例子的观察可以发现将10替换为01不是无条件的，我甚至还写了比较字符串大小的方法，如果字符串变小了就不变了。但其实是不行的，因为中间过程确实存在变小的情况。

最后经过观察分析发现必须要前面有0才可以替换，因为这样可以将高位的0置为1。以01110为例，最后能够转换为10111。

于是就想通过replace方法替换捕获组来实现，例如匹配 0(1*)0，替换为 10(匹配到的1)，试了一下发现replacement不支持。Pattern 类也是无法使用的。

基于上面的分析，我们可以通过算法模拟出替换过程，这里面需要用到双指针 start 与 i：

1. 如果 start 与 i 相同且都指向1，那么直接跳过
2. 如果 start 与 i 相差1，且 i 指向0，即00的情况，那么将 start 指向置1，start++
3. 否则，如果 start 与 i 相差大于1，且 i 指向0，即0(1+)0的情况，那么需要将start 指向置1，start 后面的置0，i 指向的置1 即可

需要注意的是，如果 start 与 i 不同，那么 start 指向的一定是0。其实步骤2与3可以合并，只需先将 i 置1，然后再将 start 后面的置0即可。

看了官网的题解，还提供了一种直接构建的算法。

如果字符串中有多个0，总可以将它们通过10->01将其前移至第一个0的位置，然后通过00->10，使高位的0变为1。最终的结果中至多包含1个0。

因此，直接构建的方法是：从第一个0开始，后面的0全置为1，然后将第一个0后移 0的个数减1 个位置。

代码

/**
 * @date 2024-04-10 0:53
 */
public class MaximumBinaryString1702 {

    /** 直接构造 */
    public String maximumBinaryString_v2(String binary) {
        char[] b = binary.toCharArray();
        int firstZero = binary.indexOf('0');
        if (firstZero == -1) {
            return binary;
        }
        int cnt = 0;
        for (int i = firstZero; i < b.length; i++) {
            cnt += '1' - b[i];
            b[i] = '1';
        }
        b[firstZero + cnt - 1] = '0';
        return new String(b);
    }

    public String maximumBinaryString_v1(String binary) {
        char[] b = binary.toCharArray();
        int start = 0;
        for (int i = 0; i < b.length; i++) {
            if (start == i && '1' == b[i]) {
                start++;
            } else if (start <= i - 1 && '0' == b[i]) {
                b[start++] = '1';
                b[i] = '1';
                b[start] = '0';
            }
        }
        return new String(b);
    }

    public String maximumBinaryString(String binary) {
        char[] b = binary.toCharArray();
        int start = 0;
        for (int i = 0; i < b.length; i++) {
            if (start == i && '1' == b[i]) {
                start++;
            } else if (start == i - 1 && '0' == b[i]) {
                b[start++] = '1';
            } else if (start < i - 1 && '0' == b[i]) {
                b[start++] = '1';
                b[start] = '0';
                b[i] = '1';
            }
        }
        return new String(b);
    }

}

性能