LeetCode 题解工作台
反转表达式值的最少操作次数
给你一个 有效的 布尔表达式，用字符串 expression 表示。这个字符串包含字符 '1' ， '0' ， '&' （按位 与 运算）， '|' （按位 或 运算）， '(' 和 ')' 。 比方说， "()1|1" 和 "(1)&()" 不是有效 布尔表达式。而 "1" ， "(((1))|(…
4
题型
0
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个 有效的 布尔表达式，用字符串 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 <= 105expression只包含'1'，'0'，'&'，'|'，'('和')'- 所有括号都有与之匹配的对应括号。
- 不会有空的括号（也就是说
"()"不是expression的子字符串）。
解题思路
方法一
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | and space depend on the number of subexpressions and states tracked. With memoization, the complexity is O(n^3) worst-case for all subexpression ranges, but practical pruning reduces it. Space stores DP tables per subexpression and target value. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Ask how to represent subexpression states and minimal costs clearly.
- question_mark
Probe whether memoization prevents redundant recalculation of nested parentheses.
- question_mark
Check if candidate considers flipping operators versus changing subexpression values.
常见陷阱
外企场景- error
Ignoring that changing an operator might not always reduce total cost.
- error
Failing to correctly track all possible states for subexpressions inside parentheses.
- error
Assuming linear traversal works without considering operator precedence and nested structures.
进阶变体
外企场景- arrow_right_alt
Compute minimal changes to achieve a specific target value other than flipping.
- arrow_right_alt
Allow changing operands '0' to '1' and vice versa, not just operators.
- arrow_right_alt
Handle expressions with additional operators like '^' while maintaining minimal cost.