Python Tricks - Iterable - Part 2

1map(function, iterables) -> iterables

1"""map to node children recursively"""
2# L104: get depth in binary tree
3def max_depth(root: TreeNode) -> int:
4    return 1 + max(map(maxDepth, (root.left, root.right))) if root else 0
5
6"""comparison map find with map index"""
7# L290: given a pattern and a string words, find if words follows the same pattern. 
8# i.e. pattern = 'abba', words = 'dog cat cat dog'
9def valid_word_pattern(pattern: str, words: str) -> bool:
10    s, t = pattern, words.split()
11    return list(map(s.find, s)) == list(map(t.index, t))
12
13"""map dict.get"""
14# L506: given scores of N athletes, find their relative ranks and the people with the top three highest scores, who will be awarded medals: "Gold Medal", "Silver Medal" and "Bronze Medal"
15def find_relative_ranks(nums: List[int]) -> List[str]:
16    sorted_nums = sorted(nums, reverse=True)
17    rank = ["Gold Medal", "Silver Medal", "Bronze Medal"] + list(map(str, range(4, len(nums) + 1)))
18    return list(map(dict(zip(sorted_nums, rank)).get, nums))

1reduce(function, sequence[, initial]) -> value

1# L136: every numbers appears twice except for one, find that single one
2def single_number(nums: List[int]) -> int:
3    return reduce(lambda x, y: x ^ y, nums)
4
5# L47: generate all possible permutations
6def permute(nums: List[int]) -> List[List[int]]:
7    return reduce(lambda P, n: [p[:i] + [n] + p[i:] for p in P for i in range(len(p)+1)], nums, [[]])

1zip(*iterables) -> iterator

1a = [1,2,3]
2b = ['one','two','three']
3zipped=zip(a,b)
4list(zipped)
5# output: [(1, 'one'), (2, 'two'), (3, 'three')]

1"""construct dict"""
2keys = ['a', 'b', 'c']
3vals = [1, 2, 3]
4zipped_dict = dict(zip(keys, vals))
5
6"""difference of neighbor pairs"""
7arr, diffs = [1, 2, 3, 4, 5], []
8for pre, post in zip(arr[:-1], arr[1:]):  # zip(arr, arr[1:]) is ok too, zip matches the shortest
9    diffs.append(post - pre)
10
11"""transpose matrix"""
12# L867: The transpose of a matrix is the matrix flipped over it's main diagonal, switching the row and column indices of the matrix.
13def transpose(matrix: List[List[int]]) -> List[List[int]]:
14    return list(map(list, zip(*matrix)))
15
16"""zip into a set"""
17# L290: given a pattern and a string words, find if words follows the same pattern. 
18# i.e. pattern = 'abba', words = 'dog cat cat dog'
19def valid_word_pattern(pattern: str, words: str) -> bool:
20    s, t = pattern, words.split()
21    return len(set(zip(s, t))) == len(set(s)) == len(set(t)) and len(s) == len(t)

1def product(a, b):
2    return a * b
3
4"""use * to unpack tuple, list or other iterables"""
5param_tuple = (2, 3)
6product(*param_tuple)
7# output: 6
8
9"""use ** to unpack dict"""
10param_dict = {'a': 2, 'b': 3}
11product(**param_dict)
12# output: 6

1"""get rest of all"""
2a, *b, c = range(5)
3# b = [1, 2, 3]
4[(c, *d, [*e]), f, *g] = [[1, 2, 3, 4, [5, 5, 5]], 6, 7, 8]
5# d = [2, 3, 4], e = [5, 5, 5], g = [7, 8]
6
7"""merge dicts"""
8a = {'1': 1, '2': 2}
9b = {'2': 3, '4': 4}
10merged_dict = {**a, **b}   #{'1': 1, '2': 3, '4': 4}
11
12"""[*a] = list(a), [*zip(*matrix)]: transpose matrix"""
13# L54: traverse matrix in spiral order.
14def traverse_spiral_order(matrix: List[List[int]]) -> List[int]:
15    return matrix and [*matrix.pop(0)] + traverse_spiral_order([*zip(*matrix)][::-1])

