Leecode解题的8大模式

2024-08-24 19:52
文章标签 模式 解题 leecode

本文主要是介绍Leecode解题的8大模式,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

在 LeetCode 上刷题时,很多题目看似复杂,但实际上,许多问题可以归纳为几种常见的算法模式。
如果掌握了这些模式,就能高效地解决大量问题。

一、滑动窗口:优化子数组和子字符串问题
滑动窗口是一种常用的技巧,特别适合解决子数组和子字符串相关的问题。滑动窗口的核心思想是在一个可变大小的窗口中维护一些信息,并通过窗口的移动来缩小问题的范围。

一般来说,可以通过三问三答的形式进行思考:
1、对于每一个右指针 right 所指的元素 ch ,做什么操作?
2、什么时候要令左指针 left 右移?left对应的元素做什么操作?【循环不变量】
3、什么时候进行ans的更新?

这三个问题,本质上对应了滑窗问题需要考虑的三个基本要素:
1、right 指针以及所对应的元素 ch
2、left 指针以及所对应的元素 left_ch
3、ans 答案变量

以 LeetCode 3. 无重复字符的最长子串 为例:
题目:给定一个字符串,请你找出其中不含有重复字符的最长子串的长度。

class Solution:def lengthOfLongestSubstring(self,s):ans = 0hash_set = set()left = 0for right, ch in enumerate(s) :# Q1:对于每一个右指针 right 所指的元素ch,做什么操作?# A1:若 ch 不在哈希集合中,将ch 加入哈希集合if ch not in hash_set:hash_set.add(ch)#Q3:什么时候进行ans的更新?# A3:若 ch 不在哈希集合中,ans 更新ans = max(ans,right-left+1)else:# Q2:什么时候要令左指针 left 右移?# left对应的元素做什么操作?【循环不变量】# A2: ch 在哈希集合中,left右移直到 ch 不在哈希集合中while(ch in hash_set):left_ch = s[left]hash_set.remove(left_ch)left += 1# A1:若 ch 在哈希集合中,left 右移完毕后,将ch 加入哈希集hash_set.add(ch)return ans

二、二分查找:寻找分割点

二分查找是一种高效的查找方法,特别适合用于有序数组或具有一定规律的数据结构中。二分查找的核心思想是每次将搜索区间缩小一半,以此快速逼近答案。

一般来说,可以通过三问三答的形式进行思考:
1、对于每个中间点 mid,我们应该如何处理?
2、如何调整左右指针 left 和 right 以缩小搜索范围?
3、在什么条件下可以直接返回答案?

这三个问题,本质上对应了二分查找问题需要考虑的三个基本要素
1、mid 指针以及所对应的元素 mid_val
2、左右指针 left 和 right 及其变化
3、返回答案的条件

以 LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置 为例:题目:在一个升序排列的数组中,找到一个目标值出现的起始和结束位置。

class Solution:def searchRange(self, nums, target):def findFirst(nums, target):left, right = 0, len(nums) - 1while left <= right:mid = left + (right - left) // 2# Q1:对于每个中间点 mid,我们应该如何处理?# A1:如果 mid_val 大于等于目标值,右边界收缩if nums[mid] >= target:right = mid - 1else:left = mid + 1# Q3:返回条件# A3:返回左指针,代表第一个满足条件的位置return leftdef findLast(nums, target):left, right = 0, len(nums) - 1while left <= right:mid = left + (right - left) // 2# A1:如果 mid_val 小于等于目标值,左边界收缩if nums[mid] <= target:left = mid + 1else:right = mid - 1# A3:返回右指针,代表最后一个满足条件的位置return right# 找第一个出现位置first = findFirst(nums, target)# 如果第一个位置超出范围或不等于目标值,说明目标值不存在if first >= len(nums) or nums[first] != target:return [-1, -1]# 找最后一个出现位置last = findLast(nums, target)return [first, last]

三、堆:寻找 top-k 元素
堆是一种适合解决 top-k 问题的数据结构。通过维护一个 k 大小的堆,可以高效地找到数组中的前 k 个最大或最小元素。

一般来说,可以通过三问三答的形式进行思考:
1、如何初始化堆?
2、如何处理新的元素以维护堆的性质?
3、如何从堆中提取最终答案?

这三个问题,本质上对应了堆问题需要考虑的三个基本要素:
1、堆的初始化
2、堆的维护操作
3、结果的提取

以 LeetCode 215. 数组中的第 K 个最大元素 为例,
题目:找到数组中第 k 个最大的元素。

import heapqclass Solution:def findKthLargest(self, nums, k):# Q1:如何初始化堆?# A1:构建一个最小堆,初始时包含前 k 个元素heap = nums[:k]# heapq.heapify(heap) : 将数组heap转换为堆heapq.heapify(heap)# Q2:如何处理新的元素以维护堆的性质?# A2:对于剩余元素,如果大于堆顶,则替换堆顶并重新调整堆for num in nums[k:]:if num > heap[0]:# heapreplace(heap,num)弹出并返回 heap 中最小的一项,同时推入新的 item, 堆的大小不变。heapq.heapreplace(heap, num)# Q3:如何从堆中提取最终答案?# A3:堆顶即为第 k 大的元素return heap[0]

