算法与数据结构面试题 - 50道高频LeetCode精选¶

def twoSum(nums: list[int], target: int) -> list[int]:
    # 哈希表：值 -> 下标
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

def threeSum(nums: list[int]) -> list[list[int]]:
    nums.sort()
    result = []
    n = len(nums)

    for i in range(n - 2):
        # 跳过重复的第一个数
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        # 剪枝：最小值已大于0，后面不可能有解
        if nums[i] > 0:
            break

        left, right = i + 1, n - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total == 0:
                result.append([nums[i], nums[left], nums[right]])
                # 跳过重复值
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1
            elif total < 0:
                left += 1
            else:
                right -= 1

    return result

def lengthOfLongestSubstring(s: str) -> int:
    # 字符 -> 最近出现的下标
    char_index = {}
    max_len = 0
    left = 0

    for right, char in enumerate(s):
        # 如果字符已在窗口内，移动左边界
        if char in char_index and char_index[char] >= left:
            left = char_index[char] + 1
        char_index[char] = right
        max_len = max(max_len, right - left + 1)

    return max_len

from collections import deque

def maxSlidingWindow(nums: list[int], k: int) -> list[int]:
    dq = deque()  # 存储下标，对应值单调递减
    result = []

    for i, num in enumerate(nums):
        # 移除超出窗口范围的队首元素
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        # 维护单调递减：移除队尾所有比当前值小的元素
        while dq and nums[dq[-1]] < num:
            dq.pop()
        dq.append(i)
        # 窗口形成后，记录最大值
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

def merge(intervals: list[list[int]]) -> list[list[int]]:
    # 按起始位置排序
    intervals.sort(key=lambda x: x[0])  # lambda匿名函数：简洁的单行函数
    merged = []

    for interval in intervals:
        # 如果结果为空，或当前区间与最后一个不重叠
        if not merged or merged[-1][1] < interval[0]:  # 负索引：从末尾倒数访问元素
            merged.append(interval)
        else:
            # 合并：更新右端点
            merged[-1][1] = max(merged[-1][1], interval[1])

    return merged

def trap(height: list[int]) -> int:
    if not height:
        return 0

    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    water = 0

    while left < right:
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                water += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                water += right_max - height[right]
            right -= 1

    return water

def longestPalindrome(s: str) -> str:
    if len(s) < 2:
        return s

    start, max_len = 0, 1

    def expand_around_center(left: int, right: int):
        """从中心向两边扩展，返回回文长度"""
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return right - left - 1

    for i in range(len(s)):
        # 奇数长度回文
        len1 = expand_around_center(i, i)
        # 偶数长度回文
        len2 = expand_around_center(i, i + 1)
        cur_len = max(len1, len2)
        if cur_len > max_len:
            max_len = cur_len
            start = i - (cur_len - 1) // 2

    return s[start:start + max_len]

def spiralOrder(matrix: list[list[int]]) -> list[int]:
    if not matrix:
        return []

    result = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1

    while top <= bottom and left <= right:
        # 向右遍历
        for col in range(left, right + 1):
            result.append(matrix[top][col])
        top += 1

        # 向下遍历
        for row in range(top, bottom + 1):
            result.append(matrix[row][right])
        right -= 1

        # 向左遍历（需检查边界）
        if top <= bottom:
            for col in range(right, left - 1, -1):
                result.append(matrix[bottom][col])
            bottom -= 1

        # 向上遍历（需检查边界）
        if left <= right:
            for row in range(bottom, top - 1, -1):
                result.append(matrix[row][left])
            left += 1

    return result

def rotate(matrix: list[list[int]]) -> None:
    n = len(matrix)

    # 第一步：转置矩阵（沿主对角线翻转）
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

    # 第二步：水平翻转每一行
    for i in range(n):
        matrix[i].reverse()

def firstMissingPositive(nums: list[int]) -> int:
    n = len(nums)

    # 将每个数放到正确的位置：nums[i] = i + 1
    for i in range(n):
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            # 交换 nums[i] 到正确位置
            correct_idx = nums[i] - 1
            nums[i], nums[correct_idx] = nums[correct_idx], nums[i]

    # 找第一个不在正确位置的数
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1

    return n + 1

