leetcodeday19 –删除链表的倒数第 N 个结点

总结方法:对于链表,一般在链表开头先添加一个头元素,该元素指向链表的第一个元素。

给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

示例 1:

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

示例 2:

输入:head = [1], n = 1
输出:[]

示例 3:

输入:head = [1,2], n = 1
输出:[1]

提示:

  • 链表中结点的数目为 sz
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

一般方法:两次for循环

第一次计算长度,第二次重构链表

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        def getLength(head: ListNode) -> int:
            length = 0
            while head:
                length += 1
                head = head.next
            return length
        
        dummy = ListNode(0, head)
        length = getLength(head)
        cur = dummy
        for i in range(1, length - n + 1):
            cur = cur.next
        cur.next = cur.next.next
        return dummy.next

改进版:

双指针

思路与算法

我们也可以在不预处理出链表的长度,以及使用常数空间的前提下解决本题。由于我们需要找到倒数第n 个节点,因此我们可以使用两个指针first 和 second 同时对链表进行遍历,并且 first 比second 超前 n个节点。当first 遍历到链表的末尾时,second 就恰好处于倒数第 n 个节点。

具体地,初始时 first 和 second 均指向头节点。我们首先使用 first 对链表进行遍历,遍历的次数为 n。此时,first 和 second 之间间隔了 n−1 个节点,即 first 比second 超前了 n个节点。

在这之后,我们同时使用 first 和second 对链表进行遍历。当 first 遍历到链表的末尾(即 first 为空指针)时,second 恰好指向倒数第 n 个节点。

根据方法一和方法二,如果我们能够得到的是倒数第 n 个节点的前驱节点而不是倒数第 n 个节点的话,删除操作会更加方便。因此我们可以考虑在初始时将 second 指向哑节点,其余的操作步骤不变。这样一来,当first 遍历到链表的末尾时,second 的下一个节点就是我们需要删除的节点。

# @lc code=start
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0, head)
        first = head
        second = dummy
        for i in range(n):
            first = first.next

        while first:
            first = first.next
            second = second.next
        
        second.next = second.next.next
        return dummy.next

复杂度分析

  • 时间复杂度:O(L),其中 L 是链表的长度。
  • 空间复杂度: O(1)。

leetcodeday18 —-四数之和

给你一个由 n 个整数组成的数组 nums ,和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] (若两个四元组元素一一对应,则认为两个四元组重复):

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。

示例 1:

