Python简单算法题

1.字符串中的第一个唯一字符def first_uniq_char(s: str) - int: from collections import Counter count Counter(s) for i, ch in enumerate(s): if count[ch] 1: return i return -12. 合并两个有序数组双指针in-place题目给你两个按非递减顺序排列的整数数组nums1和nums2另有两个整数m和n分别表示nums1和nums2中的元素个数。请你合并nums2到nums1中使合并后的数组同样按非递减顺序排列。注意nums1的长度为mn其中前m个是有效元素后面n个为 0 占位。考察点逆向双指针、原地修改、避免额外空间参考代码def merge(nums1, m, nums2, n): i, j, k m-1, n-1, mn-1 while i 0 and j 0: if nums1[i] nums2[j]: nums1[k] nums1[i] i - 1 else: nums1[k] nums2[j] j - 1 k - 1 # 如果 nums2 还有剩余 while j 0: nums1[k] nums2[j] j - 1 k - 13. 判断链表是否有环快慢指针题目给定一个链表判断链表中是否有环。考察点链表操作、快慢指针、空间复杂度 O(1)参考代码题目理解给定一个链表判断链表中是否有环。如果链表中某个节点可以通过连续 next 指针再次到达则说明有环。核心思路快慢指针Floyd判圈算法原理两个指针同时从头节点出发慢指针每次移动1步快指针每次移动2步如果有环快指针一定会追上慢指针在环内相遇如果无环快指针会先到达链表末尾nullclass ListNode: def __init__(self, x): self.val x self.next None def hasCycle(head: ListNode) - bool: # 边界条件空链表或只有一个节点且无环 if not head or not head.next: return False slow head fast head while fast and fast.next: slow slow.next # 慢指针走一步 fast fast.next.next # 快指针走两步 if slow fast: # 相遇说明有环 return True return False # 快指针到达终点无环Q: 如何计算环的长度def cycle_length(head: ListNode) - int: slow fast head # 先找到相遇点 while fast and fast.next: slow slow.next fast fast.next.next if slow fast: # 计算环长度 length 1 fast fast.next while slow ! fast: fast fast.next length 1 return length return 04. 最长公共前缀字符串处理题目编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀返回空字符串。示例[flower,flow,flight]→fl考察点字符串遍历、边界处理、工程健壮性空数组参考代码def longest_common_prefix(strs): if not strs: return prefix strs[0] for s in strs[1:]: while not s.startswith(prefix): prefix prefix[:-1] if not prefix: return return prefix