2024.5.2 —— LeetCode 高频题复盘

news/2025/1/16 15:47:29/

目录

  • 151. 反转字符串中的单词
  • 129. 求根节点到叶节点数字之和
  • 104. 二叉树的最大深度
  • 101. 对称二叉树
  • 110. 平衡二叉树
  • 144. 二叉树的前序遍历
  • 543. 二叉树的直径
  • 48. 旋转图像
  • 98. 验证二叉搜索树
  • 39. 组合总和

151. 反转字符串中的单词


题目链接

class Solution:def reverseWords(self, s: str) -> str:ls=s.strip().split()ls.reverse()res=" ".join(ls)return res

129. 求根节点到叶节点数字之和


题目链接

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def helper(self,root,i):if not root:return 0temp=i*10+root.valif not root.left and not root.right:return tempreturn self.helper(root.left,temp)+self.helper(root.right,temp)def sumNumbers(self, root: Optional[TreeNode]) -> int:return self.helper(root,0)

104. 二叉树的最大深度


题目链接

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def maxDepth(self, root: Optional[TreeNode]) -> int:if not root:return 0leftHight=self.maxDepth(root.left)rightHigh=self.maxDepth(root.right)return max(leftHight,rightHigh)+1

101. 对称二叉树


题目链接

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def isSymmetric(self, root: Optional[TreeNode]) -> bool:def judge(left,right):if not left and not right:return Trueelif not left or not right:return Falseelif left.val!=right.val:return Falseelse:return judge(left.left,right.right) and judge(left.right,right.left)if not root:return Truereturn judge(root.left,root.right)

110. 平衡二叉树


题目链接

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def isBalanced(self, root: Optional[TreeNode]) -> bool:# 二叉树的最大深度def height(root):if not root:return 0return max(height(root.left),height(root.right))+1if not root:return Truereturn abs(height(root.left)-height(root.right))<=1 and self.isBalanced(root.left) and self.isBalanced(root.right)

144. 二叉树的前序遍历


题目链接

递归

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:lis=[]def traversal(root):if not root:returnlis.append(root.val)traversal(root.left)traversal(root.right)traversal(root)return lis

非递归

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:white,gray=0,1stack=[(white,root)]res=[]while stack:color,node=stack.pop()if node is None:continueif color==white:stack.append((white,node.right))stack.append((white,node.left))stack.append((gray,node))else:res.append(node.val)return res

543. 二叉树的直径


题目链接

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:# 一条路径的长度为该路径经过的节点数减一,# 所以求直径(即求路径长度的最大值)等效于求路径经过节点数的最大值减一self.max=0def depth(root):if not root:return 0left=depth(root.left)right=depth(root.right)self.max=max(self.max,left+right+1)return max(left,right)+1depth(root)return self.max-1

48. 旋转图像


题目链接

class Solution:def rotate(self, matrix: List[List[int]]) -> None:"""Do not return anything, modify matrix in-place instead."""# 用翻转代替旋转# 先水平翻转再主对角线翻转即可得到将图像顺时针旋转90度的图像n=len(matrix)# 水平翻转for i in range(n//2):for j in range(n):matrix[i][j],matrix[n-1-i][j]=matrix[n-1-i][j],matrix[i][j]# 主对角线翻转for i in range(n):for j in range(i):matrix[i][j],matrix[j][i]=matrix[j][i],matrix[i][j]

98. 验证二叉搜索树


题目链接

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def isValidBST(self, root: Optional[TreeNode]) -> bool:# 中序遍历:左中右self.pre=Nonedef dfs(root):if not root:return Trueleft=dfs(root.left)if self.pre and self.pre.val>=root.val:return Falseself.pre=rootright=dfs(root.right)return left and rightreturn dfs(root)

39. 组合总和


题目链接

class Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:path=[]res=[]def backtracking(candidates,s,target,startIndex):if s>target: # 要剪枝必须排序returnif s==target:res.append(path[:])returnfor i in range(startIndex,len(candidates)):s+=candidates[i]path.append(candidates[i])backtracking(candidates,s,target,i) # 下一层i依然可以取到s-=candidates[i]path.pop()candidates.sort()backtracking(candidates,0,target,0)return res

http://www.ppmy.cn/news/1458737.html

相关文章

六西格玛项目的核心要素:理论学习、实践应用与项目经验

许多朋友担心&#xff0c;没有项目经验是否就意味着无法考取六西格玛证书。针对这一疑问&#xff0c;张驰咨询为大家详细解答。 首先&#xff0c;需要明确的是&#xff0c;六西格玛项目不仅仅是一种管理工具或方法&#xff0c;更是一种追求卓越、持续改进的思维方式。它强调通…

TypeScript常见面试题第六节

题目二十六:TypeScript 中的装饰器? 一、讲解视频 TS面试题二十六:TypeScript 中的可选链? 二、题目解析 本题目考察可选链的相关知识,可选链是比较新的一个语法,是一种访问嵌套对象属性的安全的方式。即使中间的属性不存在,也不会出现错误。如果可选链 ?. 前面的值为…

Java 【数据结构】常见排序算法实用详解(上) 插入排序/希尔排序/选择排序/堆排序【贤者的庇护】

登神长阶 上古神器-常见排序算法 插入排序/选择排序/堆排序 &#x1f4d4; 一.排序算法 &#x1f4d5;1.排序的概念 排序 &#xff1a;所谓排序&#xff0c;就是使一串记录&#xff0c;按照其中的某个或某些关键字的大小&#xff0c;递增或递减的排列起来的操作。 稳定性&a…

websocket简介

服务端推送消息给浏览器 WebSocket 教程 - 阮一峰的网络日志

Faiss:高效相似度搜索与索引技术深度解析

Faiss&#xff1a;高效相似度搜索与索引技术深度解析 一、引言 在大数据时代&#xff0c;信息的海量化使得快速、准确地从海量数据中检索出相似信息变得至关重要。Faiss&#xff08;Facebook AI Similarity Search&#xff09;是一个由Facebook AI团队开发的开源库&#xff0…

保研面试408复习 4——操作系统、计网

文章目录 1、操作系统一、文件系统中文件是如何组织的&#xff1f;二、文件的整体概述三、UNIX外存空闲空间管理 2、计算机网络一、CSMA/CD 协议&#xff08;数据链路层协议&#xff09;二、以太网MAC帧MTU 标记文字记忆&#xff0c;加粗文字注意&#xff0c;普通文字理解。 1、…

爬虫分布式框架PySpider

一、介绍 PySpider是一个基于Python的分布式爬虫框架,它使用了异步网络库和分布式调度器,可以快速高效地爬取大量数据。 PySpider具有以下特点: 强大的分布式能力:PySpider使用分布式调度器来管理和调度爬取任务,可以方便地扩展到多台机器上,实现分布式爬取。 灵活的配…

如何构建进攻性的网络安全防护策略

进攻性安全&#xff08;Offensive security&#xff09;是指一系列主动安全策略&#xff0c;这些策略与恶意行为者在现实世界的攻击中使用的策略相同&#xff0c;区别在于其目的是加强而非损害网络安全。常见的进攻性安全方法包括红队、渗透测试和漏洞评估。 进攻性安全行动通…