回溯介绍回溯算法是一种通过探索所有可能的候选解来找出所有解的解题策略。 - 本质就是暴力法如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化来消除那些失败的候选解，也就是说，回溯并尝试另一种可能。回溯法非常适合解决约束满足问题，其中包括组合问题、划分问题、子集问题、排列问题和棋盘问题等。回溯算法涉及的问题组合问题：求解所有可能的组合方式，如组合总和。排列问题：求解所有可能的排列方式，如全排列问题。子集问题：求解一个集合的所有可能子集，如子集问题。棋盘问题：如N皇后问题、解数独等，通常是在二维棋盘上的放置问题，需要满足特定约束。划分问题：将一个集合划分为几个...

104.二叉树的最大深度最大深度是3 class Solution: def maxDepth(self, root: TreeNode) -> int: # 主方法，用于启动深度计算过程 return self.getDepth(root) def getDepth(self, node): # 递归方法，用于计算节点的深度 if not node: # 如果当前节点为空，说明到达了叶子节点的下一个位置，返回深度0 return 0 leftheight = self.getDepth(node.left) # 对左子树递归调用getDepth，计算左子树的深度 rightheight...

二叉树的前序、中序和后序遍历各自有不同的应用场景，它们在计算机科学的多个领域中被广泛使用。下面是这些遍历方法的一些主要应用：前序遍历（根-左-右）创建拷贝：前序遍历可以用于创建二叉树的拷贝。遍历时，可以复制每个节点并递归地复制它的左右子树。打印树结构：前序遍历非常适合打印一个树的结构，尤其是当你想要显示树的层级结构时。因为你首先访问根节点，然后是左子树和右子树，这自然地反映了树的层次结构。表达式树：在解析算术或逻辑表达式时，前序遍历可以用来生成前缀表示法（也称为波兰表示法）。中序遍历（左-根-右）二叉搜索树（BST）的排序输出：对于二叉搜索树，中序遍历将按照升序访问所有节点。这是因为二叉搜索树...

栈（Stack）和队列（Queue）是两种基本的数据结构，它们的思想在日常生活中的许多场景中都有体现。栈（Stack）的思想应用：书堆：书桌上的书堆是栈的一个直观例子。你总是放下（push）一本新书在最上面，当需要一本书时，你会从顶部取走（pop）书，这是一个后进先出（LIFO）的过程。浏览器的后退按钮：浏览过的网页地址被存储在一个栈中。每当你访问一个新网页，它就被“压入”这个栈。点击后退按钮时，最近访问的网页被“弹出”，显示前一个网页。撤销（Undo）功能：在文本编辑器中，每次编辑操作（如输入、删除）都被存储在一个栈中。当你执行撤销操作时，最近的编辑动作被撤销，这也是一个后进先出的过程。队列...

344.反转字符串双指针 class Solution: def reverseString(self, s: List[str]) -> None: left, right = 0, len(s) - 1 # 该方法已经不需要判断奇偶数，经测试后时间空间复杂度比用 for i in range(len(s)//2)更低 # 因为while每次循环需要进行条件判断，而range函数不需要，直接生成数字，因此时间复杂度更低。推荐使用range while left < right: s[left], s[right] = s[right], s[left] left += 1 rig...

454.四数相加II和两数相加一个思路，先来两个循环分别把两组数加一起算一次 class Solution: def fourSumCount(self, nums1: list, nums2: list, nums3: list, nums4: list) -> int: from collections import defaultdict rec = defaultdict(lambda:0) # 为访问的不存在的键生成默认值 0 cnt = 0 for i in nums1: for j in nums2: rec[i+j] += 1 for i in nums3: for j ...

242.有效的字母异位词转化成哈希表看是不是完全相等 class Solution: def isAnagram(self, s: str, t: str) -> bool: from collections import Counter # Counter可以用来计算各个元素出现的次数，非常适合于处理频率相关的问题 s_dict = Counter(s) t_dict = Counter(t) if s_dict==t_dict: return True else: return False 349. 两个数组的交集set太好用了 class Solution: def interse...

24. 两两交换链表中的节点构建虚拟头节点，然后要用的都标上t1,t2,t3，画个图把逻辑理清 class Solution: def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]: dummy_head = ListNode(next=head) cur = dummy_head while cur.next and cur.next.next : # 注意这个也有顺序，反了会报错 t1 = cur.next t2 = cur.next.next t3 = cur.next.next.next cur.n...

203.移除链表元素创建虚拟头节点比较好做，不然头节点不好处理。这道题很简单，碰到相同的就跳过去了 # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]: # 创建虚拟头部节点以简化删除过程 dummy_head = ListNode(next = head) ...

977 有序数组的平方核心：数组其实是有序的， 只不过负数平方之后可能成为最大数了。那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。 class Solution: def sortedSquares(self, nums: List[int]) -> List[int]: left, right, i = 0, len(nums)-1, len(nums)-1 res = [float("inf")]*len(nums) # 设置成无穷大的方法 while i >= 0: if nums[right]**2 > nums[left...

二分查找二分查找前提：1. 有序 2. 无重复时间复杂度：O(log n)空间复杂度：O(1)写二分法，区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)。如何判断最好自己举个例子手推一下，也不麻烦，但是想一下或者背一下也行。 class Solution: def search(self, nums: List[int], target: int) -> int: left, right = 0, len(nums)-1 while(left<=right): middle = left + (right - left) // 2...