当前位置：首页 > news >正文

Python每日一练(20230305)

news 2025/7/26 15:05:20

1. 正则表达式匹配 ★★★

2. 寻找旋转排序数组中的最小值 II ★★★

3. 删除排序链表中的重复元素 II ★★

1. 正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖整个字符串 s的，而不是部分字符串。

示例 1：

输入：s = "aa" p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。

示例 2:

输入：s = "aa" p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例 3：

输入：s = "ab" p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

示例 4：

输入：s = "aab" p = "c*a*b"
输出：true
解释：因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

示例 5：

输入：s = "mississippi" p = "mis*is*p*."
输出：false

提示：

0 <= s.length <= 20
0 <= p.length <= 30
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
保证每次出现字符 * 时，前面都匹配到有效的字符

代码：

class Solution:def isMatch(self, s: str, p: str) -> bool:if len(p) == 0:return len(s) == 0head_match = len(s) > 0 and (s[0] == p[0] or p[0] == '.')if len(p) > 1 and p[1] == '*':if head_match and self.isMatch(s[1:], p):return Truereturn self.isMatch(s, p[2:])else:if not head_match:return Falsereturn self.isMatch(s[1:], p[1:])if __name__ == '__main__':sol = Solution()s = "aa"; p = "a"print(sol.isMatch(s,p))s = "aa"; p = "a*"print(sol.isMatch(s,p))s = "ab"; p = ".*"print(sol.isMatch(s,p))s = "aab"; p = "c*a*b"print(sol.isMatch(s,p))s = "mississippi"; p = "mis*is*p*."print(sol.isMatch(s,p))

输出：

False
True
True
True
False

2. 寻找旋转排序数组中的最小值 II

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：

若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
若旋转 7 次，则可以得到 [0,1,4,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个可能存在重复元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

示例 1：

输入：nums = [1,3,5]
输出：1

示例 2：

输入：nums = [2,2,2,0,1]
输出：0

提示：

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

进阶：

这道题是寻找旋转排序数组中的最小值的延伸题目。
允许重复会影响算法的时间复杂度吗？会如何影响，为什么？

代码：

class Solution:def findMin(self, nums: list) -> int:left = 0right = len(nums) - 1while left < right:mid = left + (right - left) // 2if nums[mid] > nums[right]:left = mid + 1elif nums[mid] == nums[right]:right -= 1else:right = midreturn nums[left]if __name__ == '__main__':s = Solution()nums = [1,3,5]print(s.findMin(nums))nums = [2,2,2,6,1]print(s.findMin(nums))

输出：

1
0

3. 删除排序链表中的重复元素 II

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。

返回同样按升序排列的结果链表。

示例 1：

输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

示例 2：

输入：head = [1,1,1,2,3]
输出：[2,3]

提示：

链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序排列

代码：

class ListNode(object):def __init__(self, x):self.val = xself.next = None
class LinkList:def __init__(self):self.head=Nonedef initList(self, data):self.head = ListNode(data[0])r=self.headp = self.headfor i in data[1:]:node = ListNode(i)p.next = nodep = p.nextreturn rdef    convert_list(self,head):ret = []if head == None:returnnode = headwhile node != None:ret.append(node.val)node = node.nextreturn ret
class Solution(object):def deleteDuplicates(self, head):""":type head: ListNode:rtype: ListNode"""newnodehead = Nonenewnode = Nonenode = headwhile node:lastval = node.valif node.next and node.next.val == lastval:while node and node.val == lastval:node=node.nextcontinueif not newnodehead:newnode=ListNode(node.val)newnodehead=newnodeelse:newnode.next=ListNode(node.val)newnode=newnode.nextnode = node.nextreturn newnodeheadif __name__ == '__main__':s = Solution()l = LinkList()list1 = [1,2,3,3,4,4,5]l1 = l.initList(list1)print(l.convert_list(s.deleteDuplicates(l1)))list2 = [1,1,1,2,3]l2 = l.initList(list2)print(l.convert_list(s.deleteDuplicates(l2)))

输出：

[1, 2, 5]
[2, 3]