23.03.02 Today’s Leetcode

160. Intersection of Two Linked Lists (easy)

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        d = set()
        cur = headA
        while cur:
            d.add(cur)
            cur = cur.next

        cur = headB
        while cur:
            if cur in d:
                return cur
            cur = cur.next
        return None

172. Factorial Trailing Zeroes (medium)

class Solution:
    def trailingZeroes(self, n: int) -> int:
        def count(base):
            cur = base
            num = 0
            while cur <= n:
                num += n // cur
                cur *= base
            return num

        count_2, count_5 = count(2), count(5)
        return min(count_2, count_5)

173. Binary Search Tree Iterator (medium)

class BSTIterator:

    def __init__(self, root: Optional[TreeNode]):
        self.arr = deque([])
        def dfs(node):
            if not node:
                return
            dfs(node.left)
            self.arr.append(node.val)
            dfs(node.right)
        dfs(root)

    def next(self) -> int:
        return self.arr.popleft()

    def hasNext(self) -> bool:
        return len(self.arr) > 0


# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()

199. Binary Tree Right Side View (medium)

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        q = deque([root])
        res = [root.val]
        while q:
            temp = deque([])
            while q:
                tar = q.popleft()
                if tar.left:
                    temp.append(tar.left)
                if tar.right:
                    temp.append(tar.right)
            
            if temp:
                res.append(temp[-1].val)
                q = temp
        
        return res

200. Number of Islands (medium)

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        def fill(x, y):
            if x < 0 or y < 0 or x >= m or y >= n:
                return
            if grid[x][y] == '0':
                return
            grid[x][y] = '0'
            fill(x + 1, y)
            fill(x - 1, y)
            fill(x, y + 1)
            fill(x, y - 1)

        count = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    count += 1
                    fill(i, j)
        return count

154. Find Minimum in Rotated Sorted Array II (hard)

class Solution {
    public int findMin(int[] nums) {
        return findMinDPS(nums, 0, nums.length - 1);
    }

    public int findMinDPS(int[] nums, int start, int end) {
        if (start == end) return nums[start];
        if (nums[start] < nums[end]) return nums[start];
        int min = (start + end) / 2;
        return Math.min(findMinDPS(nums, start, min), findMinDPS(nums, min + 1, end));
    }
}

240. Search a 2D Matrix II (medium)

class Solution(object):
    def searchMatrix(self, matrix, target):
        m, n = len(matrix), len(matrix[0])
        for i in range(m):
            for j in range(n):
                if matrix[i][0] <= target and target <= matrix[i][-1]:
                    p = bisect_left(matrix[i], target)
                    if matrix[i][p] == target:
                        return True
        return False

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        c = len(matrix[0]) - 1
        r = 0
        while c >= 0 and r < len(matrix):
            if matrix[r][c] == target:
                return True
            elif matrix[r][c] > target:
                c -= 1
            else:
                r +=1
        return False