LeetCode刷题记录

每天固定两道LeetCode，先从easy难度开始，刚入手用的还是python，C语言指针结构那里还不是很熟练，感觉之前没有学好，在算法方面要多下点功夫，水滴石穿，量变将会引起质变

这里将会记载一些刷力扣过程中对一些题的想法和笔记

哈希表

第一题求两数之和用时间复杂度O(n^2)的双重循环很简单，但问题是如何将时间复杂度进一步降低？

于是我大概查了一下，用哈希表存储已经遍历过的元素的索引，以便快速查找目标值的补数：

def two_sum(self, nums, target):
    num_to_index = {}                         # 创建一个哈希表
    for i, num in enumerate(nums):
        complement = target - num     # 差值
        if complement in num_to_index:
            return [num_to_index[complement], i]
        num_to_index[num] = i
    return []

enumerate函数

enumerate意思为：枚举

在Python中，enumerate 函数用于将一个可迭代对象的元素与其索引组合成一个个元组，然后返回这些元组组成的迭代器。当在循环中使用 enumerate 时，可以同时获取到元素的索引和值。

for i, num in enumerate(nums):
# i 为元素索引，num为元素值，nums为一列表

T13 注意字符串边界索引

出自第十三题罗马数字转整数，犯了个低级错误

for i in range(len(s)):
      if(roman_dict[s[i]]<roman_dict[s[i+1]] and i<len(s)-1):   # need change the order 

这是错误的，实际上要将and两边的逻辑判断换一下位置，因为and一旦执行到False就会停止判断而输出False，如果不换顺序会出现字符串索引越界的现象

T14 最大公共前缀

刚入手这题的时候怎么写怎么别扭，后面借鉴了GPT，它用了find()函数

def longestCommonPrefix(self, strs):
    prefix = strs[0]
    for string in strs[1:]:
        while string.find(prefix)!=0 and prefix:    #我试了下，没加"and prefix"也给对了
            prefix=prefix[:-1]		 #其实应该要加的，因为题目说了string有可能是空串
        if not prefix:
            return ""
    return prefix 

关于find函数

find 函数是 Python 字符串方法之一，用于查找子字符串在字符串中第一次出现的位置。它的主要功能是返回子字符串在字符串中首次出现的索引，如果没有找到子字符串，则返回 -1

# 示例 1: 基本用法
text = "Hello, world!"
index = text.find("world")
print(index)  # 输出: 7

# 示例 2: 子字符串不存在
index = text.find("Python")
print(index)  # 输出: -1

# 示例 3: 使用 start 参数
index = text.find("o", 5)
print(index)  # 输出: 8

# 示例 4: 使用 start 和 end 参数
index = text.find("o", 5, 10)
print(index)  # 输出: 8

# 示例 5: 查找多个字符
index = text.find("lo")
print(index)  # 输出: 3

关于"类"

由T21“合并两个有序列表“（归并排序算法）中涉及到链表类，关于这部分内容之前就有点没搞明白，所以系统地归纳一下

那就从头开始讲解Python中的类和方法。类是面向对象编程的核心概念，用于创建自定义的数据类型。类定义了一组属性和方法，这些属性和方法是类的实例（对象）所共享的。下面是详细的解释和示例。

基本概念

1. 类（Class）：类是对象的蓝图或模板。通过类可以创建对象。
2. 对象（Object）：对象是类的实例。每个对象都有类定义的属性和方法。
3. 属性（Attribute）：属性是类中定义的变量，表示对象的状态。
4. 方法（Method）：方法是类中定义的函数，用于操作对象的属性。

定义类

在Python中，使用 class 关键字来定义类。下面是一个简单的例子：

class Dog:
    def __init__(self, name, age):
        self.name = name  # 属性 name
        self.age = age  # 属性 age

    def bark(self):
        print(f"{self.name} is barking.")  # 方法 bark

    def get_age(self):
        return self.age  # 方法 get_age

解释

1. __init__ 方法：这是类的构造方法，在创建对象时自动调用。它用于初始化对象的属性。
2. self 参数：self 是一个特殊的参数，指向类的实例。通过 self 可以访问类的属性和方法。
3. 属性：name 和 age 是 Dog 类的属性。
4. 方法：bark 和 get_age 是 Dog 类的方法。

创建对象

使用类来创建对象：

my_dog = Dog("Buddy", 3)  # 创建 Dog 类的实例
print(my_dog.name)  # 输出: Buddy
print(my_dog.age)  # 输出: 3

my_dog.bark()  # 输出: Buddy is barking.
print(my_dog.get_age())  # 输出: 3

