1896. 改变表达式最终值的最小开销

Hard

题目描述

给你一个有效的布尔表达式字符串 expression，该字符串由字符 '1'、'0'、'&'（按位AND运算符）、'|'（按位OR运算符）、'(' 和 ')' 组成。

例如，"()1|1" 和 "(1)&()" 是无效的，而 "1"、"(((1))|(0))" 和 "1|(0&(1))" 是有效的表达式。

返回改变表达式最终值的最小开销。

例如，如果 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 次操作将 '|' 改为 '&'，将 "1&(0|1)" 变为 "1&(0&1)"。
新表达式求值为 0。

示例 2：

输入：expression = "(0&0)&(0&0&0)"
输出：3
解释：我们可以使用 3 次操作将 "(0&0)&(0&0&0)" 变为 "(0|1)|(0&0&0)"。
新表达式求值为 1。

示例 3：

输入：expression = "(0|(1|0&1))"
输出：1
解释：我们可以使用 1 次操作将 "(0|(1|0&1))" 变为 "(0|(0|0&1))"。
新表达式求值为 0。

约束：

1 <= expression.length <= 10^5
expression 只包含 '1'、'0'、'&'、'|'、'(' 和 ')'
所有括号都正确匹配
没有空括号（即："()" 不是 expression 的子字符串）

解题思路

这是一个动态规划问题，需要使用栈来处理表达式的计算和状态维护。

核心思路：

对于任何子表达式，我们需要维护两个信息：

将当前值变为0的最小开销
将当前值变为1的最小开销

我们使用栈来模拟表达式的计算过程，栈中存储 [当前值, 变为0的开销, 变为1的开销]。

状态转移：

数字处理：
- 遇到 ‘0’：当前值=0，变为0开销=0，变为1开销=1
- 遇到 ‘1’：当前值=1，变为0开销=1，变为1开销=0
运算符处理：对于 ‘&’ 运算：
- 结果为0的开销：min(左边变0, 右边变0)
- 结果为1的开销：左边变1 + 右边变1
- 如果原运算符是 ‘|’，需要+1（改变运算符的开销）
对于 ‘|’ 运算：
- 结果为0的开销：左边变0 + 右边变0
- 结果为1的开销：min(左边变1, 右边变1)
- 如果原运算符是 ‘&’，需要+1
括号处理：
- ‘(’：压入栈作为分隔符
- ‘)’：弹出直到遇到 ‘(’，处理括号内的表达式

算法流程：

遍历表达式字符
数字直接压栈
运算符压栈
遇到 ‘)’ 时处理括号内的完整表达式
最终栈顶元素包含整个表达式的状态信息

最后返回将最终结果翻转所需的最小开销。

代码实现

class Solution {
public:
    int minOperationsToFlip(string expression) {
        stack<vector<int>> stk; // [value, cost_to_0, cost_to_1]
        
        for (char c : expression) {
            if (c == '0') {
                stk.push({0, 0, 1}); // value=0, cost to make 0=0, cost to make 1=1
            } else if (c == '1') {
                stk.push({1, 1, 0}); // value=1, cost to make 0=1, cost to make 1=0
            } else if (c == '&' || c == '|') {
                stk.push({c, 0, 0}); // store operator
            } else if (c == '(') {
                stk.push({-1, 0, 0}); // marker for left parenthesis
            } else if (c == ')') {
                // Process the expression inside parentheses
                vector<vector<int>> temp;
                while (stk.top()[0] != -1) {
                    temp.push_back(stk.top());
                    stk.pop();
                }
                stk.pop(); // remove the '(' marker
                
                // Reverse to get correct order
                reverse(temp.begin(), temp.end());
                
                // Evaluate the expression
                vector<int> result = temp[0];
                for (int i = 1; i < temp.size(); i += 2) {
                    char op = temp[i][0];
                    vector<int> right = temp[i + 1];
                    
                    int val = (op == '&') ? (result[0] & right[0]) : (result[0] | right[0]);
                    int cost0, cost1;
                    
                    if (op == '&') {
                        cost0 = min(result[1], right[1]);
                        cost1 = result[2] + right[2];
                    } else { // op == '|'
                        cost0 = result[1] + right[1];
                        cost1 = min(result[2], right[2]);
                    }
                    
                    // Consider flipping the operator
                    int alt_cost0, alt_cost1;
                    if (op == '&') {
                        alt_cost0 = result[1] + right[1];
                        alt_cost1 = min(result[2], right[2]);
                        cost0 = min(cost0, alt_cost0 + 1);
                        cost1 = min(cost1, alt_cost1 + 1);
                    } else {
                        alt_cost0 = min(result[1], right[1]);
                        alt_cost1 = result[2] + right[2];
                        cost0 = min(cost0, alt_cost0 + 1);
                        cost1 = min(cost1, alt_cost1 + 1);
                    }
                    
                    result = {val, cost0, cost1};
                }
                
                stk.push(result);
            }
        }
        
        // Process remaining expression
        vector<vector<int>> temp;
        while (!stk.empty()) {
            temp.push_back(stk.top());
            stk.pop();
        }
        reverse(temp.begin(), temp.end());
        
        vector<int> result = temp[0];
        for (int i = 1; i < temp.size(); i += 2) {
            char op = temp[i][0];
            vector<int> right = temp[i + 1];
            
            int val = (op == '&') ? (result[0] & right[0]) : (result[0] | right[0]);
            int cost0, cost1;
            
            if (op == '&') {
                cost0 = min(result[1], right[1]);
                cost1 = result[2] + right[2];
            } else {
                cost0 = result[1] + right[1];
                cost1 = min(result[2], right[2]);
            }
            
            int alt_cost0, alt_cost1;
            if (op == '&') {
                alt_cost0 = result[1] + right[1];
                alt_cost1 = min(result[2], right[2]);
                cost0 = min(cost0, alt_cost0 + 1);
                cost1 = min(cost1, alt_cost1 + 1);
            } else {
                alt_cost0 = min(result[1], right[1]);
                alt_cost1 = result[2] + right[2];
                cost0 = min(cost0, alt_cost0 + 1);
                cost1 = min(cost1, alt_cost1 + 1);
            }
            
            result = {val, cost0, cost1};
        }
        
        return result[0] == 1 ? result[1] : result[2];
    }
};

