Python面试算法题

移动最少区间个数使得剩余区间无重叠

1.输入:[1,2][2,3][4,6][1,3] 2.输出:1 3.解释:移除[1,3]后，剩余区间无重叠。

通过贪心算法来解决。

• 先将所有区间按照结束时间排序。

• 然后从第二个区间开始，检查每个区间的开始时间是否小于前一个区间的结束时间。

• 如果有重叠，增加移除计数。

• 最后返回移除的区间数。

def eraseOverlapIntervals(intervals):"""功能：移除最少数量的区间，使剩余区间互不重叠参数：intervals: 二维列表，例如 [[1,2],[2,3],[4,6],[1,3]]返回：count   : 删除的区间数量removed : 被删除的区间列表"""#  如果输入为空，直接返回if not intervals:return 0, []#  按区间“结束位置”排序；x[1] 表示结束位置# 贪心思想：优先保留结束最早的区间intervals.sort(key=lambda x: x[1])end = intervals[0][1]  #  初始化变量 当前保留区间的结束位置（先保留排序后的第一个区间）removed = []   # 记录被删除的区间count = 0  # 记录删除数量#  从第二个区间开始遍历for i in range(1, len(intervals)):current = intervals[i] # 当前区间#   判断是否重叠： 如果 当前区间的起点 < 上一个区间的结束点if current[0] < end:# 说明发生重叠 当前区间结束一定 >= 前一个结束  所以删除当前区间是最优选择
            removed.append(current)count += 1else:end = current[1]   # 没有重叠  更新 end 为当前区间的结束位置return count, removed# ================= 测试代码 =================

intervals = [[1, 2], [2, 3], [4, 6], [1, 3]]count, removed_intervals = eraseOverlapIntervals(intervals)
print("删除数量:", count)
print("删除区间:", removed_intervals)

寻找第二大的数字

要求时间复杂度O(n)

def second_largest(nums):if len(nums) < 2:return None  # 不存在第二大
    max1 = float('-inf')max2 = float('-inf')for num in nums:# 如果找到新的最大值if num > max1:max2 = max1max1 = num# 如果介于 max1 和 max2 之间elif max1 > num > max2:max2 = num# 如果 max2 仍然是 -inf，说明不存在第二大return max2 if max2 != float('-inf') else None

不包含重复字母的最大子字符串

• 使用 哈希集合（set）来记录当前窗口中的字符。

• 用两个指针：left 和 right，其中 right 用于扩展窗口，left 用于缩小窗口，确保每个字符不重复。

• 每当遇到重复字符时，left 指针向右移动，直到窗口内没有重复字符。

• 在每一步，更新最长子串的长度。

def longest_substring(s):n = len(s)if n == 0:return "", 0# 字符集用于存储当前窗口中的字符char_set = set()left = 0  # 窗口的左边界max_len = 0  # 最大长度start = 0  # 最大子串的起始位置for right in range(n):# 如果字符重复，移动左边界直到去掉重复字符while s[right] in char_set:char_set.remove(s[left])left += 1# 添加当前字符到集合中
        char_set.add(s[right])# 更新最大子串的长度及起始位置if right - left + 1 > max_len:max_len = right - left + 1start = left# 返回最大子串及其长度return s[start:start + max_len], max_len# 测试
s = "abcabcbb"
substring, length = longest_substring(s)
print("最大子串:", substring)
print("最大子串长度:", length)

合并两个升序链表

要求：不能新建链表

class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef merge_two_lists(l1, l2):# 处理空链表情况if not l1:return l2if not l2:return l1# 确保 l1 是较小的起点if l1.val > l2.val:l1, l2 = l2, l1   # 交换变量指针head = l1  # 最终返回的头节点while l1 and l2:prev = None# 找到 l1 中最后一个 <= l2.val 的节点while l1 and l1.val <= l2.val:prev = l1l1 = l1.next# 把 l2 接到 prev 后面prev.next = l2# 交换 l1 和 l2（继续下一轮）l1, l2 = l2, l1return head