骨骼现场两道

是一段时间之前在狗家遇到的面经了，两道题是我自己没在蠡寇上见到的，加一个数据点，也看看大家有没有什么更好的解法

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

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

稍微简化版的来啦。去掉了构建表达式树这一步骤，不过思路还是一样。
解释几点：
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)

复制代码

第二题本质上就是一个非常非常非常基础的DP...

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

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

请问群主如何在O(n)时间使用map找到S和T中是否存在一对相同的 character pair呢， 尤其在有重复character的情况下

第一题想法和lz一样

第二题我一开始觉得时间复杂度是O(n * num of “|&”)，就是每次找中间的符号然后判断怎么改。后来想想确实可以On，就是recursion的时候每次返回两个值，一个是当前的段落变成1要变几个，二是变成0要变几个。。不过想想implementation就很复杂。。

悲慘新农 码克 留影 楼主好运

感觉这两题难度都比较大啊

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

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

flyingforce 发表于 2020-12-6 06:58
前面一道题简单， 维护一个 Map  对象，保存所有没有找到match的t 的character以及位置， 任何时候看到一个 ...

第一题的解法看的不太明白。如果这样做最坏情况下的时间复杂度不是O(n^2) 吗

您好！
本帖隐藏的内容需要积分高于 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