输入:nums = [1,0,-1,0,-2,2], target = 0
输出:[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2:

输入:nums = [2,2,2,2,2], target = 8
输出:[[2,2,2,2]]

思路:三数之和+一层遍历

# @lc code=start
class Solution:
  def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
    n = len(nums)
    nums.sort()
    result=list()
    def threeSum(nums: List[int],targets: int,fst:int) -> List[List[int]]:
        n = len(nums)
        ans = list()
        
        # 枚举 a
        for first in range(n):
            # 需要和上一次枚举的数不相同
            if first > 0 and nums[first] == nums[first - 1]:
                continue
            # c 对应的指针初始指向数组的最右端
            third = n - 1
            target = targets-nums[first]
            # 枚举 b
            for second in range(first + 1, n):
                # 需要和上一次枚举的数不相同
                if second > first + 1 and nums[second] == nums[second - 1]:
                    continue
                # 需要保证 b 的指针在 c 的指针的左侧
                while second < third and nums[second] + nums[third] > target:
                    third -= 1
                # 如果指针重合,随着 b 后续的增加
                # 就不会有满足 a+b+c=0 并且 b<c 的 c 了,可以退出循环
                if second == third:
                    break
                if nums[second] + nums[third] == target:
                    ans.append([fst,nums[first], nums[second], nums[third]])
        
        return ans
    
    for first in range(n):
        if first > 0 and nums[first] == nums[first - 1]:
                continue
        targets= target-nums[first]
        result.extend(threeSum(nums[first+1:],targets,nums[first]))
    return result

leetcodeday17 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

示例 1:

输入:digits = “23”
输出:[“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce”,”cf”]
示例 2:

输入:digits = “”
输出:[]
示例 3:

输入:digits = “2”
输出:[“a”,”b”,”c”]

提示:

  • 0 <= digits.length <= 4
  • digits[i] 是范围 ['2', '9'] 的一个数字

思路:遍历递归求解

# @lc code=start
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if digits=="": 
            return []
        n=len(digits)
        sets={"2":["a","b","c"],"3":["d","e","f"],"4":["g","h","i"],"5":["j","k","l"],"6":["m","n","o"],"7":["p","q","r","s"],"8":["t","u","v"],"9":["w","x","y","z"]}
        def upsort(strs): 
            if len(strs)==1: 
                return sets[strs]
    
            result = upsort(strs[:-1])
            rev=[]
            for i in range(len(result)):
                 for j in sets[strs[-1]]:
                    rev.append(result[i]+j)
            return rev
        return upsort(digits)

leetcodeday16 —最接近的三数之和

这个思路和上一个题差不多,不过简单一些,只需要找出三个数的和。因此给出官方答案。

给你一个长度为 n 的整数数组 nums和 一个目标值 target。请你从 nums中选出三个整数,使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

示例 1:

输入:nums = [-1,2,1,-4], target = 1
输出:2
解释:与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

排序 + 双指针
思路与算法

题目要求找到与目标值 target 最接近的三元组,这里的「最接近」即为差值的绝对值最小。我们可以考虑直接使用三重循环枚举三元组,找出与目标值最接近的作为答案,时间复杂度为 O(N^3)。然而本题的 N 最大为 1000,会超出时间限制。

那么如何进行优化呢?我们首先考虑枚举第一个元素 a,对于剩下的两个元素 b 和 c,我们希望它们的和最接近 target−a。对于 b 和 c,如果它们在原数组中枚举的范围(既包括下标的范围,也包括元素值的范围)没有任何规律可言,那么我们还是只能使用两重循环来枚举所有的可能情况。因此,我们可以考虑对整个数组进行升序排序,这样一来:

假设数组的长度为 n,我们先枚举 a,它在数组中的位置为 i;

为了防止重复枚举,我们在位置 [i+1,n) 的范围内枚举 b 和 c。

当我们知道了 b 和 c 可以枚举的下标范围,并且知道这一范围对应的数组元素是有序(升序)的,那么我们是否可以对枚举的过程进行优化呢?

答案是可以的。借助双指针,我们就可以对枚举的过程进行优化。我们用 p_b和 p_c
分别表示指向 b 和 c的指针,初始时,p_b指向位置 i+1,即左边界;p_c指向位置 n-1,即右边界。在每一步枚举的过程中,我们用 a+b+c 来更新答案,并且:

如果 a+b+c≥target,那么就将 p_c向左移动一个位置;

如果 a+b+c<target,那么就将 p_b向右移动一个位置。这是为什么呢?我们对 a+b+c≥target 的情况进行一个详细的分析:

如果 a+b+c≥target,并且我们知道 p_b到 p_c这个范围内的所有数是按照升序排序的,那么如果 p_c不变而 p_b向右移动,那么 a+b+c 的值就会不断地增加,显然就不会成为最接近 target 的值了。因此,我们可以知道在固定了 p_c的情况下,此时的 p_b就可以得到一个最接近target 的值,那么我们以后就不用再考虑 p_c了,就可以将 p_c向左移动一个位置。

同样地,在 a+b+c<target 时:

如果 a+b+c<target,并且我们知道 p_b到 p_c这个范围内的所有数是按照升序排序的,那么如果 p_b不变而 p_c向左移动,那么 a+b+c 的值就会不断地减小,显然就不会成为最接近 target 的值了。因此,我们可以知道在固定了 p_b的情况下,此时的 p_cp就可以得到一个最接近 target 的值,那么我们以后就不用再考虑 p_b了,就可以将 p_b向右移动一个位置。实际上,p_b和 p_c就表示了我们当前可以选择的数的范围,而每一次枚举的过程中,我们尝试边界上的两个元素,根据它们与 target 的值的关系,选择「抛弃」左边界的元素还是右边界的元素,从而减少了枚举的范围。这种思路与盛最多水的容器 中的双指针解法也是类似的。

小优化

本题也有一些可以减少运行时间(但不会减少时间复杂度)的小优化。当我们枚举到恰好等于target 的 a+b+c时,可以直接返回 target 作为答案,因为不会有再比这个更接近的值了。

另一个优化与 三数之和的官方题解 中提到的类似。当我们枚举 a, b, c中任意元素并移动指针时,可以直接将其移动到下一个与这次枚举到的不相同的元素,减少枚举的次数。

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        n = len(nums)
        best = 10**7
        
        # 根据差值的绝对值来更新答案
        def update(cur):
            nonlocal best
            if abs(cur - target) < abs(best - target):
                best = cur
        
        # 枚举 a
        for i in range(n):
            # 保证和上一次枚举的元素不相等
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            # 使用双指针枚举 b 和 c
            j, k = i + 1, n - 1
            while j < k:
                s = nums[i] + nums[j] + nums[k]
                # 如果和为 target 直接返回答案
                if s == target:
                    return target
                update(s)
                if s > target:
                    # 如果和大于 target,移动 c 对应的指针
                    k0 = k - 1
                    # 移动到下一个不相等的元素
                    while j < k0 and nums[k0] == nums[k]:
                        k0 -= 1
                    k = k0
                else:
                    # 如果和小于 target,移动 b 对应的指针
                    j0 = j + 1
                    # 移动到下一个不相等的元素
                    while j0 < k and nums[j0] == nums[j]:
                        j0 += 1
                    j = j0

        return best

leetcodeday15 —三数之和

给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。

注意:答案中不可以包含重复的三元组。

示例 1:

输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]

