LeetCode入门

写在前面

我终于也开始搞Leetcode了耶✌️～但是全英文看起来还是蛮难受的。。

随便写一点题解填补博客哈哈哈哈

两数之和

这是一道非常基础的题目，要求在一个数组中找到两个数，它们的和等于一个目标值。

解题思路：使用一个字典（dictionary）来记录已经遍历过的数值及其下标，然后对于每一个新的数值，判断它与目标值的差是否已经在字典中出现过。如果已经出现过，说明之前已经遍历过与差相等的数值，那么就可以直接返回当前数值和之前的数值下标。

这样就可以在O(n)的时间复杂度内解决这个问题。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_dict = {}
        for i, num in enumerate(nums):
            if target - num in nums_dict:
                return [nums_dict[target - num], i]
            nums_dict[num] = i
        return []

盛最多水的容器

这是一道比较经典的题目，要求在一个数组中找到两个数值，它们的距离与较小的数值之间形成的面积最大。

解题思路：使用双指针来遍历数组，分别从数组的两端开始，每次计算当前面积，并将较小的那个指针向中心移动一步。这样可以保证每次移动都是移动较小的指针，最终可以得到最大的面积。

这个算法的时间复杂度为O(n)，空间复杂度为O(1)。

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        max_area = 0
        while left < right:
            area = min(height[left], height[right]) * (right - left)
            max_area = max(max_area, area)
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return max_area

反转链表

这是一道链表操作的题目，要求将一个链表反转。

解题思路：使用两个指针来遍历链表，分别记录当前节点和前一个节点。每次将当前节点指向前一个节点，然后将当前指针往后移动一位，循环遍历整个链表。这样可以实现链表的反转。

时间复杂度为O(n)，空间复杂度为O(1)。

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None:
            return head
        prev, cur = None, head
        while cur is not None:
            nx = cur.next
            cur.next = prev
            prev = cur
            cur = nx
        return prev