class Solution:
    def minOperationsToFlip(self, expression: str) -> int:
        stack = []
        
        for c in expression:
            if c == '0':
                stack.append([0, 0, 1])  # [value, cost_to_0, cost_to_1]
            elif c == '1':
                stack.append([1, 1, 0])
            elif c in '&|':
                stack.append([ord(c), 0, 0])  # store operator as ASCII
            elif c == '(':
                stack.append([-1, 0, 0])  # marker
            elif c == ')':
                temp = []
                while stack[-1][0] != -1:
                    temp.append(stack.pop())
                stack.pop()  # remove '(' marker
                
                temp.reverse()
                result = temp[0]
                
                for i in range(1, len(temp), 2):
                    op = chr(temp[i][0])
                    right = temp[i + 1]
                    
                    val = (result[0] & right[0]) if op == '&' else (result[0] | right[0])
                    
                    if op == '&':
                        cost0 = min(result[1], right[1])
                        cost1 = result[2] + right[2]
                        # Try flipping to '|'
                        alt_cost0 = result[1] + right[1]
                        alt_cost1 = min(result[2], right[2])
                        cost0 = min(cost0, alt_cost0 + 1)
                        cost1 = min(cost1, alt_cost1 + 1)
                    else:  # op == '|'
                        cost0 = result[1] + right[1]
                        cost1 = min(result[2], right[2])
                        # Try flipping to '&'
                        alt_cost0 = min(result[1], right[1])
                        alt_cost1 = result[2] + right[2]
                        cost0 = min(cost0, alt_cost0 + 1)
                        cost1 = min(cost1, alt_cost1 + 1)
                    
                    result = [val, cost0, cost1]
                
                stack.append(result)
        
        # Process remaining expression
        temp = stack[:]
        result = temp[0]
        
        for i in range(1, len(temp), 2):
            op = chr(temp[i][0])
            right = temp[i + 1]
            
            val = (result[0] & right[0]) if op == '&' else (result[0] | right[0])
            
            if op == '&':
                cost0 = min(result[1], right[1])
                cost1 = result[2] + right[2]
                alt_cost0 = result[1] + right[1]
                alt_cost1 = min(result[2], right[2])
                cost0 = min(cost0, alt_cost0 + 1)
                cost1 = min(cost1, alt_cost1 + 1)
            else:
                cost0 = result[1] + right[1]
                cost1 = min(result[2], right[2])
                alt_cost0 = min(result[1], right[1])
                alt_cost1 = result[2] + right[2]
                cost0 = min(cost0, alt_cost0 + 1)
                cost1 = min(cost1, alt_cost1 + 1)
            
            result = [val, cost0, cost1]
        
        return result[1] if result[0] == 1 else result[2]

