We fall,
We break,
We fail,

But then,

We rise,
We heal,
We overcome.

Word Break

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

• The same word in the dictionary may be reused multiple times in the segmentation.
• You may assume the dictionary does not contain duplicate words.

Example 1:

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false
# TLE solution
class Solution:
def helper(self, s):
if not s: return True
return any(self.helper(s[len(word):]) for word in self.wordDict if s.startswith(word))

def wordBreak(self, s: str, wordDict: List[str]) -> bool:
self.wordDict = wordDict
return self.helper(s)
# Basic DP
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
dp = [False] * len(s)

for i in range(len(s)):
for word in wordDict:
if s[:i+1].endswith(word) and (dp[i-len(word)] or i-len(word) == -1):
dp[i] = True

return dp[-1]
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
dp = [True]
for i in range(1, len(s)+1):
dp += any(dp[j] and s[j:i] in wordDict for j in range(i)),
return dp[-1]

Increasing Triplet Subsequence

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.

Note: Your algorithm should run in O(n) time complexity and O(1) space complexity.

Example 1:

Input: [1,2,3,4,5]
Output: true

Example 2:

Input: [5,4,3,2,1]
Output: false

History is always recurrent.

At the very first, I thought it is a typical dp question, and then I wrote a classical dp solution, and then I got a TLE…

This AC solution I actually checked it out from discuss board, that is really smart.

class Solution:
def increasingTriplet(self, nums: List[int]) -> bool:
N = len(nums)
first = float("inf")
second = float("inf")

for i in range(N):
if nums[i] < first:
first = nums[i]

elif first < nums[i] < second:
second = nums[i]

if nums[i] > second:
return True

return False

Evaluate Division

Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.

Example:
Given a / b = 2.0, b / c = 3.0.
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .
return [6.0, 0.5, -1.0, 1.0, -1.0 ].

The input is: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector<double>.

According to the example above:

equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].

The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

class Solution:
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
graph = dict()

# Build graph
for (a, b), value in zip(equations, values):
graph[a] = graph.get(a, []) + [(b, value)]
graph[b] = graph.get(b, []) + [(a, 1/value)]

def check(source, target):
# If there is any one number of the query didn't appear in the graph, answer certainly doesn't exist.
if source not in graph or target not in graph:
return -1.0

visited = set()
stack = collections.deque([(source, 1.0)])

while stack:
front, current = stack.popleft()

if front == target:
return current

for back, value in graph[front]:
if back not in visited:
stack.append((back, current * value))

return -1.0

return [check(source, target) for (source, target) in queries]

↓Code inside ↓

Missing Ranges

Given a sorted integer array nums, where the range of elements are in the inclusive range [lowerupper], return its missing ranges.

Example:

Input:   nums = [0, 1, 3, 50, 75], lower = 0 and upper = 99,
Output: ["2", "4->49", "51->74", "76->99"]
class Solution:
def findMissingRanges(self, nums, lower: int, upper: int):
nums.insert(0, lower-1) # Left Bound
nums.append(upper+1)    # Right Bound

res = []

for i in range(len(nums)-1):
left, right = nums[i], nums[i + 1]

if left != right:
if right - left == 2:
res.append(str(left+1))
elif right - left > 2:
res.append(str(left+1) + "->" + str(right-1))

return res

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.