示例 2:

输入:nums = []
输出:[]

示例 3:

输入:nums = [0]
输出:[]

提示:

  • 0 <= nums.length <= 3000
  • -105 <= nums[i] <= 105

思路双指针方法:依次对每个元素进行如下判断:-s[i]==s[j]+s[m],其中 s[j]+s[m] 要遍历剩下的元素(采用双指针)


# @lc code=start
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
            if set(nums)=={0} and len(nums)>=3:
                return [[0,0,0]]
                   
            sets=set()
            lens=len(nums)
            nums =sorted(nums)
            result=[]
            for i in range(lens):
                newlist=nums[0:i]+nums[i+1:]
                
                m=0
                j=lens-1-1
                if nums[i] in sets:
                    continue
                else:
                    sets.add(nums[i])
                while m<j:
                    if newlist[m]+newlist[j]==-nums[i] and sorted([newlist[m],newlist[j],nums[i]])not  in result:
            
                        result.append(sorted([newlist[m],newlist[j],nums[i]]))
                        m=m+1
                    elif newlist[m]+newlist[j]>-nums[i]:
                        j=j-1
                    else:
                        m=m+1
            return result

# @lc code=end

就差超时了……

方法一:排序 + 双指针
题目中要求找到所有「不重复」且和为 0 的三元组,这个「不重复」的要求使得我们无法简单地使用三重循环枚举所有的三元组。这是因为在最坏的情况下,数组中的元素全部为 0,即

[0, 0, 0, 0, 0, …, 0, 0, 0]
任意一个三元组的和都为 00。如果我们直接使用三重循环枚举三元组,会得到 O(N^3)个满足题目要求的三元组(其中 N是数组的长度)时间复杂度至少为 O(N^3)。在这之后,我们还需要使用哈希表进行去重操作,得到不包含重复三元组的最终答案,又消耗了大量的空间。这个做法的时间复杂度和空间复杂度都很高,因此我们要换一种思路来考虑这个问题。

「不重复」的本质是什么?我们保持三重循环的大框架不变,只需要保证:

第二重循环枚举到的元素不小于当前第一重循环枚举到的元素;

第三重循环枚举到的元素不小于当前第二重循环枚举到的元素。

也就是说,我们枚举的三元组 (a, b, c) 满足 a≤b≤c,保证了只有 (a,b,c) 这个顺序会被枚举到,而 (b,a,c)、(c,b,a) 等等这些不会,这样就减少了重复。要实现这一点,我们可以将数组中的元素从小到大进行排序,随后使用普通的三重循环就可以满足上面的要求。

同时,对于每一重循环而言,相邻两次枚举的元素不能相同,否则也会造成重复。举个例子,如果排完序的数组为

[0, 1, 2, 2, 2, 3]

我们使用三重循环枚举到的第一个三元组为 (0, 1, 2),如果第三重循环继续枚举下一个元素,那么仍然是三元组 (0, 1, 2),产生了重复。因此我们需要将第三重循环「跳到」下一个不相同的元素,即数组中的最后一个元素 3,枚举三元组 (0, 1, 3)。

nums.sort()
for first = 0 .. n-1
    // 只有和上一次枚举的元素不相同,我们才会进行枚举
    if first == 0 or nums[first] != nums[first-1] then
        for second = first+1 .. n-1
            if second == first+1 or nums[second] != nums[second-1] then
                for third = second+1 .. n-1
                    if third == second+1 or nums[third] != nums[third-1] then
                        // 判断是否有 a+b+c==0
                        check(first, second, third)

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/3sum/solution/san-shu-zhi-he-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