from collections import Counter

def minWindow(s: str, t: str) -> str:
    if not s or not t:
        return ""

    need = Counter(t)        # 需要的字符计数
    missing = len(t)         # 还缺少的字符数
    left = 0
    start, min_len = 0, float('inf')

    for right, char in enumerate(s):
        # 扩展窗口
        if need[char] > 0:
            missing -= 1
        need[char] -= 1

        # 收缩窗口
        while missing == 0:
            window_len = right - left + 1
            if window_len < min_len:
                min_len = window_len
                start = left

            need[s[left]] += 1
            if need[s[left]] > 0:
                missing += 1
            left += 1

    return s[start:start + min_len] if min_len != float('inf') else ""

def myAtoi(s: str) -> int:
    INT_MAX, INT_MIN = 2**31 - 1, -(2**31)

    s = s.lstrip()  # 去前导空格
    if not s:
        return 0

    sign = 1
    idx = 0

    # 处理正负号
    if s[0] in ('+', '-'):
        sign = -1 if s[0] == '-' else 1
        idx = 1

    result = 0
    while idx < len(s) and s[idx].isdigit():
        digit = int(s[idx])
        # 溢出检查
        if result > (INT_MAX - digit) // 10:
            return INT_MAX if sign == 1 else INT_MIN
        result = result * 10 + digit
        idx += 1

    return sign * result

def longestCommonPrefix(strs: list[str]) -> str:
    if not strs:
        return ""

    # 纵向扫描
    for i in range(len(strs[0])):
        char = strs[0][i]
        for s in strs[1:]:
            if i >= len(s) or s[i] != char:
                return strs[0][:i]

    return strs[0]

def moveZeroes(nums: list[int]) -> None:
    slow = 0
    for fast in range(len(nums)):
        if nums[fast] != 0:
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow += 1

def nextPermutation(nums: list[int]) -> None:
    n = len(nums)

    # 第一步：从右往左找第一个递减位置
    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1

    if i >= 0:
        # 第二步：从右往左找第一个大于 nums[i] 的数
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1
        # 第三步：交换
        nums[i], nums[j] = nums[j], nums[i]

    # 第四步：翻转 i+1 之后的部分
    left, right = i + 1, n - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseList(head: ListNode) -> ListNode:
    # 迭代法
    prev, curr = None, head
    while curr:
        next_node = curr.next   # 暂存下一个节点
        curr.next = prev        # 翻转指向
        prev = curr             # prev 前进
        curr = next_node        # curr 前进
    return prev

def reverseListRecursive(head: ListNode) -> ListNode:
    # 递归法
    if not head or not head.next:
        return head
    new_head = reverseListRecursive(head.next)
    head.next.next = head    # 后继节点指回自己
    head.next = None         # 断开原来的指向
    return new_head

import heapq

def mergeKLists(lists: list[ListNode]) -> ListNode:
    # 最小堆方法
    dummy = ListNode(0)
    curr = dummy
    heap = []

    # 初始化：每个链表的头节点入堆
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))

    while heap:
        val, idx, node = heapq.heappop(heap)
        curr.next = node
        curr = curr.next
        if node.next:
            heapq.heappush(heap, (node.next.val, idx, node.next))

    return dummy.next

def detectCycle(head: ListNode) -> ListNode:
    slow = fast = head

    # 第一步：快慢指针判断是否有环
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            # 第二步：找入口
            slow = head
            while slow != fast:
                slow = slow.next
                fast = fast.next
            return slow

    return None

