# Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example:

```Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is `[1, 2, 3, 4]`. Therefore its length is 4.```
```class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
nums = set(nums)
ans = 0

for x in nums:
# Find the first element in one segment
if x-1 not in nums:
y = x + 1
# reach the last consecutive element in one element
while y in nums:
y += 1
ans = max(ans, y - x)

return ans```
```class Solution:
def longestConsecutive(self, nums) -> int:
UF = {}
nums = set(nums)

if not nums:
return 0

# for num in nums:
#     UF[num] = num

def find(x):
if x != UF[x]:
UF[x] = find(UF[x])
return UF[x]

def union(x, y):
UF.setdefault(x, x)
UF.setdefault(y, y)
UF[find(x)] = find(y)

for n in nums:
if (n - 1) in nums:
union(n - 1, n)
if (n + 1) in nums:
union(n, n + 1)

ans = 1

for num in nums:
if num in UF:
ans = max(ans, find(num) - num + 1)
return ans```

# Python Daemon

```# coding=utf8
import os
import sys
import atexit

def daemonize(pid_file=None):
"""
Create daemon process
:param pid_file: File that saves process id
:return:
"""
# Fork a subprocess from parent process
pid = os.fork()

# The id of subprocess equals 0, and of parent process must larger than 0
if pid:
# Exit from parent process(sys.exit() executes flush while os._exit() doesn't)
sys.exit(0)

# The subprocess defaults the working directory of its parent process.
os.chdir('/')

# The subprocess defaults umask(File permission mask), reset it to 0(Fully control) in order to avoiding R/W operations.

# Let the subprocess be the leader of the conversation and the process.
os.setsid()

# Second Fork
_pid = os.fork()
if _pid:
# Exit subprocess
sys.exit(0)

# Grandson process is daemon right now. Redirecting stdin/stdout/stderr descriptions to avoid errors in the printing process.

# Flush stdout/stderr buffer
sys.stdout.flush()
sys.stderr.flush()

# Atomically close and duclipate file description, and redirect into /dev/null(Drop off all input and output)
with open('/dev/null') as read_null, open('/dev/null', 'w') as write_null:
os.dup2(write_null.fileno(), sys.stdout.fileno())
os.dup2(write_null.fileno(), sys.stderr.fileno())

# Write PID
if pid_file:
with open(pid_file, 'w+') as f:
f.write(str(os.getpid()))
# Register Exit function for abnormal exit
atexit.register(os.remove, pid_file)```
1. Fork sub-process, and exit parent-process.
2. Change Working Directory (chdir), File Permission Mask(umask), Process Group and Conversation Group (setsid).
3. Fork grandson-process, and exit sub-process.
4. Flush buffer and atomically close and duclipate file description, and redirect into /dev/null(Drop off all input and output)
5. (Option) Write PID.

# Most Stones Removed with Same Row or Column

On a 2D plane, we place stones at some integer coordinate points.  Each coordinate point may have at most one stone.

Now, a move consists of removing a stone that shares a column or row with another stone on the grid.

What is the largest possible number of moves we can make?

Example 1:

```Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5
```

Example 2:

```Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
Output: 3
```

Example 3:

`Input: stones = [[0,0]]`

At very first I read this problem, the MOVE operation is described as confusing as heck. I read some explanations on the discussboard, and then finally got the actual meaning.

We can treat each coordinate as two parts (x and y), and can maintain an Union-Find in order to calculate how many groups in the entire field.

``` class Solution:
def removeStones(self, stones: List[List[int]]) -> int:
UF = {}

def find(x):
if x != UF[x]:
UF[x] = find(UF[x])
return UF[x]

def union(x, y):
UF.setdefault(x, x)
UF.setdefault(y, y)
UF[find(x)] = find(y)

for i, j in stones:
print(i, j, ~j)
union(i, ~j)

return len(stones) - len({find(x) for x in UF})```

# Brace Expansion

A string `S` represents a list of words.

Each letter in the word has 1 or more options.  If there is one option, the letter is represented as is.  If there is more than one option, then curly braces delimit the options.  For example, `"{a,b,c}"` represents options `["a", "b", "c"]`.

For example, `"{a,b,c}d{e,f}"` represents the list `["ade", "adf", "bde", "bdf", "cde", "cdf"]`.

Return all words that can be formed in this manner, in lexicographical order.

Example 1:

```Input: "{a,b}c{d,e}f"
Output: ["acdf","acef","bcdf","bcef"]
```

Example 2:

```Input: "abcd"
Output: ["abcd"]
```

Note:

1. `1 <= S.length <= 50`
2. There are no nested curly brackets.
3. All characters inside a pair of consecutive opening and ending curly brackets are different.
```class Solution:
def expand(self, S):

def func(remain, result, results):
if not remain:
results.append(result)

else:
# if a single character appear at the first of the remain string
if remain != "{":
func(remain[1:], result + remain, results)
return
else:
temp = list()
i = 0

# find elements in the first brace of the remain string
while remain[i] != "}":
if remain[i].isalpha():
temp.append(remain[i])
i += 1

for t in temp:
func(remain[i + 1:], result + t, results)

results = []

func(S, "", results)

return results```

# In me the tiger sniffs the rose

I wanted you to see what real courage is, instead of getting the idea that courage is a man with a gun in his hand. It’s when you know you’re licked before you begin anyway and you see it through no matter what. You rarely win, but sometimes you do.

# Delete Nodes And Return Forest

