leetcode 271(구현), 696(구현), 138(구현, 링크드 리스트), 133(구현)

271 https://leetcode.com/problems/encode-and-decode-strings/

인코딩, 디코딩 함수를 구현하는 문제이다. 근데 그냥 인코딩후 디코딩이 제대로 되기만 하면 되니까 아주 간편하다.

원래는 base64같은거로 인코딩하고, 디코딩했을것같은데 여기서는 간편하게 절대 안나타날것같은 구분자인 ' <|> '로 나누고 합쳐주는거로 했다..

class Codec:
    def encode(self, strs):
        if strs == []:
            return None
        return ' <|> '.join(strs)

    def decode(self, s):
        if s is None:
            return []
        return s.split(' <|> ')

696 https://leetcode.com/problems/count-binary-substrings/

000111의 경우 01, 0011, 000111 이렇게 3개가 나온다. 001111의 경우에는 01, 0011 2개가 나온다. 숫자가 달라지면 앞 뒤중 작은 숫자의 갯수대로 부분문자열의 갯수가 나온다는 소리이다. 

class Solution(object):
    def countBinarySubstrings(self, s):
        c_list = []
        count = 1
        for i in xrange(len(s)-1):
            if s[i] == s[i+1]:
                count += 1
            else:
                c_list.append(count)
                count = 1
        c_list.append(count)
        s = [min(c_list[i], c_list[i+1]) for i in xrange(len(c_list)-1)]
        return sum(s)

근데 discussion을 보니 멋있게 푼게 있어서 공유함.

1. 정규식 사용 https://leetcode.com/problems/count-binary-substrings/discuss/108604/1-liners

정규식으로 나눈다. 신박하다.

def countBinarySubstrings(self, s):
    lengths = map(len, re.findall('0+|1+', s))
    return sum(map(min, lengths[:-1], lengths[1:]))

2. 어차피 문자열이 바뀌는 지점이 주목해야할 포인트이므로 그 부분을 스페이스바로 한칸씩 띄워주고 계산한다.

https://leetcode.com/problems/count-binary-substrings/discuss/108625/PythonC%2B%2BJava-Easy-and-Concise-with-Explanation

def countBinarySubstrings(self, s):
    s = map(len, s.replace('01', '0 1').replace('10', '1 0').split())
    return sum(min(a, b) for a, b in zip(s, s[1:]))

개똑똑한듯

138 https://leetcode.com/problems/copy-list-with-random-pointer/

좋아요가 많은데 이게 왜 좋은 문제인지 모르겠다. random_pointer는 도대체 왜 있는거고 그냥 링크드 리스트 복사하는거랑 뭐가 다른지 모르겠다.

class Solution(object):
    def copyRandomList(self, head):
        if head is None: 
            return None
        
        node_dict = {}
        cur = head
        while cur:
            node_dict[cur] = Node(cur.val, cur.next, cur.random)
            cur = cur.next
            
        cur = head
        while cur:
            if cur.next:
                node_dict[cur].next = node_dict[cur.next]
            if cur.random:
                node_dict[cur].random = node_dict[cur.random]
            cur = cur.next
        return node_dict[head]

133 https://leetcode.com/problems/clone-graph/

위 문제랑 똑같다. bfs로 탐색해준다.

class Solution(object):
    def cloneGraph(self, node):
        if node is None:
            return None
        
        graph_dict = {}
        queue = [node]
        visited = set([node])
        while queue:
            cur = queue.pop(0)
            graph_dict[cur] = Node(cur.val, cur.neighbors)
            neighbors = cur.neighbors
            if neighbors:
                for n in neighbors:
                    if n not in visited:
                        queue.append(n)
                        visited.add(n)
        
        queue = [node]
        visited = set([node])
        while queue:
            cur = queue.pop(0)
            neighbors = cur.neighbors
            graph_dict[cur].neighbors = map(lambda x: graph_dict[x], cur.neighbors)
            if neighbors:
                for n in neighbors:
                    if n not in visited:
                        queue.append(n)
                        visited.add(n)
                        
        return graph_dict[node]