class DLinkedNode:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.cache = {}           # key -> DLinkedNode
        self.capacity = capacity
        self.size = 0
        # 伪头部和伪尾部
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._move_to_head(node)  # 标记为最近使用
        return node.value

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self._move_to_head(node)
        else:
            node = DLinkedNode(key, value)
            self.cache[key] = node
            self._add_to_head(node)
            self.size += 1
            if self.size > self.capacity:
                # 移除最久未使用的节点
                removed = self._remove_tail()
                del self.cache[removed.key]
                self.size -= 1

    def _add_to_head(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def _remove_node(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _move_to_head(self, node):
        self._remove_node(node)
        self._add_to_head(node)

    def _remove_tail(self):
        node = self.tail.prev
        self._remove_node(node)
        return node

def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode(0)
    curr = dummy
    carry = 0

    while l1 or l2 or carry:
        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0
        total = val1 + val2 + carry
        carry = total // 10
        curr.next = ListNode(total % 10)
        curr = curr.next
        l1 = l1.next if l1 else None
        l2 = l2.next if l2 else None

    return dummy.next

def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
    dummy = ListNode(0, head)
    fast = slow = dummy

    # 快指针先走 n+1 步
    for _ in range(n + 1):
        fast = fast.next

    # 同时移动
    while fast:
        fast = fast.next
        slow = slow.next

    # 删除目标节点
    slow.next = slow.next.next
    return dummy.next

def sortList(head: ListNode) -> ListNode:
    # 递归归并排序（简洁版，空间 O(log n)）
    if not head or not head.next:
        return head

    # 快慢指针找中点
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    mid = slow.next
    slow.next = None  # 断开

    # 递归排序两半
    left = sortList(head)
    right = sortList(mid)

    # 合并
    dummy = ListNode(0)
    curr = dummy
    while left and right:
        if left.val <= right.val:
            curr.next = left
            left = left.next
        else:
            curr.next = right
            right = right.next
        curr = curr.next
    curr.next = left or right

    return dummy.next

def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode:
    pA, pB = headA, headB
    while pA != pB:
        pA = pA.next if pA else headB
        pB = pB.next if pB else headA
    return pA

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def levelOrder(root: TreeNode) -> list[list[int]]:
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)
        level = []
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)

    return result

def isValidBST(root: TreeNode) -> bool:
    def validate(node, min_val, max_val):
        if not node:
            return True
        if node.val <= min_val or node.val >= max_val:
            return False
        return (validate(node.left, min_val, node.val) and
                validate(node.right, node.val, max_val))

    return validate(root, float('-inf'), float('inf'))

def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    if not root or root == p or root == q:
        return root

    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)

    if left and right:
        return root      # p 和 q 分别在左右子树
    return left or right  # 都在同一侧

class Codec:
    def serialize(self, root: TreeNode) -> str:
        """前序遍历序列化"""
        result = []

        def dfs(node):
            if not node:
                result.append("#")
                return
            result.append(str(node.val))
            dfs(node.left)
            dfs(node.right)

        dfs(root)
        return ",".join(result)

    def deserialize(self, data: str) -> TreeNode:
        """反序列化"""
        values = iter(data.split(","))

        def dfs():
            val = next(values)
            if val == "#":
                return None
            node = TreeNode(int(val))
            node.left = dfs()
            node.right = dfs()
            return node

        return dfs()

def maxPathSum(root: TreeNode) -> int:
    max_sum = float('-inf')

    def max_gain(node):
        nonlocal max_sum
        if not node:
            return 0

        # 左右子树的最大贡献值（负数贡献不要）
        left_gain = max(max_gain(node.left), 0)
        right_gain = max(max_gain(node.right), 0)

        # 经过当前节点的最大路径和
        price_new_path = node.val + left_gain + right_gain
        max_sum = max(max_sum, price_new_path)

        # 返回单侧最大贡献值
        return node.val + max(left_gain, right_gain)

    max_gain(root)
    return max_sum

def buildTree(preorder: list[int], inorder: list[int]) -> TreeNode:
    # 中序值 -> 下标映射，加速查找
    inorder_map = {val: idx for idx, val in enumerate(inorder)}  # enumerate同时获取索引和值
    pre_idx = 0

    def helper(in_left, in_right):
        nonlocal pre_idx
        if in_left > in_right:
            return None

        root_val = preorder[pre_idx]
        root = TreeNode(root_val)
        pre_idx += 1

        # 在中序中找到根的位置
        in_root = inorder_map[root_val]

        # 先构建左子树，再构建右子树（与前序遍历顺序一致）
        root.left = helper(in_left, in_root - 1)
        root.right = helper(in_root + 1, in_right)

        return root

    return helper(0, len(inorder) - 1)

