Leetcode78. 子集
Leetcode78. 子集
题目描述
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
12输入：nums = [1,2,3]输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
12输入：nums = [0]输出：[[],[0]]
提示：
1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同
解题思路
这道题只能用暴力枚举的方式求解。使用DFS+回溯实现比较简单。
用index来代表当前处理元素的下标，对于每一个元素，都有选择和不选择两种状态，对这两种情况分别递归：
如果不选择当前元素，则：
1DFS(nums,index+1,temp);
直接递归下一个元素即可。
如果选择当前元素，则：
12temp.push_back(nums[index]);DFS(nums,index+1,temp);
将当前元素加入一个可能的答案序 ...
Leetcode76. 最小覆盖子串
Leetcode76. 最小覆盖子串
题目描述
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
**注意：**如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
12输入：s = "ADOBECODEBANC", t = "ABC"输出："BANC"
示例 2：
12输入：s = "a", t = "a"输出："a"
提示：
1≤s.length,t.length≤1051 \leq s.length, t.length \leq 10^51≤s.length,t.length≤105
s 和 t 由英文字母组成
**进阶：**你能设计一个在 o(n) 时间内解决此问题的算法吗？
解题思路
这道题要求给出时间复杂度为O(n)O(n)O(n)的算法，我们考虑用滑动窗口算法去解决。
思路如下：用两个指针分别指示窗口的边界，记为i和j ...
Leetcode72. 编辑距离
Leetcode72. 编辑距离
题目描述
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
示例 1：
123456输入：word1 = "horse", word2 = "ros"输出：3解释：horse -> rorse (将 'h' 替换为 'r')rorse -> rose (删除 'r')rose -> ros (删除 'e')
示例 2：
12345678输入：word1 = "intention", word2 = "execution"输出：5解释：intention -> inention (删除 't')inention -> enention (将 'i' 替换为 'e')e ...
Leetcode64. 最小路径和
Leetcode64. 最小路径和
题目描述
给定一个包含非负整数的 *m* x *n* 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
**说明：**每次只能向下或者向右移动一步。
示例 1：
123输入：grid = [[1,3,1],[1,5,1],[4,2,1]]输出：7解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：
12输入：grid = [[1,2,3],[4,5,6]]输出：12
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100
解题思路
这道题是经典的动态规划题。
由于路径的方向只能是向下或向右，因此网格的第一行的每个元素只能从左上角元素开始向右移动到达，网格的第一列的每个元素只能从左上角元素开始向下移动到达，此时的路径是唯一的，因此每个元素对应的最小路径和即为对应的路径上的数字总和。
对于不在第一行和第一列的元素，可以从其上方相邻元素向下移动一步到达，或者从其左方相邻元素向右移动一 ...
Leetcode62. 不同路径
Leetcode62. 不同路径
题目描述
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
12输入：m = 3, n = 7输出：28
示例 2：
1234567输入：m = 3, n = 2输出：3解释：从左上角开始，总共有 3 条路径可以到达右下角。1. 向右 -> 向下 -> 向下2. 向下 -> 向下 -> 向右3. 向下 -> 向右 -> 向下
示例 3：
12输入：m = 7, n = 3输出：28
示例 4：
12输入：m = 3, n = 3输出：6
提示：
1 <= m, n <= 100
题目数据保证答案小于等于 2×1092 \times 10^92×109
解题思路
这道题第一反应就是先用动态规划试试，与最小路径和有些类似。
如果我们用dp[i][j]dp[i][j]dp[i][j]表示从左上角走到(i,j)(i,j)(i ...
Leetcode56. 合并区间
Leetcode56. 合并区间
题目描述
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
示例 1：
123输入：intervals = [[1,3],[2,6],[8,10],[15,18]]输出：[[1,6],[8,10],[15,18]]解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
123输入：intervals = [[1,4],[4,5]]输出：[[1,5]]解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
提示：
1≤intervals.length≤1041 \leq intervals.length \leq 10^41≤intervals.length≤104
intervals[i].length==2intervals[i].length == 2intervals[i].length==2
0≤starti≤endi≤1040 \leq st ...
Leetcode54. 螺旋矩阵
Leetcode54. 螺旋矩阵
题目描述
给你一个 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
解题思路
这道题不涉及复杂难懂的算法，是一道模拟题。我们只需要去模拟螺旋的过程就可以得出答案。
为了模拟螺旋的过程，我们需要标记二维表的四个角的位置：左上（top,left)，左下(bottom,left)，右上(top,right)，右下(bottom,right)。容易看出的是，我们只需要标记上(top)下(bottom)左(left ...
Leetcode48. 旋转图像
Leetcode48. 旋转图像
题目描述
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在** 原地** 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
示例 1：
12输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]输出：[[7,4,1],[8,5,2],[9,6,3]]
示例 2：
12输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
示例 3：
12输入：matrix = [[1]]输出：[[1]]
示例 4：
12输入：matrix = [[1,2],[3,4]]输出：[[3,1],[4,2]]
提示：
matrix.length == n
matrix[i].length == n
1 <= n <= 20
-1000 <= matrix[i][j] <= ...
Leetcode46. 全排列
Leetcode46. 全排列
题目描述
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
12345678910输入: [1,2,3]输出:[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
解题思路
这道题不涉及巧妙头疼的算法，只是单纯的考察递归回溯的编程技巧。
我们以示例数据为例，分析一下我们的思路，力求清晰易懂。
[1,2,3]的全排列怎么求呢？按照我们高中学的排列组合的知识，全排列的求解相当于在_ _ _三个位置上依次选择一个数字填入。在第一个位置可以选择1，2，3中的任意一个，第二个位置可以选择除去第一个位置选择的数字之外的所有数字，第三个位置只能选择剩下的唯一一个数字。比如，如果第一个位置选择1，2，3中的1，那么第二个位置可以选择2，3中的一个任意一个，假设选择3，那么第三个位置就只能选择2。
上述过程就是求解全排列的过程，然后我们思考怎么用递归的方式去模拟这一过程。
为了避免选择之前位置已经选择的数字，我们使用一个visited数组去记录当前数字是否已经被选择。我们用path数组去 ...
Leetcode43. 字符串相乘
Leetcode43. 字符串相乘
题目描述
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
示例 1:
12输入: num1 = "2", num2 = "3"输出: "6"
示例 2:
12输入: num1 = "123", num2 = "456"输出: "56088"
说明：
num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头，除非是数字 0 本身。
不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。
解题思路
方法一 列竖式计算法
算法详述
这道题最常见的解法就是模拟列竖式计算的方法进行计算两个字符串的值。
如上图所示，当nums1和nums2均不为0的时候，将nums1和nums2分别视为被乘数和乘数，从右往左遍历乘数，将乘数的每一位与被乘数相乘得到相应的结 ...