改进:

nums.sort()
for first = 0 .. n-1
    if first == 0 or nums[first] != nums[first-1] then
        // 第三重循环对应的指针
        third = n-1
        for second = first+1 .. n-1
            if second == first+1 or nums[second] != nums[second-1] then
                // 向左移动指针,直到 a+b+c 不大于 0
                while nums[first]+nums[second]+nums[third] > 0
                    third = third-1
                // 判断是否有 a+b+c==0
                check(first, second, third)

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        nums.sort()
        ans = list()
        
        # 枚举 a
        for first in range(n):
            # 需要和上一次枚举的数不相同
            if first > 0 and nums[first] == nums[first - 1]:
                continue
            # c 对应的指针初始指向数组的最右端
            third = n - 1
            target = -nums[first]
            # 枚举 b
            for second in range(first + 1, n):
                # 需要和上一次枚举的数不相同
                if second > first + 1 and nums[second] == nums[second - 1]:
                    continue
                # 需要保证 b 的指针在 c 的指针的左侧
                while second < third and nums[second] + nums[third] > target:
                    third -= 1
                # 如果指针重合,随着 b 后续的增加
                # 就不会有满足 a+b+c=0 并且 b<c 的 c 了,可以退出循环
                if second == third:
                    break
                if nums[second] + nums[third] == target:
                    ans.append([nums[first], nums[second], nums[third]])
        
        return ans

leetcodeday14 —最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀,返回空字符串 ""

示例 1:

输入:strs = ["flower","flow","flight"]
输出:"fl"

示例 2:

输入:strs = ["dog","racecar","car"]
输出:""
解释:输入不存在公共前缀。

提示:

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] 仅由小写英文字母组成

第一次解法:(暴力)依次比较每个str的元素

# @lc code=start
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        lens=len(strs[0])
        lenlist=len(strs)
        j=0
        if lenlist==1 or strs[0]=="":
            return strs[0]
        while j<lens:
         
            for i in range(1,lenlist):
                fist=strs[0][j]
                if j>=len(strs[i]) or strs[i][j] != fist:
                    return  strs[0][0:j]
            j=j+1
        return strs[0][0:j]


#递归函数
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        def lcp(start, end):
            if start == end:
                return strs[start]

            mid = (start + end) // 2
            lcpLeft, lcpRight = lcp(start, mid), lcp(mid + 1, end)
            minLength = min(len(lcpLeft), len(lcpRight))
            for i in range(minLength):
                if lcpLeft[i] != lcpRight[i]:
                    return lcpLeft[:i]

            return lcpLeft[:minLength]

        return "" if not strs else lcp(0, len(strs) - 1)

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/longest-common-prefix/solution/zui-chang-gong-gong-qian-zhui-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        def isCommonPrefix(length):
            str0, count = strs[0][:length], len(strs)
            return all(strs[i][:length] == str0 for i in range(1, count))

        if not strs:
            return ""

        minLength = min(len(s) for s in strs)
        low, high = 0, minLength
        while low < high:
            mid = (high - low + 1) // 2 + low
            if isCommonPrefix(mid):
                low = mid
            else:
                high = mid - 1

        return strs[0][:low]

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/longest-common-prefix/solution/zui-chang-gong-gong-qian-zhui-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

leetcodeday13– 罗马数字转整数

罗马数字包含以下七种字符: I, V, X, LCD 和 M

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如, 罗马数字 2 写做 II ,即为两个并列的 1 。12 写做 XII ,即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。

通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:

  • I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。 
  • C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。

给定一个罗马数字,将其转换成整数。

示例 1:

输入: s = "III"
输出: 3

示例 2:

输入: s = "IV"
输出: 4

示例 3:

输入: s = "IX"
输出: 9

示例 4:

输入: s = "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.

示例 5:

输入: s = "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

提示:

  • 1 <= s.length <= 15
  • s 仅含字符 ('I', 'V', 'X', 'L', 'C', 'D', 'M')
  • 题目数据保证 s 是一个有效的罗马数字,且表示整数在范围 [1, 3999] 内
  • 题目所给测试用例皆符合罗马数字书写规则,不会出现跨位等情况。
  • IL 和 IM 这样的例子并不符合题目要求,49 应该写作 XLIX,999 应该写作 CMXCIX 。

思路:使用字典,遍历s字符串:

