反转表达式值的最少操作次数

标签: 栈 数学 字符串 动态规划

难度: Hard

给你一个 有效的 布尔表达式，用字符串 expression 表示。这个字符串包含字符 '1'，'0'，'&'（按位 与 运算），'|'（按位 或 运算），'(' 和 ')' 。

  • 比方说，"()1|1" 和 "(1)&()" 不是有效 布尔表达式。而 "1"， "(((1))|(0))" 和 "1|(0&(1))" 是 有效 布尔表达式。

你的目标是将布尔表达式的 值 反转 （也就是将 0 变为 1 ，或者将 1 变为 0），请你返回达成目标需要的 最少操作 次数。

  • 比方说，如果表达式 expression = "1|1|(0&0)&1" ，它的 值 为 1|1|(0&0)&1 = 1|1|0&1 = 1|0&1 = 1&1 = 1 。我们想要执行操作将 新的 表达式的值变成 0 。

可执行的 操作 如下：

  • 将一个 '1' 变成一个 '0' 。
  • 将一个 '0' 变成一个 '1' 。
  • 将一个 '&' 变成一个 '|' 。
  • 将一个 '|' 变成一个 '&' 。

注意：'&' 的 运算优先级 与 '|' 相同 。计算表达式时，括号优先级 最高 ，然后按照 从左到右 的顺序运算。

 

示例 1：

输入：expression = "1&(0|1)"
输出：1
解释：我们可以将 "1&(0|1)" 变成 "1&(0&1)" ，执行的操作为将一个 '|' 变成一个 '&' ，执行了 1 次操作。
新表达式的值为 0 。

示例 2：

输入：expression = "(0&0)&(0&0&0)"
输出：3
解释：我们可以将 "(0&0)&(0&0&0)" 变成 "(0|1)|(0&0&0)" ，执行了 3 次操作。
新表达式的值为 1 。

示例 3：

输入：expression = "(0|(1|0&1))"
输出：1
解释：我们可以将 "(0|(1|0&1))" 变成 "(0|(0|0&1))" ，执行了 1 次操作。
新表达式的值为 0 。

 

提示：

  • 1 <= expression.length <= 105
  • expression 只包含 '1'，'0'，'&'，'|'，'(' 和 ')'
  • 所有括号都有与之匹配的对应括号。
  • 不会有空的括号（也就是说 "()" 不是 expression 的子字符串）。

Submission

运行时间: 240 ms

内存: 17.8 MB

class Solution:
    def minOperationsToFlip(self, expression: str) -> int:
        costs = []
        ops = []

        for ch in expression:
            if ch in "|&(":
                # Memorize the op
                ops.append(ch)
                continue
            
            # Add an initial cost pair if needed
            if ch == "0":
                # 0 cost to turn 0; 1 cost to turn 1
                costs.append((0, 1))
            elif ch == "1":
                # 1 cost to turn 0; 0 cost to turn 1
                costs.append((1, 0))
            elif ch == ")":
                # Pause caused by '(' should end here
                assert(ops[-1] == "(")
                ops.pop()
            
            # Try to use the previous op to calculate
            # If '(', then skip to reserve the previous op
            if len(ops) > 0 and ops[-1] != "(":
                # Pop an op and two cost pairs
                op = ops.pop()
                c0_r, c1_r = costs.pop()
                c0_l, c1_l = costs.pop()

                # Calculate new cost pair using DP
                if op == "&":
                    cost = (
                        min(c0_l, c0_r), # No change
                        min(
                            c1_l + c1_r, # No change
                            1 + min(c1_l, c1_r) # Change op
                        )
                    )
                elif op == "|":
                    cost = (
                        min(
                            c0_l + c0_r, # No change
                            1 + min(c0_l, c0_r) # Change op
                        ),
                        min(c1_l, c1_r), # No change
                    )
                costs.append(cost)
        
        # The smaller one is 0,
        # namely the final value doesn't change
        return max(costs[-1])

Explain

