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

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给你一个有效的布尔表达式，用字符串 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 <= 10⁵
expression 只包含 '1'，'0'，'&'，'|'，'(' 和 ')'
所有括号都有与之匹配的对应括号。
不会有空的括号（也就是说 "()" 不是 expression 的子字符串）。

# 思路

ArrayDeque

# 解法

class Solution {
    public int minOperationsToFlip(String expression) {
        Deque<Character> opt = new ArrayDeque<>();
        Deque<int[]> state = new ArrayDeque<>();
        for(char c:expression.toCharArray()){
            if("10)".contains(c+"")){
                if(c=='0')  state.add(new int[]{0,1});
                else if(c=='1') state.add(new int[]{1,0});
                else {
                    if(opt.peekLast()=='(') opt.pollLast();
                }
                if(!opt.isEmpty()&&opt.peekLast()!='('){
                    int[] p1 = state.pollLast();
                    int[] p2 = state.pollLast();
                    char op = opt.pollLast();
                    int[] p = new int[2];
                    if(op=='&'){
                        p[0] = Math.min(p1[0],p2[0]);
                        p[1] = Math.min(p1[1]+p2[1],Math.min(p1[1],p2[1])+1);
                    }else{
                        p[0] = Math.min(p1[0]+p2[0],Math.min(p1[0],p2[0])+1);
                        p[1] = Math.min(p1[1],p2[1]);
                    }
                    state.add(p);
                }
            }else{
                opt.add(c);
            }
        }
        return Math.max(state.peekLast()[0],state.peekLast()[1]);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

# 总结

分析出几种情况，然后分别对各个情况实现

#Java