# @lc code=start
class Solution:
    def romanToInt(self, s: str) -> int:

        num=0
        j=0
        dicts={"M":1000,"CM":900,"D":500,"CD":400,"C":100,"XC":90,"L":50,"XL":40,"X":10,"I":1,"IV":4,"V":5,"IX":9}
        while j<len(s):
            if s[j:j+2]!='' and dicts.get(s[j:j+2])!=None:
                num=num+dicts[s[j:j+2]]
                j=j+2
            else:
                num = num + dicts[s[j]]
                j=j+1
        return num

        
# @lc code=end

leetcodeday12—整数转罗马数字

罗马数字包含以下七种字符: I, V, X, LCD 和 M

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如, 罗马数字 2 写做 II ,即为两个并列的 1。12 写做 XII ,即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。

通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:

  • I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。 
  • C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。

给你一个整数,将其转为罗马数字。

示例 1:

输入: num = 3
输出: "III"

示例 2:

输入: num = 4
输出: "IV"

示例 3:

输入: num = 9
输出: "IX"

示例 4:

输入: num = 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.

示例 5:

输入: num = 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.

我的思路:其实就是和我们的123455数字表示法差不多。

对于 个位数:用 [“I”,”IV”,”V”,”IX”] 中的元素组合表示

十位数: 用 [“X”,”XL”,”L”,”XC”] 中的元素组合表示 、

百位数: [“C”,”CD”,”D”,”CM”]

千位数:用M表示

因此遍历数中的每一位,分别用相应的元素表示,然后在组装起来。

# @lc code=start
class Solution:
    def intToRoman(self, num: int) -> str:
        str2=str(num)
        str0=[" "]
        str1=["","","",""]
        lens=len(str2)
        if lens==4:
            str0 = [int(str2[0])*"M"]
            str2=str2[1:]
            lens=len(str2)
        m=lens-1
        mod=[["I","IV","V","IX"],["X","XL","L","XC"],["C","CD","D","CM"]]
        for i  in range(lens):
            j=int(str2[i])
    
            if 0 <= j < 4:
                str1[i]=mod[m][0]*j
            elif j==4:
                str1[i]=mod[m][1]
            elif 4<j<9:
                str1[i]=mod[m][2]+mod[m][0]*(j-5)
            elif j==9:
                str1[i]=mod[m][3]
            m=m-1
        return ("".join(str0+str1)).strip()
        
# @lc code=end

leetcode10 –正则匹配

给你一个字符串 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

思路:动态规划求解

一开始没有思路,因此,看了官方教程,然后自己开始动手写。

思路与算法

题目中的匹配是一个「逐步匹配」的过程:我们每次从字符串 p 中取出一个字符或者「字符 + 星号」的组合,并在 s 中进行匹配。对于 p 中一个字符而言,它只能在 s 中匹配一个字符,匹配的方法具有唯一性;而对于 p 中字符 + 星号的组合而言,它可以在 ss 中匹配任意自然数个字符,并不具有唯一性。因此我们可以考虑使用动态规划,对匹配的方案进行枚举。

我们用 f[i][j] 表示 s 的前 i 个字符与 p 中的前 j 个字符是否能够匹配。在进行状态转移时,我们考虑p 的第 j 个字符的匹配情况:

如果 p 的第 j 个字符是一个小写字母,那么我们必须在 s 中匹配一个相同的小写字母,即

也就是说,如果 s 的第 i 个字符与 p 的第 j 个字符不相同,那么无法进行匹配;否则我们可以匹配两个字符串的最后一个字符,完整的匹配结果取决于两个字符串前面的部分。

如果 p 的第 j 个字符是 *,那么就表示我们可以对 p 的第 j-1 个字符匹配任意自然数次。在匹配 0 次的情况下,我们有

如果我们通过这种方法进行转移,那么我们就需要枚举这个组合到底匹配了 s 中的几个字符,会增导致时间复杂度增加,并且代码编写起来十分麻烦。我们不妨换个角度考虑这个问题:字母 + 星号的组合在匹配的过程中,本质上只会有两种情况:

  • 匹配 s 末尾的一个字符,将该字符扔掉,而该组合还可以继续进行匹配;
  • 不匹配字符,将该组合扔掉,不再进行匹配

如果按照这个角度进行思考,我们可以写出很精巧的状态转移方程:

细节

动态规划的边界条件为f[0][0]=true,即两个空字符串是可以匹配的。最终的答案即为 f[m][n],其中 m 和 n 分别是字符串 s 和 p 的长度。由于大部分语言中,字符串的字符下标是从 0 开始的,因此在实现上面的状态转移方程时,需要注意状态中每一维下标与实际字符下标的对应关系。

