Python面试题【数据结构和算法部分101-130】

Python面试题【数据结构和算法部分101-130】

101. 问题：如何在Python中实现二分查找？
     答案：

    def binary_search(arr, target):low, high = 0, len(arr) - 1while low <= high:mid = (low + high) // 2if arr[mid] == target:return midelif arr[mid] < target:low = mid + 1else:high = mid - 1return -1

102. 问题：Python中如何实现链表？
     答案：

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

103. 问题：如何在Python中反转链表？
     答案：

    def reverse_list(head):prev = Nonecurrent = headwhile current:next_node = current.nextcurrent.next = prevprev = currentcurrent = next_nodereturn prev

104. 问题：Python中的栈和队列有什么区别？
     答案：
     栈是一种后进先出（LIFO）的数据结构，而队列是一种先进先出（FIFO）的数据结构。

105. 问题：如何在Python中实现一个栈？
     答案：

    class Stack:def __init__(self):self.items = []def push(self, item):self.items.append(item)def pop(self):return self.items.pop()def is_empty(self):return not self.items

106. 问题：如何在Python中实现一个队列？
     答案：

    class Queue:def __init__(self):self.items = []def enqueue(self, item):self.items.insert(0, item)def dequeue(self):return self.items.pop()def is_empty(self):return not self.items

107. 问题：解释Python中的堆（Heap）及其用途。
     答案：
     堆是一种特殊的完全二叉树。所有的父节点都大于或等于（最大堆）或小于或等于（最小堆）它们的子节点。堆常用于实现优先队列。

108. 问题：如何在Python中找到列表中的第k个最大元素？
     答案：

    import heapqdef find_kth_largest(nums, k):return heapq.nlargest(k, nums)[-1]

109. 问题：解释Python中的哈希表（Hash Table）及其用途。
     答案：
     哈希表是一种使用哈希函数组织数据，以支持快速插入和搜索的数据结构。Python中的字典（dict）是哈希表的一个实例。

110. 问题：如何在Python中检测循环链表？
     答案：

    def has_cycle(head):slow, fast = head, headwhile fast and fast.next:slow = slow.nextfast = fast.next.nextif slow == fast:return Truereturn False

111. 问题：如何在Python中实现图的深度优先遍历？
     答案：

    def dfs(graph, start, visited=None):if visited is None:visited = set()visited.add(start)print(start)for next_node in graph[start] - visited:dfs(graph, next_node, visited)return visited

112. 问题：如何在Python中实现图的广度优先遍历？
     答案：

    from collections import dequedef bfs(graph, start):visited = set()queue = deque([start])while queue:vertex = queue.popleft()if vertex not in visited:visited.add(vertex)queue.extend(graph[vertex] - visited)return visited

113. 问题：如何在Python中检查两个字符串是否是变位词（anagrams）？
     答案：

    from collections import Counterdef are_anagrams(str1, str2):return Counter(str1) == Counter(str2)

