Java 中的最小后缀翻转

寻找最小后缀翻转的问题涉及处理两个二进制字符串：初始字符串 s 和目标字符串 target。这里，两个字符串的长度均为 n，初始字符串 s 是一个全零字符串（即 s = "000. .. 0"）。目标是在最少的翻转操作次数内，将字符串 s 转换为目标字符串。

示例 1

输入

输出

 
Minimum operations needed: 3

解释

示例 2

输入

输出

 
Minimum operations needed: 3    

解释

方法 1：使用递归

递归方法的核心思想是使用递归来处理转换。在每一步，我们检查当前字符是否与（基于迄今为止的翻转次数）预期的字符匹配。如果不匹配，我们执行翻转并进行递归调用来处理字符串的其余部分。

算法

步骤 1：定义 minOperations 方法，该方法使用初始索引 0 和 flipped 设置为 false 调用 helper 方法 minOperationsHelper。

步骤 2：minOperationsHelper 方法检查索引是否已到达字符串末尾。如果是，则返回 0，因为不再需要更多操作。

步骤 3：根据翻转状态确定当前索引处的预期字符（如果 flipped 为 true 则为“1”，否则为“0”）。

步骤 4：字符比较：如果 target 中的当前字符与预期字符不匹配，则意味着需要翻转：将操作计数增加 1。使用下一个索引和切换的翻转状态进行递归调用。

步骤 5：如果字符匹配，则无需翻转：使用下一个索引进行递归调用，而不更改翻转状态。

文件名：MinimumSuffixFlips.java

输出

 
Minimum operations needed: 3   

时间复杂度

整体时间复杂度为 O(n)，其中 n 是目标字符串的长度。递归处理字符串中的每个字符一次。

空间复杂度

整体空间复杂度为 O(n)，因为递归调用堆栈，在最坏情况下，该堆栈的深度可能与字符串的长度一样大。

方法 2：使用栈

使用栈的方法的核心思想是跟踪目标字符串中位值从“0”变为“1”或从“1”变为“0”的过渡点。每次过渡都代表了一个需要进行翻转的点。通过将目标字符串的字符压入栈并计算变化次数，我们可以确定所需的翻转次数。

算法

步骤 1：初始化：创建一个空栈来跟踪目标字符串中的过渡。初始化一个操作计数器为 0，该计数器将跟踪所需翻转操作的数量。

步骤 2：遍历目标字符串：使用 for 循环遍历目标字符串中的每个字符。对于每个字符，检查栈是否为空，或者栈顶元素是否与当前字符不同。

步骤 3：如果任一条件为真，则将当前字符压入栈并增加操作计数器，这表示需要翻转的新段。

步骤 4：操作计数器将包含将 s 转换为 target 所需的最少翻转操作次数，然后返回最小翻转次数。

文件名：MinimumSuffixFlips1.java

输出

 
Minimum operations needed: 3    

时间复杂度

基于栈的方法的时间复杂度为 O(n)，其中 n 是目标字符串的长度。该算法只遍历目标字符串一次。目标字符串中的每个字符都以恒定时间处理。

空间复杂度

基于栈的方法的空间复杂度为 O(n)。在最坏情况下，如果每个字符都与其前一个字符不同，栈可以容纳目标字符串的所有字符。因此，栈使用的空间与目标字符串的长度呈线性增长。

方法 3：直接过渡计数

使用直接过渡计数方法可以有效地解决将初始二进制字符串 s（全零）转换为目标二进制字符串 target 的问题，其中需要最少数量的翻转操作。

算法

步骤 1：首先将操作计数器设置为 0，它跟踪执行的翻转操作的数量。初始化一个变量 currentBit 为“0”，表示字符串 s 中位的初始状态。

步骤 2：遍历目标字符串：循环遍历目标字符串 target 中的每个字符。对于每个字符，将其与 currentBit 进行比较。

步骤 3：如果 target 中的当前字符与 currentBit 不同，则意味着发生了过渡

步骤 3.1：将操作计数器加 1。将 currentBit 更新为 target 中的当前字符。

步骤 4：遍历完整个目标字符串后，操作计数器将包含将 s 转换为 target 所需的最少翻转次数。

文件名：MinimumSuffixFlips2.java

输出

 
Minimum operations needed: 3    

时间复杂度

直接过渡计数方法的时间复杂度为 O(n)，其中 n 是目标字符串的长度。这是因为算法只遍历目标字符串一次。

空间复杂度

直接过渡计数方法的空间复杂度为 O(1)。该算法使用的额外空间量恒定，与输入大小无关。只有少数变量（operations、currentBit）用于跟踪当前状态和操作计数。

方法 4：贪心翻转计数

贪心翻转计数是一种简单的方法，用于确定将初始二进制字符串 s（最初全零）转换为目标二进制字符串 target 所需的最少翻转操作次数。此方法依赖于贪心策略直接计数过渡，从而得到一种有效的解决方案。

算法

步骤 1：将操作计数器设置为 0，以计算所需的翻转操作次数。首先比较目标字符串中的每一位与其前一位，以检测变化。

步骤 2：遍历目标字符串：对于每个字符，将其与前一个字符（或第一个字符的“0”）进行比较。

步骤 3：每当当前字符与前一个字符不同时，就增加操作计数器，因为它表示需要翻转操作才能匹配字符串的该段。

步骤 4：处理完整个字符串后，返回操作计数器，该计数器现在包含所需的最少翻转次数。

文件名：MinimumSuffixFlips3.java

输出

 
Minimum operations needed: 3    

时间复杂度

贪心翻转计数方法的时间复杂度为 O(n)，其中 n 是目标字符串的长度。该算法只遍历目标字符串一次。目标字符串中的每个字符都以恒定时间处理。

空间复杂度

贪心翻转计数方法ii 的空间复杂度为 O(1)。该算法使用的额外空间量恒定，与输入大小无关。只有少数变量（operations）用于跟踪翻转操作的数量。

方法 5：双指针技术

双指针技术提供了一种有效的方法来解决将初始二进制字符串 s（全零）转换为目标二进制字符串 target 的问题。此技术使用两个指针来跟踪目标字符串中的过渡并计算需要翻转的段数。

算法

步骤 1：初始化两个指针，current 和 next。将 current 指针设置为 target 字符串的第一个字符。将 next 指针设置为第二个字符。初始化操作计数器为 0。

步骤 2：遍历目标字符串：使用 next 指针遍历目标字符串。将 next 指针处的字符与 current 指针处的字符进行比较。

步骤 3：每当 next 指针处的字符与 current 指针处的字符不同时，就表示发生了过渡

步骤 3.1：增加操作计数器。将 current 指针移到 next 指针。继续此过程直到字符串末尾。

步骤 4：操作计数器将包含将 s 转换为 target 所需的最少翻转次数，然后返回结果。

文件名：MinimumSuffixFlips4.java

输出

 
Minimum operations needed: 3    

时间复杂度

双指针技术的时间复杂度为 O(n)，其中 n 是目标字符串的长度。这是因为算法只遍历目标字符串一次。

空间复杂度

双指针技术ii 的空间复杂度为 O(1)。该算法使用的额外空间量恒定，与输入大小无关。

结论

总之，最小后缀翻转问题可以通过各种方法来解决，每种方法在可读性、效率和空间利用率方面都有其优点。方法的选择可以取决于具体的约束和偏好。