23.02.27 Today’s Leetcode

427. Construct Quad Tree (medium)

"""
# Definition for a QuadTree node.
class Node:
    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):
        self.val = val
        self.isLeaf = isLeaf
        self.topLeft = topLeft
        self.topRight = topRight
        self.bottomLeft = bottomLeft
        self.bottomRight = bottomRight
"""

class Solution:
    def construct(self, grid: List[List[int]]) -> 'Node':

        def isLeaf(grid, x, y, size):
            target = grid[x][y]
            for i in range(x, x + size):
                for j in range(y, y + size):
                    if grid[i][j] != target:
                        return 0
            return 1
        
        def getVal(grid, x, y, size):
            target = grid[x][y]
            for i in range(x, x + size):
                for j in range(y, y + size):
                    if grid[i][j] == 1:
                        return 1
            return 0

        n = len(grid)
        def dfs(grid, x, y, size):
            p = size // 2
            leaf = isLeaf(grid, x, y, size)
            val = getVal(grid, x, y, size)
            if leaf == 0:
                tl = dfs(grid, x, y, p)
                tr = dfs(grid, x, y + p, p)
                bl = dfs(grid, x + p, y, p)
                br = dfs(grid, x + p, y + p, p)
                node = Node(val, leaf, tl, tr, bl, br)
                return node
            return Node(val, leaf, None, None, None, None)
        
        return dfs(grid, 0, 0, n)

876. Middle of the Linked List (easy)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def node_len(node):
            cur = node
            count = 0
            while cur:
                cur = cur.next
                count += 1
            return count

        t = node_len(head) // 2
        cur = head
        for i in range(t):
            cur = cur.next
        return cur

19. Remove Nth Node From End of List (medium)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        cur = head
        def node_len(node):
            cur = node
            count = 0
            while cur:
                cur = cur.next
                count += 1
            return count
        t = node_len(head) - n - 1
        for i in range(t):
            cur = cur.next
        if t == -1:
            return head.next
        if cur and cur.next:
            cur.next = cur.next.next
        return head

3. Longest Substring Without Repeating Characters (medium)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        d = {}
        n = len(s)
        if n <= 1:
            return n
        start = res = 0
        for i in range(n):
            a = s[i]
            if a in d:
                print(i - start)
                res = max(res, i - start)
                start = max(start, d[a] + 1)
            d[a] = i
        res = max(res, n - start)
        # if start == 0:
        #    res = n
        return res

733. Flood Fill (easy)

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        m, n = len(image), len(image[0])
        def dfs(image, x, y, target, color):
            nonlocal m, n
            if x < 0 or x >= m or y < 0 or y >= n: return
            if image[x][y] != target: return

            image[x][y] = color
            dfs(image, x + 1, y, target, color)
            dfs(image, x - 1, y, target, color)
            dfs(image, x, y + 1, target, color)
            dfs(image, x, y - 1, target, color)

        if image[sr][sc] != color:
            dfs(image, sr, sc, image[sr][sc], color)
        return image

695. Max Area of Island (medium)

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        def dfs(image, x, y):
            nonlocal m, n
            if x < 0 or x >= m or y < 0 or y >= n:
                return 0
            if image[x][y] == 0:
                return 0

            image[x][y] = 0
            res = 1
            res += dfs(image, x + 1, y)
            res += dfs(image, x - 1, y)
            res += dfs(image, x, y + 1)
            res += dfs(image, x, y - 1)
            return res

        ans = 0
        for i in range(m):
            for j in range(n):
                ans = max(ans, dfs(grid, i, j))
        return ans

155. Min Stack (medium)

class MinStack:

    def __init__(self):
        self.stack = []
        self.minStack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        minNum = val
        if self.minStack:
            minNum = min(minNum, self.minStack[-1])
        
        self.minStack.append(minNum)
        

    def pop(self) -> None:
        self.stack.pop()
        self.minStack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.minStack[-1]
        


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

165. Compare Version Numbers (medium)

class Solution:
    def compareVersion(self, version1: str, version2: str) -> int:
        split1, split2 = version1.split('.'), version2.split('.')
        n1, n2 = len(split1), len(split2)
        n3 = max(n1, n2)
        for i in range(n3):
            p1, p2 = 0, 0
            if i < n1:
                p1 = int(split1[i])
            if i < n2:
                p2 = int(split2[i])
            # print(i, p1, p2)
            if p1 > p2:
                return 1
            elif p1 < p2:
                return -1
        return 0