骨骼现场两道

对于第二题，我有个行得通但是很麻烦的方法，复杂度也是O(n).
1. 构建表达式树。
2. 根据表达式树算出最小flips。

贴出一个代码，我已经感觉到部分优化的点了。看看能不能写个更简单的方法。

1. class ExpressionNode:
   
2. 
   
3.     def __init__(self, e, left=None, right=None):
   
4.         self.e = e
   
5.         self.left, self.right = left, right
   
6. 
   
7.     def left_flips(self):  
   
8.         return self.left.flips() if self.left else 0
   
9. 
   
10.     def right_flips(self):
    
11.         return self.right.flips() if self.right else 0
    
12. 
    
13.     def left_val(self):
    
14.         return self.left.val() if self.left else 0
    
15. 
    
16.     def right_val(self):
    
17.         return self.right.val() if self.right else 0
    
18. 
    
19.     def val(self):
    
20.         if self.e == "1" or self.e == "0":
    
21.             return int(self.e)
    
22.         if self.e == "|":
    
23.             return self.left_val() or self.right_val()
    
24.         if self.e == "&":
    
25.             return self.left_val() and self.right_val()
    
26. 
    
27.         raise Exception("invalid expression")
    
28. 
    
29.     def flips(self):
    
30.         if self.e == "1" or self.e == "0":
    
31.             return 1
    
32.         if self.e == "|":
    
33.             # 1 | 0, 0 | 1  => 1 & 0, 0 & 1
    
34.             if self.left_val() != self.right_val():
    
35.                 return 1
    
36.             # 1 | 1  = > 1 & 0, 0 & 1
    
37.             elif self.left_val() == 1:
    
38.                 return min(self.left_flips(), self.right_flips()) + 1
    
39.             # 0 | 0 => 1 | 0, 0 | 1
    
40.             else:
    
41.                 return min(self.left_flips(), self.right_flips())
    
42.         elif self.e == "&":
    
43.             # 1 & 0, 0 & 1 => 1 | 0, 0 | 1
    
44.             if self.left_val() != self.right_val():
    
45.                 return 1
    
46.             # 1 & 1 => 0 & 1, 1 & 0
    
47.             elif self.left_val() == 1:
    
48.                 return min(self.left_flips(), self.right_flips())
    
49.             # 0 & 0 => 0 | 1, 1 | 0
    
50.             return min(self.left_flips(), self.right_flips()) + 1
    
51.            
    
52.         raise Exception("Invalid node")
    
53. 
    
54. def convert_to_suffix(exp):
    
55. 
    
56.     P = {
    
57.         "|": 2,
    
58.         "&": 3,
    
59.         "(": 1,
    
60.     }
    
61. 
    
62.     stk = []
    
63.     ans = []
    
64.     for e in exp:
    
65.         if e == "1" or e == "0":
    
66.             ans.append(e)
    
67.         elif e in ["&", "|"]:
    
68.             while stk and P[stk[-1]] > P[e]:
    
69.                 ans.append(stk.pop())
    
70.             stk.append(e)
    
71.         elif e == "(":
    
72.             stk.append(e)
    
73.         elif e == ")":
    
74.             while stk and stk[-1] != "(":
    
75.                 ans.append(stk.pop())
    
76.             # popout "("
    
77.             stk.pop()
    
78. 
    
79.     while stk:
    
80.         ans.extend(stk.pop())
    
81.     return "".join(ans)
    
82. 
    
83. def build_tree(suffix_exp):
    
84.     stk = []
    
85.     for e in suffix_exp:
    
86.         if e == "1" or e == "0":
    
87.             stk.append(ExpressionNode(e))
    
88.         else:
    
89.             right = stk.pop()
    
90.             left = stk.pop()
    
91.             stk.append(ExpressionNode(e, left, right))
    
92.    
    
93.     return stk[0]
    
94. 
    
95. if __name__ == "__main__":
    
96.     # e = "1 & (0&(1|1))"
    
97.     # print(build_tree(convert_to_suffix(e)).flips())
    
98.     testcases = [
    
99.         ["1 | 0 & 1", 1],
    
100.         ["1 & 0 | 0", 1],
     
101.         ["1 | 0 | 0", 1],
     
102.         ["1 & (0&(1|1))", 1],
     
103.         ["1 | (0&(1|1))", 1],
     
104.         ["1 | (1&(1|1))", 2],
     
105.     ]
     