本题解采用了堆栈和动态规划的方式解决问题。首先，使用两个堆栈，一个用于保存操作符（包括'&'、'|'和'('），另一个用于保存每个子表达式的转换成本。转换成本用一对整数表示，其中第一个整数表示将子表达式的值从0转换成1的最小操作次数，第二个整数表示从1转换成0的最小操作次数。遍历表达式字符串，根据当前字符的类型（数字、操作符或括号），更新堆栈。遇到数字时，直接将其转换成本入栈。遇到操作符时，将其入操作符栈。遇到')'时，处理到对应的'('之间的表达式，应用动态规划公式来计算合并后的成本，并更新成本堆栈。最后，堆栈顶的成本对就是整个表达式的转换成本，其中较大的值表示将整个表达式的值反转的最小操作次数。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def minOperationsToFlip(self, expression: str) -> int:
        costs = []  # Stack to hold the cost pairs (cost to make 0, cost to make 1)
        ops = []  # Stack to hold operations and '('

        for ch in expression:
            if ch in '|&(':  # Push operation or open parenthesis to ops stack
                ops.append(ch)
                continue

            if ch == '0':
                costs.append((0, 1))  # No cost to keep 0, cost 1 to change to 1
            elif ch == '1':
                costs.append((1, 0))  # Cost 1 to change to 0, no cost to keep 1

            if ch == ')':  # Resolve expression inside the parenthesis
                assert(ops[-1] == '(', 'Mismatched parentheses')
                ops.pop()

            while len(ops) > 0 and ops[-1] != '(':  # Apply operations to top two cost pairs
                op = ops.pop()
                c0_r, c1_r = costs.pop()  # Right operand costs
                c0_l, c1_l = costs.pop()  # Left operand costs

                if op == '&':
                    new_cost = (
                        min(c0_l, c0_r),  # Cost for result 0
                        min(c1_l + c1_r, 1 + min(c1_l, c1_r))  # Cost for result 1 (including operation change)
                    )
                elif op == '|':
                    new_cost = (
                        min(c0_l + c0_r, 1 + min(c0_l, c0_r)),  # Cost for result 0 (including operation change)
                        min(c1_l, c1_r)  # Cost for result 1
                    )
                costs.append(new_cost)  # Push the combined costs

        return max(costs[-1])  # Max of the final costs gives minimum operations to flip the entire expression

Explore

堆栈在处理布尔表达式时扮演了储存和管理运算符及表达式值的临时状态的角色。使用堆栈可以方便地处理嵌套结构和后序计算。表达式中的括号和运算符的顺序要求后遇到的元素先处理，这符合堆栈的后进先出（LIFO）原则。相比其他数据结构，堆栈提供了简单有效的方式来逆序访问元素，这对于遵循数学和逻辑表达式的运算顺序尤为重要。

在处理 ')' 时，代码逻辑首先确认顶部操作符为 '('，从而确保括号内的表达式可以被正确处理。随后，程序从堆栈中取出相应的运算符和操作数来进行计算。使用动态规划的方法，根据运算符（如 '&', '|'）更新操作数的转换成本。例如，对于与操作 '&', 新的成本计算为：结果为0的最小成本取决于两侧任一为0的成本较小者；结果为1的最小成本则是两侧都为1的成本总和，但如果改变操作符，可能只需一侧为1的较小成本加上一次操作变更。

断言 `assert(ops[-1] == '(', 'Mismatched parentheses')` 用于确保每次遇到 ')' 时，操作符堆栈的顶部元素必须是 '('。这是为了保证括号正确匹配，以维护表达式的结构完整性。如果顶部不是 '('，则程序将抛出错误，提示括号匹配不正确。这个断言处理的边界情况包括处理到达右括号时栈顶不是左括号的错误情况，这通常指示表达式中括号的使用错误或不平衡。

在计算与('&')和或('|')操作的转换成本时，需要考虑操作本身的变更成本，因为改变操作符可能会减少将表达式的值反转所需的总操作数。例如，改变 '|' 为 '&' 可能会降低将表达式从1变为0的成本。在实现过程中，通过考虑保持当前操作符不变和改变操作符所需的成本，并取两者的较小值来进行计算。这样做可以确保得到最少的操作次数，从而最小化转换成本。