public class Solution {
    public int MinOperationsToFlip(string expression) {
        Stack<int[]> stack = new Stack<int[]>();
        
        foreach (char c in expression) {
            if (c == '0') {
                stack.Push(new int[] {0, 0, 1});
            } else if (c == '1') {
                stack.Push(new int[] {1, 1, 0});
            } else if (c == '&' || c == '|') {
                stack.Push(new int[] {c, 0, 0});
            } else if (c == '(') {
                stack.Push(new int[] {-1, 0, 0});
            } else if (c == ')') {
                List<int[]> temp = new List<int[]>();
                while (stack.Peek()[0] != -1) {
                    temp.Add(stack.Pop());
                }
                stack.Pop(); // remove '(' marker
                
                temp.Reverse();
                int[] result = temp[0];
                
                for (int i = 1; i < temp.Count; i += 2) {
                    char op = (char)temp[i][0];
                    int[] right = temp[i + 1];
                    
                    int val = (op == '&') ? (result[0] & right[0]) : (result[0] | right[0]);
                    int cost0, cost1;
                    
                    if (op == '&') {
                        cost0 = Math.Min(result[1], right[1]);
                        cost1 = result[2] + right[2];
                        int altCost0 = result[1] + right[1];
                        int altCost1 = Math.Min(result[2], right[2]);
                        cost0 = Math.Min(cost0, altCost0 + 1);
                        cost1 = Math.Min(cost1, altCost1 + 1);
                    } else {
                        cost0 = result[1] + right[1];
                        cost1 = Math.Min(result[2], right[2]);
                        int altCost0 = Math.Min(result[1], right[1]);
                        int altCost1 = result[2] + right[2];
                        cost0 = Math.Min(cost0, altCost0 + 1);
                        cost1 = Math.Min(cost1, altCost1 + 1);
                    }
                    
                    result = new int[] {val, cost0, cost1};
                }
                
                stack.Push(result);
            }
        }
        
        List<int[]> finalTemp = new List<int[]>();
        while (stack.Count > 0) {
            finalTemp.Add(stack.Pop());
        }
        finalTemp.Reverse();
        
        int[] finalResult = finalTemp[0];
        for (int i = 1; i < finalTemp.Count; i += 2) {
            char op = (char)finalTemp[i][0];
            int[] right = finalTemp[i + 1];
            
            int val = (op == '&') ? (finalResult[0] & right[0]) : (finalResult[0] | right[0]);
            int cost0, cost1;
            
            if (op == '&') {
                cost0 = Math.Min(finalResult[1], right[1]);
                cost1 = finalResult[2] + right[2];
                int altCost0 = finalResult[1] + right[1];
                int altCost1 = Math.Min(finalResult[2], right[2]);
                cost0 = Math.Min(cost0, altCost0 + 1);
                cost1 = Math.Min(cost1, altCost1 + 1);
            } else {
                cost0 = finalResult[1] + right[1];
                cost1 = Math.Min(finalResult[2], right[2]);
                int altCost0 = Math.Min(finalResult[1], right[1]);
                int altCost1 = finalResult[2] + right[2];
                cost0 = Math.Min(cost0, altCost0 + 1);
                cost1 = Math.Min(cost1, altCost1 + 1);
            }
            
            finalResult = new int[] {val, cost0, cost1};
        }
        
        return finalResult[0] == 1 ? finalResult[1] : finalResult[2];
    }
}

var minOperationsToFlip = function(expression) {
    let i = 0;
    
    function parse() {
        let left = parseFactor();
        
        while (i < expression.length && (expression[i] === '&' || expression[i] === '|')) {
            let op = expression[i++];
            let right = parseFactor();
            
            let val = op === '&' ? left[0] & right[0] : left[0] | right[0];
            let cost;
            
            if (op === '&') {
                if (val === 1) {
                    cost = Math.min(left[1], right[1]);
                } else {
                    cost = Math.min(left[2] + right[2], Math.min(left[2], right[2]) + 1);
                }
            } else {
                if (val === 0) {
                    cost = Math.min(left[2], right[2]);
                } else {
                    cost = Math.min(left[1] + right[1], Math.min(left[1], right[1]) + 1);
                }
            }
            
            left = [val, val === 1 ? cost : (op === '&' ? left[1] + right[1] : Math.min(left[1], right[1]) + 1), 
                    val === 0 ? cost : (op === '|' ? left[2] + right[2] : Math.min(left[2], right[2]) + 1)];
        }
        
        return left;
    }
    
    function parseFactor() {
        if (expression[i] === '(') {
            i++;
            let result = parse();
            i++;
            return result;
        } else {
            let val = parseInt(expression[i++]);
            return [val, val === 1 ? 0 : 1, val === 0 ? 0 : 1];
        }
    }
    
    let result = parse();
    return result[result[0] === 1 ? 2 : 1];
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	复杂度
时间复杂度	O(n)
空间复杂度	O(n)

解释：

时间复杂度：O(n)，其中 n 是表达式的长度。每个字符最多被处理常数次。
空间复杂度：O(n)，栈的最大深度与表达式中括号的嵌套深度和操作数数量成正比。

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析