def diameterOfBinaryTree(root: TreeNode) -> int:
    diameter = 0

    def depth(node):
        nonlocal diameter
        if not node:
            return 0
        left = depth(node.left)
        right = depth(node.right)
        diameter = max(diameter, left + right)
        return 1 + max(left, right)

    depth(root)
    return diameter

def invertTree(root: TreeNode) -> TreeNode:
    if not root:
        return None
    root.left, root.right = root.right, root.left
    invertTree(root.left)
    invertTree(root.right)
    return root

def rightSideView(root: TreeNode) -> list[int]:
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)
        for i in range(level_size):
            node = queue.popleft()
            if i == level_size - 1:  # 每层最后一个节点
                result.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    return result

def countNodes(root: TreeNode) -> int:
    if not root:
        return 0

    left_height = right_height = 0
    left_node, right_node = root, root

    while left_node:
        left_height += 1
        left_node = left_node.left
    while right_node:
        right_height += 1
        right_node = right_node.right

    # 如果高度相同，是满二叉树
    if left_height == right_height:
        return 2**left_height - 1

    return 1 + countNodes(root.left) + countNodes(root.right)

def knapsack(weights: list[int], values: list[int], capacity: int) -> int:
    n = len(weights)
    # 空间优化：一维 DP
    dp = [0] * (capacity + 1)

    for i in range(n):
        # 倒序遍历容量，避免重复使用同一物品
        for j in range(capacity, weights[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])

    return dp[capacity]

import bisect

def lengthOfLIS(nums: list[int]) -> int:
    # 贪心 + 二分查找 O(n log n)
    tails = []  # tails[i] = 长度为 i+1 的 LIS 的最小末尾元素

    for num in nums:
        pos = bisect.bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)  # 扩展 LIS
        else:
            tails[pos] = num   # 替换，使末尾更小

    return len(tails)

def minDistance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    # dp[i][j]: word1[:i] -> word2[:j] 的最少操作
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # 基础情况
    for i in range(m + 1):
        dp[i][0] = i  # 全删除
    for j in range(n + 1):
        dp[0][j] = j  # 全插入

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]  # 字符相同，无需操作
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],      # 删除
                    dp[i][j - 1],      # 插入
                    dp[i - 1][j - 1]   # 替换
                )

    return dp[m][n]

# 买卖一次
def maxProfit_once(prices: list[int]) -> int:
    min_price = float('inf')
    max_profit = 0
    for price in prices:
        min_price = min(min_price, price)
        max_profit = max(max_profit, price - min_price)
    return max_profit

# 无限次买卖
def maxProfit_unlimited(prices: list[int]) -> int:
    return sum(max(0, prices[i] - prices[i - 1]) for i in range(1, len(prices)))

# 最多 k 次买卖
def maxProfit_k(k: int, prices: list[int]) -> int:
    n = len(prices)
    if n < 2:
        return 0

    # 如果 k >= n/2，等同于无限次
    if k >= n // 2:
        return sum(max(0, prices[i] - prices[i - 1]) for i in range(1, n))

    # dp[j][0/1]: 完成 j 次交易，不持有/持有 的最大利润
    dp = [[0, float('-inf')] for _ in range(k + 1)]

    for price in prices:
        for j in range(1, k + 1):
            dp[j][0] = max(dp[j][0], dp[j][1] + price)     # 卖出
            dp[j][1] = max(dp[j][1], dp[j - 1][0] - price) # 买入

    return dp[k][0]

def coinChange(coins: list[int], amount: int) -> int:
    # dp[i] 表示凑成金额 i 的最少硬币数
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

def longestCommonSubsequence(text1: str, text2: str) -> int:
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]

