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 ...
LeetCode 142. 环形链表 II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
img
输入：head = [3,2,0,-4], pos = 1输出：返回索引为 1 的链表节点解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
img
输入：head = [1,2], pos = 0输出：返回索引为 0 的链表节点解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
img
输入：head = [1], pos = -1输出：返回 null解释：链表中没有环。
提示：
链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的 ...
LeetCode 82. 删除排序链表中的重复元素 II
给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
示例 1：
img
输入：head = [1,2,3,3,4,4,5]输出：[1,2,5]
示例 2：
img
输入：head = [1,1,1,2,3]输出：[2,3]
提示：
链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序 排列
思路
使用dummy保存头结点，prev和curr进行移动，每当发现curr后面的值重复时，则将curr移动到下一个不重复的节点，然后将prev的next指向curr即可。
class Solution { public ListNode deleteDuplicates(ListNode head) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode prev = dummy, curr = head; w ...
LeetCode 98. 验证二叉搜索树
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
img
输入：root = [2,1,3]输出：true
示例 2：
img
输入：root = [5,1,4,null,null,3,6]输出：false解释：根节点的值是 5 ，但是右子节点的值是 4 。
提示：
树中节点数目范围在[1, 104] 内
-231 <= Node.val <= 231 - 1
思路
一棵树是二叉搜索树当且仅当它的左孩子和右孩子是二叉搜索树，且当前节点的值在范围内。故得出递归算法如下。
class Solution { public boolean isValidBST(TreeNode root) { return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE); } public boolean ...
LeetCode 1401. 圆和矩形是否有重叠
给你一个以 (radius, x_center, y_center) 表示的圆和一个与坐标轴平行的矩形 (x1, y1, x2, y2)，其中 (x1, y1) 是矩形左下角的坐标，(x2, y2) 是右上角的坐标。
如果圆和矩形有重叠的部分，请你返回 True ，否则返回 False 。
换句话说，请你检测是否 存在 点 (xi, yi) ，它既在圆上也在矩形上（两者都包括点落在边界上的情况）。
示例 1：
img
输入：radius = 1, x_center = 0, y_center = 0, x1 = 1, y1 = -1, x2 = 3, y2 = 1输出：true解释：圆和矩形有公共点 (1,0)
示例 2：
输入：radius = 1, x_center = 0, y_center = 0, x1 = -1, y1 = 0, x2 = 0, y2 = 1输出：true
示例 3：
输入：radius = 1, x_center = 1, y_center = 1, x1 = -3, y1 = -3, x2 = 3, y2 = 3输出：true
示例 4：
输 ...
LeetCode 232. 用栈实现队列
本题是一道简单题，饶有趣味的是，本题的解法是分摊复杂度的一种典型应用。
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：
你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
示例 1：
输入：["MyQueue", "push", "push", "peek", "pop", "empty"][[], [1], [2], [], [], []]输出：[null, null, null, 1, 1, false]解释：My ...
LeetCode 5. 最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad"输出："bab"解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"输出："bb"
提示：
1 <= s.length <= 1000
s 仅由数字和英文字母组成
思路
不难发现，当到构成一个回文子串时，到一定也构成一个回文子串。若表示到的子串长度，那么状态转移方程为： 但是本题并不需要求最长的子串长，而是求下标。所以我们让dp[i][j]表示i和j之间是否构成回文子串。
class Solution { public String longestPalindrome(String s) { int len = s.length(); if (len < 2) return s; int max = 0; int x = 0, y = 0; // dp[i][j]表示从s[i]到s[j]是不是一个回文字符串 boolean[][] dp = new boo ...