Appearance
question:Given a binary tree, implement a function `rightSideView` that returns the values of the nodes you can see ordered from top to bottom when looking at the tree from the right side. Here's the function signature: ```python def rightSideView(root: Optional[TreeNode]) -> List[int]: # Your code here ``` Where `TreeNode` is defined as: ```python class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right ```
answer:from typing import List, Optional class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def rightSideView(root: Optional[TreeNode]) -> List[int]: if not root: return [] right_view = [] queue = [(root, 0)] while queue: node, depth = queue.pop(0) if len(right_view) == depth: right_view.append(node.val) else: right_view[depth] = node.val if node.left: queue.append((node.left, depth + 1)) if node.right: queue.append((node.right, depth + 1)) return right_view
question:Implement a function that takes a 2D grid representing a map of '1's (land) and '0's (water) and counts the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are surrounded by water.
answer:def num_islands(grid): Given a 2D grid map of '1's (land) and '0's (water), counts the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. if not grid: return 0 nrows, ncols = len(grid), len(grid[0]) visited = [[False for _ in range(ncols)] for _ in range(nrows)] def dfs(row, col): if row < 0 or col < 0 or row >= nrows or col >= ncols or grid[row][col] == '0' or visited[row][col]: return visited[row][col] = True dfs(row + 1, col) dfs(row - 1, col) dfs(row, col + 1) dfs(row, col - 1) count = 0 for i in range(nrows): for j in range(ncols): if grid[i][j] == '1' and not visited[i][j]: count += 1 dfs(i, j) return count
question:A company has a management hierarchy organized as a tree. The tree consists of `n` nodes, where each node represents an employee. Each employee has a unique ID from `0` to `n-1`. You are given a 0-indexed integer array `manager` of length `n`, where `manager[i]` is the direct manager of the `i-th` employee and `manager[0] == -1`, indicating that the employee with ID `0` is the CEO of the company. The `directReports` array is a 2D list where `directReports[i]` is the list of employees who report directly to employee `i`. It is possible to change some managers, but there must still be a valid tree hierarchy. If changing the manager of exactly one employee maximizes the total number of direct reports for that employee, determine the maximum number of direct reports that this employee can have after the change. **Inputs:** - A 0-indexed integer array `manager` of length `n`. - A 2D list `directReports`, where each element is a list of integers representing the direct reports of an employee. **Outputs:** - Return an integer representing the maximum number of direct reports an employee can have after changing the manager of exactly one employee.
answer:def find_max_direct_reports(manager, directReports): Returns the maximum number of direct reports an employee can have after changing the manager of exactly one employee. :param manager: List of integers representing the current manager of each employee. :param directReports: 2D List where each element is a list of direct reports of an employee. :return: Integer representing the maximum number of direct reports any employee can have after one change. n = len(manager) # Calculate the total direct reports for each employee before any change total_direct_reports = [0] * n for i in range(n): total_direct_reports[manager[i]] += 1 max_direct_reports = max(total_direct_reports) for emp in range(1, n): old_manager = manager[emp] # Remove emp from its old_manager's direct reports total_direct_reports[old_manager] -= 1 # Try to reassign emp to every other manager for new_manager in range(n): if new_manager != old_manager: # Add emp to the new_manager's direct reports total_direct_reports[new_manager] += 1 new_max = max(total_direct_reports) max_direct_reports = max(max_direct_reports, new_max) # Restore the counts back to their original state total_direct_reports[new_manager] -= 1 # Restore the original state for the old manager total_direct_reports[old_manager] += 1 return max_direct_reports
question:You are given two strings `s` and `t`, both of which only contain lowercase letters. You need to determine if a substring of `s` can be rearranged to match `t`. Return `true` if it is possible and `false` otherwise. Note that a substring of `s` can be rearranged to match `t` if and only if the frequency of each character in `t` is less than or equal to the frequency of the same character in some substring of `s`.
answer:def can_rearrange_to_match(s, t): Determines if a substring of s can be rearranged to match t. from collections import Counter len_s = len(s) len_t = len(t) if len_t > len_s: return False counter_t = Counter(t) window_counter = Counter(s[:len_t]) if window_counter == counter_t: return True for i in range(len_t, len_s): window_counter[s[i]] += 1 window_counter[s[i - len_t]] -= 1 if window_counter[s[i - len_t]] == 0: del window_counter[s[i - len_t]] if window_counter == counter_t: return True return False