这个文档仅用于记录leetcode热题100的记录，重点记录我这个菜鸡认为惊为天人的解题思路。

1.【哈希】两数之和

题面

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

solution：暴力题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:

    def twoSum(self, nums: List[int], target: int) -> List[int]:

        res=[]

        for i in range(len(nums)):

            for j in range(i+1,len(nums)):

                if (nums[i]+nums[j]==target):

                    res.append(i)

                    res.append(j)

        return res

2.【哈希】异位字符

题面

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

Solution：defultdict

将排序后的字符当作键，遍历所有字符串，符合要求的存为值。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:

    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:

        anagramdict=defaultdict(list)

        for s in strs:

            key="".join(sorted(s))

            anagramdict[key].append(s)

        return list(anagramdict.values())

3.【哈希】最长连续序列

题面

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

Solution 遍历

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
def longestConsecutive(self, nums: List[int]) -> int:

        num_set = set(nums)  # 去重并存入集合

        max_length = 0

        for num in num_set:

            # 检查是否是连续序列的起点

            if num - 1 not in num_set:

                current_num = num

                current_length = 1

                # 向后扩展序列

                while current_num + 1 in num_set:

                    current_num += 1

                    current_length += 1

                # 更新最长长度

                max_length = max(max_length, current_length)

        return max_length

4.【动态规划】爬楼梯

题面

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

Solution

动态规划自底向上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:

    def climbStairs(self, n: int) -> int:

        if n==1:

            return 1

        dp=[0]*(n+1)

        dp[0]=0

        dp[1]=1

        dp[2]=2

        for i in range(3,n+1):

            dp[i]=dp[i-1]+dp[i-2]

        return dp[n]

5.【动态规划】杨辉三角

题面

 给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:

    def generate(self, numRows: int) -> List[List[int]]:

        triangle=[]

        for i in range(numRows):

            num_row=[1]*(i+1)

            for j in range(1,i):

                num_row[j]=triangle[i-1][j-1]+triangle[i-1][j]

            triangle.append(num_row)

        return triangle

6.【双指针】移动0

题面

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。请注意 ，必须在不复制数组的情况下原地对数组进行操作。

Solution：

双指针，i用来遍历所有元素，j寻找放置非0的位置，然后再一次循环把剩下的位置置为0

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 moveZeroes(self, nums: List[int]) -> None:

        """

        Do not return anything, modify nums in-place instead.

        """

        j=0

        for i in range(len(nums)):

            if nums[i]!=0:

                nums[j]=nums[i]

                j+=1

        for i in range(j,len(nums)):

            nums[i]=0

        return nums

7.【双指针】乘最多水的容器

题面

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

Solution

设置双指针，左右各一。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        j=0
        for i in range(len(nums)):
            if nums[i]!=0:
                nums[j]=nums[i]
                j+=1

        for i in range(j,len(nums)):
            nums[i]=0
        return nums

8.【双指针】三数之和

题面：

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

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

Solution：

双指针之前排序，固定第一个数nums[i]为结果中的第一个数（这个数的结果等于另外两个数求和取负），然后在剩下的元素中设置双指针挨个寻找符合要求的数，相同则跳过。

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
43
44
45
46
47
48
49
class Solution:

    def threeSum(self, nums: List[int]) -> List[List[int]]:

        res=[]

        nums.sort()

        for i in range(len(nums)-2):

            if i>0 and nums[i]==nums[i-1]:

                continue

            target=-nums[i]

            left=i+1

            right=len(nums)-1

            while left<right:

                current_sum=nums[left]+nums[right]

                if current_sum==target:

                    res.append([nums[i],nums[left],nums[right]])

                    left+=1

                    right-=1

                    while left<right and nums[left]==nums[left-1]:

                        left+=1

                    while left<right and nums[right+1]==nums[right]:

                        right-=1

                elif current_sum < target:

                    left += 1

                else:

                    right -= 1

        return res

9.【双指针】接雨水

题面

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水

Solution:

双指针分别从左右两边开始遍历，谁小处理谁。如果左边小，比较左边当前位置的高度和最高位置谁大，要是当前位置大于最大位置，则更新最大位置，否则计算雨水（最高-当前），然后左边指针右移；右边同理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
   def trap(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        left_max, right_max = height[left], height[right]
        water = 0

        while left < right:
            if height[left] < height[right]:
                left += 1
                left_max = max(left_max, height[left])
                water += left_max - height[left]
            else:
                right -= 1
                right_max = max(right_max, height[right])
                water += right_max - height[right]
        return water       return water

10.【滑动窗口】无重复字符的最长字串

题面：

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。

Solution：

  1. 初始化：seen 集合存储当前窗口字符，left 指针初始化为 0，max_length 记录最长子串长度。

  2. 遍历字符串：

    • 字符存在时：移动 left 并从 seen 中移除字符，直到 s[right] 不在集合中。

    • 字符不存在时：添加到 seen，并更新 max_length。

  3. 返回结果：max_length 即为最长无重复字符子串的长度。

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

        for right in range(len(s)):
            while s[right] in seen:
                seen.remove(s[left])
                left += 1
            seen.add(s[right])
            max_length = max(max_length, right - left + 1)

        return max_length

11.【滑动窗口】找到字符串中所有字母异位词

题面

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        if len(s) < len(p):
            return []

        p_len = len(p)
        p_sorted = sorted(p)
        res = []

        for i in range(len(s) - p_len + 1):
            window = s[i:i+p_len]
            if sorted(window) == p_sorted:
                res.append(i)

        return res

12.【普通数组】最大子数和

题目

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

Solution

Kadane算法（动态规划）

  1. 初始化：

    • max_current：记录以当前元素结尾的最大子数组和。

    • max_global：记录全局最大子数组和。

  2. 遍历数组：

    • 对于每个元素，更新 max_current：

      • 要么将当前元素加入之前的子数组（max_current + nums[i]），

      • 要么以当前元素作为新的子数组起点（nums[i]）。

    • 更新 max_global 为 max_current 和 max_global 中的较大值。

  3. 返回结果：max_global 即为最大子数组和。

1
2
3
4
5
6
7
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_current=globalmax_current=nums[0]
        for num in nums[1:]:
            max_current=max(num,max_current+num)
            globalmax_current=max(globalmax_current,max_current)
        return globalmax_current

13.【普通数组】

题目

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

Solution

  1. 排序区间：首先按照区间的起始点进行排序，这样相邻的区间更容易判断是否重叠。

  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
class Solution:

    def merge(self, intervals: List[List[int]]) -> List[List[int]]:

        if not intervals:

            return []

        intervals.sort(key=lambda x: x[0])

        res=[intervals[0]]

        for current in intervals[1:]:

            last=res[-1]

            if last[1] >= current[0]:

                last[1]=max(last[1],current[1])

            else:

                res.append(current)

        return res

【普通数组】轮转数组

题目

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

Solution

1
2
3
4
5
6
7
8
class Solution:#python切片
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k %= n
        nums[:] = nums[-k:] + nums[:-k]

  1. 创建一个新数组，将原数组的元素按照轮转后的位置放入新数组。

  2. 计算每个元素的新位置：(i + k) % n，其中 n 是数组长度。

    1
    2
    3
    4
    5
    6
    7
    class Solution:
        def rotate(self, nums: List[int], k: int) -> None:
            n = len(nums)
            rotated = [0] * n
            for i in range(n):
                rotated[(i + k) % n] = nums[i]
            nums[:] = rotated

【普通数组】除自身以外的数组乘积

题目

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

Solution

维护两个数组，对于numi，lefti和righti分别表示左右两边的乘积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n=len(nums)
        right=[1]*n
        left=[1]*n
        res=[1]*n

        for i in range(1,n):
            left[i]=left[i-1]*nums[i-1]
        for i in range(n-2,-1,-1):
            right[i]=right[i+1]*nums[i+1]

        for i in range(0,n):
            res[i]=left[i]*right[i]

        return res

【普通数组】最小数

题目

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

Solution

来自ds的解法

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)

        # 检查是否包含1
        if 1 not in nums:
            return 1

        # 预处理：将所有非正数和大于n的数替换为1
        for i in range(n):
            if nums[i] <= 0 or nums[i] > n:
                nums[i] = 1

        # 使用索引作为哈希键，标记出现的数字
        for i in range(n):
            num = abs(nums[i])
            if num == n:
                nums[0] = -abs(nums[0])  # 用索引0表示n
            else:
                nums[num] = -abs(nums[num])

        # 查找第一个正数的索引
        for i in range(1, n):
            if nums[i] > 0:
                return i

        # 检查n是否出现
        if nums[0] > 0:
            return n

        # 如果1到n都出现，则返回n+1
        return n + 1

