Appearance
question:You are given a matrix of integers `grid` of size `m x n`, representing a field of pumpkins. Each cell can contain a non-negative integer, representing the number of pumpkins in that part of the field. You start at the top-left cell (0, 0) of the field and want to travel to the bottom-right cell (m-1, n-1). From any cell `(i, j)`, you can only move to either the cell to the right `(i, j+1)` or the cell below `(i+1, j)`. Your goal is to collect the maximum number of pumpkins possible on your way to the bottom-right cell. Write a function that returns the maximum number of pumpkins you can collect. Example: ``` Input: grid = [ [1, 3, 1], [1, 5, 1], [4, 2, 1] ] Output: 12 Explanation: The path with the maximum number of pumpkins is 1 → 3 → 5 → 2 → 1, which gives a total of 12 pumpkins. ```
answer:def max_pumpkins(grid): Returns the maximum number of pumpkins that can be collected from the top-left to the bottom-right of the field. if not grid or not grid[0]: return 0 m, n = len(grid), len(grid[0]) dp = [[0] * n for _ in range(m)] dp[0][0] = grid[0][0] # Initialize the first row for j in range(1, n): dp[0][j] = dp[0][j-1] + grid[0][j] # Initialize the first column for i in range(1, m): dp[i][0] = dp[i-1][0] + grid[i][0] # Fill the rest of the dp matrix for i in range(1, m): for j in range(1, n): dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j] return dp[m-1][n-1]
question:Given an array of integers `arr` and an integer `d`, you need to determine if it is possible to select two integers from the array such that their absolute difference is exactly `d`. Return _true_ if there exist such a pair, otherwise return _false_.
answer:def has_pair_with_difference(arr, d): Determines if there are two integers in the array whose absolute difference is exactly d. :param arr: List of integers :param d: Integer difference to check for :return: True if such a pair exists, False otherwise num_set = set(arr) for num in arr: if (num + d) in num_set or (num - d) in num_set: return True return False
question:You are given a string `s` which consists of lowercase English letters and an integer `k`. You need to split the string into `k` non-empty contiguous substrings such that the **lexicographic order** of these substrings, when sorted, is the same as the order they appear in `s`. Your task is to determine if it is possible to split the string `s` into exactly `k` parts satisfying the condition. If it is possible, return _a list of the `k` substrings_; otherwise, return an **empty list**.
answer:def split_string(s, k): Determines if it's possible to split the string s into exactly k parts such that their lexicographic order is the same as their appearance in s. If possible, returns a list of the k substrings. Otherwise, returns an empty list. n = len(s) # If k is greater than the number of characters in the string, it's not possible if k > n: return [] # Initialize a list to store the substrings substrings = [] # Start cutting the string start = 0 for i in range(1, k): substrings.append(s[start:i]) start = i substrings.append(s[start:]) return substrings
question:Given a string `s`, you need to split it into as many parts as possible such that each part is a palindrome. Return _the minimum number of cuts needed to achieve this_. A palindrome is defined as a string that reads the same backward as forward. Each substring must be a contiguous block of characters from the original string.
answer:def min_palindrome_cuts(s): Returns the minimum number of cuts needed to partition the string s such that every part is a palindrome. n = len(s) if n <= 1: return 0 # Create a table to check if s[i:j+1] is a palindrome palindrome = [[False] * n for _ in range(n)] for i in range(n): palindrome[i][i] = True # Every single character is a palindrome for i in range(n-1): if s[i] == s[i+1]: palindrome[i][i+1] = True # Two consecutive same characters are a palindrome for length in range(3, n+1): for i in range(n-length+1): j = i + length - 1 palindrome[i][j] = (s[i] == s[j]) and palindrome[i+1][j-1] # Array to store the minimum cuts needed for a palindrome partition cuts = [0] * n for i in range(n): if palindrome[0][i]: cuts[i] = 0 else: min_cuts = float('inf') for j in range(1, i+1): if palindrome[j][i]: min_cuts = min(min_cuts, cuts[j-1] + 1) cuts[i] = min_cuts return cuts[-1]