在上面的状态转移方程中,如果字符串 p 中包含一个「字符 + 星号」的组合(例如 a),那么在进行状态转移时,会先将 a 进行匹配(当 p[j] 为 a 时),再将 a 作为整体进行匹配(当 p[j] 为 * 时)。然而,在题目描述中,我们必须将 a* 看成一个整体,因此将 a 进行匹配是不符合题目要求的。看来我们进行了额外的状态转移,这样会对最终的答案产生影响吗?这个问题留给读者进行思考。

# @lc code=start
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m=len(s)
        n=len(p)
        def matches(i:int,j:int)-> bool:
            if i == 0:
                return False
            if p[j - 1] == '.':
                return True
            return s[i - 1] == p[j - 1]
        f = [[False] * (n + 1) for _ in range(m + 1)]
        f[0][0]=True
        for i in range(m+1):
            for j in range(1, n + 1):
                if p[j - 1] == '*':
                   f[i][j] |= f[i][j - 2]
                   if matches(i, j - 1):
                        f[i][j] |= f[i - 1][j]
                else:
                    if matches(i, j):
                        f[i][j] |= f[i - 1][j - 1]
        return f[m][n]

leetcodeday11 —盛最多水的容器

本题用到的方法:双指针,在数组首尾部设两个指针,根据指针的值的大小,每次更新一个指针。

给你 n 个非负整数 a1,a2,...,an每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明:你不能倾斜容器。

方法1:暴力求解,遍历就完了

# @lc code=start
class Solution:
    def maxArea(self, height: List[int]) -> int:
        maxwarter=0
        for i in range(len(height)-1):
            j=i+1
            while j<=len(height)-1:
                new=min(height[i],height[j])*(j-i)
                maxwarter=maxwarter if new<maxwarter else new
                j=j+1
        return maxwarter
# @lc code=end

然而:超出时间限制了

官方方法:双指针

[1, 8, 6, 2, 5, 4, 8, 3, 7]

在初始时,左右指针分别指向数组的左右两端,它们可以容纳的水量为 min(1, 7) * 8 = 8。

此时我们需要移动一个指针。移动哪一个呢?直觉告诉我们,应该移动对应数字较小的那个指针(即此时的左指针)。这是因为,由于容纳的水量是由

两个指针指向的数字中较小值 * 指针之间的距离

决定的。如果我们移动数字较大的那个指针,那么前者「两个指针指向的数字中较小值」不会增加,后者「指针之间的距离」会减小,那么这个乘积会减小。因此,我们移动数字较大的那个指针是不合理的。因此,我们移动 数字较小的那个指针。

有读者可能会产生疑问:我们可不可以同时移动两个指针? 先别急,我们先假设 总是移动数字较小的那个指针 的思路是正确的,在走完流程之后,我们再去进行证明。

所以,我们将左指针向右移动:

[1, 8, 6, 2, 5, 4, 8, 3, 7]

此时可以容纳的水量为min(8,7)∗7=49。由于右指针对应的数字较小,我们移动右指针:

[1, 8, 6, 2, 5, 4, 8, 3, 7]

此时可以容纳的水量为 min(8,3)∗6=18。由于右指针对应的数字较小,我们移动右指针:

[1, 8, 6, 2, 5, 4, 8, 3, 7]

此时可以容纳的水量为min(8,8)∗5=40。两指针对应的数字相同,我们可以任意移动一个,例如左指针:

[1, 8, 6, 2, 5, 4, 8, 3, 7]

此时可以容纳的水量为min(6,8)∗4=24。由于左指针对应的数字较小,我们移动左指针,并且可以发现,在这之后左指针对应的数字总是较小,因此我们会一直移动左指针,直到两个指针重合。在这期间,对应的可以容纳的水量为:min(2,8)∗3=6,min(5,8)∗2=10,min(4,8)∗1=4。

在我们移动指针的过程中,计算到的最多可以容纳的数量为 49,即为最终的答案。

# @lc code=start
class Solution:
    def maxArea(self, height: List[int]) -> int:
        maxwarter=0
        i=0
        j=len(height)-1
        while i<j:
            new =min(height[i],height[j])*(j-i)
            maxwarter=new if new>maxwarter else maxwarter
            if height[i]>=height[j]:
               j=j-1
            else: i=i+1

        return maxwarter
# @lc code=end
晚安