给出20个有点难度的python题目以及答案

给定一个列表，如何找到其中最大的三个数？

lst = [10, 50, 30, 70, 20, 90, 80, 40, 60]

# 方法1：使用sorted函数
print(sorted(lst)[-3:])

# 方法2：使用堆排序
import heapq
print(heapq.nlargest(3, lst))

将一个整数转换为罗马数字。

def int_to_roman(num: int) -> str:
    roman_map = {1: 'I', 4: 'IV', 5: 'V', 9: 'IX', 10: 'X', 40: 'XL', 50: 'L', 90: 'XC', 100: 'C',
                 400: 'CD', 500: 'D', 900: 'CM', 1000: 'M'}
    result = ''
    for value, symbol in sorted(roman_map.items(), reverse=True):
        while num >= value:
            result += symbol
            num -= value
    return result

print(int_to_roman(1994))

给出一个字符串，找到其中第一个不重复的字符。

def first_non_repeating_char(s: str) -> str:
    from collections import Counter
    counter = Counter(s)
    for char in s:
        if counter[char] == 1:
            return char
    return None

print(first_non_repeating_char('leetcode'))

给定两个整数数组，找到它们的交集。

def intersection(nums1, nums2):
    set1 = set(nums1)
    set2 = set(nums2)
    return list(set1 & set2)

print(intersection([1,2,2,1], [2,2]))

给定一个字符串，找到其中最长的回文子串。

def longest_palindrome(s: str) -> str:
    n = len(s)
    if n < 2:
        return s
    start, max_len = 0, 1
    for i in range(n):
        l, r = i, i
        while r < n-1 and s[r] == s[r+1]:
            r += 1
        while l > 0 and r < n-1 and s[l-1] == s[r+1]:
            l -= 1
            r += 1
        if r-l+1 > max_len:
            max_len = r-l+1
            start = l
    return s[start:start+max_len]

print(longest_palindrome('babad'))

给定一个字符串，找到其中最长的无重复字符子串。

def longest_substring(s: str) -> int:
    n = len(s)
    max_len = 0
    start = 0
    d = {}
    for i in range(n):
        if s[i] in d and d[s[i]] >= start:
            start = d[s[i]] + 1
        d[s[i]] = i
        max_len = max(max_len, i-start+1)
    return max_len

print(longest_substring('abcabcbb'))

实现一个LRU缓存。

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}
        self.keys = []

    def get(self, key: int) -> int:
        if key in self.cache:
            self.keys.remove(key)
            self.keys.append(key)
            return self.cache[key]
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.keys.remove(key)
        elif len(self.cache) >= self.capacity:
            oldest = self.keys.pop(0)
            del self.cache[oldest]
        self.cache[key] = value
        self.keys.append(key)

给定一个字符串，找到其中出现次数最多的字符和次数。

def most_common_char(s: str) -> tuple:
    from collections import Counter
    counter = Counter(s)
    return counter.most_common(1)[0]

print(most_common_char('leetcode'))

实现一个二叉树的前序遍历。

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def preorder_traversal(root: TreeNode) -> List[int]:
    if not root:
        return []
    stack = [root]
    res = []
    while stack:
        node = stack.pop()
        res.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return res

实现一个二叉树的中序遍历。

def inorder_traversal(root: TreeNode) -> List[int]:
    stack = []
    res = []
    while stack or root:
        while root:
            stack.append(root)
            root = root.left
        node = stack.pop()
        res.append(node.val)
        root = node.right
    return res

给定一个排序数组，将其转换为二叉搜索树。

def sorted_array_to_bst(nums: List[int]) -> TreeNode:
    if not nums:
        return None
    mid = len(nums) // 2
    root = TreeNode(nums[mid])
    root.left = sorted_array_to_bst(nums[:mid])
    root.right = sorted_array_to_bst(nums[mid+1:])
    return root

给定两个字符串，判断它们是否互为变位词。