106.     for inp, out in testcases:
     
107.         ans = build_tree(convert_to_suffix(inp)).flips()
     
108.         assert(ans == out), (inp, out, ans)

复制代码

稍微简化版的来啦。去掉了构建表达式树这一步骤，不过思路还是一样。
解释几点：
1. 依然后缀表达式，主要是为了去掉括号。
2. class Val 存储了当前sub表达式的value和min flip。

1. def min_flips(exp):
   
2. 
   
3.     # trim whitespace
   
4.     exp = "".join([e for e in exp if e != " "])
   
5.    
   
6.     class Val:
   
7.         def __init__(self, v, flip):
   
8.             self.v, self.flip = v, flip
   
9. 
   
10.         def __str__(self):
    
11.             return "Val (%s, %s,)" %(self.v, self.flip)
    
12. 
    
13.     def convert_to_suffix(exp):
    
14.         P = {
    
15.                 "|": 2,
    
16.                 "&": 3,
    
17.                 "(": 1,
    
18.             }
    
19.         ans = []
    
20.         stk = []
    
21.         for e in exp:
    
22.             if e == " ":
    
23.                 continue
    
24.             if e in ["1", "0"]:
    
25.                 ans.append(Val(int(e), 1))
    
26.             elif e == "(":
    
27.                 stk.append(e)
    
28.             elif e == ")":
    
29.                 while stk and stk[-1] != "(":
    
30.                     ans.append(stk.pop())
    
31.                 stk.pop()
    
32.             else:
    
33.                 while stk and P[stk[-1]] >= P[e]:
    
34.                     ans.append(stk.pop())
    
35.                 stk.append(e)
    
36. 
    
37.         ans.extend(stk[::-1])
    
38.         return ans
    
39. 
    
40.     arr = convert_to_suffix(exp)
    
41.     stk = []
    
42.     for e in arr:
    
43.         if e in ["|", "&"]:
    
44.             rv, lv = stk.pop(), stk.pop()
    
45.             curv = Val(None, None)
    
46.             if e == "|":
    
47.                 curv.v = lv.v or rv.v
    
48.                 # 1 | 0, 0 | 1 => 1 & 0, 0 & 1
    
49.                 if lv.v != rv.v:
    
50.                     curv.flip = 1
    
51.                 # 0 | 0 => 1 | 0, 0 | 1
    
52.                 elif lv.v == 0:
    
53.                     curv.flip = min(lv.flip, rv.flip)
    
54.                 # 1 | 1 => 1 & 0, 0 & 1
    
55.                 elif lv.v == 1:
    
56.                     curv.flip = min(lv.flip, rv.flip) + 1
    
57.             else:
    
58.                 curv.v = lv.v and rv.v
    
59.                 # 1 & 0, 0 & 1 => 1 | 0, 0 | 1
    
60.                 if lv.v != rv.v:
    
61.                     curv.flip = 1
    
62.                 # 1 & 1 => 0 & 1, 1 & 0
    
63.                 elif lv.v == 1:
    
64.                     curv.flip = min(lv.flip, rv.flip)
    
65.                 # 0 & 0 => 0 | 1, 1 | 0
    
66.                 elif lv.v == 0:
    
67.                     curv.flip = min(lv.flip, rv.flip) + 1
    
68.             stk.append(curv)
    
69.         else:
    
70.             stk.append(e)
    
71.    
    
72.     return stk[-1].flip
    
73. 
    
74. 
    
75. 
    
76. # 1 (&1|( 0&0 )|1)|0&(0& (1|1| 0))
    
77. 
    
78. if __name__ == "__main__":
    
79.     testcases = [
    
80.         ["1 | 0 & 1", 1],
    
81.         ["1 & 0 | 0", 1],
    
82.         ["1 | 0 | 0", 1],
    
83.         ["1 & (0&(1|1))", 1],
    
84.         ["1 | (0&(1|1))", 1],
    
85.         ["1 | (1&(1|1))", 2],
    
86.         ["1&(0|1)", 1],
    
87.         ["(1 |(1&1|( 0&0 )|1))|0&(0& (1|1| 0))", 1]
    
88.     ]
    
89.     for inp, out in testcases:
    
90.         # ans = build_tree(convert_to_suffix(inp)).flips()
    
