C++

69. Sqrt(x)Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well. You must not use any built-in exponent function or operator. For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python. Example 1: 123Input: x = 4Output: 2Explanation: The square root of 4 is 2, so we return 2. Example 2: 123Input: x = 8Output: 2Explanation: The square root of 8 is 2.82842..., and since we round it down to t...

59. Spiral Matrix IIGiven a positive integer n, generate an n x n matrix filled with elements from 1 to n2 in spiral order. Example 1: 12Input: n = 3Output: [[1,2,3],[8,9,4],[7,6,5]] Example 2: 12Input: n = 1Output: [[1]] Constraints: 1 <= n <= 20 题目大意给定一个正整数 n，生成一个 n×n 的矩阵，其中元素从 1 到 n² 按螺旋顺序填充。 解题思路 创建一个 n×n 的空矩阵 定义四个边界：上、下、左、右 按顺时针方向（右→下→左→上）填充数字 每填充完一行或一列就调整相应的边界 重复步骤 3-4 直到所有数字都被填充 123456789101112131415161718192021222324252627282930313233343536373839class Solution {publ...

55. Jump GameYou are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position. Return true if you can reach the last index, or false otherwise. Example 1: 123Input: nums = [2,3,1,1,4]Output: trueExplanation: Jump 1 step from index 0 to 1, then 3 steps to the last index. Example 2: 123Input: nums = [3,2,1,0,4]Output: falseExplanation: You will always arrive at index 3 no matter ...

54. 螺旋矩阵给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。 示例 1： 12输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]输出：[1,2,3,6,9,8,7,4,5] 示例 2： 12输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]输出：[1,2,3,4,8,12,11,10,9,5,6,7] 提示： m == matrix.length n == matrix[i].length 1 <= m, n <= 10 -100 <= matrix[i][j] <= 100 题目大意给定一个 m 行 n 列的矩阵，按顺时针螺旋顺序返回矩阵中的所有元素。 解题思路采用方向向量结合边界判断的方法： 定义四个方向（右、下、左、上）的坐标变化 遍历矩阵元素，按当前方向移动 当遇到边界或已访问元素时，顺时针切换方向 直到收集完所有元素 12345678910111213141516171819202122232425262728...

53. Maximum SubarrayGiven an integer array nums, find the subarray with the largest sum, and return its sum. Example 1: 123Input: nums = [-2,1,-3,4,-1,2,1,-5,4]Output: 6Explanation: The subarray [4,-1,2,1] has the largest sum 6. Example 2: 123Input: nums = [1]Output: 1Explanation: The subarray [1] has the largest sum 1. Example 3: 123Input: nums = [5,4,-1,7,8]Output: 23Explanation: The subarray [5,4,-1,7,8] has the largest sum 23. 题目大意给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 例如： ...

48. Rotate ImageYou are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise). You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation. Example 1: 12Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]Output: [[7,4,1],[8,5,2],[9,6,3]] Example 2: 12Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]] ...

46. PermutationsGiven an array nums of distinct integers, return all the possible permutations. You can return the answer in any order. Example 1: 12Input: nums = [1,2,3]Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] Example 2: 12Input: nums = [0,1]Output: [[0,1],[1,0]] Example 3: 12Input: nums = [1]Output: [[1]] 题目大意给定一个无重复元素的整数数组 nums，返回该数组所有可能的全排列。全排列是指包含数组所有元素的有序序列，且每个元素仅出现一次，结果顺序可任意。 例如： 输入 nums = [1,2,3]，输出 [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]（共 3! = 6 种...

45. 跳跃游戏 II给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。 每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处： 0 <= j <= nums[i] 且 i + j < n 返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 n - 1。 示例 1: 1234输入: nums = [2,3,1,1,4]输出: 2解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。 示例 2: 12输入: nums = [2,3,0,1,4]输出: 2 解题思路核心思路是贪心算法，通过跟踪 “当前跳跃的最远边界” 和 “下一次跳跃的最远可达位置”，在每一步跳跃时选择最优范围，实现最少跳跃次数： 贪心策略： 用 end 表示当前跳跃能到达的最远边界（初始为 0）； 用 max_reach 表示从当前位置到 end 之间的所有位置能跳到的最远位置； 用 s...