关于堆的详解:
https://blog.csdn.net/weixin_43283397/article/details/104983664

四、深度优先搜索(DFS):遍历图和树的基础

深度优先搜索(DFS)是一种遍历或搜索图、树结构的算法,常用于解决全路径、连通性等问题。

一般来说,可以通过三问三答的形式进行思考:
1、如何处理当前节点?
2、如何递归到子节点?
3、如何处理递归返回后的结果?

这三个问题,本质上对应了 DFS 问题需要考虑的三个基本要素:
1、当前节点的处理
2、递归调用的处理
3、递归返回后的结果处理

以 LeetCode 104. 二叉树的最大深度 为例,
题目:计算二叉树的最大深度。

class Solution:def maxDepth(self, root):# Q1:如何处理当前节点?# A1:如果节点为空,直接返回 0if not root:return 0# Q2:如何递归到子节点?# A2:分别递归计算左子树和右子树的深度left_depth = self.maxDepth(root.left)right_depth = self.maxDepth(root.right)# Q3:如何处理递归返回后的结果?# A3:返回左子树和右子树深度的较大者,再加 1 表示当前层级return max(left_depth, right_depth) + 1

五、广度优先搜索(BFS):层级遍历与最短路径

广度优先搜索(BFS)是一种层级遍历算法,特别适合用于搜索最短路径或进行层级遍历的问题。

一般来说,可以通过三问三答的形式进行思考:
1、如何处理当前层的节点?
2、如何扩展到下一层的节点?
3、如何确定搜索是否完成?

这三个问题,本质上对应了 BFS 问题需要考虑的三个基本要素:
1、当前层节点的处理
2、扩展到下一层的处理
3、搜索完成的条件

以 LeetCode 102. 二叉树的层序遍历 为例,
题目:返回二叉树的层序遍历结果。

from collections import dequeclass Solution:def levelOrder(self, root):if not root:return []# Q1:如何处理当前层的节点?# A1:使用队列存储当前层的所有节点queue = deque([root])result = []while queue:level_size = len(queue)level = []# Q2:如何扩展到下一层的节点?# A2:遍历当前层所有节点,将其子节点加入队列for _ in range(level_size):node = queue.popleft()level.append(node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)# Q3:搜索完成的条件# A3:将当前层结果加入最终结果集result.append(level)return result

六、拓扑排序:任务调度与依赖

拓扑排序用于解决具有依赖关系的任务排序问题,通常在有向无环图(DAG)中应用。

一般来说,可以通过三问三答的形式进行思考:
1、如何构建图和入度数组?
2、如何处理入度为 0 的节点?
3、如何更新其他节点的入度?

这三个问题,本质上对应了拓扑排序问题需要考虑的三个基本要素:
1、图的构建
2、入度为 0 的节点处理
3、入度更新

以 LeetCode 207. 课程表 为例,
题目:判断是否可能完成所有课程。

from collections import deque, defaultdictclass Solution:def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:# Q1:如何构建图和入度数组?# A1:构建邻接表和入度数组graph = defaultdict(list)in_degree = [0] * numCoursesfor dest, src in prerequisites:graph[src].append(dest)in_degree[dest] += 1# Q2:如何处理入度为 0 的节点?# A2:将所有入度为 0 的节点入队列,并开始遍历queue = deque([i for i in range(numCourses) if in_degree[i] == 0])completed_courses = 0while queue:course = queue.popleft()completed_courses += 1# Q3:如何更新其他节点的入度?# A3:减少邻接节点的入度,如果入度变为 0,加入队列for neighbor in graph[course]:in_degree[neighbor] -= 1if in_degree[neighbor] == 0:queue.append(neighbor)return completed_courses == numCourses

七、双指针:高效遍历与查找

双指针技巧适用于数组和字符串的遍历与查找问题,尤其是在需要高效处理对称性或前后关系时。

一般来说,可以通过三问三答的形式进行思考:
1、如何初始化两个指针?
2、如何移动指针以满足条件?
3、如何更新结果或停止移动?

这三个问题,本质上对应了双指针问题需要考虑的三个基本要素:
1、指针的初始化
2、指针的移动逻辑
3、结果的更新或停止条件

以 LeetCode 167. 两数之和 II - 输入有序数组 为例,
题目:在一个已升序排列的数组中,找到两个数使得它们的和等于目标值。

class Solution:def twoSum(self, numbers, target):# Q1:如何初始化两个指针?# A1:初始化左指针指向开头,右指针指向结尾left, right = 0, len(numbers) - 1while left < right:# Q2:如何移动指针以满足条件?# A2:根据当前和与目标值的关系,调整指针位置current_sum = numbers[left] + numbers[right]if current_sum == target:# Q3:如何更新结果或停止移动?# A3:找到目标值,返回结果return [left + 1, right + 1]elif current_sum < target:left += 1else:right -= 1return []

八、子集与组合:子集生成与组合求解

子集与组合问题涉及生成所有子集、组合或排列,通常使用回溯法进行求解。