91.         # assert(ans == out), (inp, out, ans)
    
92. 
    
93.         ans2 = min_flips(inp)
    
94.         assert(ans2 == out), (inp, out, ans2)

复制代码

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

1 建树
2 遍历树得到eval的值
3 再次遍历树通过 eval的 值 和 当前的符号 | 还是 & 还是 0 1 得到当前node的最小flip值

1. struct node
   
2. {
   
3.     char v;
   
4.     int r;
   
5.     // c == 0 , v is 0 or 1, else c == 2
   
6.     int c = 0;
   
7.     node* a[2];
   
8.     node(char input)
   
9.     {
   
10.         v = input;
    
11.         if (input == '|' || input == '&')
    
12.         {
    
13.             c = 2;
    
14.             a[0] = nullptr;
    
15.             a[1] = nullptr;
    
16.         }
    
17.         else
    
18.         {
    
19.             c = 0;
    
20.         }
    
21.     }
    
22. };
    
23. class Solution {
    
24. public:
    
25.     string s;
    
26.     int n;
    
27.     node* getnumber(int& i)
    
28.     {
    
29.         if (i >= n)
    
30.         {
    
31.             return nullptr;
    
32.         }
    
33.         node* n1 = nullptr;
    
34.         if (s == '(')
    
35.         {
    
36.             i++;
    
37.             n1 = build(i);
    
38.         }
    
39.         else if (s == '0' || s == '1')
    
40.         {
    
41.             n1 = new node(s);
    
42.             i++;
    
43.         }
    
44.         return n1;
    
45.     }
    
46.     node* build(int& i)
    
47.     {
    
48.         if (i >= n)
    
49.         {
    
50.             return nullptr;
    
51.         }
    
52.         node* n1 = getnumber(i);
    
53.         if (i >= n)
    
54.         {
    
55.             return nullptr;
    
56.         }
    
57.         node* cur = new node(s);
    
58.         i++;
    
59.         node* n2 = getnumber(i);
    
60.         if (i < n && s == ')')
    
61.         {
    
62.             i++;
    
63.         }
    
64.         cur->a[0] = n1;
    
65.         cur->a[1] = n2;
    
66.         return cur;
    
67.     }
    
68.     int res = INT_MAX;
    
69.     int eval(node* root)
    
70.     {
    
71.         if (root->c == 0)
    
72.         {
    
73.             root->r = root->v - '0';
    
74.             return root->r;
    
75.         }
    
76.         int l = eval(root->a[0]);
    
77.         int r = eval(root->a[1]);
    
78.         root->r = (root->v == '|') ? (l | r) : (l & r);
    
79.         return root->r;
    
80.     }
    
81.     int flip(node* root)
    
82.     {
    
83.         if (root->c == 0)
    
84.         {
    
85.             return 1;
    
86.         }
    
87.         int l = root->a[0]->r;
    
88.         int r = root->a[1]->r;
    
89.         if (root->v == '|')
    
90.         {
    
91.             if (root->v == 0)
    
92.             {
    
93.                 return min(flip(root->a[0]), flip(root->a[1]));
    
94.             }
    
95.             else
    
96.             {
    
97.                 // both 1
    
98.                 if (l == r)
    
99.                 {
    
100.                     // change to &
     
101.                     return min(flip(root->a[0]), flip(root->a[1])) + 1;
     
102.                 }
     
103.                 else
     
104.                 {
     
105.                     return 1;
     
106.                 }
     
107.             }
     
108.         }
     
109.         else
     
110.         {
     
111.             if (root->v == 1)
     
112.             {
     
113.                 return min(flip(root->a[0]), flip(root->a[1]));
     
114.             }
     
115.             else // a&b == 0
     
116.             {
     
117.                 // both 0
     
118.                 if (l == r)
     
119.                 {
     
120.                     return min(flip(root->a[0]), flip(root->a[1])) + 1;
     
121.                 }
     
122.                 else
     
123.                 {
     
124.                     return 1;
     
125.                 }
     
126.             }
     
127.         }
     
128.     }
     
129.     int minflip(string exp)
     
130.     {
     
131.         n = exp.size();
     
132.         s = exp;
     
133.         int i = 0;
     
134.         node* root = build(i);
     
135.         eval(root);
     
136.         return flip(root);
     
137.     }
     
138. };

复制代码

[i][i][i][/i][/i][/i]

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies