-
Notifications
You must be signed in to change notification settings - Fork 111
/
minimum-cost-to-change-the-final-value-of-expression.rs
74 lines (72 loc) · 2.69 KB
/
minimum-cost-to-change-the-final-value-of-expression.rs
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
// Minimum Cost to Change the Final Value of Expression
impl Solution {
pub fn min_operations_to_flip(e: String) -> i32 {
let mut isp = vec![0; 127];
isp[b'&' as usize]=3; isp[b'|' as usize]=3; isp[b'(' as usize]=1;
let mut icp = vec![0; 127];
icp[b'&' as usize]=2; icp[b'|' as usize]=2; icp[b'(' as usize]=4; icp[b')' as usize]=1;
let mut op = vec![b'\0'];
let mut st = vec![];
for &c in e.as_bytes().iter().chain(std::iter::once(&b'\0')) {
if c == b'0' || c == b'1' {
let v = (c-b'0') as i32;
st.push((v, 1-v));
continue;
}
while isp[op[op.len()-1] as usize] > icp[c as usize] {
let y = st.pop().unwrap();
let x = st.pop().unwrap();
let c00 = x.0+y.0; let c01 = x.0+y.1;
let c10 = x.1+y.0; let c11 = x.1+y.1;
st.push(if op.pop().unwrap() == b'&' {
(c00.min(c01).min(c10), c11.min(c01+1).min(c10+1))
} else {
(c00.min(c01+1).min(c10+1), c11.min(c01).min(c10))
});
}
if isp[op[op.len()-1] as usize] == icp[c as usize] {
op.pop();
} else {
op.push(c);
}
}
let x = st.pop().unwrap();
x.0.max(x.1)
}
}
///
impl Solution {
pub fn min_operations_to_flip(e: String) -> i32 {
let mut isp = vec![0; 127];
isp[b'&' as usize]=3; isp[b'|' as usize]=3; isp[b'(' as usize]=1;
let mut icp = vec![0; 127];
icp[b'&' as usize]=2; icp[b'|' as usize]=2; icp[b'(' as usize]=4; icp[b')' as usize]=1;
let mut op = vec![b'\0'];
let mut st = vec![];
for &c in e.as_bytes().iter().chain(std::iter::once(&b'\0')) {
if c == b'0' || c == b'1' {
let v = (c-b'0') as i32;
st.push((v, 1-v));
continue;
}
while isp[op[op.len()-1] as usize] > icp[c as usize] {
let y = st.pop().unwrap();
let x = st.pop().unwrap();
let c00 = x.0+y.0; let c01 = x.0+y.1;
let c10 = x.1+y.0; let c11 = x.1+y.1;
st.push(if op.pop().unwrap() == b'&' {
(c00.min(c01).min(c10), c11.min(c01+1).min(c10+1))
} else {
(c00.min(c01+1).min(c10+1), c11.min(c01).min(c10))
});
}
if isp[op[op.len()-1] as usize] == icp[c as usize] {
op.pop();
} else {
op.push(c);
}
}
let x = st.pop().unwrap();
x.0.max(x.1)
}
}