乐趣区

关于后端:761-特殊的二进制序列-经典构造题

jiezi

题目形容

这是 LeetCode 上的 761. 非凡的二进制序列 ，难度为 艰难。

Tag :「结构」

非凡的二进制序列是具备以下两个性质的二进制序列：

  • 0 的数量与 1 的数量相等。
  • 二进制序列的每一个前缀码中 1 的数量要大于等于 0 的数量。

给定一个非凡的二进制序列 S，以字符串模式示意。定义一个操作为首先抉择 S 的两个间断且非空的非凡的子串，而后将它们替换。（两个子串为间断的当且仅当第一个子串的最初一个字符恰好为第二个子串的第一个字符的前一个字符。)

在任意次数的操作之后，替换后的字符串依照字典序排列的最大的后果是什么？

示例 1:

输出: S = "11011000"

输入: "11100100"

解释:
将子串 "10"（在 S[1]呈现）和 "1100"（在 S[3]呈现）进行替换。这是在进行若干次操作后按字典序排列最大的后果。

阐明:

  • S 的长度不超过 $50$。
  • S 保障为一个满足上述定义的非凡 的二进制序列。

结构

咱们能够定义每个字符的得分：字符 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$ 的时候：
  1. 当 $i > j$ 的时候：
  1. 当 $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)$

最初

这是咱们「刷穿 LeetCode」系列文章的第 No.761 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。

在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。

在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉

本文由 mdnice 多平台公布

退出移动版