114. 问题：如何在Python中实现快速排序？
     答案：

    def quicksort(arr):if len(arr) <= 1:return arrpivot = arr[len(arr) // 2]left = [x for x in arr if x < pivot]middle = [x for x in arr if x == pivot]right = [x for x in arr if x > pivot]return quicksort(left) + middle + quicksort(right)

115. 问题：如何在Python中实现归并排序？
     答案：

    def merge_sort(arr):if len(arr) > 1:mid = len(arr) // 2L = arr[:mid]R = arr[mid:]merge_sort(L)merge_sort(R)i = j = k = 0while i < len(L) and j < len(R):if L[i] < R[j]:arr[k] = L[i]i += 1else:arr[k] = R[j]j += 1k += 1while i < len(L):arr[k] = L[i]i += 1k += 1while j < len(R):arr[k] = R[j]j += 1k += 1return arr

116. 问题：如何在Python中找到数组中的最长连续序列？
     答案：

    def longest_consecutive(nums):num_set = set(nums)longest = 0for n in nums:if n - 1 not in num_set:length = 0while n + length in num_set:length += 1longest = max(longest, length)return longest

117. 问题：在Python中如何实现动态规划解决方案？
     答案：
     动态规划是一种将复杂问题分解为更小子问题的算法设计技术。通常通过填充一个表格来解决，并将子问题的解存储在表格中供后续引用，以避免重复计算。

118. 问题：如何在Python中实现二叉树？
     答案：

    class TreeNode:def __init__(self, value):self.value = valueself.left = Noneself.right = None

119. 问题：如何在Python中检测二叉树是否平衡？
     答案：

    def is_balanced(root):def check(node):if node is None:return 0left_height = check(node.left)if left_height == -1:return -1right_height = check(node.right)if right_height == -1:return -1if abs(left_height - right_height) > 1:return -1return max(left_height, right_height) + 1return check(root) != -1

120. 问题：如何在Python中找到二叉搜索树中第k小的元素？
     答案：

    def kth_smallest(root, k):stack = []while True:while root:stack.append(root)root = root.leftroot = stack.pop()k -= 1if not k:return root.valueroot = root.right

121. 问题：如何在Python中实现堆排序算法？
     答案：

    import heapqdef heap_sort(iterable):h = []for value in iterable:heapq.heappush(h, value)return [heapq.heappop(h) for _ in range(len(h))]

122. 问题：在Python中如何找出数组中的重复数字？
     答案：

    def find_duplicates(nums):duplicates = set()seen = set()for num in nums:if num in seen:duplicates.add(num)seen.add(num)return list(duplicates)

123. 问题：描述Python中的双端队列（deque）及其用途。
     答案：
     双端队列（deque）是一种具有队列和栈的性质的数据结构。在collections模块中，deque是一个双端队列的实现，允许我们从前面或后面添加或删除元素。

124. 问题：如何在Python中实现二叉树的层序遍历？
     答案：

    from collections import dequedef level_order_traversal(root):if not root:return []queue = deque([root])result = []while queue:level_size = len(queue)current_level = []for _ in range(level_size):node = queue.popleft()current_level.append(node.value)if node.left:queue.append(node.left)if node.right:queue.append(node.right)result.append(current_level)return result

125. 问题：如何在Python中实现前缀树（Trie）？
     答案：

    class TrieNode:def __init__(self):self.children = {}self.is_end_of_word = Falseclass Trie:def __init__(self):self.root = TrieNode()def insert(self, word):node = self.rootfor char in word:if char not in node.children:node.children[char] = TrieNode()node = node.children[char]node.is_end_of_word = True

126. 问题：如何在Python中找到数组的所有子集？
     答案：

    def subsets(nums):result = [[]]for num in nums:result += [curr + [num] for curr in result]return result

127. 问题：如何在Python中找到无序数组中的中位数？
     答案：

    import heapqdef find_median(nums):min_heap = []max_heap = []for num in nums:heapq.heappush(max_heap, -heapq.heappushpop(min_heap, num))if len(max_heap) > len(min_heap):heapq.heappush(min_heap, -heapq.heappop(max_heap))if len(min_heap) > len(max_heap):return min_heap[0]return (min_heap[0] - max_heap[0]) / 2.0

128. 问题：描述Python中的广度优先搜索（BFS）算法。
     答案：
     广度优先搜索（BFS）是一种遍历或搜索树或图的算法，它从根节点开始，逐层遍历所有节点，每次遍历同一层的所有节点。

129. 问题：如何在Python中找到字符串中的最长不含重复字符的子串？
     答案：

    def length_of_longest_substring(s):char_map = {}left = 0max_length = 0for right, char in enumerate(s):if char in char_map and char_map[char] >= left:left = char_map[char] + 1char_map[char] = rightmax_length = max(max_length, right - left + 1)return max_length

130. 问题：如何在Python中实现动态数组？
     答案：
     动态数组可以通过内置的list类型实现，它在底层自动扩展其大小。