标签： 数组

目标

一个整数数组 original 可以转变成一个 双倍 数组 changed ，转变方式为将 original 中每个元素 值乘以 2 加入数组中，然后将所有元素 随机打乱 。

给你一个数组 changed ，如果 change 是 双倍 数组，那么请你返回 original数组，否则请返回空数组。original 的元素可以以 任意 顺序返回。

示例 1：

输入：changed = [1,3,4,2,6,8]
输出：[1,3,4]
解释：一个可能的 original 数组为 [1,3,4] :
- 将 1 乘以 2 ，得到 1 * 2 = 2 。
- 将 3 乘以 2 ，得到 3 * 2 = 6 。
- 将 4 乘以 2 ，得到 4 * 2 = 8 。
其他可能的原数组方案为 [4,3,1] 或者 [3,1,4] 。

示例 2：

输入：changed = [6,3,0,1]
输出：[]
解释：changed 不是一个双倍数组。

示例 3：

输入：changed = [1]
输出：[]
解释：changed 不是一个双倍数组。

说明：

• 1 <= changed.length <= 10^5
• 0 <= changed[i] <= 10^5

思路

所谓双倍数组指的是由原数组以及其每个元素乘以2之后的元素合并在一起的数组。现在想要从双倍数组还原为原数组，如果不是合法的双倍数组则返回空数组。

首先，如果元素个数为奇数肯定不是双倍数组。注意到数组中的元素如果是奇数那么一定属于原数组。由于返回数组的顺序任意，那么先排序会更好处理。

接着就想到将奇数与偶数分开，然后看奇数*2是否有相应的偶数对应，或者可以将偶数元素/2看是否有奇数对应（不过这样就得处理0的情况，因为0只能与它自己匹配）。匹配完成后可能还剩下原数组中的偶数元素与其对应的双倍元素。

该如何处理呢？看了具体的例子很容易有一些想当然的想法，比如剩余[2,2,4,4]很容易将其平分为两部分，然后同时比较这两部分相应的位置是否满足二倍关系。这种假设是没有根据的，也是不对的，比如剩余[2、2、4、4、4、6、8、12]也是合法的。那我们该怎么比较呢？

这时突然有一个想法出现在大脑中，可以先将当前元素存到队列中，如果后面的元素不是其二倍就添加到队列中，如果是则将队列的第一个元素取出，这样遍历完之后看队列中是否还有数据即可。我们之所以可以这么做是因为前面排过序了，队首元素的二倍元素一定会最先出现。如果不排序的话，比如说[2,1]，2先加入队列，后加入的1就无法匹配了。再比如[4,8,2,16]，4与8匹配了，剩下的就匹配不了了。

有了这个想法之后，前面区分奇数、偶数，对0做特殊处理就都没有必要了。

网友还介绍了一种消消乐的方法，可以不排序。这个需要先统计各元素出现的次数，然后如果x % 2 == 0 && cnt.containsKey(x / 2)则跳过，即如果 x/2 在 cnt 中，则跳过，直到找到开始的那个x，然后一次性处理之前被跳过的2x、4x、6x...。这里其实也利用了顺序，只不过没有排序而是先找到不能再分的那个初始节点再向后倍增。

还有的使用大数组保存了 0~max 元素出现次数的数组cnt，然后遍历cnt，如果cnt[i]>0 而 2*i>max || cnt[2i]==0 直接返回空数组，否则cnt[2i]--。这个方法也不用排序，是因为统计个数时变相地将数组元素映射为下标，遍历cnt数组是从小到大有序的。

代码

/**
 * @date 2024-04-18 8:48
 */
public class FindOriginalArray2007 {

    public int[] findOriginalArray(int[] changed) {
        int n = changed.length;
        if (n % 2 == 1) {
            return new int[0];
        }
        Arrays.sort(changed);
        int originLength = n / 2;
        int[] res = new int[originLength];
        Deque<Integer> collect = new ArrayDeque<>();
        int i = 0;
        for (int j = 0; j < changed.length; j++) {
            if (collect.size() == 0 || changed[j] % 2 == 1 || !collect.peek().equals(changed[j] / 2)) {
                collect.add(changed[j]);
            } else {
                res[i++] = collect.poll();
            }
        }
        if (collect.size() > 0) {
            return new int[0];
        }
        return res;
    }

}

性能

目标

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

说明：

• 2 <= nums.length <= 10^5
• -30 <= nums[i] <= 30
• 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内

进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）

思路

最简单的想法是先计算所有元素的乘积，然后挨个除，但是题目要求不能用除法，略过。

后面又要求不要创建额外的空间，即最好只创建一个用于返回结果的数组。

考虑先保存数组元素的右/左侧的乘积，然后二次遍历计算左/右侧乘积，然后与之前保存的值相乘即可。

网友还有一种一次遍历的写法，初始化结果数组为1，同时从前计算左边乘积，从后计算右边乘积，但是每次循环执行了4次乘法，效率并不高。

代码

/**
 * @date 2024-04-07 11:35
 */
public class ProductExceptSelf238 {

    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] right = new int[n];
        right[n- 1] = 1;
        for (int i = n - 2; i >= 0; i--) {
            right[i] = nums[i + 1] * right[i + 1];
        }
        int left = 1;
        for (int i = 1; i < n; i++) {
            left *= nums[i - 1];
            right[i] *= left;
        }
        return right;
    }

    /**  一次遍历的版本 */
    public int[] productExceptSelf_v1(int[] nums) {
        int[] res = new int[nums.length];
        Arrays.fill(res, 1);
        int j = nums.length - 2;
        int left = 1, right = 1;
        for (int i = 1; i < nums.length; i++) {
            left *= nums[i - 1];
            right *= nums[j + 1];
            res[i] = left * res[i];
            res[j] = right * res[j];
            j--;
        }
        return res;
    }
}

性能

目标

给你一个二进制字符串 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);
    }

}

性能