修改属性

可以直接访问和修改对象的属性：

my_dog.age = 4
print(my_dog.get_age())  # 输出: 4

完整示例

我们可以结合之前讲到的链表，创建一个更复杂的例子，展示如何使用类来定义和操作链表节点。

# 定义链表节点类
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val  # 节点的值
        self.next = next  # 指向下一个节点的指针

# 定义链表类
class LinkedList:
    def __init__(self):
        self.head = None  # 初始化链表为空

    # 向链表末尾添加节点
    def append(self, val):
        new_node = ListNode(val)
        if self.head is None:  # 链表为空时，新节点作为头节点
            self.head = new_node
        else:
            current = self.head
            while current.next:  # 找到链表的最后一个节点
                current = current.next
            current.next = new_node

    # 打印链表
    def print_list(self):
        current = self.head
        while current:
            print(current.val, end=" -> ")
            current = current.next
        print("None")

# 使用链表类
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.print_list()  # 输出: 1 -> 2 -> 3 -> None

解释

1. ListNode 类：定义了链表节点，每个节点有一个值和一个指向下一个节点的指针。
2. LinkedList 类：定义了链表，包含一个头节点。
3. append 方法：在链表末尾添加节点。
4. print_list 方法：打印链表的所有节点。

类提供了一种组织代码的方式，使其更易于管理和扩展。

关于链表类

链表是一种数据结构，它由一组节点组成，每个节点包含一个数据域和一个指向下一个节点的指针。链表的主要类型有单向链表（单链表）和双向链表（双链表）。我们将首先介绍单链表，然后再简单介绍双链表。

单链表

基本概念

1. 节点（Node）：链表的基本组成部分。每个节点包含数据域（存储数据）和指针域（指向下一个节点）。
2. 头节点（Head）：链表的起始节点，通常我们用一个单独的变量来保存头节点。
3. 尾节点（Tail）：链表的最后一个节点，其指针域指向 None（空）。

单链表的定义

在Python中，我们可以定义一个链表节点类 ListNode，并实现链表的一些基本操作，如插入和删除节点。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val  # 数据域
        self.next = next  # 指针域

class LinkedList:
    def __init__(self):
        self.head = None  # 初始化链表为空

    # 插入节点到链表末尾
    def append(self, val):
        new_node = ListNode(val)
        if self.head is None:  # 链表为空时，新节点作为头节点
            self.head = new_node
        else:
            current = self.head
            while current.next:  # 找到链表的最后一个节点
                current = current.next
            current.next = new_node

    # 打印链表
    def print_list(self):
        current = self.head
        while current:
            print(current.val, end=" -> ")
            current = current.next
        print("None")

使用示例

# 创建链表
ll = LinkedList()

# 插入节点
ll.append(1)
ll.append(2)
ll.append(3)

# 打印链表
ll.print_list()  # 输出：1 -> 2 -> 3 -> None

常见操作

1. 插入节点：可以在链表头部、尾部或中间插入节点。
2. 删除节点：可以删除特定值的节点或指定位置的节点。
3. 搜索节点：可以搜索链表中是否存在特定值的节点。
4. 链表反转：可以反转整个链表。

链表操作实现

插入节点到头部

def prepend(self, val):
    new_node = ListNode(val)
    new_node.next = self.head
    self.head = new_node

删除指定值的节点

def delete(self, val):
    current = self.head
    if current and current.val == val:  # 如果头节点就是要删除的节点
        self.head = current.next
        return
    prev = None
    while current and current.val != val:
        prev = current
        current = current.next
    if current:  # 找到节点并删除
        prev.next = current.next

反转链表

def reverse(self):
    prev = None
    current = self.head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    self.head = prev

双向链表

双向链表是链表的一个扩展，每个节点不仅有指向下一个节点的指针，还有指向前一个节点的指针。

双向链表的定义

class DoublyListNode:
    def __init__(self, val=0, next=None, prev=None):
        self.val = val
        self.next = next
        self.prev = prev

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    # 插入节点到链表末尾
    def append(self, val):
        new_node = DoublyListNode(val)
        if self.tail is None:  # 链表为空时，新节点作为头节点和尾节点
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node

    # 打印链表
    def print_list(self):
        current = self.head
        while current:
            print(current.val, end=" <-> ")
            current = current.next
        print("None")

使用示例

# 创建双向链表
dll = DoublyLinkedList()

# 插入节点
dll.append(1)
dll.append(2)
dll.append(3)

# 打印双向链表
dll.print_list()  # 输出：1 <-> 2 <-> 3 <-> None