【矩阵】矩阵置零

题面

给定一个 *m* x *n* 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法

Solution：

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.
        """
        marks=[]
        len_col=len(matrix)
        len_row=len(matrix[0])
        for col in range(len_col):
            for row in range(len_row):
                if matrix[col][row]==0:
                    marks.append([col,row])

        for mark in marks:
            for col in range(len_col):
                matrix[col][mark[1]]=0
            for row in range(len_row):
                matrix[mark[0]][row]=0

【矩阵】螺旋矩阵

题面：

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

Solution:

【边界模拟】

  1. 初始化边界：

    • 上边界 top = 0，下边界 bottom = m - 1

    • 左边界 left = 0，右边界 right = n - 1

  2. 循环遍历：

    • 从左到右遍历上边界，完成后上边界下移（top += 1）

    • 从上到下遍历右边界，完成后右边界左移（right -= 1）

    • 检查是否仍需遍历（top <= bottom 且 left <= right）：

      • 从右到左遍历下边界，完成后下边界上移（bottom -= 1）

      • 从下到上遍历左边界，完成后左边界右移（left += 1）

  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
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        left=0
        top=0
        right=len(matrix[0])-1
        bottom=len(matrix)-1
        res=[]
        while left<=right and top<=bottom:
            for i in range(left,right+1):
                res.append(matrix[top][i])
            top+=1
            for j in range(top,bottom+1):
                res.append(matrix[j][right])
            right-=1

            if left<=right and top<=bottom:
                for i in range(right,left-1,-1):
                    res.append(matrix[bottom][i])

                bottom-=1
                for j in range(bottom,top-1,-1):
                    res.append(matrix[j][left])

                left+=1

        return res

【矩阵】旋转图像

题面

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

Solution

  1. 转置矩阵：首先将矩阵的行和列互换，即转置矩阵。转置后的矩阵会将原来的行变为列，原来的列变为行。

  2. 翻转每一行：然后将转置后的矩阵的每一行进行翻转，即第一个元素和最后一个元素交换，第二个元素和倒数第二个元素交换，以此类推。

这样操作后，矩阵就会顺时针旋转 90 度。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n=len(matrix)
        for i in range(n):
            for j in range(i,n):
                matrix[i][j],matrix[j][i]=matrix[j][i],matrix[i][j]
        
        for i in range(n):
            matrix[i].reverse()

【矩阵】搜索二维矩阵Ⅱ

题面

编写一个高效的算法来搜索 *m* x *n* 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。

Solution

从矩阵的左下角或者右上角开始遍历，因为这两个位置分别对应所在行的最大（小）值和所在列的最小（大）值。示例从右上角开始，如果当前值大于目标，则行号+1，小于目标则列号减一。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix:
            return False
        n=len(matrix)
        m=len(matrix[0])

        row=0
        col=m-1
        while row<n and col>=0:
            if matrix[row][col]==target:
                return True
            elif matrix[row][col]<target:
                row+=1
            else:
                col-=1
        return False

【矩阵】和为K的子数组

题面

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

Solution：

一开始用滑动窗口结果超时了，换个思路，前缀和+哈希表：

  1. 前缀和：定义 prefix_sum[i] 为 nums[0] + nums[1] + ... + nums[i-1]。

  2. 关键观察：子数组 nums[i..j] 的和可以表示为 prefix_sum[j+1] - prefix_sum[i]。

  3. 哈希表优化：

    • 用哈希表记录前缀和出现的次数。

    • 对于当前前缀和 curr_sum，检查 curr_sum - k 是否在哈希表中，若存在则累加计数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from collections import defaultdict

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        prefix_count = defaultdict(int)
        prefix_count[0] = 1  # 初始前缀和为0出现1次
        curr_sum = 0
        count = 0
        
        for num in nums:
            curr_sum += num
            # 检查是否存在前缀和满足 curr_sum - prefix = k
            if (curr_sum - k) in prefix_count:
                count += prefix_count[curr_sum - k]
            # 记录当前前缀和
            prefix_count[curr_sum] += 1
        
        return count

【链表】反转链表

题目

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

Solution

1