[Mock] Facebook 6

463. Island Perimeter

You are given row x col grid representing a map where grid[i][j] = 1 represents land and grid[i][j] = 0 represents water.

Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).

The island doesn't have "lakes", meaning the water inside isn't connected to the water around the island. One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.

My Answer 1: Accepted (Runtime: 628 ms - 37.97% / Memory Usage: 17.9 MB - 14.51%)

class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        def func(grid, i, j):
            if i < 0 or i > len(grid)-1 or j < 0 or j > len(grid[0])-1:
                return
            
            grid[i][j] = -1
            
            a = 4
            if i > 0 and grid[i-1][j] == 1:
                a -= 1
                func(grid, i-1, j)
            elif i > 0 and grid[i-1][j] == -1:
                a -= 1
                
            if i < len(grid)-1 and grid[i+1][j] == 1:
                a -= 1
                func(grid, i+1, j)
            elif i < len(grid)-1 and grid[i+1][j] == -1:
                a -= 1
                
            if j > 0 and grid[i][j-1] == 1:
                a -= 1
                func(grid, i, j-1)
            elif j > 0 and grid[i][j-1] == -1:
                a -= 1
                
            if j < len(grid[0])-1 and grid[i][j+1] == 1:
                a -= 1
                func(grid, i, j+1)
            elif j < len(grid[0])-1 and grid[i][j+1] == -1:
                a -= 1
            
            self.ans += a
        
        self.ans = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    func(grid, i, j)
        
        return self.ans

1 인 값부터 재귀로 island 찾아줌

지나간 곳은 -1 로 바꿔주기

사각형이니까 a = 4 로 시작해서
사방 중에 1 이 있는 곳은 연결되는 곳이니까 a - 1 해주고 재귀로 넘어감
사방 중에 -1 이 있는 곳도 연결되는 곳이니까 a - 1 but 재귀로 넘어가진 X

모두 더해주면 끗~

---

143. Reorder List

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln
Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
You may not modify the values in the list's nodes. Only nodes themselves may be changed.

My Answer 1: Time Limit Exceeded (10 / 12 test cases passed.)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        while head.next:
            last = head
            while last.next and last.next.next:
                last = last.next
            if last == head:
                break
            tmp = head.next
            head.next = last.next
            last.next = None
            head = head.next
            head.next = tmp
            head = head.next

last: 마지막 노드의 바로 전 노드를 가리킴
마지막 노드는 last.next 가 됨
없으면 break

있으면 head 와 head.next 사이에 넣어주기
last.next 는 자리를 찾아갔으니까 None 으로

head 는 두칸 앞으로 가기

개수 다시 계산하기 귀찮읍니다...

Solution 1: Accepted (Runtime: 88 ms - 86.45% / Memory Usage: 23.3 MB - 77.22%)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        #step 1: find middle
        if not head: return []
        slow, fast = head, head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        
        #step 2: reverse second half
        prev, curr = None, slow.next
        while curr:
            nextt = curr.next
            curr.next = prev
            prev = curr
            curr = nextt    
        slow.next = None
        
        #step 3: merge lists
        head1, head2 = head, prev
        while head2:
            nextt = head1.next
            head1.next = head2
            head1 = head2
            head2 = nextt

1. 중간 값 찾아주기
   => slow 는 1 칸씩 가고 fast 는 2 칸씩 감
   => 최종적으로 slow 가 middle 값

2. 오른쪽 절반을 reverse
   => prev, curr, nextt 세개로 reverse
   => prev 는 reverse 된 오른쪽 절반이 됨

3. head 와 prev 합치기

---

133. Clone Graph

Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.

class Node {
    public int val;
    public List<Node> neighbors;
}

Solution 1: Accepted (Runtime: 40 ms - 55.53% / Memory Usage: 14.7 MB - 55.68%)

"""
# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
"""

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return node
        m = {node: Node(node.val)}
        stack = [node]
        while stack:
            n = stack.pop()
            for neigh in n.neighbors:
                if neigh not in m:
                    stack.append(neigh)
                    m[neigh] = Node(neigh.val)
                m[n].neighbors.append(m[neigh])
        return m[node]

DFS iteratively

stack 을 이용해서 노드를 하나씩 보면서
m[n].neighbors 에 이웃들 넣어주기...?