def is_anagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    counter = [0] * 26
    for i in range(len(s)):
        counter[ord(s[i]) - ord('a')] += 1
        counter[ord(t[i]) - ord('a')] -= 1
    return all(x == 0 for x in counter)

print(is_anagram('anagram', 'nagaram'))

给定一个二叉树，判断它是否是平衡二叉树。

def is_balanced(root: TreeNode) -> bool:
    def height(node):
        if not node:
            return 0
        left_height = height(node.left)
        right_height = height(node.right)
        if left_height == -1 or right_height == -1 or abs(left_height - right_height) > 1:
            return -1
        return 1 + max(left_height, right_height)

    return height(root) != -1

给定一个数组和一个目标值，找到其中两个数的和等于目标值。

def two_sum(nums: List[int], target: int) -> List[int]:
    d = {}
    for i, num in enumerate(nums):
        if target - num in d:
            return [d[target - num], i]
        d[num] = i
    return None

print(two_sum([2, 7, 11, 15], 9))

实现一个堆排序。

def heap_sort(nums: List[int]) -> List[int]:
    def heapify(nums, n, i):
        largest = i
        left = 2*i + 1
        right = 2*i + 2
        if left < n and nums[left] > nums[largest]:
            largest = left
        if right < n and nums[right] > nums[largest]:
            largest = right
        if largest != i:
            nums[i], nums[largest] = nums[largest], nums[i]
            heapify(nums, n, largest)
    
    n = len(nums)
    for i in range(n//2 - 1, -1, -1):
        heapify(nums, n, i)
    for i in range(n-1, 0, -1):
        nums[0], nums[i] = nums[i], nums[0]
        heapify(nums, i, 0)
    return nums

print(heap_sort([3, 2, 1, 5, 4]))

实现一个快速排序。

def quick_sort(nums: List[int]) -> List[int]:
    if len(nums) <= 1:
        return nums
    pivot = nums[0]
    left = [x for x in nums[1:] if x < pivot]
    right = [x for x in nums[1:] if x >= pivot]
    return quick_sort(left) + [pivot] + quick_sort(right)

print(quick_sort([3, 2, 1, 5, 4]))

实现一个归并排序。

def merge_sort(nums: List[int]) -> List[int]:
    if len(nums) <= 1:
        return nums
    mid = len(nums) // 2
    left = merge_sort(nums[:mid])
    right = merge_sort(nums[mid:])
    return merge(left, right)

def merge(left, right):
    res = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            res.append(left[i])
            i += 1
        else:
            res.append(right[j])
            j += 1
    res.extend(left[i:])
    res.extend(right[j:])
    return res

print(merge_sort([3, 2, 1, 5, 4]))

实现一个希尔排序。

def shell_sort(nums: List[int]) -> List[int]:
    n = len(nums)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            temp = nums[i]
            j = i
            while j >= gap and nums[j-gap] > temp:
                nums[j] = nums[j-gap]
                j -= gap
            nums[j] = temp
        gap = gap // 2
    return nums

print(shell_sort([3, 2, 1, 5, 4]))

实现一个基数排序。

def radix_sort(nums: List[int]) -> List[int]:
    def counting_sort(nums, exp):
        n = len(nums)
        output = [0] * n
        count = [0] * 10
        for i in range(n):
            index = nums[i] // exp
            count[index % 10] += 1
        for i in range(1, 10):
            count[i] += count[i-1]
        for i in range(n-1, -1, -1):
            index = nums[i] // exp
            output[count[index % 10] - 1] = nums[i]
            count[index % 10] -= 1
        nums[:] = output[:]
    
    max_num = max(nums)
    exp = 1
    while max_num // exp > 0:
        counting_sort(nums, exp)
        exp *= 10
    return nums

print(radix_sort([3, 2, 1, 5, 4]))

实现一个二分查找。

def binary_search(nums: List[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

print(binary_search([1, 2, 3, 4, 5], 3))