Python Basic

使用Custom Comparator

使用cmp_to_key

from functools import cmp_to_key
def compare(item1, item2):
    return item1 - item2
    
mylist.sort(key=cmp_to_key(compare))

# Or
from functools import cmp_to_key
mylist.sort(key=cmp_to_key(
    lambda item1, item2: len(item1) - len(item2)
                            # str compare 只能用 > <
                            # str a < b 只會返回 true false
    if item1 == item2 else (-1 if item1<item2 else 1)))

如果比較物件不是primitive type，可以用一個wrapper class 實作 lt

class ListNode:
    def __init__(self, x):
         self.val = x
         self.next = None
     
class Wrapper():
    def __init__(self, node):
        self.node = node
    def __lt__(self, other):
        return self.node.val < other.node.val

frozenset()使用

The frozenset() is an inbuilt function is Python which takes an iterable object as input and makes them immutable. Since frozenset object are immutable they are mainly used as key in dictionary or elements of other sets

694 Number of Distinct Islands

尋找地圖中圖型pattern distinct的個數

1. dfs中紀錄原始座標，並在set中紀錄相對座標

def numDistinctIslands(self, grid: List[List[int]]) -> int:
    self.m, self.n = len(grid), len(grid[0])
    shapes = set()
    for i in range(self.m):
        for j in range(self.n):
            if grid[i][j] == 1:
                shape = set()
                self.helper(grid, shape, i, j, i, j)
                shape = frozenset(shape)
                if shape not in shapes:
                    shapes.add(shape)
    return len(shapes)


def helper(self, grid, shape, i, j, i0, j0):
    grid[i][j] = 0
    shape.add((i-i0, j-j0))
    for dy, dx in ((0, 1),(1, 0), (0, -1), (-1, 0)):
        y = i + dy
        x = j + dx
        if not (0 <= y < self.m and 0 <= x < self.n and grid[y][x] == 1): continue
        self.helper(grid, shape, y, x, i0, j0)
        

zfill

補0

s = 'abc'
s = zfill(6)
# s = '000abc'

frozenset()

將iterable 變成 hashable

694. Number of Distinct Islands

def numDistinctIslands(self, grid: List[List[int]]) -> int:
    self.m, self.n = len(grid), len(grid[0])
    shapes = set()
    for i in range(self.m):
        for j in range(self.n):
            if grid[i][j] == 1:
                shape = set()
                self.helper(grid, shape, i, j, i, j)
                shape = frozenset(shape)
                if shape not in shapes:
                    shapes.add(shape)
    return len(shapes)


def helper(self, grid, shape, i, j, i0, j0):
    grid[i][j] = 0
    shape.add((i-i0, j-j0))
    for dy, dx in ((0, 1),(1, 0), (0, -1), (-1, 0)):
        y = i + dy
        x = j + dx
        if not (0 <= y < self.m and 0 <= x < self.n and grid[y][x] == 1): continue
        self.helper(grid, shape, y, x, i0, j0)