Appearance
question:Given a list of `n` words, return a Boolean value indicating whether it is possible to rearrange these words such that each word is positioned next to another word that starts with the last letter of the previous word. Note that each word can only be used once and all words must be used in the rearrangement.
answer:def can_rearrange_words(words): Determines whether it is possible to rearrange words such that each word is followed by a word starting with the last letter of the previous word. Args: words (list): A list of words (strings). Returns: bool: True if such an arrangement is possible, False otherwise. from collections import defaultdict, Counter # Create a graph where each word points to words that start with their last letter graph = defaultdict(list) in_degree = Counter() out_degree = Counter() for word in words: graph[word[-1]].append(word) in_degree[word[0]] += 1 out_degree[word[-1]] += 1 # Check Eulerian path condition for directed graph start_nodes, end_nodes = 0, 0 for letter in set(in_degree.keys()).union(out_degree.keys()): if abs(in_degree[letter] - out_degree[letter]) > 1: return False elif in_degree[letter] > out_degree[letter]: start_nodes += 1 elif out_degree[letter] > in_degree[letter]: end_nodes += 1 # Eulerian path condition: at most one start node and one end node return start_nodes <= 1 and end_nodes <= 1
question:Given an integer array `arr` and an integer `k`, write a function to find the number of subarrays that have a sum equal to `k`. A subarray is a contiguous, non-empty sequence of elements within an array. Your function should return the count of such subarrays.
answer:def subarray_sum(arr, k): Returns the number of subarrays whose sum is equal to k. :param arr: List[int] - List of integers :param k: int - Target sum for the subarrays :return: int - Number of subarrays whose sum equals k count = 0 current_sum = 0 prefix_sums = {0: 1} for num in arr: current_sum += num if (current_sum - k) in prefix_sums: count += prefix_sums[current_sum - k] if current_sum in prefix_sums: prefix_sums[current_sum] += 1 else: prefix_sums[current_sum] = 1 return count
question:You are given two strings, `version1` and `version2`, which represent version numbers of software components. A version number is a string that contains one or more numbers separated by dots (e.g., `1.0`, `2.1.3`). Each number can have any number of digits, and may contain leading zeros. Write a function that compares two version numbers version1 and version2. * If `version1` > `version2`, return `1`. * If `version1` < `version2`, return `-1`. * Otherwise, return `0`. Compare version numbers by comparing their components numerically from left to right. Different lengths of version strings are addressed by considering missing components as zeros (e.g., `2.0` is equal to `2.0.0`).
answer:def compare_version(version1: str, version2: str) -> int: Compares two version numbers. Args: version1 (str): The first version number. version2 (str): The second version number. Returns: int: 1 if version1 > version2, -1 if version1 < version2, 0 if they are equal. v1_parts = [int(part) for part in version1.split('.')] v2_parts = [int(part) for part in version2.split('.')] # Equalize the lengths of both version parts max_length = max(len(v1_parts), len(v2_parts)) v1_parts.extend([0] * (max_length - len(v1_parts))) v2_parts.extend([0] * (max_length - len(v2_parts))) for v1, v2 in zip(v1_parts, v2_parts): if v1 > v2: return 1 elif v1 < v2: return -1 return 0
question:Given an integer array `nums` and an integer `k`, return the maximum sum of a non-empty subarray that contains at most `k` distinct integers. If there are multiple subarrays that have the same maximum sum, return the one that appears first in the array. Use a sliding window approach to solve this problem efficiently.
answer:def maxSumSubarrayWithKDistinct(nums, k): Returns the maximum sum of a non-empty subarray that contains at most k distinct integers. If there are multiple subarrays with the same sum, return the one that appears first. from collections import defaultdict n = len(nums) left = 0 max_sum = float('-inf') current_sum = 0 counts = defaultdict(int) max_subarray = [] for right in range(n): counts[nums[right]] += 1 current_sum += nums[right] while len(counts) > k: counts[nums[left]] -= 1 if counts[nums[left]] == 0: del counts[nums[left]] current_sum -= nums[left] left += 1 if current_sum > max_sum: max_sum = current_sum max_subarray = nums[left:right+1] return max_subarray