作者： admin

目标

给你一个整数数组 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);
    }

}

性能

目标

一个王国里住着国王、他的孩子们、他的孙子们等等。每一个时间点，这个家庭里有人出生也有人死亡。

这个王国有一个明确规定的王位继承顺序，第一继承人总是国王自己。我们定义递归函数 Successor(x, curOrder) ，给定一个人 x 和当前的继承顺序，该函数返回 x 的下一继承人。

Successor(x, curOrder):
    如果 x 没有孩子或者所有 x 的孩子都在 curOrder 中：
        如果 x 是国王，那么返回 null
        否则，返回 Successor(x 的父亲, curOrder)
    否则，返回 x 不在 curOrder 中最年长的孩子

比方说，假设王国由国王，他的孩子 Alice 和 Bob （Alice 比 Bob 年长）和 Alice 的孩子 Jack 组成。

1. 一开始， curOrder 为 ["king"].
2. 调用 Successor(king, curOrder) ，返回 Alice ，所以我们将 Alice 放入 curOrder 中，得到 ["king", "Alice"] 。
3. 调用 Successor(Alice, curOrder) ，返回 Jack ，所以我们将 Jack 放入 curOrder 中，得到 ["king", "Alice", "Jack"] 。
4. 调用 Successor(Jack, curOrder) ，返回 Bob ，所以我们将 Bob 放入 curOrder 中，得到 ["king", "Alice", "Jack", "Bob"] 。
5. 调用 Successor(Bob, curOrder) ，返回 null 。最终得到继承顺序为 ["king", "Alice", "Jack", "Bob"] 。

通过以上的函数，我们总是能得到一个唯一的继承顺序。

请你实现 ThroneInheritance 类：

• ThroneInheritance(string kingName) 初始化一个 ThroneInheritance 类的对象。国王的名字作为构造函数的参数传入。
• void birth(string parentName, string childName) 表示 parentName 新拥有了一个名为 childName 的孩子。
• void death(string name) 表示名为 name 的人死亡。一个人的死亡不会影响 Successor 函数，也不会影响当前的继承顺序。你可以只将这个人标记为死亡状态。
• string[] getInheritanceOrder() 返回 除去 死亡人员的当前继承顺序列表。

示例：

输入：
["ThroneInheritance", "birth", "birth", "birth", "birth", "birth", "birth", "getInheritanceOrder", "death", "getInheritanceOrder"]
[["king"], ["king", "andy"], ["king", "bob"], ["king", "catherine"], ["andy", "matthew"], ["bob", "alex"], ["bob", "asha"], [null], ["bob"], [null]]
输出：
[null, null, null, null, null, null, null, ["king", "andy", "matthew", "bob", "alex", "asha", "catherine"], null, ["king", "andy", "matthew", "alex", "asha", "catherine"]]

解释：
ThroneInheritance t= new ThroneInheritance("king"); // 继承顺序：king
t.birth("king", "andy"); // 继承顺序：king > andy
t.birth("king", "bob"); // 继承顺序：king > andy > bob
t.birth("king", "catherine"); // 继承顺序：king > andy > bob > catherine
t.birth("andy", "matthew"); // 继承顺序：king > andy > matthew > bob > catherine
t.birth("bob", "alex"); // 继承顺序：king > andy > matthew > bob > alex > catherine
t.birth("bob", "asha"); // 继承顺序：king > andy > matthew > bob > alex > asha > catherine
t.getInheritanceOrder(); // 返回 ["king", "andy", "matthew", "bob", "alex", "asha", "catherine"]
t.death("bob"); // 继承顺序：king > andy > matthew > bob（已经去世）> alex > asha > catherine
t.getInheritanceOrder(); // 返回 ["king", "andy", "matthew", "alex", "asha", "catherine"]

说明：

• 1 <= kingName.length, parentName.length, childName.length, name.length <= 15
• kingName，parentName， childName 和 name 仅包含小写英文字母。
• 所有的参数 childName 和 kingName 互不相同。
• 所有 death 函数中的死亡名字 name 要么是国王，要么是已经出生了的人员名字。
• 每次调用 birth(parentName, childName) 时，测试用例都保证 parentName 对应的人员是活着的。
• 最多调用 10^5 次birth 和 death 。
• 最多调用 10 次 getInheritanceOrder 。

思路

首先要弄清皇位继承顺序，国王孩子中最大的先继承，如果他也有后代同样按照长幼继承，然后才轮到国王的次子继承。刚开始以为是先在老一辈里面按顺序继承，然后才轮到孩子辈的。国王生的孩子直接按顺序加入，如果国王死了就将继承国王的后代加入继承序列。

继承顺序可以有两种处理方式，一个是在出生与死亡的时候维护，另一个是在调用继承顺序方法的时候根据现有的状态生成。

动态维护的算法不容易实现，死亡的时候需要从继承序列中删除，出生时需要在特定位置插入，在哪插？

根据状态生成更容易实现，每次都是从开国的国王开始，按照继承规则遍历即可。写的时候也没有意识到这其实就是多叉树的前序遍历。

代码

/**
 * @date 2024-04-07 8:42
 */
public class ThroneInheritance1600 {

    private final Map<String, List<String>> children;

    private final Set<String> dead;

    private final String originator;

    public ThroneInheritance1600(String kingName) {
        originator = kingName;
        children = new HashMap<>();
        dead = new HashSet<>();
    }

    public void birth(String parentName, String childName) {
        children.computeIfAbsent(parentName, k -> new ArrayList<>()).add(childName);
    }

    public void death(String name) {
        dead.add(name);
    }

    public List<String> getInheritanceOrder() {
        List<String> curOrder = new ArrayList<>();
        if (!dead.contains(originator)) {
            curOrder.add(originator);
        }
        successor(originator, curOrder);
        return curOrder;
    }

    public void successor(String name, List<String> curOrder) {
        if (children.get(name) != null && children.get(name).size() != 0) {
            for (String child : children.get(name)) {
                if (!dead.contains(child)) {
                    curOrder.add(child);
                }
                successor(child, curOrder);
            }
        }
    }

    public static void main(String[] args) {
        ThroneInheritance1600 main = new ThroneInheritance1600("king");
        System.out.println(main.getInheritanceOrder());
        main.birth("king", "logan");
        main.birth("logan", "hosea");
        main.birth("king", "leonard");
        main.death("king");
        main.birth("logan", "carl");
        main.death("hosea");
        main.birth("leonard", "ronda");
        main.birth("logan", "betty");
        System.out.println(main.getInheritanceOrder());
    }
}

性能