leetcode中简单题的算法思想

1: 二分法

二分法是一种在有序数组中查找特定元素的搜索算法。它通过反复将数组分成两半来缩小搜索范围，直到找到目标元素或确定元素不存在。以下是二分法的基本步骤：

1. 确定数组的中间元素。
2. 将中间元素与目标值进行比较。
3. 如果中间元素等于目标值，则搜索成功。
4. 如果中间元素小于目标值，则在数组的右半部分继续搜索。
5. 如果中间元素大于目标值，则在数组的左半部分继续搜索。
6. 重复步骤1-5，直到找到目标元素或搜索范围为空。

二分法的时间复杂度为O(log n)，其中n是数组的长度。这使得二分法比线性搜索（时间复杂度为O(n)）更高效，特别是在处理大型数据集时。

下面是一个二分法的Python实现示例：

python

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid  # 找到目标元素，返回其索引
        elif arr[mid] < target:
            left = mid + 1  # 在右半部分继续搜索
        else:
            right = mid - 1  # 在左半部分继续搜索
    return -1  # 目标元素不存在，返回-1

使用这个函数，你可以通过提供一个有序数组和一个目标值来查找元素的索引。如果元素存在，函数将返回其索引；如果不存在，将返回-1。

2: 双指针法

双指针法是一种常用的算法技巧，它在处理数组、链表等数据结构时非常有效。这种方法通常涉及两个指针，它们在数据结构中移动，以实现特定的目标。双指针法可以用于多种问题，如查找、排序、合并等。

以下是双指针法的一些常见应用：

1. 查找问题：例如，在一个有序数组中查找两个数，使它们的和等于一个特定的目标值。可以使用两个指针，一个从数组的开始位置向后移动，另一个从数组的结束位置向前移动，直到找到满足条件的两个数或两个指针相遇。

2. 合并问题：例如，合并两个有序数组。可以使用两个指针，分别指向两个数组的开始位置，然后比较指针所指向的元素，将较小的元素添加到结果数组中，并移动相应的指针。

3. 链表问题：例如，反转链表。可以使用两个指针，一个指向当前节点，另一个指向当前节点的前一个节点，通过改变指针的指向来实现链表的反转。

4. 滑动窗口问题：例如，在一个数组中找到一个子数组，使其和等于一个特定的目标值。可以使用两个指针，一个表示子数组的开始位置，另一个表示子数组的结束位置，通过移动指针来调整子数组的大小，直到找到满足条件的子数组。

下面是一个双指针法的Python实现示例，用于在一个有序数组中查找两个数，使它们的和等于一个特定的目标值：

python

