Appearance
question:def climb_stairs(n: int) -> int: Calculate the number of distinct ways to climb a staircase with `n` steps. You can climb either 1 step, 2 steps, or 3 steps at a time. >>> climb_stairs(0) 1 >>> climb_stairs(1) 1 >>> climb_stairs(2) 2 >>> climb_stairs(3) 4 >>> climb_stairs(4) 7 >>> climb_stairs(5) 13 >>> climb_stairs(6) 24
answer:def climb_stairs(n): Returns the number of distinct ways to climb a staircase with n steps, given that you can climb 1, 2, or 3 steps at a time. if n == 0: return 1 elif n == 1: return 1 elif n == 2: return 2 dp = [0] * (n + 1) dp[0] = 1 dp[1] = 1 dp[2] = 2 for i in range(3, n + 1): dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] return dp[n]
question:from typing import List def findLadders(beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]: Write a function `findLadders` that finds all shortest transformation sequences from `beginWord` to `endWord`, given a dictionary `wordList`. Each transformed word must exist in the word list. Note that `beginWord` is not a transformed word. Each transformation must change exactly one letter. Example: >>> findLadders("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]) [["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"]] >>> findLadders("hit", "cog", ["hot", "dot", "dog", "lot", "log"]) [] pass # Unit Tests def test_find_ladders_example1(): beginWord = "hit" endWord = "cog" wordList = ["hot", "dot", "dog", "lot", "log", "cog"] expected = [ ["hit", "hot", "dot", "dog", "cog"], ["hit", "hot", "lot", "log", "cog"] ] result = findLadders(beginWord, endWord, wordList) assert all(path in expected for path in result) and all(path in result for path in expected) def test_find_ladders_no_path(): beginWord = "hit" endWord = "cog" wordList = ["hot", "dot", "dog", "lot", "log"] expected = [] result = findLadders(beginWord, endWord, wordList) assert result == expected def test_find_ladders_single_transform(): beginWord = "hit" endWord = "hot" wordList = ["hot"] expected = [["hit", "hot"]] result = findLadders(beginWord, endWord, wordList) assert result == expected def test_find_ladders_direct_path(): beginWord = "hot" endWord = "cog" wordList = ["hot", "dot", "dog", "cog"] expected = [["hot", "dot", "dog", "cog"]] result = findLadders(beginWord, endWord, wordList) assert result == expected
answer:from collections import defaultdict, deque def findLadders(beginWord, endWord, wordList): if endWord not in wordList: return [] wordList = set(wordList) wordList.add(beginWord) # Create a map to store the graph neighbors = defaultdict(list) # Build the adjacency list def buildGraph(): for word in wordList: for i in range(len(word)): pattern = word[:i] + '*' + word[i+1:] neighbors[pattern].append(word) buildGraph() # BFS to find the shortest paths def bfs(): queue = deque([[beginWord]]) visited = set([beginWord]) found = False while queue and not found: local_visited = set() for _ in range(len(queue)): path = queue.popleft() word = path[-1] for i in range(len(word)): pattern = word[:i] + '*' + word[i+1:] for neighbor in neighbors[pattern]: if neighbor == endWord: found = True results.append(path + [endWord]) if neighbor not in visited: local_visited.add(neighbor) queue.append(path + [neighbor]) visited.update(local_visited) results = [] bfs() return results
question:from typing import List def longest_substring_with_k_deletions(s: str, k: int) -> int: Finds the length of the longest substring that can be made by deleting at most k characters. :param s: The input string consisting of only lowercase alphabets :param k: The number of characters that can be deleted :return: The length of the longest possible substring Examples: >>> longest_substring_with_k_deletions("abcde", 0) 5 >>> longest_substring_with_k_deletions("abcde", 1) 4 pass # Unit Tests def test_longest_substring_no_deletions(): assert longest_substring_with_k_deletions("abcde", 0) == 5 def test_longest_substring_one_deletion(): assert longest_substring_with_k_deletions("abcde", 1) == 4 def test_longest_substring_multiple_deletions(): assert longest_substring_with_k_deletions("abacaba", 2) == 5 def test_longest_substring_all_deletions(): assert longest_substring_with_k_deletions("aaaaa", 5) == 0 def test_longest_substring_insufficient_deletions(): assert longest_substring_with_k_deletions("abcde", 10) == 0 def test_longest_substring_with_repeats(): assert longest_substring_with_k_deletions("aabbaacc", 2) == 6 def test_longest_substring_only_deletions(): assert longest_substring_with_k_deletions("abcdefg", 7) == 0
answer:def longest_substring_with_k_deletions(s, k): This function finds the length of the longest substring that can be made by deleting at most k characters. :param s: The input string consisting of only lowercase alphabets :param k: The number of characters that can be deleted :return: The length of the longest possible substring from collections import defaultdict char_count = defaultdict(int) for char in s: char_count[char] += 1 sorted_chars = sorted(char_count.items(), key=lambda x: x[1], reverse=True) total_length = len(s) deletions = 0 for char, count in sorted_chars: if deletions + count <= k: deletions += count total_length -= count else: total_length -= (k - deletions) break return max(0, total_length)
question:def minConferenceRooms(intervals): Return the minimum number of conference rooms required to hold all booking requests. Parameters: intervals (List[List[int]]): List of booking intervals [start_i, end_i] Returns: int: Minimum number of conference rooms required Examples: >>> minConferenceRooms([[1, 2], [3, 4], [5, 6]]) 1 >>> minConferenceRooms([[1, 4], [2, 5], [3, 6]]) 3 >>> minConferenceRooms([[1, 3], [2, 4], [3, 5]]) 2 >>> minConferenceRooms([[1, 10]]) 1 >>> minConferenceRooms([[1, 4], [2, 4], [3, 4]]) 3 >>> minConferenceRooms([[1, 4], [2, 3], [3, 6], [7, 8], [8, 9]]) 2
answer:def minConferenceRooms(intervals): Return the minimum number of conference rooms required to hold all booking requests. if not intervals: return 0 # Separate start and end times starts = sorted([interval[0] for interval in intervals]) ends = sorted([interval[1] for interval in intervals]) start_ptr, end_ptr = 0, 0 used_rooms = 0 max_rooms = 0 while start_ptr < len(starts): if starts[start_ptr] < ends[end_ptr]: used_rooms += 1 start_ptr += 1 else: used_rooms -= 1 end_ptr += 1 max_rooms = max(max_rooms, used_rooms) return max_rooms