期货贵金属网站建设,网站建设感谢信,广告优化师怎么入行,比较好的网站设计目录
1. 正则表达式匹配 ★★★
2. 寻找旋转排序数组中的最小值 II ★★★
3. 删除排序链表中的重复元素 II ★★ 1. 正则表达式匹配
给你一个字符串 s 和一个字符规律 p#xff0c;请你来实现一个支持 . 和 * 的正则表达式匹配。
. 匹配任意单个字符* 匹配零个或多个…
目录
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 200 p.length 30s 可能为空且只包含从 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 aprint(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*bprint(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.length1 n 5000-5000 nums[i] 5000nums 原来是一个升序排序的数组并进行了 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.headNonedef initList(self, data):self.head ListNode(data[0])rself.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: ListNodenewnodehead Nonenewnode Nonenode headwhile node:lastval node.valif node.next and node.next.val lastval:while node and node.val lastval:nodenode.nextcontinueif not newnodehead:newnodeListNode(node.val)newnodeheadnewnodeelse:newnode.nextListNode(node.val)newnodenewnode.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] 每日一练刷题专栏
✨ 持续努力奋斗做强刷题搬运工 点赞你的认可是我坚持的动力
★ 收藏你的青睐是我努力的方向
✏️ 评论你的意见是我进步的财富 C/C 每日一练 专栏 Python 每日一练 专栏
