LeetCode 516. 最长回文子序列
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
输入：s = "bbbab"输出：4解释：一个可能的最长回文子序列为 "bbbb" 。
示例 2：
输入：s = "cbbd"输出：2解释：一个可能的最长回文子序列为 "bb" 。
提示：
1 <= s.length <= 1000
s 仅由小写英文字母组成
思路
本题与LeetCode 5. 最长回文子串的思路大体相同。
状态转移方程为 与最长回文子串的状态转移方程大同小异。我们只需根据子串的长度迭代即可。
class Solution { public int longestPalindromeSubseq(String s) { // dp[i][j] 表示i和j之间最长的子序列 int len = s.length(), max = 1; int[][] dp = new int[len][len]; for (int i = ...
LeetCode 221. 最大正方形
在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
示例 1：
img
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]输出：4
示例 2：
img
输入：matrix = [["0","1"],["1","0"]]输出：1
示例 3：
输入：matrix = [["0"]]输出：0
提示：
m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] 为 '0' 或 '1'
思路
本题也是动态规划的题，重点在于找到转台转移方程。
设表示第行第列包含的最大正方形边长，稍加观察即发现其满足下列方程： 我们只需设置好边界条件，然后填充dp数组即可。
class Solution { public int maximalSquare(char[][] matrix) { ...
LeetCode 40. 组合总和 II
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,输出:[[1,1,6],[1,2,5],[1,7],[2,6]]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,输出:[[1,2,2],[5]]
提示:
1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30
思路
本题的思路与组合总数大抵一致，但由于本题存在重复元素，所以要先进行排序，然后剪枝，否则会超时。
如果当前搜索的序列中的前缀存在重复元素，只需将前缀中的重复元素去除即可。
如序列1,1,1,2,3的搜索结果中一定包含了1,1,2,3的搜索结果。
cla ...
LeetCode 39. 组合总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 1：
输入：candidates = [2,3,6,7], target = 7输出：[[2,2,3],[7]]解释：2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。7 也是一个候选， 7 = 7 。仅有这两种组合。
示例 2：
输入: candidates = [2,3,5], target = 8输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：
输入: candidates = [2], target = 1输出: []
提示：
1 <= candidates.length <= 30
1 ...
LeetCode 189. 轮转数组
给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例 1:
输入: 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:
输入：nums = [-1,-100,3,99], k = 2输出：[3,99,-1,-100]解释: 向右轮转 1 步: [99,-1,-100,3]向右轮转 2 步: [3,99,-1,-100]
提示：
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105
进阶：
尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？
思路
问题的难度在于仅借助复杂度的空间，使得数组向前移动位。蛮力算法需要花费时间，我们考虑迭代版本。
假设从开始 ...
LeetCode 46. 全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3]输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1]输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1]输出：[[1]]
提示：
1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同
思路
直接爆搜。
class Solution { int[] nums; boolean[] visit; int len; List<List<Integer>> ans; public List<List<Integer>> permute(int[] nums) { ans = new ArrayList<>(); this.nu ...
LeetCode 77. 组合
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1：
输入：n = 4, k = 2输出：[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4],]
示例 2：
输入：n = 1, k = 1输出：[[1]]
提示：
1 <= n <= 20
1 <= k <= n
思路
与全排列的算法比较像，不同的是此处求组合，需要用一个start变量控制当前搜索到的分支，即只搜索start之后的区间，避免跟之前的结果重复。
class Solution { int n, k; List<List<Integer>> ans; public List<List<Integer>> combine(int n, int k) { this.n = n; this.k = k; ans = new ArrayList<>(); d ...
LeetCode 78. 子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3]输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0]输出：[[],[0]]
提示：
1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同
思路
个元素有个子集。只需从遍历至，每一个数对应的比特位组合都表示不同的子集。
class Solution { int len; public List<List<Integer>> subsets(int[] nums) { len = nums.length; int size = 1 << len; List<List<Integer>> ans = new Ar ...
极限题库
本篇文章主要搜集一些有意思的极限数学题，不定期更新。
primary@声明：
本文所有题目来源于网络，知识产权归出题人所有。
1.
Solution.
变上限积分的极限，离不开三种方法：
洛必达
中值定理
分区间积分
此处我们尝试分区间积分。根据海涅原理，有
2.
Solution.
尝试幂指化。 由Lagrange中值定理，原式化为： 其中介于和之间。不难求得它们的极限为。所以原式化为： 再次使用Lagrange中值定理，得： 其中介于和之间。同样不难求得它们的极限为。 此解法的巧妙之处在于连续运用Lagrange中值定理化简极限。
3.
Solution 1.
Solution 2.
4.
Solution.
这里需要使用一个常见的技巧： 为奇数为偶数
5.
Solution 1.
Solution 2.
参照武忠祥老师的”三部曲“法则，可略过幂指化的过程。另外此处用到了一个常见的等价无穷小：
6.
Solution.
注意到广义二项式定理（牛顿二项式定理）：
7.
Solution 1.
注意到Stiring公式： ...
LeetCode 322. 零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11输出：3 解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3输出：-1
示例 3：
输入：coins = [1], amount = 0输出：0
提示：
1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104
思路
一道简单的动规题。状态转移方程为
class Solution { public int coinChange(int[] coins, int amount) { if (amount == 0) return 0; // dp[i] = min(dp[amo ...