1

2221 三角和

第一眼看题完全没想法呃(⊙o⊙)…原来是不断的替代😥

1
2
3
4
5
6
class Solution(object):
    def triangularSum(self, nums):
        for n in range(len(nums) - 1, 0, -1):
            for i in range(n):
                nums[i] = (nums[i] + nums[i + 1]) % 10
        return nums[0]

2

49 字母异位词分组

  1. 哈希

  2. defaultdict 是 Python 标准库 collections 模块中的一个类，它是内置 dict 类的子类，主要用于简化字典中缺失键的处理。

与普通字典不同，defaultdict 在初始化时需要指定一个默认工厂函数（如 list、int、set 等），当访问字典中不存在的键时，会自动调用该工厂函数创建一个默认值，而不是抛出 KeyError 异常。

类似 if key not in d: d[key] = []

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

3

128 最长连续序列

集合的 O (1) 时间复杂度查找 特性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        s = set(nums)
        length = 0
        for x in s:
            if x-1 not in s:
                y = x
                z = 1
                while y + 1 in s:
                    y += 1
                    z += 1
                length = max(length, z)
    
        return length

还有是直接删掉元素，s.remove(y)也是实现了减小了时间复杂度

4

11 乘最多水的容器

双指针 移动短的

我只能想到用两个for循环，但是这样子的话时间复杂度就不满足了::>_<::

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def maxArea(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        area = 0
        while left < right:
            width = right - left
            h = min(height[left], height[right])
            a = width * h
            area = max(a, area)
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return area

5

15 三数之和

1
2
3
4
5
6
7
8
9
10
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        result=set()
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                for k in range(j+1,len(nums)):
                    if nums[i] + nums[j] + nums[k] == 0:
                        triplet=tuple(sorted([nums[i], nums[j], nums[k]]))
                        result.add(triplet)
        return [list(triplet) for triplet in result]

超出了时间限制直观但是数据量大的时候性能不行

主要是去重比较难想吧去网上搜了一下

排序+双指针

  1. 排序
  2. 遍历
  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
26
27
28
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        n, res = len(nums), []
        if(not nums or n<3):
            return []

        for i in range(n):
            if(nums[i]>0):
                return res
            if(i>0 and nums[i]==nums[i-1]):
                continue
            L=i+1
            R=n-1
            while(L<R):
                if(nums[i]+nums[L]+nums[R]==0):
                    res.append([nums[i],nums[L],nums[R]])
                    while(L<R and nums[L]==nums[L+1]):
                        L=L+1
                    while(L<R and nums[R]==nums[R-1]):
                        R=R-1
                    L=L+1
                    R=R-1
                elif(nums[i]+nums[L]+nums[R]>0):
                    R=R-1
                else:
                    L=L+1
        return res

6

42 接雨水

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
if not height:return 0
        n = len(height)
        left,right = 0,n-1 # 定义左指针，右指针，分别是从最左和最右开始
        maxleft,maxright = height[0],height[n-1] 
        ans = 0
 
        while left <= right: # 当左边指针<=右指针时
            maxleft = max(height[left],maxleft) # 左边最长柱子
            maxright = max(height[right],maxright) # 右边最长柱子
            if maxleft < maxright: # 当左边最长柱子 < 右边最长柱子
                ans = ans + maxleft - height[left] # 左边最长柱子减去当前指针所在的柱子的高度就是能接到多少雨水，不理解的看图比较
                left += 1 # 因为右边柱子比较长，所以我们把左指针往右移动
            else: # 如果左边最大柱子>=右边最大柱子
                ans = ans + maxright - height[right] # 右边最长柱子减去当前柱子的高度就是能接到多少雨水
                right -= 1 # 右指针往左移动
        return ans