def two_sum(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        current_sum = arr[left] + arr[right]
        if current_sum == target:
            return [left, right]  # 找到满足条件的两个数，返回它们的索引
        elif current_sum < target:
            left += 1  # 增加当前和，向右移动左指针
        else:
            right -= 1  # 减少当前和，向左移动右指针
    return []  # 没有找到满足条件的两个数，返回空列表

使用这个函数，你可以通过提供一个有序数组和一个目标值来查找两个数的索引。如果找到满足条件的两个数，函数将返回它们的索引；如果没有找到，将返回空列表。

3: 递归法

递归法是一种算法设计技巧，它通过将问题分解为更小的、相似的子问题来解决复杂问题。递归法的基本思想是，如果一个大问题可以表示为若干个较小问题的组合，那么我们可以通过解决这些较小问题来解决大问题。

递归法通常涉及两个主要部分：

1. 基本情况（Base Case）：这是递归的最简单情况，可以直接解决而不需要进一步分解。基本情况是递归的终止条件，没有基本情况，递归将无限进行下去。

2. 递归步骤（Recursive Step）：这是递归的分解过程，将大问题分解为一个或多个较小问题，然后对这些较小问题进行递归调用。在递归步骤中，问题的规模逐渐减小，直到达到基本情况。

递归法可以用于解决许多问题，如阶乘计算、斐波那契数列、树的遍历、图的搜索等。

下面是一个递归法的Python实现示例，用于计算一个数的阶乘：

python

def factorial(n):
    if n == 0:  # 基本情况
        return 1
    else:  # 递归步骤
        return n * factorial(n - 1)

使用这个函数，你可以通过提供一个非负整数来计算其阶乘。函数将递归地调用自身，直到达到基本情况（n == 0），然后返回结果。

递归法虽然强大，但也有其缺点。递归调用会消耗更多的内存和时间，因为每次调用都需要保存当前的执行状态。此外，如果递归深度过大，可能会导致栈溢出错误。因此，在使用递归法时，需要仔细考虑其适用性和效率。

4:迭代法

迭代法是一种基本的算法设计技术，它通过重复执行一组指令来逐步解决问题。与递归法相比，迭代法使用循环结构来实现重复操作，而不是通过函数的自我调用。迭代法通常更节省内存，因为它不需要为每次函数调用保留堆栈帧。

迭代法的关键组成部分包括：

1. 初始化：设置循环开始前所需的初始状态，比如循环计数器的初始值。

2. 循环条件：定义循环继续执行的条件。

3. 循环体：在每次循环迭代中执行的操作。

4. 更新/迭代：在每次循环迭代结束时更新循环变量，以接近问题解决方案或准备下一次迭代。

5. 终止：当循环条件不再满足时，循环终止，问题得到解决。

迭代法可以应用于各种算法和数据结构，例如排序算法（如冒泡排序、选择排序）、搜索算法（如广度优先搜索）、动态规划等。

下面是一个迭代法的Python实现示例，用于实现一个简单的冒泡排序算法：

python

def bubble_sort(arr):
    n = len(arr)
    # 外层循环控制排序的总轮数
    for i in range(n):
        # 内层循环控制每轮的比较次数
        for j in range(0, n-i-1):
            # 如果当前元素比下一个元素大，则交换它们
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr  # 返回排序后的数组

使用这个函数，你可以通过提供一个数组来对其进行排序。函数将通过重复比较和交换相邻元素来排序数组，直到数组完全有序。

迭代法的优点包括：

• 内存效率：由于不需要额外的函数调用堆栈，迭代通常比递归更节省内存。
• 控制简单：迭代法通常更容易控制和理解，尤其是在处理复杂的算法时。
• 适用性广：迭代法可以应用于几乎所有需要重复操作的场景。

然而，迭代法也有其局限性，比如在某些情况下可能不如递归法直观，特别是在处理自然递归的问题（如树和图的遍历）时。此外，迭代法可能需要更多的循环控制逻辑，这在某些情况下可能会导致代码复杂度增加。

5:分治法

分治法（Divide and Conquer）是一种算法设计范式，它将一个难以直接解决的大问题分解（Divide）成若干个规模较小但与原问题形式相同的子问题，递归地解决这些子问题（Conquer），然后将子问题的解合并（Combine）起来解决原问题

分治法的三个主要步骤如下：

1. 分解（Divide）：

   • 将原问题分解为若干个规模较小的相同问题。分解的目的是简化问题，使其易于解决。

2. 解决（Conquer）：

   • 递归地解决这些子问题。如果子问题的规模足够小，可以直接解决。

3. 合并（Combine）：

   • 将子问题的解合并，以形成原问题的解。

下面是一个归并排序的Python实现示例，展示了分治法的典型应用：

python

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # 找到中间位置
        left_half = arr[:mid]  # 分解为左半部分
        right_half = arr[mid:]  # 分解为右半部分

        merge_sort(left_half)  # 递归排序左半部分
        merge_sort(right_half)  # 递归排序右半部分

        i = j = k = 0

        # 合并两个有序数组
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        # 将剩余的元素添加到合并后的数组中
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

    return arr

使用这个函数，你可以通过提供一个数组来对其进行排序。函数将递归地将数组分成两半，分别排序，然后将排序好的两半合并成一个有序数组。

6:hashmap(字典法)

Hashmap（或称为哈希表、字典）是一种基于哈希函数的数据结构，它允许快速插入、删除和搜索操作。在Python中，字典（dict）是一种内置的哈希表实现，它使用键值对存储数据，其中键（key）是唯一的，而值（value）可以是任何数据类型。

Hashmap的一个常见应用是作为计数器，用于统计元素出现的次数。

python

def count_elements(elements):
    count_dict = {}
    for element in elements:
        if element in count_dict:
            count_dict[element] += 1
        else:
            count_dict[element] = 1
    return count_dict

# 统计列表中元素的出现次数
elements = ["apple", "banana", "apple", "orange", "banana", "apple"]
count_result = count_elements(elements)
print(count_result)  # 输出: {'apple': 3, 'banana': 2, 'orange': 1}

Hashmap是一种非常强大的数据结构，适用于需要快速查找、插入和删除操作的场景。在实际应用中，Hashmap可以极大地提高程序的性能和效率。

7: 堆栈法

栈是一种遵循后进先出（LIFO）原则的数据结构，只允许在一端（称为栈顶）进行添加和移除操作。

栈的基本操作包括：

• 入栈（Push）：将元素添加到栈顶。
• 出栈（Pop）：移除栈顶元素。
• 查看栈顶元素（Peek/Top）：查看栈顶元素但不移除它。

括号匹配（使用栈）

python

def is_balanced(expression):
    stack = []
    for char in expression:
        if char in '({[':
            stack.append(char)
        elif char in ')}]':
            if not stack or (char == ')' and stack[-1] != '(') or (char == ']' and stack[-1] != '[') or (char == '}' and stack[-1] != '{'):
                return False
            stack.pop()
    return not stack

expression = "{[()()]}"
print(is_balanced(expression))  # 输出: True

8: 动态规划

动态规划（Dynamic Programming，DP）是一种算法设计技术，用于解决具有重叠子问题和最优子结构的问题。动态规划通过将问题分解为更小的子问题，并存储这些子问题的解（通常在表格中），来避免重复计算，从而提高效率。

动态规划的关键概念

1. 重叠子问题：问题可以分解为多个子问题，这些子问题不是独立的，而是相互重叠的。这意味着相同的子问题会被多次计算。

2. 最优子结构：问题的最优解包含其子问题的最优解。这意味着可以通过组合子问题的最优解来构建原问题的最优解。

3. 存储子问题的解：为了避免重复计算，将子问题的解存储在表格（通常是数组或矩阵）中，以便在需要时直接查找。

动态规划的步骤

1. 定义状态：确定子问题的参数，这些参数定义了子问题的唯一性。

2. 建立状态转移方程：根据问题的性质，找出子问题之间的关系，即如何从一个或多个子问题的解得到原问题的解。

3. 初始化：确定边界条件，即最简单子问题的解。

4. 计算：按照状态转移方程，从最简单的子问题开始，逐步计算更复杂子问题的解，直到得到原问题的解。

5. 构造解：如果需要，从存储的子问题解中构造出原问题的解。

动态规划的应用示例

斐波那契数列

斐波那契数列是一个经典的动态规划问题。斐波那契数列的定义是：

F(n)=F(n−1)+F(n−2)

F(0)=0,F(1)=1

使用动态规划，我们可以避免重复计算相同的子问题。

python

def fibonacci(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

print(fibonacci(10))

9: 贪心算法

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法策略。贪心算法不保证会得到最优解，但在某些问题中，贪心算法的解足够接近最优解或者确实是最优解。

贪心算法的关键特性包括：

1. 局部最优选择：在每一步选择中都采取当前状态下的最优选择。
2. 贪心选择性质：问题的一个解可以通过一系列贪心选择来达到。
3. 最优子结构：一个问题的最优解包含其子问题的最优解。

贪心算法适用于那些具有最优子结构的问题，即问题的全局最优解可以通过一系列局部最优解来获得。此外，贪心算法通常在执行过程中需要进行决策，并且一旦做出决策，就不能回退。

贪心算法的应用示例

活动选择问题

假设有一系列活动，每个活动都有开始时间和结束时间，目标是选择最大数量的互不重叠的活动。贪心算法的策略是总是选择结束时间最早的活动，然后在此活动之后选择下一个结束时间最早的活动。

python复制

def activity_selection(activities):
    # 按照结束时间排序
    activities.sort(key=lambda x: x[1])
    selected Activities = []
    last_finish_time = 0

    for start, finish in activities:
        if start >= last_finish_time:
            selected_activities.append([start, finish])
            last_finish_time = finish

    return selected_activities

# 示例活动 [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
print(activity_selection(activities))