leetcode 第二天 2024.3.6

1. 长度最小的子数组：

 题目链接: 209. 长度最小的子数组 - 力扣（LeetCode）

应用条件：滑动窗口，双指针

难点：第一次看题时根本想不到滑动窗口。想到了双指针但没有具体的实现思路，想不到可以用第二个指针end来进行循环遍历，end这个指针才是最关键的，不用用第一个指针start进行遍历，因为用start进行遍历，我们不知道应该在哪里停下，start指向每一个元素的时候，我们不能找以这个元素开头的所有子数组，这样和两个for循环暴力解题没有区别了.

个人错误：

1.想不到滑动窗口啊，好难想，看到题目根本没有这个思路，只能想到两个for循环。

2.同时，在寻找最小长度时，当while条件不满足时，上一次循环已经将start += 1 了，在这次循环开始，end也 + 1 所以并不会出现问题，做题时候想不明白这个逻辑，导致对初始summ应该写在哪混淆，初始summ就定义在end循环开始前，虽然后面end增加后可能summ不为零，start也不为零，但并不影响，在内置while中summ小于target时，end会再增加，summ会在原来的基础上加nums中end这个数，直到summ再次大于target时，再对start进行操作判断.

思路： end遍历整个数组元素，前面的所有数之和大于等于target则再用第一个指针start对前面所有的数从第一个开始进行递减，用一个summ代表start到end中间这个数组的所有数之和，判断summ与target大小，大于等于target的时候，start++ start向end靠近，找到满足条件时最小的数组。

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        res = float('inf')
        start = 0
        summ = 0
        for end in range(len(nums)):
            summ = summ + nums[end]
            while summ >= target:
                subl = end - start + 1
                res = min(res,subl)
                summ = summ - nums[start]
                start += 1
        if res == float('inf'):
            return 0
        else:
            return res

2. 替换后的最长重复字符：

 题目链接: 424. 替换后的最长重复字符 - 力扣（LeetCode）

应用条件：双指针

难点：由于上午做了上一题，做这道题时候想到了要用双指针，但又想不出具体的实现方式，也想到了用end指针然后往前查，但没想到只用管两指针数组中出现次数最多的数就好了，当时想着如果出现次数最多的数满足不了要计算出现次数第二多的数看能不能满足条件，可实际上这么考虑太琐碎，不需要管出现次数第二多的数，只需要在right右指针右移操作后，通过左指针的右移，左指针++的同时更新各个字母出现的次数，左指针left ++ 前 在记录字母出现次数的dic中，先把此时此刻左指针指向的字母的出现次数-1，再对左指针进行++操作。

个人错误：

1.想到双指针但没做出来，想不到左指针向右滑动的过程中更新记录次数的dic。想着没次滑动指针的时候重新对整个子数组进行出现次数的dic计算，其实不需要，只要在左右指针更新位置的同时更新原来存在的dic就可以了。

思路： right遍历整个数组元素的同时在dic中记录每个字母出现的次数，每次遍历中对right到left这段字母进行判断，判断这段字母长度 - 其中出现次数最多的字母的出现次数 会不会比k多，如果比k多则说明不满足条件，我们需要将left++ 来缩短这段字母的总长度，同时在left右移的同时也要注意更新记录字母出现次数的dic中的数据，这样可以满足在这段字母中出现次数最多的字母就是我们要找的，虽然可能和前一次遍历中出现次数最多的字母不一样，但就是我们要找的。

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        left = 0
        dic={}
        res = float('-inf') 
        for right in range(len(s)):
            if s[right] in dic:
                dic[s[right]]+=1
            else:
                dic[s[right]] = 1
            while (right - left +1 - max(dic.values())) > k:
                dic[s[left]] -= 1
                left += 1
                 
            res = max(res,(right - left +1))
        if res != float('-inf'):
            return res
        else:
            return 0

3. 字符串转化整数：

 题目链接: 8. 字符串转换整数 (atoi) - 力扣（LeetCode）

应用条件：正则表达式

