Leetcode-review

Posted on Edited on In Views: Word count in article: 20k Reading time ≈ 36 mins.
索引

68. 文本左右对齐

68. 文本左右对齐 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
  def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
    ans=[]
    word_list=[]
    cur_len = 0
    for word in words:
      if cur_len + len(word) + len(word_list) > maxWidth:
        spaces = maxWidth - cur_len
        gaps = len(word_list) - 1
        if gaps == 0:
          line = word_list[0] + ' ' * spaces
        else:
          average,left = divmod(spaces,gaps)
          line = ''
          for i in range(gaps):
            line += word_list[i]
            line += average* ' '
            if i<left:
              line +=' '
          line += word_list[-1]
        ans.append(line)
        #initialize
        word_list = []
        cur_len = 0
      word_list.append(word)
      cur_len += len(word)
    #最后一行
    line = ' '.join(word_list)
    spaces = maxWidth - len(line)
    line += ' ' * spaces
    ans.append(line)
    
    return ans

一开始先写了处理溢出的情况，不过中间还需要先存储那些可以的word再合成一个line

思路就是一行一行读一行一行造，里面有一个问题是在这里

1
2
3
4
5
for i in range(gaps):
  line += word_list[i]
  line += average* ' '
  if i<left:
    line +=' '

这个i<left我想了很久

left是余数，i是中间有的空格-1，这边要的效果是把余数在前面的空里面填满

那假设有3个要填的，有四个空格，要填的i是0，1，2，此时left=3

5个要填的，有七个空格，要填的i是0，1，2，3，4，此时left=5

那很明显可以用i<left来限制

然后就造吧

392. 判断子序列

1
2
3
4
class Solution:
  def isSubsequence(self, s: str, t: str) -> bool:
    it = iter(t)
    return all(c in it for c in s)

迭代器神力，同时判断是不是在里面
同时使用all( )

68. 文本左右对齐

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
  def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
    ans=[]
    word_list=[]
    cur_len = 0
    for word in words:
      if cur_len + len(word) + len(word_list) > maxWidth:
        spaces = maxWidth - cur_len
        gaps = len(word_list) - 1
        if gaps == 0:
          line = word_list[0] + ' ' * spaces
        else:
          average,left = divmod(spaces,gaps)
          line = ''
          for i in range(gaps):
            line += word_list[i]
            line += average* ' '
            if i<left:
              line +=' '
          line += word_list[-1]
        ans.append(line)
        #initialize
        word_list = []
        cur_len = 0
      word_list.append(word)
      cur_len += len(word)
    #最后一行
    line = ' '.join(word_list)
    spaces = maxWidth - len(line)
    line += ' ' * spaces
    ans.append(line)
    
    return ans

思路：一行一行造
先根据数量造出一行的word_list,然后计算出来中间的gap,然后根据规则和divmod()同时整除和求余再分配空格,然后组装