42. 接雨水给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 示例 1： 123输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]输出：6解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 示例 2： 12输入：height = [4,2,0,3,2,5]输出：9 解题思路核心思路是双指针边界，通过每个柱子能接住的雨水量取决于其左右两侧的最高柱子中较矮的那个（短板效应）： 边界定义： 对于位置 i，左侧最高柱子高度为 left_max[i]； 右侧最高柱子高度为 right_max[i]； 位置 i 能接住的雨水量为 min(left_max[i], right_max[i]) - height[i]（若结果为正，否则为 0）。 优化实现： 采用双指针法，无需额外存储 left_max 和 right_max 数组，将空间复杂度降至 O (1)； 用 left 和 right 指针分别从左右两端向...

40. Combination Sum IIGiven a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target. Each number in candidates may only be used once in the combination. Note: The solution set must not contain duplicate combinations. Example 1: 12345678Input: candidates = [10,1,2,7,6,1,5], target = 8Output: [[1,1,6],[1,2,5],[1,7],[2,6]] Example 2: 123456Input: candidates = [2,5,2,1,2], target = 5Output:...

39. Combination SumGiven an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order. The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different. The test cases are generated such that the number of unique combinations that sum up to ...

35. Search Insert Position题目Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array. Example 1: 12Input: [1,3,5,6], 5Output: 2 Example 2: 12Input: [1,3,5,6], 2Output: 1 Example 3: 12Input: [1,3,5,6], 7Output: 4 Example 4: 12Input: [1,3,5,6], 0Output: 0 题目大意给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。 你可以假设数组中无重复元素。 核心思路问题本质上是要找到第一个大于等...

34. Find First and Last Position of Element in Sorted Array题目Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value. Your algorithm's runtime complexity must be in the order of O(log n). If the target is not found in the array, return [-1, -1]. Example 1: Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4] Example 2: Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1] 查找第一个出现的位置： 当找到目标值时，不立即返回，而是继续向左查找（right ...

33. Search in Rotated Sorted Array题目Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array. Your algorithm's runtime complexity must be in the order of O(log n). Example 1: Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4 Example 2: Input: nums =...

28. Find the Index of the First Occurrence in a StringGiven two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. Example 1: 1234Input: haystack = "sadbutsad", needle = "sad"Output: 0Explanation: "sad" occurs at index 0 and 6.The first occurrence is at index 0, so we return 0. Example 2: 123Input: haystack = "leetcode", needle = "leeto"Output: -1Explanation: &...

27. Remove Element给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。 假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作： 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。 返回 k。 用户评测： 评测机将使用以下代码测试您的解决方案： 123456789101112int[] nums = [...]; // 输入数组int val = ...; // 要移除的值int[] expectedNums = [...]; // 长度正确的预期答案。 // 它以不等于 val 的值排序。int k = removeElement(nums, val); // 调用你的实现assert k == expectedNums.length;sort(nums, 0, k); // 排序 n...

26. Remove Duplicates from Sorted Array给你一个 非严格递增排列 的数组 nums ，请你** 原地** 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。 考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过： 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。 返回 k 。 判题标准: 系统会用下面的代码来测试你的题解: 123456789int[] nums = [...]; // 输入数组int[] expectedNums = [...]; // 长度正确的期望答案int k = removeDuplicates(nums); // 调用assert k == expectedNums.length;for (int i = 0; i < k; i++) { assert num...

25. K 个一组翻转链表给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。 k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。 示例 1： 12输入：head = [1,2,3,4,5], k = 2输出：[2,1,4,3,5] 示例 2： 12输入：head = [1,2,3,4,5], k = 3输出：[3,2,1,4,5] 解题思路：「K 个一组翻转链表」的核心思路是： 分组遍历：每次取 K 个节点作为一组，若不足 K 个则停止。 翻转每组：对当前 K 个节点进行翻转。 连接各组：将翻转后的组与前一组连接，更新指针继续处理下一组。 具体步骤： 用 dummy 虚拟头节点简化边界处理（避免头节点特殊逻辑）。 用 pre 记录上一组的尾节点（翻转后作为连接点）。 用 end 遍历并检查当前组是否有 K 个节点。 翻转当前组后，重新连接 pre 与翻转后的组，并更新 pre 和 end。 1234567891...

