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) == 0 head_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 True return self.isMatch(s, p[2:]) else: if not head_match: return False return 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 = 0 right = len(nums) - 1 while left < right: mid = left + (right - left) // 2 if nums[mid] > nums[right]: left = mid + 1 elif nums[mid] == nums[right]: right -= 1 else: right = mid return 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 = x self.next = None class LinkList: def __init__(self): self.head=None def initList(self, data): self.head = ListNode(data[0]) r=self.head p = self.head for i in data[1:]: node = ListNode(i) p.next = node p = p.next return r def convert_list(self,head): ret = [] if head == None: return node = head while node != None: ret.append(node.val) node = node.next return ret class Solution(object): def deleteDuplicates(self, head): """ :type head: ListNode :rtype: ListNode """ newnodehead = None newnode = None node = head while node: lastval = node.val if node.next and node.next.val == lastval: while node and node.val == lastval: node=node.next continue if not newnodehead: newnode=ListNode(node.val) newnodehead=newnode else: newnode.next=ListNode(node.val) newnode=newnode.next node = node.next return newnodehead if __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]
