"""LBYL"""
if "key" in dict_:
    value += dict_["key"]
    
"""EAFP"""
# downplays the importance of the key
try:
    value += dict_["key"]
except KeyError:
    pass
    

      """pythonic fibonacci"""
# generator function
def fibonacci(n):
    a, b, counter = 0, 1, 0
    while counter <= n:
        yield a
        a, b = b, a + b	# multiple assignment
        counter += 1
        
f = fibonacci(5)
# EAFP
while True:
    try:
        print (next(f), end=" ")
    except StopIteration:
        break
# output: 0 1 1 2 3 5
    

      """used in detect cycle in linked list"""
# L141: determine there is a cycle in a linked list
def has_cycle_in_linked_list(head: ListNode) -> bool:
    try:
        slow = head
        fast = head.next
        while slow is not fast:
            slow = slow.next
            fast = fast.next.next
        return True
    except:
        return False

"""used in binary search and insert"""
# L334: given an unsorted array return whether an increasing subsequence (incontinuous) of length k exists or not in the array.
def increasing_triplet(nums: List[int], k: int) -> bool:
    try:
        inc = [float('inf')] * (k - 1)
        for x in nums:
            inc[bisect.bisect_left(inc, x)] = x
        return k == 0
    except:
        return True

"""used in eval"""
# L301: Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.
def remove_invalid_parentheses(s: str) -> List[str]:
    def isvalid(s):
        try:
            eval('0,' + ''.join(filter('()'.count, s)).replace(')', '),'))
            return True
        except:
            pass
    level = {s}
    while True:
        valid = list(filter(isvalid, level))
        if valid:
            return valid
        level = {s[:i] + s[i+1:] for s in level for i in range(len(s))}
    

      """reuse self to save the cost of dummy node"""
def traverse_linked_list(self, head: TreeNode) -> TreeNode:
    pre, pre.next = self, head
    while pre.next:
        self.process_logic(pre.next)
    return self.next  # return head node
    

      # L536: construct binary tree from string
def str2tree(s: str) -> TreeNode:
    def t(val, left=None, right=None):
        node, node.left, node.right = TreeNode(val), left, right
        return node
    return eval('t(' + s.replace('(', ',t(') + ')') if s else None
    

      # L331: verify preorder serialization of a binary tree, if it is a null node, we record using a sentinel value #
def is_valid_serialization(preorder: str) -> bool:
    need = 1
    for val in preorder.split(','):
        if not need:
            return False
        need -= ' #'.find(val)
    return not need
    

      """convert int to unicode char, and use str.replace to merge the connected nodes by reduce"""
# L323: given n nodes from 0 to n - 1 and a list of undirected edges, find the number of connected components in an undirected graph.
def count_connected_components(n: int, edges: List[List[int]]) -> int:
    return len(set(reduce(lambda s, edge: s.replace(s[edge[1]], s[edge[0]]), edges, ''.join(map(chr, range(n))))))
    

      """Use ^ to remove even exactly same numbers and save the odd, or save the distinct bits and remove the same."""
"""bit manipulate: a^b^b = a"""
# L268: Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.
def missing_number(nums: List[int]) -> int:
    res = 0
    for i, e in enumerate(nums):
        res = res ^ i ^ e
    return res ^ len(nums)

"""simply find the first index whose "partner index" (the index xor 1) holds a different value."""
# L540: find the single element, in a sorted array where every element appears twice except for one. 
def single_non_duplicate(nums: List[int]) -> int:
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] == nums[mid ^ 1]:
            lo = mid + 1
        else:
            hi = mid
    return nums[lo]

"""parity in triple comparisons"""
# L81: search a target in a rotated sorted array
def search_in_rotated_sorted_arr(nums: List[int], target: int) -> int:
    """I have three checks (nums[0] <= target), (target <= nums[i]) and (nums[i] < nums[0]), and I want to know
    whether exactly two of them are true. They can't all be true or all be false (check it), so I just need to
    distinguish between "two true" and "one true". Parity is enough for that, so instead of adding them I xor them"""
    self.__getitem__ = lambda i: (nums[0] <= target) ^ (nums[0] > nums[i]) ^ (target > nums[i])
    i = bisect.bisect_left(self, True, 0, len(nums))
    return i if target in nums[i:i+1] else -1