Leetcode

78. SubsetsGiven an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order. Example 1: 12Input: nums = [1,2,3]Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] Example 2: 12Input: nums = [0]Output: [[],[0]] 题目大意给定一个无重复元素的整数数组 nums，返回该数组所有可能的子集（即幂集）。幂集需包含所有可能的子集（包括空集和数组本身），且不能有重复子集，结果顺序可任意。 例如： 输入 nums = [1,2,3]，输出 [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]（共 2³=8 个子集）； ...

77. CombinationsGiven two integers n and k, return all possible combinations of k numbers chosen from the range [1, n]. You may return the answer in any order. Example 1: 1234Input: n = 4, k = 2Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]Explanation: There are 4 choose 2 = 6 total combinations.Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination. Example 2: 123Input: n = 1, k = 1Output: [[1]]Explanation: There is 1 choose 1 = 1 total combinat...

76. Minimum Window Substring题目Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). Example: 12Input: S = "ADOBECODEBANC", T = "ABC"Output: "BANC" Note: If there is no such window in S that covers all characters in T, return the empty string "". If there is such window, you are guaranteed that there will always be only one unique minimum window in S. 题目大意给定一个源字符串 s，再给一个字符串 T，要...

74. 搜索二维矩阵给你一个满足下述两条属性的 m x n 整数矩阵： 每行中的整数从左到右按非严格递增顺序排列。 每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。 示例 1： 12输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3输出：true 示例 2： 12输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13输出：false 解法1：二分查找由于矩阵具有特殊的有序性，可以将其视为一个有序的一维数组来处理： 整个矩阵可以看作是按行拼接而成的有序数组 使用二分查找高效定位目标值 通过计算将一维索引转换为二维矩阵的行和列 1234567891011121314151617181920212223242526272829303132class Solution {public: bool searchM...

73. Set Matrix Zeroes题目Given an *m* x *n* matrix. If an element is 0, set its entire row and column to 0. Do it in-place. Follow up: A straight forward solution using O(mn) space is probably a bad idea. A simple improvement uses O(m + n) space, but still not the best solution. Could you devise a constant space solution? Example 1: 12Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]Output: [[1,0,1],[0,0,0],[1,0,1]] Example 2: 12Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]Output: [[0,0,0,0],[0,4,...

72. Edit DistanceGiven two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. You have the following three operations permitted on a word: Insert a character Delete a character Replace a character Example 1: 123456Input: word1 = "horse", word2 = "ros"Output: 3Explanation: horse -> rorse (replace 'h' with 'r')rorse -> rose (remove 'r')rose -> ros (remove 'e') Example 2: 12...

71. Simplify PathYou are given an absolute path for a Unix-style file system, which always begins with a slash '/'. Your task is to transform this absolute path into its simplified canonical path. The rules of a Unix-style file system are as follows: A single period '.' represents the current directory. A double period '..' represents the previous/parent directory. Multiple consecutive slashes such as '//' and '///' are treated as a single slash &...

70. Climbing Stairs题目You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Note: Given n will be a positive integer. Example 1: Input: 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps Example 2: Input: 3 Output: 3 Explanation: There are three ways to climb to the top. 1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step ...

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