---
Yang Min
---
# Crashing Leetcode
This is Place holder to test if slides mode work.
---
## Stack
- Calculator & True statement evaluation
- https://leetcode.com/problems/basic-calculator-iv/
- https://leetcode.com/problems/parsing-a-boolean-expression/
- Pay attention to the way to deal with `()`
- O≥(2n)
----
```python=
class Solution:
def parseBoolExpr(self, expression: str) -> bool:
stack = []
for c in expression:
if c == ')':
cache = []
while stack[-1] != '(':
cache.append(stack.pop())
stack.pop()
cur = stack.pop()
stack.append(all(cache) if cur == '&' else any(cache) if cur == '|' else not cache.pop())
elif c != ',':
stack.append(True if c == 't' else False if c == 'f' else c)
return stack.pop()
```
----
### 155. Min Stack
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
- push(x) -- Push element x onto stack.
- pop() -- Removes the element on top of the stack.
- top() -- Get the top element.
- getMin() -- Retrieve the minimum element in the stack.
----
```Python
class MinStack(object):
def __init__(self):
"""
initialize your data structure here.
"""
self.stack = []
self.minval = float('inf')
def push(self, x):
"""
:type x: int
:rtype: None
"""
self.minval = min(self.minval, x)
self.stack.append((x, self.minval))
def pop(self):
"""
:rtype: None
"""
self.stack.pop()
self.minval = self.stack[-1][1] if self.stack else float('inf')
def top(self):
"""
:rtype: int
"""
return self.stack[-1][0]
def getMin(self):
"""
:rtype: int
"""
return self.stack[-1][1]
```
---
## Dynamic Programming
---
### DP Types
- 坐标型
- 序列型
- 划分型
- 区间型
- 背包
- 双序列
---
### Paint House II (序列型)
- Link: https://leetcode.com/problems/paint-house-ii/
- last step depends on previous state => we need to consider different states.
----
- `dp[i][j]`: the min cost for house i when use color j
- Transfer Function
- `dp[i][j] = min(dp[i-1][0], ..., dp[i-1][j-1], ... dp[i-1][j+1], ..., dp[i-1][k-1]) + cost[i][j]`
- find the next min according to the previous one
- This should be able to cover all of the possibilities
----
```python=
def minCostII(self, costs):
if not costs:
return 0
h = len(costs)
c = len(costs[0])
dp = [[costs[i][j] for j in range(c)] for i in range(h)]
for i in range(c):
dp[0][i] = costs[0][i]
for i in range(1, h):
m1 = min(dp[i-1])
idx = dp[i-1].index(m1)
m2 = min(dp[i-1][:idx]+dp[i-1][idx+1:])
for j in range(c):
if j == idx:
dp[i][j] += m2
else:
dp[i][j] += m1
return min(dp[-1])
```
---
### Palindrome Partitioning II (划分型)
- Transfer function
- `DP[i] = min(dp[i-n] form chr i with previous one, possibilities) + 1`
----
**划分型动态规划**
- 常见动态规划类型
- 给定长度为N的序列或字符串，要求划分成若干段 – 段数不限，或指定K段
- 每一段满足一定的性质
- 做法
– 类似于序列型动态规划，但是通常要加上段数信息
– 一般用f[i][j]记录前i个元素(元素0~i-1)分成j段的性质，如最小代价
----
例子：
https://leetcode.com/problems/palindrome-partitioning-ii/discuss/137296/two-python-dp-solution-with-explaination
---
### 1024. Video Stitching
- 转移方程
- `dp[i] = min(dp[s], ..., dp[e]) + 1`
- min:
``` python
class Solution(object):
def videoStitching(self, clips, T):
"""
:type clips: List[List[int]]
:type T: int
:rtype: int
"""
dp = [0] + [float("inf")] * T
for i in range(T + 1):
for clip in clips:
if clip[0] <= i <= clip[1]:
dp[i] = min(dp[i], dp[clip[0]] + 1)
return dp[-1] if dp[-1] != float("inf") else -1
```
```Python
class Solution(object):
def videoStitching(self, clips, T):
"""
:type clips: List[List[int]]
:type T: int
:rtype: int
"""
dp = [0] + [float('inf')] * T
sc = sorted(clips, key=lambda x: x[0])
if sc[0][0] != 0:
return -1
for clip in sc:
s, e = clip
for i in range(s, e+1):
if i > T:
break
dp[i] = min(dp[s] + 1, dp[i])
return dp[-1] if dp[-1] < float('inf') else -1
```
---
### 729. My Calendar I
```Python
class MyCalendar(object):
def __init__(self):
self.books = {}
self.starts = []
def book(self, start, end):
"""
:type start: int
:type end: int
:rtype: bool
"""
for st in self.starts:
if st < start and start < self.books[st]:
return False
elif start <= st < end:
return False
elif st >= end:
break
self.starts.append(start)
self.starts.sort()
self.books[start] = end
return True
```
{"metaMigratedAt":"2023-06-14T22:34:14.246Z","metaMigratedFrom":"Content","title":"Crashing Leetcode","breaks":true,"contributors":"[{\"id\":null,\"add\":3764,\"del\":114},{\"id\":\"377a1375-e18a-4549-8aab-48ac12feb377\",\"add\":6242,\"del\":7007}]"}