24. Swap Nodes in PairsGiven a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.) Example 1: Input: head = [1,2,3,4] Output: [2,1,4,3] Explanation: Example 2: Input: head = []$ Output: [] Example 3: Input: head = [1] Output: [1] Example 4: Input: head = [1,2,3] Output: [2,1,3] 题目大意给定一个链表，要求两两交换相邻节点（如 1→2→3→4 变为 2→1→4→3），且只能通过调...

23. 合并 K 个升序链表给你一个链表数组，每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中，返回合并后的链表。 示例 1： 12345678910输入：lists = [[1,4,5],[1,3,4],[2,6]]输出：[1,1,2,3,4,4,5,6]解释：链表数组如下：[ 1->4->5, 1->3->4, 2->6]将它们合并到一个有序链表中得到。1->1->2->3->4->4->5->6 示例 2： 12输入：lists = []输出：[] 示例 3： 12输入：lists = [[]]输出：[] 题目大意多个有序链表的合并，使用归并排序整理有序链表，更优秀的思考是采用优先级队列（小根堆）来排序。归并可以看21题。 解题思路解法一：分治法（两两合并）思路核心借鉴「归并排序」的分治思想，将 K 个链表逐步拆分为成对的子问题，合并后再递归 / 迭代合并结果，减少重复比较次数。 步骤拆解边界处理：若 lists 为空，直接返回 nullptr； 迭代合并： 初始时...

22. Generate Parentheses题目Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is: [ "((()))", "(()())", "(())()", "()(())", "()()()" ] 题目大意给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。 解题思路 这道题乍一看需要判断括号是否匹配的问题，如果真的判断了，那时间复杂度就到 O(n * 2^n)了，虽然也可以 AC，但是时间复杂度巨高。 这道题实际上不需要判断括号是否匹配的问题。因为在 DFS 回溯的过程中，会让 ( 和 ) 成对的匹配上的。 123456789101112131415161...

21. 合并两个有序链表将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1： 12输入：l1 = [1,2,4], l2 = [1,3,4]输出：[1,1,2,3,4,4] 示例 2： 12输入：l1 = [], l2 = []输出：[] 示例 3： 12输入：l1 = [], l2 = [0]输出：[0] 题目大意需要将两个升序排列的链表合并成一个新的升序链表，新链表由原两个链表的所有节点组成，且保持升序排列。 解题思路 使用虚拟头节点（dummy node）简化边界情况处理 双指针遍历两个链表，比较当前节点值，将较小的节点接入结果链表 当一个链表遍历完毕后，将另一个链表的剩余部分直接接入结果链表 这种方法的时间复杂度为 O (n + m)，其中 n 和 m 分别是两个链表的长度，空间复杂度为 O (1)，仅使用了常数个额外节点。 1234567891011121314151617181920212223242526272829303132333435363738/** * Definition for si...

20. Valid ParenthesesGiven a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Every close bracket has a corresponding open bracket of the same type. 题目大意给定一个只包含 '('、')'、'{'、'}'、'[' 和 &...

19. Remove Nth Node From End of ListGiven the head of a linked list, remove the nth node from the end of the list and return its head. Example 1: 12Input: head = [1,2,3,4,5], n = 2Output: [1,2,3,5] Example 2: 12Input: head = [1], n = 1Output: [] Example 3: 12Input: head = [1,2], n = 1Output: [1] 题目大意给定一个链表的头节点，要求删除链表的倒数第 N 个节点，并返回删除后的链表头节点。 解题思路可以使用双指针法高效解决这个问题，只需一次遍历： 定义两个指针 fast 和 slow，初始都指向虚拟头节点 先让 fast 指针向前移动 N 步 然后让 fast 和 slow 同时向前移动，直到 fast 到达链表末尾 此时 slow 指针指向的就是要删除节点的前一个节点 通过调整指...

17. Letter Combinations of a Phone Number题目Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters. Example: 12Input: "23"Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. Note: Although th...