1312. 让字符串成为回文串的最少插入次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
  def minInsertions(self, s: str) -> int:
    re_str=s[::-1]
    def longestCommonSubsequence(text1: str, text2: str) -> int:
      m = len(text1)
      n = len(text2)

      dp = [[0] * (n + 1) for _ in range(m + 1)]
      for i in range(1, m + 1):
        for j in range(1, n + 1):
          if text1[i - 1] == text2[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + 1
          else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
      return dp[m][n]

    return len(s)-longestCommonSubsequence(s,re_str)

套用了另外一道简单题目lcs，第一次涉及dp

如何求lcs

1
2
3
4
5
6
7
8
9
10
11
12
def longestCommonSubsequence(text1: str, text2: str) -> int:
  m = len(text1)
  n = len(text2)

  dp = [[0] * (n + 1) for _ in range(m + 1)]
  for i in range(1, m + 1):
    for j in range(1, n + 1):
      if text1[i - 1] == text2[j - 1]:
        dp[i][j] = dp[i - 1][j - 1] + 1
      else:
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
  return dp[m][n]

m = "abccdca"
n = "adcaab" lcs = “aca”`

情况一：两个字符串的最后一个字符相等
如果 text1[i-1] == text2[j-1]

  • 这意味着我们找到了一个公共字符！这个字符必然可以作为它们公共子序列的一部分。
  • 那么，text1 的前 i 个字符和 text2 的前 j 个字符的LCS，就等于它们各自去掉最后一个字符后的LCS长度再加1。
  • 用 dp 数组来表示就是：dp[i][j] = dp[i-1][j-1] + 1

举例： 求 “abc” 和 “adc” 的LCS。因为最后一个字符 ‘c’ 相等，问题就转化为求 “ab” 和 “ad” 的LCS长度，然后加1。

情况二：两个字符串的最后一个字符不相等
如果 text1[i-1] != text2[j-1]

  • 这意味着这两个不同的字符不可能同时出现在LCS的末尾。
  • 那么，我们就要在两种可能性中取一个较大值：
    1. text1 的前 i 个字符和 text2 的前 j-1 个字符的LCS长度（相当于把 text2 的最后一个字符扔掉，看看结果）。这个值就是 dp[i][j-1]。
    2. text1 的前 i-1 个字符和 text2 的前 j 个字符的LCS长度（相当于把 text1 的最后一个字符扔掉，看看结果）。这个值就是 dp[i-1][j]。
  • 我们取这两者中的最大值，因为它代表了更长的公共子序列。
  • 用 dp 数组来表示就是：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

这题看题解去吧,俺也懵懵的

3354. 使数组元素等于零 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
  def countValidSelections(self, nums: List[int]) -> int:
    num_sum= sum(nums)
    left_sum = 0
    ans = 0
    right_sum = num_sum
    for num in nums:
      if num == 0:
        if left_sum == right_sum:
          ans+=2
        elif left_sum - right_sum == 1 or right_sum - left_sum == 1:
          ans+=1
      else:
        left_sum+=num
        right_sum=num_sum-left_sum
    return ans


思路非常简单，发现题目根本没必要使用动态的想法

167. 两数之和 II - 输入有序数组 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
  def twoSum(self, numbers: List[int], target: int) -> List[int]:
    index1=0
    index2=0
    for index,num in enumerate(numbers):
      requirement=target-num
      if requirement in numbers:
        index1=index+1
        if num == requirement:
          index2 = numbers.index(requirement, index1) + 1
          return [index1, index2]
        else:
          index2 = numbers.index(requirement) +1
          return [index1,index2]

这是第一次ac代码，执行用时分布 5813ms 击败5.20%
没错高贵的O(n^2),那可得好好优化一下了

在这应该使用双指针来快速查找,避免多次遍历

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
  def twoSum(self, numbers: List[int], target: int) -> List[int]:
    left=0
    right=len(numbers)-1
    while left < right:
      cur_sum=numbers[left]+numbers[right]
      if cur_sum==target:
        return [left+1,right+1]
      elif cur_sum < target:
        left+=1
      else:
        right-=1

该方法时间复杂度为O(n) 执行用时分布 4ms 击败50.86%
奇怪，为什么一样的算法他们能跑到0ms的，是我没充钱吗？

11. 盛最多水的容器 - 力扣（LeetCode）

贪心双指针一遍过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
  def maxArea(self, height: List[int]) -> int:
    max_volume=0
    left=0
    right=len(height)-1
    while(left!=right):
      x=right-left
      y=min(height[left],height[right])
      v=x*y
      if v>max_volume:
        max_volume=v
      if height[left]>=height[right]:
        right-=1
      else:
        left+=1
    return max_volume

15. 三数之和 - 力扣（LeetCode）

这是第一版🔟山,最后tle了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution:
  def threeSum(self, nums: List[int]) -> List[List[int]]:
    if len(nums) < 3:
      return []
    sorted_nums = sorted(nums)
    count = 0
    for num in sorted_nums:
      if num < 0:
        count += 1
    nums1 = sorted_nums[:count]
    nums2 = sorted_nums[count:]
    if not nums1 or not nums2:
      if sorted_nums.count(0) >= 3:
        return [[0, 0, 0]]
      return []
    ans = []
    seen = []
    for i in nums1:
      for j in nums2:
        k = -i - j
        if k not in sorted_nums:
          continue
        if [i, j, k].count(i) > sorted_nums.count(i):
          continue
        if [i, j, k].count(j) > sorted_nums.count(j):
          continue
        if [i, j, k].count(k) > sorted_nums.count(k):
          continue

        triple = sorted([i, j, k])
        if triple not in seen:
          seen.append(triple)
          ans.append(triple)

    if sorted_nums.count(0) >= 3:
      ans.append([0, 0, 0])
    return ans

这是高贵的O(n^3)算法，暴力的后果还是被卡了啊，同时内存也多到爆炸，于是想到三指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
  def threeSum(self, nums: List[int]) -> List[List[int]]:
    ans=[]
    nums.sort()
    n=len(nums)
    for i in range(n-2):
      if i > 0 and nums[i]==nums[i-1]:
        continue
      left=i+1
      right=n-1
      while left < right:
        s = nums[i]+nums[left]+nums[right]
        if s==0:
          ans.append([nums[i],nums[left],nums[right]])
          while left < right and nums[left]==nums[left+1]:
            left+=1
          while left < right and nums[right]==nums[right-1]:
            right-=1
          left+=1
          right-=1
        elif s<0:
          left+=1
        else:
          right-=1
    return ans

209. 长度最小的子数组 - 力扣（LeetCode）

滑动窗口初尝试，好像不难，和双指针很像了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
  def minSubArrayLen(self, target: int, nums: List[int]) -> int:
    n=len(nums)
    ans=n+1
    s=0
    left=0
    for right,num in enumerate(nums):
      s+=num
      while s>=target:
        ans=min(ans,right-left+1)
        s-=nums[left]
        left+=1
    if ans==n+1:return 0
    return ans

3. 无重复字符的最长子串 - 力扣（LeetCode）

滑动窗口+hashmap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
  def lengthOfLongestSubstring(self, s: str) -> int:
    start = 0
    seen = set()
    maxlen = 0

    for end in range(len(s)):
      while s[end] in seen:
        seen.remove(s[start])
        start += 1
      seen.add(s[end])
      maxlen = max(maxlen, end - start + 1)
  
    return maxlen

和LCR 167. 招式拆解 I - 力扣（LeetCode）是一样的，因此一起过了

30. 串联所有单词的子串 - 力扣（LeetCode）

一开始思路不好，神秘的O(n!xn)算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
  def generate_permutations(self,words:str) -> List[str]:
    if len(words) == 1:
      return words
    res = []
    for i in range(len(words)):
      first = words[i]
      rest = words[:i] + words[i+1:]
      for sub in self.generate_permutations(rest):
        res.append(first + sub)
    return res

  def findSubstring(self, s: str, words: List[str]) -> List[int]:
    sub_words = set(self.generate_permutations(words))
    l=len(s)
    window = len(words[0]) * len(words)
    if window > len(s): return []
    ans=[]
    for start in range(0, len(s) - window + 1): 
      if s[start : start + window] in sub_words:
        ans.append(start)
    return ans

124 / 182 个通过的测试用例
提交于 2025.10.30 21:35
s ="fffffffffffffffffffffffffffffffff"
words =["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"]
很明显会因为生成子串的过程太长导致tle
所以换一个思路，把words用键值对一一对应

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
  def findSubstring(self, s: str, words: List[str]) -> List[int]:
    if not s or not words:
      return []
    word_len = len(words[0]) 
    total_len = word_len * len(words)
    word_map = {w: words.count(w) for w in words} 
    ans = []
    n = len(s)
    for i in range(0, n - total_len + 1):
      seen = {}
      j = 0    
      while j < len(words):
        word_start = i + j * word_len
        word_end = word_start + word_len
        word = s[word_start:word_end]
        if word not in word_map:
          break
        seen[word] = seen.get(word, 0) + 1
        if seen[word] > word_map[word]:
          break
        j += 1
      if j == len(words):
        ans.append(i)
    return ans

30. 串联所有单词的子串 - 力扣（LeetCode）
这测试点诗人啊
181 / 182 个通过的测试用例

ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
  def findSubstring(self, s: str, words: List[str]) -> List[int]:
    if not s or not words:
      return []
    word_len = len(words[0])
    total_len = word_len * len(words)
    word_map = {w: words.count(w) for w in words}
    ans = []
    n = len(s)
    for offset in range(word_len):
      left = offset
      seen = {}
      count = 0
      for right in range(offset, n - word_len + 1, word_len):
        word = s[right:right+word_len]
        if word in word_map:
          seen[word] = seen.get(word, 0) + 1
          count += 1
          while seen[word] > word_map[word]:
            left_word = s[left:left+word_len]
            seen[left_word] -= 1
            left += word_len
            count -= 1
          if count == len(words):
            ans.append(left)
        else:
          seen.clear()
          count = 0
          left = right + word_len
    return ans

最快的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
  def findSubstring(self, s: str, words: List[str]) -> List[int]:
    n = len(s)
    step = len(words[0])
    total_len = step * len(words)
    res = []
    for i in range(step):
      map_word_cnt = {}
      for word in words:
        if word not in map_word_cnt:
          map_word_cnt[word] = 1
        else:
          map_word_cnt[word] += 1
      match_cnt = len(words)
      right = i
      while right + step - 1 < n:
        left = right + step - total_len
        left_out = left - step
        if left_out >= 0:
          w_left_out = s[left_out:left_out+step]
          if w_left_out in map_word_cnt:
            map_word_cnt[w_left_out] += 1
            if map_word_cnt[w_left_out] > 0:
              match_cnt += 1
        w_right = s[right:right+step]
        if w_right in map_word_cnt:
          map_word_cnt[w_right] -= 1
          if map_word_cnt[w_right] >= 0:
            match_cnt -= 1
        if left >= 0 and match_cnt == 0:
          res.append(left)
        right += step
    return res

76. 最小覆盖子串 - 力扣（LeetCode）

滑动窗口 哈希表

如果min_len=len(s)会导致维护出错

使用哈希表还是不熟练
.items()忘了

还有一个注意点是切片，切片左闭右开 [left , right + 1) 老记错
right-left+1 是长度

滑动窗口从窗口为零开始，向右扩张，同时维护window_counts ，一边向右添加一边保持左边没有额外的字符
就这样遍历，复杂度O(N) 600ms 击败44.06%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution:
  def count(self, t: str) -> dict:
    t_count = {}
    for char in t:
      if char in t_count:
        t_count[char] += 1
      else:
        t_count[char] = 1
    return t_count

  def check(self, current_dict: dict, t_count: dict) -> bool:
    for char, required_count in t_count.items():
      if current_dict.get(char, 0) < required_count:
        return False
    return True

  def minWindow(self, s: str, t: str) -> str:
    t_count = self.count(t)
    window_counts = {}
    left = 0
    min_len = len(s) + 1
    result = ""

    for right in range(len(s)):
      char_in = s[right]
      window_counts[char_in] = window_counts.get(char_in, 0) + 1

      while self.check(window_counts, t_count):
        current_len = right - left + 1
        if current_len < min_len:
          min_len = current_len
          result = s[left : right + 1]

        char_out = s[left]
        window_counts[char_out] -= 1

        if window_counts[char_out] == 0:
          del window_counts[char_out]

        left += 1
    return result

这次想法里面的问题所在是这块

1
2
3
4
5
def check(self, current_dict: dict, t_count: dict) -> bool:
  for char, required_count in t_count.items(): 
    if current_dict.get(char, 0) < required_count:
      return False
  return True

这个循环的次数取决于 t 中有多少个 不重复 的字符
但是如果字典有27个字符的时候就很明显不合理了
而且check了非常非常多次，也浪费了很多的时间
看看这个代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
  def minWindow(self, s: str, t: str) -> str:
    need=defaultdict(int)
    for c in t:
      need[c]+=1
    needCnt=len(t)
    i=0
    res=(0,float('inf'))
    for j,c in enumerate(s):
      if need[c]>0:
        needCnt-=1
      need[c]-=1
      if needCnt==0:
        while True:
          c=s[i]
          if need[c]==0:
            break
          need[c]+=1
          i+=1
        if j-i<res[1]-res[0]:
          res=(i,j)
        need[s[i]]+=1
        needCnt+=1
        i+=1
    return ''if res[1]>len(s) else s[res[0]:res[1]+1]

在这边发现了defaultdict，这才知道leetcode已经import过了collections
那这块内容需要好好学一学,写到Python-algorithm去

36. 有效的数独 - 力扣（LeetCode）

这题只要判断是否合理，不需要解出来数独其实还好
一次遍历就行了
用set来创建集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
  def isValidSudoku(self, board: List[List[str]]) -> bool:
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
        
    for i in range(0,9):
      for j in range(0,9):
        num = board[i][j]
        if num == '.':
          continue
        if num in rows[i]:
          return False
        rows[i].add(num)
        if num in cols[j]:
          return False
        cols[j].add(num)

        box_index = (i // 3) * 3 + (j // 3)
        if num in boxes[box_index]:
          return False
        boxes[box_index].add(num)
    return True

54. 螺旋矩阵 - 力扣（LeetCode）

我的思路是用上下左右限制，有点复杂，维护起来也好累。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
  def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
    if not matrix or not matrix[0]:
      return []
    ans = []
    num_rows = len(matrix)
    num_cols = len(matrix[0])

    left, right = 0, num_cols - 1
    top, bottom = 0, num_rows - 1

    while left <= right and top <= bottom:
      for col in range(left, right + 1):
        ans.append(matrix[top][col])
      top += 1
      for row in range(top, bottom + 1):
        ans.append(matrix[row][right])
      right -= 1
      if not (left <= right and top <= bottom):
        break
      for col in range(right, left - 1, -1):
        ans.append(matrix[bottom][col])
      bottom -= 1
      for row in range(bottom, top - 1, -1):
        ans.append(matrix[row][left])
      left += 1
    return ans

但看官方第二种解法是这样的
对于每层，从左上方开始以顺时针的顺序遍历所有元素。假设当前层的左上角位于 (top,left)，右下角位于 (bottom,right)，按照如下顺序遍历当前层的元素。

从左到右遍历上侧元素，依次为 (top,left) 到 (top,right)。

从上到下遍历右侧元素，依次为 (top+1,right) 到 (bottom,right)。

如果 left<right 且 top<bottom，则从右到左遍历下侧元素，依次为 (bottom,right−1) 到 (bottom,left+1)，以及从下到上遍历左侧元素，依次为 (bottom,left) 到 (top+1,left)。

遍历完当前层的元素之后，将 left 和 top 分别增加 1，将 right 和 bottom 分别减少 1，进入下一层继续遍历，直到遍历完所有元素为止。

48. 旋转图像 - 力扣（LeetCode）

想法很多都不好实现。
没写，但是看到了一个逆天答案

1
2
3
4
class Solution:
  def rotate(self, matrix: List[List[int]]) -> None:
    matrix[:] = list(map(list, zip(*matrix)))
    for row in matrix: row.reverse()

73. 矩阵置零 - 力扣（LeetCode）

思路非常简单，找到0的位置，然后直接改，这题目凭什么是中档题？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
  def setZeroes(self, matrix: List[List[int]]) -> None:
    """
    Do not return anything, modify matrix in-place instead.
    """
    rows = len(matrix)
    cols = len(matrix[0])
    temp = []
    for i in range(rows):
      for j in range(cols):
        if matrix[i][j] == 0:
          temp.append([i, j])

    for r, c in temp:
      for j in range(cols):
        matrix[r][j] = 0
      for i in range(rows):
        matrix[i][c] = 0

但由于使用了temp存储，导致空间复杂度为O(M+N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
  def setZeroes(self, matrix: List[List[int]]) -> None:
    m, n = len(matrix), len(matrix[0])
    flag_col0 = False
    
    for i in range(m):
      if matrix[i][0] == 0:
        flag_col0 = True
      for j in range(1, n):
        if matrix[i][j] == 0:
          matrix[i][0] = matrix[0][j] = 0
    
    for i in range(m - 1, -1, -1):
      for j in range(1, n):
        if matrix[i][0] == 0 or matrix[0][j] == 0:
          matrix[i][j] = 0
      if flag_col0:
        matrix[i][0] = 0

这个是leetcode官方给出的空间复杂度为O(1)的算法
如果 matrix[i][j]是 0，它就把这个信息记录在 matrix[i][0]和 matrix[0][j] 上，将它们也设置为 0。
这样一来，matrix[i][0]就成了第 i 行是否需要置零的标记位。
同理，matrix[0][j]就成了第 j 列是否需要置零的标记位。
很巧妙的直接使用原矩阵在不破坏的情况下标记并且置零，不额外开空间

289. 生命游戏 - 力扣（LeetCode）

充满小巧思了
第一个小巧思是使用元组来传neighbor,然后python会自动解包，写起来好看
第二个小巧思是要判断当前状态：状态 1 和 2 都代表“原来是活的”，状态 0 和 3 都代表“原来是死的”
这样区分避免出现在修改过程中误判的情况，最后第二次遍历把状态再修正
和官方第二个题解差不多，但是官方只用到2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
  def gameOfLife(self, board: List[List[int]]) -> None:
    """
    Do not return anything, modify board in-place instead.
    """
    m, n = len(board), len(board[0])
    neighbors = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]
    for i in range(m):
      for j in range(n):
        alive = 0
        for dx, dy in neighbors:
          r, c = i + dx, j + dy
          if 0 <= r < m and 0 <= c < n:
            if board[r][c] == 1 or board[r][c] == 2:
              alive += 1
        if board[i][j] == 1 and (alive < 2 or alive > 3):
          board[i][j] = 2 
        elif board[i][j] == 0 and alive == 3:
          board[i][j] = 3
    
    for i in range(m):
      for j in range(n):
        if board[i][j] == 2:
          board[i][j] = 0
        elif board[i][j] == 3:
          board[i][j] = 1

383. 赎金信 - 力扣（LeetCode）

用Counter自动计数
然后直接在本体上操作就行

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
  def canConstruct(self, ransomNote: str, magazine: str) -> bool:
    if len(ransomNote) > len(magazine):
      return False
    magazine_counts = Counter(magazine)
    
    for char in ransomNote:
      if magazine_counts[char] > 0:
        magazine_counts[char] -= 1
      else:
        return False
        
    return True

这样写也可以

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
  def canConstruct(self, ransomNote: str, magazine: str) -> bool:
    if len(ransomNote)>len(magazine) or len(set(magazine)) < len(set(ransomNote)):
      return False
    count = {}
    for i in magazine:
      count[i] = count.get(i,0)+1
    for i in ransomNote:
      if count.get(i, 0) == 0:
        return False
      count[i] -= 1
    return True

205. 同构字符串 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
  def isIsomorphic(self, s: str, t: str) -> bool:
    if len(s)!=len(t):
      return False
    s2tdict={}
    t2sdict={}
    for sstr,tstr in zip(s,t):
      if sstr in s2tdict and s2tdict[sstr]!=tstr:
        return False
      if tstr in t2sdict and t2sdict[tstr]!=sstr:
        return False
      s2tdict[sstr]=tstr
      t2sdict[tstr]=sstr
    return True

但是zip()用法太别致了吧

1
2
3
class Solution:
  def isIsomorphic(self, s: str, t: str) -> bool:
    return len(set(s)) == len(set(t)) == len(set(zip(s, t)))

被吓哭了
也许应该复习一下set()和zip()
set(t)创建的是t中所有不重复字符的集合
zip(s, t) 会生成一系列的配对元组（tuple）：
(‘p’, ‘t’), (‘a’, ‘i’), (‘p’, ‘t’), (‘e’, ‘l’), (‘r’, ‘e’)
这些配对就代表了 s 到 t 的映射关系。例如，第一个 ‘p’ 映射到 ‘t’，‘a’ 映射到 ‘i’，第二个 ‘p’ 也映射到 ‘t’。
因此映射和set()长度相同的情况下就可以得出结论

290. 单词规律 - 力扣（LeetCode）

和上一题同一个道理

1
2
3
4
5
class Solution:
  def wordPattern(self, pattern: str, s: str) -> bool:
    s2list=s.split(" ")
    p2list=list(pattern)
    return len(s2list)==len(p2list) and len(set(zip(s2list,p2list)))==len(set(s2list))==len(set(p2list))

思路：s2list和p2list
首先两个长度要相等
然后要保证set出来的长度也相同
eg:
“abba”“wow mom mom wow”
set(list(“abba”))={“a”,“b”}
set(list(“wow mom mom wow”.split(" ")))={“wow”,“mom”}
set(zip(s2list,p2list))={(“a”,“wow”),(“b”,“mom”)}

242. 有效的字母异位词 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
class Solution:
  def isAnagram(self, s: str, t: str) -> bool:
    s2list=list(s)
    t2list=list(t)
    scounter=Counter(s2list)
    tcounter=Counter(t2list)
    if scounter==tcounter:
      return True
    return False

其实"str"可以直接到Counter里面去使用
直接return Counter(t)==Counter(s)就结束了
或者也可以使用sorted(),return sorted(t)==sorted(s)

49. 字母异位词分组 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
class Solution:
  def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
    anagram_map = defaultdict(list)
    for s in strs:
      sorted_s=str(sorted(s))
      anagram_map[sorted_s].append(s)
      
    return list(anagram_map.values())

复杂度是O(Nklogk)，有点高了

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
  def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
    if len(strs) == 1:
      return [strs]
    ans= {}
    for ss in strs:
      s = str(sorted(ss))
      if s not in ans : 
        ans[s] = [ss]
      else :
        ans[s].append(ss)

    return list(ans.values())

这样一个道理

1
2
3
4
5
6
7
8
9
class Solution:
  def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
    mp = collections.defaultdict(list)

    for str in strs:
      key=''.join(sorted(str))
      mp[key].append(str)

    return list(mp.values())

1. 两数之和 - 力扣（LeetCode）

哈希

1
2
3
4
5
6
7
8
9
class Solution:
  def twoSum(self, nums: List[int], target: int) -> List[int]:
    num_map = {}
    for i, num in enumerate(nums):
      complement = target - num
      if complement in num_map:
        return [num_map[complement], i]
      num_map[num] = i
    return []Q

202. 快乐数 - 力扣（LeetCode）

第一版
371 / 420 个通过的测试用例

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
  def isHappy(self, n: int) -> bool:
    while n/10>1:
      if n==1:
        return True
      sum=0
      n2str=str(n)
      for num in n2str:
        sum+=(int(num))**2
      n=sum
      if n==1:
        return True
    return False

while那边的判断条件写错了，看到测试用例7,在一开始就返回false了，但是迭代到最后是可以到1的

第二版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
  def isHappy(self, n: int) -> bool:
    seen = set()
    while n != 1 and n not in seen:
      seen.add(n)

      total_sum = 0
      n2str = str(n)
      for digit in n2str:
        total_sum += int(digit) ** 2

      n = total_sum

    return n==1

时间复杂度O(Log(N))，7ms在这个题目里算最慢的一档了

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
  def isHappy(self, n: int) -> bool:
    result = []
    while n not in result:
      result.append(n)
      s = 0
      for i in str(n):
        s+=int(i)**2
      if s == 1:
        return True
      n = s
    return False

4ms
稍微快了一些

219. 存在重复元素 II - 力扣（LeetCode）

思路：用map存，时间复杂度O(N)，

1
2
3
4
5
6
7
8
class Solution:
  def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
    num_map={}
    for i, num in enumerate(nums):
      if num in num_map and i - num_map[num] <= k:
        return True
      num_map[num] = i
    return False

官方第二个滑动窗口
思路是维护k+1大小的set

1
2
3
4
5
6
7
8
9
10
11
class Solution:
  def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
    s = set()
    for i, num in enumerate(nums):
      if i > k:
        s.remove(nums[i - k - 1])
      if num in s:
        return True
      s.add(num)
    return False

128. 最长连续序列 - 力扣（LeetCode）

思路：去重，然后迭代，哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
  def longestConsecutive(self, nums: List[int]) -> int:
    num_set = set(nums)
    longest_streak = 0
    for num in num_set:
      if num - 1 not in num_set:
        current_num = num
        current_streak = 1
        while current_num + 1 in num_set:
          current_num += 1
          current_streak += 1
        longest_streak = max(longest_streak, current_streak)
    return longest_streak