一般来说,可以通过三问三答的形式进行思考:
1、如何选择当前元素加入子集?
2、如何递归生成子集或组合?
3、如何处理递归返回后的结果?

这三个问题,本质上对应了子集与组合问题需要考虑的三个基本要素:
1、当前元素的选择
2、递归生成的处理
3、递归返回的结果处理

以 LeetCode 78. 子集 为例,题目:返回一个数组的所有可能子集。

class Solution:def subsets(self, nums):result = []def backtrack(start, path):# Q3:如何处理递归返回后的结果?# A3:将当前路径添加到结果集中result.append(path[:])for i in range(start, len(nums)):# Q1:如何选择当前元素加入子集?# A1:将当前元素添加到路径中path.append(nums[i])# Q2:如何递归生成子集或组合?# A2:递归处理下一个元素backtrack(i + 1, path)path.pop()backtrack(0, [])return result

这篇关于Leecode解题的8大模式的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1103444

相关文章

在JS中的设计模式的单例模式、策略模式、代理模式、原型模式浅讲

1. 单例模式(Singleton Pattern) 确保一个类只有一个实例,并提供一个全局访问点。 示例代码: class Singleton {constructor() {if (Singleton.instance) {return Singleton.instance;}Singleton.instance = this;this.data = [];}addData(value)

模版方法模式template method

学习笔记,原文链接 https://refactoringguru.cn/design-patterns/template-method 超类中定义了一个算法的框架, 允许子类在不修改结构的情况下重写算法的特定步骤。 上层接口有默认实现的方法和子类需要自己实现的方法

【iOS】MVC模式

MVC模式 MVC模式MVC模式demo MVC模式 MVC模式全称为model(模型)view(视图)controller(控制器),他分为三个不同的层分别负责不同的职责。 View:该层用于存放视图,该层中我们可以对页面及控件进行布局。Model:模型一般都拥有很好的可复用性,在该层中,我们可以统一管理一些数据。Controlller:该层充当一个CPU的功能,即该应用程序

迭代器模式iterator

学习笔记,原文链接 https://refactoringguru.cn/design-patterns/iterator 不暴露集合底层表现形式 (列表、 栈和树等) 的情况下遍历集合中所有的元素

《x86汇编语言:从实模式到保护模式》视频来了

《x86汇编语言:从实模式到保护模式》视频来了 很多朋友留言,说我的专栏《x86汇编语言:从实模式到保护模式》写得很详细,还有的朋友希望我能写得更细,最好是覆盖全书的所有章节。 毕竟我不是作者,只有作者的解读才是最权威的。 当初我学习这本书的时候,只能靠自己摸索,网上搜不到什么好资源。 如果你正在学这本书或者汇编语言,那你有福气了。 本书作者李忠老师,以此书为蓝本,录制了全套视频。 试

利用命令模式构建高效的手游后端架构

在现代手游开发中,后端架构的设计对于支持高并发、快速迭代和复杂游戏逻辑至关重要。命令模式作为一种行为设计模式,可以有效地解耦请求的发起者与接收者,提升系统的可维护性和扩展性。本文将深入探讨如何利用命令模式构建一个强大且灵活的手游后端架构。 1. 命令模式的概念与优势 命令模式通过将请求封装为对象,使得请求的发起者和接收者之间的耦合度降低。这种模式的主要优势包括: 解耦请求发起者与处理者

springboot实战学习(1)(开发模式与环境)

目录 一、实战学习的引言 (1)前后端的大致学习模块 (2)后端 (3)前端 二、开发模式 一、实战学习的引言 (1)前后端的大致学习模块 (2)后端 Validation:做参数校验Mybatis:做数据库的操作Redis:做缓存Junit:单元测试项目部署:springboot项目部署相关的知识 (3)前端 Vite:Vue项目的脚手架Router:路由Pina:状态管理Eleme

状态模式state

学习笔记,原文链接 https://refactoringguru.cn/design-patterns/state 在一个对象的内部状态变化时改变其行为, 使其看上去就像改变了自身所属的类一样。 在状态模式中,player.getState()获取的是player的当前状态,通常是一个实现了状态接口的对象。 onPlay()是状态模式中定义的一个方法,不同状态下(例如“正在播放”、“暂停

软件架构模式:5 分钟阅读

原文: https://orkhanscience.medium.com/software-architecture-patterns-5-mins-read-e9e3c8eb47d2 软件架构模式:5 分钟阅读 当有人潜入软件工程世界时,有一天他需要学习软件架构模式的基础知识。当我刚接触编码时,我不知道从哪里获得简要介绍现有架构模式的资源,这样它就不会太详细和混乱,而是非常抽象和易

使用Spring Boot集成Spring Data JPA和单例模式构建库存管理系统

引言 在企业级应用开发中,数据库操作是非常重要的一环。Spring Data JPA提供了一种简化的方式来进行数据库交互,它使得开发者无需编写复杂的JPA代码就可以完成常见的CRUD操作。此外,设计模式如单例模式可以帮助我们更好地管理和控制对象的创建过程,从而提高系统的性能和可维护性。本文将展示如何结合Spring Boot、Spring Data JPA以及单例模式来构建一个基本的库存管理系统