Leetcode 0227. Basic Calculator II
227. Basic Calculator IIGiven a string s which represents an expression, evaluate this expression and return its value. The integer division should truncate toward zero. You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 - 1]. Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval(). 题目大意给定一个字符串 s 表示一个算术表达式，要求计算该表达式的值并返回。表达式仅包含非负整数、+、-、*、/ 四种运算符，以及可能的空格。整数除法需要向...
Leetcode 0226. Invert Binary Tree
226. Invert Binary TreeGiven the root of a binary tree, invert the tree, and return its root. Example 1: 12Input: root = [4,2,7,1,3,6,9]Output: [4,7,2,9,6,3,1] Example 2: 12Input: root = [2,1,3]Output: [2,3,1] Example 3: 12Input: root = []Output: [] 题目大意给定一棵二叉树的根节点 root，翻转这棵二叉树（即交换每个节点的左子树和右子树），并返回翻转后的根节点。 例如： 输入二叉树 [4,2,7,1,3,6,9]，翻转后每个节点的左右子树互换，输出为 [4,7,2,9,6,3,1]。 解题思路翻转二叉树的核心是交换每个节点的左子节点和右子节点，可以通过递归或迭代两种方式实现： 1. 递归法利用二叉树的递归性质： 若当前节点为空，直接返回； 否则，先交换当前节点的左、右子节点； 递归翻转当前节点的左子树和右子树。 2...
Leetcode 0225. Implement Stack using Queues
225. Implement Stack using QueuesImplement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty). Implement the MyStack class: void push(int x): Pushes element x to the top of the stack. int pop(): Removes the element on the top of the stack and returns it. int top(): Returns the element on the top of the stack. boolean empty(): Returns true if the stack is empty, false otherwise. Notes: ...
Leetcode 0222. Count Complete Tree Nodes
222. Count Complete Tree NodesGiven the root of a complete binary tree, return the number of the nodes in the tree. According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h. Design an algorithm that runs in less than O(n) time complexity. Example 1: 12Input: root = [1,2,3,4,5,6]Output: 6 Example 2: 12Input: root ...
Leetcode 0216. Combination Sum III
216. Combination Sum IIIFind all valid combinations of k numbers that sum up to n such that the following conditions are true: Only numbers 1 through 9 are used. Each number is used at most once. Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order. Example 1: 12345Input: k = 3, n = 7Output: [[1,2,4]]Explanation:1 + 2 + 4 = 7There are no other valid combinations. Example 2: 1234567Input: k ...
Leetcode 0209. Minimum Size Subarray Sum
209. Minimum Size Subarray Sum题目Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead. Example 1: 123Input: s = 7, nums = [2,3,1,2,4,3]Output: 2Explanation: the subarray [4,3] has the minimal length under the problem constraint. Follow up: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n). 解题思路这一题的解题思...
Leetcode 0206. Reverse Linked List
206. Reverse Linked ListGiven the head of a singly linked list, reverse the list, and return the reversed list. Example 1: 12Input: head = [1,2,3,4,5]Output: [5,4,3,2,1] Example 2: 12Input: head = [1,2]Output: [2,1] Example 3: 12Input: head = []Output: [] Constraints: The number of nodes in the list is the range [0, 5000]. -5000 <= Node.val <= 5000 解法 1：迭代解法123456789101112131415161718192021222324252627/** * Definition for singly-linked list. * struct ListNode { * int v...
Leetcode 0199. Binary Tree Right Side View
199. Binary Tree Right Side ViewGiven the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom. Example 1: Input: root = [1,2,3,null,5,null,4] Output: [1,3,4] Explanation: Example 2: Input: root = [1,2,3,4,null,null,null,5] Output: [1,3,4,5] Explanation: Example 3: Input: root = [1,null,3] Output: [1,3] Example 4: Input: root = [] Output: [] 题目大意给定一棵二叉树的根节点 root，想象自己站在树的右侧，返回从顶部到底...
Leetcode 0189. 轮转数组
189. 轮转数组给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。 示例 1: 123456输入: nums = [1,2,3,4,5,6,7], k = 3输出: [5,6,7,1,2,3,4]解释:向右轮转 1 步: [7,1,2,3,4,5,6]向右轮转 2 步: [6,7,1,2,3,4,5]向右轮转 3 步: [5,6,7,1,2,3,4] 示例 2: 12345输入：nums = [-1,-100,3,99], k = 2输出：[3,99,-1,-100]解释: 向右轮转 1 步: [99,-1,-100,3]向右轮转 2 步: [3,99,-1,-100] 题目大意给定一个整数数组 nums 和非负整数 k，将数组元素向右轮转 k 个位置（即每个元素向右移动 k 位，末尾元素移动到开头）。要求尽可能优化时间和空间复杂度。 核心解题思路：三次反转法常规思路（如临时数组、多次右移）要么空间复杂度高（O (n)），要么时间复杂度高（O (nk)）。三次反转法通过巧妙的反转操作，实现 O (n) 时间复杂度 + O (1) 空间复杂度...
Leetcode 0180. 连续出现的数字
180. 连续出现的数字表：Logs 12345678+-------------+---------+| Column Name | Type |+-------------+---------+| id | int || num | varchar |+-------------+---------+在 SQL 中，id 是该表的主键。id 是一个自增列。 找出所有至少连续出现三次的数字。 返回的结果表中的数据可以按 任意顺序 排列。 结果格式如下面的例子所示： 示例 1: 123456789101112131415161718192021输入：Logs 表：+----+-----+| id | num |+----+-----+| 1 | 1 || 2 | 1 || 3 | 1 || 4 | 2 || 5 | 1 || 6 | 2 || 7 | 2 |+----+-----+输出：Result 表：+-----------------+| ConsecutiveNums |+----...
Leetcode 0162. Find Peak Element
162. Find Peak Element题目A peak element is an element that is greater than its neighbors. Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index. The array may contain multiple peaks, in that case return the index to any one of the peaks is fine. You may imagine that nums[-1] = nums[n] = -∞. Example 1: Input: nums = [1,2,3,1] Output: 2 Explanation: 3 is a peak element and your function should return the index number 2. Example 2: Input: nums = [1,2,1,3,...
Leetcode 0155. Min Stack
155. Min StackDesign a stack that supports push, pop, top, and retrieving the minimum element in constant time. Implement the MinStack class: MinStack() initializes the stack object. void push(int val) pushes the element val onto the stack. void pop() removes the element on the top of the stack. int top() gets the top element of the stack. int getMin() retrieves the minimum element in the stack. You must implement a solution with O(1) time complexity for each function. 题目大意设计一个支持 push（压栈）、p...
Leetcode 0151. Reverse Words in a String
151. Reverse Words in a StringGiven an input string s, reverse the order of the words. A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space. Return a string of the words in reverse order concatenated by a single space. Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces. Example 1: 12Input: s =...
Leetcode 0150. Evaluate Reverse Polish Notation
150. Evaluate Reverse Polish NotationYou are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation. Evaluate the expression. Return an integer that represents the value of the expression. Note that: The valid operators are '+', '-', '*', and '/'. Each operand may be an integer or another expression. The division between two integers always truncates toward zero. There will not be any division by zero. The input ...
Leetcode 0148. 排序链表
148. 排序链表给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。 示例 1： 12输入：head = [4,2,1,3]输出：[1,2,3,4] 示例 2： 12输入：head = [-1,5,3,4,0]输出：[-1,0,3,4,5] 示例 3： 12输入：head = []输出：[] 题目大意给定链表的头节点 head，要求将链表按升序排列并返回排序后的链表头节点。 解题思路对于链表排序，最适合的高效算法是归并排序，原因如下： 归并排序的时间复杂度为 O (n log n)，是链表排序的最优选择 链表的归并操作不需要像数组那样额外分配 O (n) 的空间 链表的中点查找可以通过快慢指针高效实现 归并排序的核心步骤： 分解：使快慢指针找到链表中点，将链表分成两部分 递归：对左右两部分分别进行排序 合并：将两个已排序的链表合并成一个有序链表 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253...
Leetcode 0146. LRU Cache
146. LRU CacheDesign a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class: LRUCache(int capacity) Initialize the LRU cache with positive size capacity. int get(int key) Return the value of the key if the key exists, otherwise return -1. void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the l...
Leetcode 0145. Binary Tree Postorder Traversal
145. Binary Tree Postorder TraversalGiven the root of a binary tree, return the postorder traversal of its nodes' values. Example 1: Input: root = [1,null,2,3] Output: [3,2,1] Explanation: Example 2: Input: root = [1,2,3,4,5,null,8,null,null,6,7,9] Output: [4,6,7,5,2,9,8,3,1] Explanation: Example 3: Input: root = [] Output: [] Example 4: Input: root = [1] Output: [1] 题目大意给定一棵二叉树的根节点 root，返回其节点值的后序遍历结果。后序遍历的顺序是「左子树 → 右子树 → 根节点」，遵循 "左 - 右 - 根" 的递归逻辑。 解题思路后序遍...
Leetcode 0144. Binary Tree Preorder Traversal
144. Binary Tree Preorder TraversalGiven the root of a binary tree, return the preorder traversal of its nodes' values. Example 1: Input: root = [1,null,2,3] Output: [1,2,3] Explanation: Example 2: Input: root = [1,2,3,4,5,null,8,null,null,6,7,9] Output: [1,2,4,5,6,7,3,8,9] Explanation: Example 3: Input: root = [] Output: [] Example 4: Input: root = [1] Output: [1] 题目大意给定一棵二叉树的根节点 root，返回其节点值的前序遍历结果。前序遍历的顺序是「根节点 → 左子树 → 右子树」，遵循 "根 - 左 - 右" 的递归逻辑。 解题思路前序遍历的...
Leetcode 0142. Linked List Cycle II
142. Linked List Cycle IIGiven the head of a linked list, return the node where the cycle begins. If there is no cycle, return null. There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter. Do not modify the linked list. Examp...
Leetcode 0131. Palindrome Partitioning
131. Palindrome PartitioningGiven a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. Example 1: 12Input: s = "aab"Output: [["a","a","b"],["aa","b"]] Example 2: 12Input: s = "a"Output: [["a"]] 题目大意给定一个字符串 s，将其分割成若干个子串，使得每个子串都是回文串。返回所有可能的分割方案。 例如： 输入 s = "aab"，输出 [["a","a","b"],["aa&quo...
Leetcode 0116. Populating Next Right Pointers in Each Node
116. Populating Next Right Pointers in Each NodeYou are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition: 123456struct Node { int val; Node *left; Node *right; Node *next;} Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. Initially, all next pointers are set to NULL. Example 1: 123Input: root = [1...
Leetcode 0112. Path Sum
112. Path SumGiven the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum. A leaf is a node with no children. Example 1: 123Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22Output: trueExplanation: The root-to-leaf path with the target sum is shown. Example 2: 123456Input: root = [1,2,3], targetSum = 5Output: falseExplanation: There are two root-to-leaf pat...
Leetcode 0110. Balanced Binary Tree
110. Balanced Binary TreeGiven a binary tree, determine if it is height-balanced. Example 1: 12Input: root = [3,9,20,null,null,15,7]Output: true Example 2: 12Input: root = [1,2,2,3,3,null,null,4,4]Output: false Example 3: 12Input: root = []Output: true 题目大意给定一棵二叉树，判断它是否是高度平衡的。高度平衡平衡二叉树 ** 的定义是：二叉树的每个节点的左右两个子树的高度差的绝对值不超过 1。 例如： 输入二叉树 [3,9,20,null,null,15,7]，每个节点的左右子树高度差均不超过 1，返回 true； 输入二叉树 [1,2,2,3,3,null,null,4,4]，根节点的左子树高度为 3，右子树高度为 1，差为 2，返回 false。 解题思路判断平衡二叉树的核心是计算每个节点的左右子树高度，并检查高...
Leetcode 0108. Convert Sorted Array to Binary Search Tree
108. Convert Sorted Array to Binary Search TreeGiven an integer array nums where the elements are sorted in ascending order, convert it to a *height-balanced* binary search tree. Example 1: 123Input: nums = [-10,-3,0,5,9]Output: [0,-3,9,-10,null,5]Explanation: [0,-10,5,null,-3,null,9] is also accepted: Example 2: 123Input: nums = [1,3]Output: [3,1]Explanation: [1,null,3] and [3,1] are both height-balanced BSTs. 题目大意给定一个升序排列的整数数组 nums，将其转换为一棵高度平衡的二叉搜索树（BST）。高度平衡的定义是：二叉树的左右两个子树的高度差的绝对值不超过 ...
Leetcode 0107. Binary Tree Level Order Traversal II
107. Binary Tree Level Order Traversal IIGiven the root of a binary tree, return the bottom-up level order traversal of its nodes' values. (i.e., from left to right, level by level from leaf to root). Example 1: 12Input: root = [3,9,20,null,null,15,7]Output: [[15,7],[9,20],[3]] Example 2: 12Input: root = [1]Output: [[1]] Example 3: 12Input: root = []Output: [] 题目大意给定一棵二叉树的根节点 root，返回其节点值的自底向上的层序遍历结果。即按「从叶子节点所在层到根节点所在层」的顺序逐层返回，每层内部仍保持「从左到右」的顺序。 例如： 输入二叉树 [3,9,20,null,null,15,7]，其自底向上...
