Leetcode

367. Valid Perfect Square题目Given a positive integer num, write a function which returns True if num is a perfect square else False. Note: Do not use any built-in library function such as sqrt. Example 1: Input: 16 Output: true Example 2: Input: 14 Output: false 完全平方数可以表示为连续奇数的和。 算法原理该算法利用了以下数学特性： 1 = 1（1²） 1 + 3 = 4（2²） 1 + 3 + 5 = 9（3²） 1 + 3 + 5 + 7 = 16（4²） 以此类推，n² = 1 + 3 + 5 + ... + (2n-1) 算法通过不断从目标数中减去连续的奇数（1, 3, 5, 7...），如果最终结果恰好为 0，则说明该数是完全平方数。 123456789...

349. Intersection of Two ArraysGiven two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order. Example 1: 12Input: nums1 = [1,2,2,1], nums2 = [2,2]Output: [2] Example 2: 123Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]Output: [9,4]Explanation: [4,9] is also accepted. 题目大意给定两个整数数组 nums1 和 nums2，返回它们的交集。结果中的每个元素必须是唯一的，并且可以按任意顺序返回。 解题思路可以使用哈希集合来高效求解： 先将第一个数组中的元素存入一个哈希集合，自动去除重复元素 遍历第二个数组，检查每个元...

316. 去除重复字母给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。 示例 1： 12输入：s = "bcabc"输出："abc" 示例 2： 12输入：s = "cbacdcbc"输出："acdb" 核心思路是单调栈 + 贪心算法，通过维护一个单调递增的栈来确保字典序最小，同时利用计数数组判断字符是否还有剩余，确保每个字符只保留一次： 预处理： 统计字符串中每个字符的出现次数（count 数组）； 记录字符是否已在栈中（in_stack 数组），避免重复添加。 单调栈逻辑： 遍历字符串中的每个字符C： 减少 count[c]（当前字符已被考虑）； 若 c 已在栈中，直接跳过； 若 c 不在栈中，且栈不为空，且栈顶字符大于 c，且栈顶字符在后续还有出现（count[栈顶字符] > 0），则弹出栈顶字符（确保字典序更小）； 将 c 压入栈，并标记为已在栈中。 结果构建： 栈中字符即为去重...

287. Find the Duplicate NumberGiven an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive. There is only one repeated number in nums, return this repeated number. You must solve the problem without modifying the array nums and using only constant extra space. Example 1: 12Input: nums = [1,3,4,2,2]Output: 2 Example 2: 12Input: nums = [3,1,3,4,2]Output: 3 Example 3: 12Input: nums = [3,3,3,3,3]Output: 3 题目大意给定一个包含 n + 1 个整数的数组 nums，其中每个整数都在 [1...

283. Move Zeroes题目Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements. Example 1: 12Input: [0,1,0,3,12]Output: [1,3,12,0,0] Note: You must do this in-place without making a copy of the array. Minimize the total number of operations. 解法1：双指针1234567891011121314151617181920class Solution {public: void moveZeroes(vector<int>& nums) { int n = nums.size(); int i = 0; // 慢指针，记录下...

257. Binary Tree PathsGiven the root of a binary tree, return all root-to-leaf paths in any order. A leaf is a node with no children. Example 1: 12Input: root = [1,2,3,null,5]Output: ["1->2->5","1->3"] Example 2: 12Input: root = [1]Output: ["1"] 题目大意给定一棵二叉树的根节点 root，返回所有从根节点到叶子节点的路径。叶子节点是指没有子节点的节点，路径以字符串形式表示，节点值之间用 "->" 连接。 例如： 输入二叉树 [1,2,3,null,5]，根到叶子的路径为 1->2->5 和 1->3，返回 ["1->2->5","1->3"]。 解题思...

239. Sliding Window MaximumYou are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window. Example 1: 1234567891011Input: nums = [1,3,-1,-3,5,3,6,7], k = 3Output: [3,3,5,5,6,7]Explanation: Window position Max--------------- -----[1 3 -1] -3 5 3 6 ...

232. Implement Queue using StacksImplement a first in first out (FIFO) queue using only two Stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty). Implement the MyQueue class: void push(int x) Pushes element x to the back of the queue. int pop() Removes the element from the front of the queue and returns it. int peek() Returns the element at the front of the queue. boolean empty() Returns true if the queue is empty, false otherwise. No...

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 表示一个算术表达式，要求计算该表达式的值并返回。表达式仅包含非负整数、+、-、*、/ 四种运算符，以及可能的空格。整数除法需要向...

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...

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: ...

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 ...

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 ...

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). 解题思路这一题的解题思...

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...

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，想象自己站在树的右侧，返回从顶部到底...

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) 空间复杂度...

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 |+----...

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,...

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...

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 =...

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 ...

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...

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...

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，返回其节点值的后序遍历结果。后序遍历的顺序是「左子树 → 右子树 → 根节点」，遵循 "左 - 右 - 根" 的递归逻辑。 解题思路后序遍...