难点：对于正则表达式，我们可以先编译正则表达式对象，用  正则表达式对象= re.compile(表达式)， 然后再调用正则表达式对象中的.findall(string) 函数进行正则，这样做的好处是当你需要多次使用同一个正则表达式时，先编译它可以提升性能。当然也可以直接用re.findall(patten,string)直接正则。对于正则表达式的编写，

• .: 匹配任何单个字符，除了换行符。
• ^: 匹配字符串的开始。
• $: 匹配字符串的结束。
• *: 前面的字符可以出现零次或多次。
• +: 前面的字符至少出现一次。
• ?: 前面的字符可以出现零次或一次。
• \d: 匹配任何数字，等价于[0-9]。
• \w: 匹配任何字母数字字符，等价于[a-zA-Z0-9_]。
• \s: 匹配任何空白字符。

  本题中r'^[\+\-]?\d+'注意+ - 在正则表达式中有多重含义，我们只是要它代表正负，我们不需要考虑它在正则中的含义，所以前面带上了转译符\.

  注意 .findall()方法返回的是一个list

  而也可以中re.match方法，这样返回的是一个一个匹配Match对象，可以用match.group(1)输出第一个捕获组匹配的字符串，或者match.group(0)输出整个匹配的字符串， match.group(0)输出整个匹配的字符串. 

  在用re.match时候，需要在正则表达式中用（）标注捕获组，例如本题r'^([\+\-]?\d+)' 这里放在括号内的[\+\-]?\d+，表示我们对匹配这部分特别感兴趣，将其捕获  。 

  个人错误：

  一看到这个题就想到正则，但不会写正则表达式，对怎么应用正则也不是很精通所以做不出来.

  思路： 先用s.lstrip()去除左边的空格，（.rstrip()去除右边的，.strip()去除所有的，）然后再写正则表达式，返回出list后取第一个元素，将其转化为int，最后别忘记判断边界值。注释部分为用match做.

  class Solution:
      def myAtoi(self, s: str) -> int:
          Imax = 2**31 - 1
          Imin = -2**31
          strs = s.lstrip()
          num_re = re.compile(r'^[\+\-]?\d+')
          # num_re = re.compile(r'^([\+\-]?\d+)')
          # match = num_re.match(strs)
          # if not match:
          #     return 0
          # nums = int(match.group(1))
          nums = num_re.findall(strs)
          if len(nums) ==0:
              return 0
          else:
              num = int(nums[0])

  4. 回文对：

   题目链接: 424. 替换后的最长重复字符 - 力扣（LeetCode）336. 回文对 - 力扣（LeetCode） 424. 替换后的最长重复字符 - 力扣（LeetCode）

  应用条件：哈希表加前后缀

  难点：想不到前后缀的使用，把words里的每一个word都分成前缀和后缀两个词，如果前缀的逆序在字典，且不是自身，并且后缀是回文，则存在配对。如果后缀的逆序在字典，且不是自身，并且前缀是回文，则存在配对。注意要遍历整个word，使得每一个前缀和后缀都查找到。

  个人错误：

  想不到这么绝妙的方法。

  思路： 创建dic key为每个单词word，value为word在words中对应的索引。再次遍历整个words，对于每个单词word，将其分成before和after两截，遍历word，确保把所有的前后缀都考虑进去，每一次划分前后缀，对before和after都进行判断，如果前缀的逆序在字典，且不是自身，并且后缀是回文，将这个单词索引以及前缀逆序索引加入res。或者后缀的逆序在字典，且不是自身，并且前缀是回文，将后缀逆序索引以及这个单词索引加入res.

  class Solution:
      def palindromePairs(self, words: List[str]) -> List[List[int]]:
          res = []
          dic = {}
          for i, word in enumerate(words):
              dic[word] = i
          for i, word in enumerate(words):
              for j in range(len(word)+1):
                  before = word[:j]
                  after = word[j:]
                  if before[::-1] in dic and dic[before[::-1]] != i and after == after[::-1]:
                      res.append([i,dic[before[::-1]]])
                  if j > 0 and after[::-1] in dic and dic[after[::-1]] != i and before == before[::-1]:
                      res.append([dic[after[::-1]],i])
          return res