def isMatch(s: str, p: str) -> bool:
    m, n = len(s), len(p)
    # dp[i][j]: s[:i] 是否匹配 p[:j]
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True

    # 初始化：空字符串匹配 a*b*c* 形式
    for j in range(2, n + 1):
        if p[j - 1] == '*':
            dp[0][j] = dp[0][j - 2]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j - 1] == '*':
                # * 匹配零次 or 匹配一次以上
                dp[i][j] = dp[i][j - 2]  # 匹配零次
                if p[j - 2] == '.' or p[j - 2] == s[i - 1]:
                    dp[i][j] = dp[i][j] or dp[i - 1][j]  # 匹配一次以上
            elif p[j - 1] == '.' or p[j - 1] == s[i - 1]:
                dp[i][j] = dp[i - 1][j - 1]

    return dp[m][n]

def rob(nums: list[int]) -> int:
    if not nums:
        return 0
    if len(nums) <= 2:
        return max(nums)

    # 空间优化：只需前两个状态
    prev2, prev1 = nums[0], max(nums[0], nums[1])
    for i in range(2, len(nums)):
        curr = max(prev1, prev2 + nums[i])
        prev2, prev1 = prev1, curr

    return prev1

# 打家劫舍 II（环形）
def rob_circular(nums: list[int]) -> int:
    if len(nums) == 1:
        return nums[0]
    # 分两种情况：不偷第一间 or 不偷最后一间
    return max(rob(nums[1:]), rob(nums[:-1]))

def uniquePaths(m: int, n: int) -> int:
    # 空间优化：一维 DP
    dp = [1] * n
    for i in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j - 1]
    return dp[n - 1]

# 数学方法：组合数 C(m+n-2, m-1)
from math import comb
def uniquePaths_math(m: int, n: int) -> int:
    return comb(m + n - 2, m - 1)

def maxSubArray(nums: list[int]) -> int:
    max_sum = nums[0]
    current_sum = nums[0]

    for i in range(1, len(nums)):
        # 要么延续之前的子数组，要么从当前元素重新开始
        current_sum = max(nums[i], current_sum + nums[i])
        max_sum = max(max_sum, current_sum)

    return max_sum

import heapq
from collections import Counter  # Counter计数器：统计元素出现次数

def topKFrequent(nums: list[int], k: int) -> list[int]:
    count = Counter(nums)
    # 最小堆，堆大小为 k
    return heapq.nlargest(k, count.keys(), key=count.get)

# 桶排序方法 O(n)
def topKFrequent_bucket(nums: list[int], k: int) -> list[int]:
    count = Counter(nums)
    n = len(nums)

    # 频率桶：bucket[i] 存储出现 i 次的元素
    bucket = [[] for _ in range(n + 1)]
    for num, freq in count.items():
        bucket[freq].append(num)

    result = []
    for freq in range(n, 0, -1):
        for num in bucket[freq]:
            result.append(num)
            if len(result) == k:
                return result
    return result

import heapq

class MedianFinder:
    def __init__(self):
        self.small = []  # 最大堆（取反实现）
        self.large = []  # 最小堆

    def addNum(self, num: int) -> None:
        # 先加入最大堆
        heapq.heappush(self.small, -num)
        # 确保最大堆的最大值 ≤ 最小堆的最小值
        heapq.heappush(self.large, -heapq.heappop(self.small))
        # 平衡大小：最大堆可以多一个
        if len(self.large) > len(self.small):
            heapq.heappush(self.small, -heapq.heappop(self.large))

    def findMedian(self) -> float:
        if len(self.small) > len(self.large):
            return -self.small[0]
        return (-self.small[0] + self.large[0]) / 2

def numIslands(grid: list[list[str]]) -> int:
    if not grid:
        return 0

    m, n = len(grid), len(grid[0])
    count = 0

    def dfs(i, j):
        if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != '1':
            return
        grid[i][j] = '0'  # 标记已访问
        dfs(i + 1, j)
        dfs(i - 1, j)
        dfs(i, j + 1)
        dfs(i, j - 1)

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

    return count