[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で再び島に戻ります
経由地を-1に変更
正方形なのでa = 4から
周囲に1があるところが接続されているので、a - 1に電話して、回ってから帰ります.
四方八方に-1があるので、つながっているところです.
みんなでもう一度やってみると~

143. Reorder List

You are given the head of a singly linked-list. The list can be represented as:a - 1Reorder the list to be on the following form:L0 → L1 → … → Ln - 1 → LnYou 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

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …:最後のノードを指す前のノード
最後のノードはlastです
なくてもいいです.last.nextとheadの間に挿入head.nextは既に着席しているので、last.nextでNone前に2つのグリッド
個数を再計算するのは難しい...

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

中間値の検索
=>headそれぞれ1マス、slowそれぞれ2マス
=>最終fastが中間値

右半分を逆さにする
=>slow、prevおよびcurr=>nexttは反右半

prevとheadの合併

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 iterativelyprevを使用してノードを個別に表示します.stackで隣人に加わる...?