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]
# Advanced DP
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
                
                visited.add(front)
                
                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]

Implement Trie (Prefix Tree)

我今天是打算去维妈买螃蟹的。

因为昨天自行车放在学校没有骑回家,所以今天是坐电车去学校的。上车的时候,算了一下边际成本,愉快的刷了卡。

到了州立图书馆之后,本来是说要去吃DonDon的,但是想到学校旁边的Don Tojo就突然想吃点别的了。于是找了一家网红店吃了一份鳗鱼饭。

吃完饭,捋了捋自己狂放不羁的头发,顺道去了一趟理发店。理完发,神清气爽的去了维妈。

发现没开门。

之后回学校坐定开始学校,打算随手水道题,于是瞄了一眼问题列表,选了Trie Tree。

以前写Trie都是要写好久的,但是这次居然五分钟不到就一次性Bug Free了,蛮开心的。

↓Code inside ↓

Continue reading

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.
    os.umask(0)

    # 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(read_null.fileno(), sys.stdin.fileno())
        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.