Given the `root` of a binary tree, each node in the tree has a distinct value.

After deleting all nodes with a value in `to_delete`, we are left with a forest (a disjoint union of trees).

Return the roots of the trees in the remaining forest.  You may return the result in any order.

Example 1:

```Input: root = [1,2,3,4,5,6,7], to_delete = [3,5]
Output: [[1,2,null,4],,]
```

Constraints:

• The number of nodes in the given tree is at most `1000`.
• Each node has a distinct value between `1` and `1000`.
• `to_delete.length <= 1000`
• `to_delete` contains distinct values between `1` and `1000`.
```# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def delNodes(self, root: TreeNode, to_delete: List[int]) -> List[TreeNode]:
forest = []
to_delete = set(to_delete)

def buttom_up(root):
if root:
left, right = dfs(root.left), dfs(root.right)

root.left, root.right = left, right

if root.val in to_delete:
if left: forest.append(left)
if right: forest.append(right)
else:
return root

dfs(root)

return ([] if root.val in to_delete else [root]) + forest

#########################################################

to_delete_set = set(to_delete)
res = []

def top_down(root, is_root):
if not root:
return None

root_deleted = root.val in to_delete_set

if is_root and not root_deleted:
res.append(root)

root.left = helper(root.left, root_deleted)
root.right = helper(root.right, root_deleted)

return None if root_deleted else root

top_down(root, True)

return res```

# Decode String

Given an encoded string, return its decoded string.

The encoding rule is: `k[encoded_string]`, where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like `3a` or `2`.

Examples:

```s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".```
```class Solution:
def decodeString(self, s: str) -> str:
stack = list()
times = list()

for i, v in enumerate(s):
if v.isdigit():
# Single Digit, like 1,2,3...
if not s[i-1].isdigit():
times.append(int(v))
# Multiple digits, like 100, 200...
else:
times[-1] = times[-1] * 10 + int(v)

# push
elif v != "]":
stack.append(v)

# reach "]"
else:
# Retrive string in cloest level square brackets
b = ""
t = stack.pop()
while t != "[":
b = t + b
t = stack.pop()

stack.append(b * times.pop())

return "".join(stack)```

# Sentence Similarity II

Given two sentences `words1, words2` (each represented as an array of strings), and a list of similar word pairs `pairs`, determine if two sentences are similar.

For example, `words1 = ["great", "acting", "skills"]` and `words2 = ["fine", "drama", "talent"]` are similar, if the similar word pairs are `pairs = [["great", "good"], ["fine", "good"], ["acting","drama"], ["skills","talent"]]`.

Note that the similarity relation is transitive. For example, if “great” and “good” are similar, and “fine” and “good” are similar, then “great” and “fine” are similar.

Similarity is also symmetric. For example, “great” and “fine” being similar is the same as “fine” and “great” being similar.

Also, a word is always similar with itself. For example, the sentences `words1 = ["great"], words2 = ["great"], pairs = []` are similar, even though there are no specified similar word pairs.

Finally, sentences can only be similar if they have the same number of words. So a sentence like `words1 = ["great"]` can never be similar to `words2 = ["doubleplus","good"]`.

Note:

• The length of `words1` and `words2` will not exceed `1000`.
• The length of `pairs` will not exceed `2000`.
• The length of each `pairs[i]` will be `2`.
• The length of each `words[i]` and `pairs[i][j]` will be in the range `[1, 20]`.
```class Solution:
def areSentencesSimilarTwo(self, words1: List[str], words2: List[str], pairs: List[List[str]]) -> bool:
parent = {}

if len(words1) != len(words2):
return False

def find(w):
if w not in parent:
return w
if parent[w] != w:
w = find(parent[w])
return w

def union(w1, w2):
parent[w1] = w2

for pair in pairs:
union(find(pair), find(pair))

for word_pair in zip(words1, words2):
if word_pair == word_pair:
continue
else:
continue
else:
return False
return True```

# Campus Bikes II

On a campus represented as a 2D grid, there are `N` workers and `M` bikes, with `N <= M`. Each worker and bike is a 2D coordinate on this grid.

We assign one unique bike to each worker so that the sum of the Manhattan distances between each worker and their assigned bike is minimized.

The Manhattan distance between two points `p1` and `p2` is `Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|`.

Return the minimum possible sum of Manhattan distances between each worker and their assigned bike.

Example 1:

```Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
Output: 6
Explanation:
We assign bike 0 to worker 0, bike 1 to worker 1. The Manhattan distance of both assignments is 3, so the output is 6.
```

Example 2:

```Input: workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]]
Output: 4
Explanation:
We first assign bike 0 to worker 0, then assign bike 1 to worker 1 or worker 2, bike 2 to worker 2 or worker 1. Both assignments lead to sum of the Manhattan distances as 4.
```

Note:

1. `0 <= workers[i], workers[i], bikes[i], bikes[i] < 1000`
2. All worker and bike locations are distinct.
3. `1 <= workers.length <= bikes.length <= 10`
```from functools import lru_cache

class Solution:
def dis(self, a, b):
return abs(a - b) + abs(a - b)

def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:
@lru_cache(None)
def dfs(p, arr):
return 0 if p == self.W else min([self.dis(bikes[i], workers[p]) + dfs(p + 1, arr + 2 ** i) for i in range(self.B) if not (arr>>i) & 1])

self.W = len(workers)
self.B = len(bikes)

return dfs(0, 0)```