1sum(iterable[, start]) -> number

1"""sum"""
2# L771: S is stones you have, J is types of stones which are jewels, and you want to know how many stones are also jewels.
3def num_jewels_in_stones(J: str, S: str) -> int:
4    return sum(map(J.count, S))
5
6# L389: string t is generated by random shuffling string s and then add one more letter at a random position, find the letter.
7def find_the_difference(s: str, t: str) -> str:
8    return chr(sum(map(ord, t)) - sum(map(ord, s)))
9
10# L266: determine if a permutation of the string could form a palindrome
11def can_permute_palindrome(s: str) -> bool:
12    """at most one odd count character"""
13    return sum(v % 2 for v in Counter(s).values()) <= 1

1max(iterable[, default=obj, key=func]) -> value

1"""max"""
2# L169: find the majority element which appears more than ⌊ n/2 ⌋ times.
3def majority_element(nums: List[int]) -> int:
4    counts = Counter(nums)
5    return max(counts.keys(), key=counts.get)
6
7"""min"""
8# L14: find the longest common prefix string amongst an array of strings.
9def longest_common_prefix(strs: List[str]) -> str:
10    shortest = min(strs, key=len)
11    for i, ch in enumerate(shortest):
12        if any(s[i] != ch for s in strs):
13            return shortest[:i]
14    return shortest

1any(iterable) -> bool

1"""any"""
2# L36: determine if a 9x9 Sudoku board is valid, which means 1-9 in row, column, 3x3 sub-boxes
3def is_valid_sudoku(board: List[List[str]]) -> bool:
4    seen = set()
5    return not any(x in seen or seen.add(x)
6                   for i, row in enumerate(board)
7                   for j, c in enumerate(row)
8                   if c != '.'
9                   for x in ((c, i), (j, c), (i/3, j/3, c)))
10
11"""all"""
12# L766: a matrix is Toeplitz if every diagonal from top-left to bottom-right has the same element.
13def is_toeplitz_matrix(matrix: List[List[int]]) -> bool:
14    return all(r == 0 or c == 0 or matrix[r-1][c-1] == val
15               for r, row in enumerate(matrix)
16               for c, val in enumerate(row))
17
18# L246: verify the number is strobogrammatic, strobogrammatic number looks the same when rotated 180 degrees
19def is_strobogrammatic(num: str) -> bool:
20    return all(map('696 00 11 88'.count, map(operator.add, num, num[::-1])))
21
22# L261: given n nodes labeled from 0 to n-1 and a list of undirected edges, check whether these edges make up a valid tree.
23def valid_tree(n: int, edges: List[List[int]]) -> bool:
24    """all check in union find"""
25    parent = range(n)
26    def find(x):
27        return x if parent[x] == x else find(parent[x])
28    def union(xy):
29        x, y = map(find, xy)
30        parent[x] = y
31        return x != y
32    return len(edges) == n-1 and all(map(union, edges))

1bisect.bisect_left(a, x[, lo=0, hi=len(a)]) -> int

1"""use binary search to find the first number that's less than or equal to the last."""
2# L153: find the minimum element in rotated sorted array
3def find_min_in_rotated_sorted_arr(self, nums: List[int]) -> int:
4    """construct iterable which distinguish the two parts of rotated array"""
5    self.__getitem__ = lambda i: nums[i] <= nums[-1]
6    return nums[bisect.bisect(self, False, 0, len(nums))]
7
8"""construct a boolean iterable and use binary search"""
9# L4: find the median of the two sorted arrays
10def find_median_in_two_sorted_arrays(nums1: List[int], nums2: List[int]) -> float:
11    a, b = sorted((nums1, nums2), key=len)
12    m, n = len(a), len(b)
13    after = (m + n - 1) // 2
14    class Range:
15        def __getitem__(self, i):
16            return after-i-1 < 0 or a[i] >= b[after-i-1]
17    i = bisect.bisect_left(Range(), True, 0, m)
18    nextfew = sorted(a[i:i+2] + b[after-i:after-i+2])
19    return (nextfew[0] + nextfew[1 - (m+n)%2]) / 2