题目描述：
给定一个整数数组
nums
和一个目标值
target
，请你在该数组中找出和为目标值的那
两个
整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
Solution:
public class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(nums[i])) {
return new int[]{map.get(nums[i]), i};
map.put(target - nums[i], i);
return null;
题目描述：
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
节点结构：
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
Solution:
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int carry = 0;
ListNode dummy = new ListNode(0);
ListNode pre = dummy;
while (l1 != null || l2 != null || carry == 1) {
pre.next = new ListNode(carry);
pre = pre.next;
if (l1 != null) {
pre.val += l1.val;
l1 = l1.next;
if (l2 != null) {
pre.val += l2.val;
l2 = l2.next;
carry = pre.val / 10;
pre.val %= 10;
return dummy.next;
题目描述：
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
Solution:
public class Solution {
public int lengthOfLongestSubstring(String s) {
int[] map = new int[256];
int l = 0, r = 0;
int res = 0;
while (l <= r && l < s.length()) {
if (r < s.length() && map[s.charAt(r)] == 0) {
map[s.charAt(r++)]++;
res = Math.max(res, r - l);
} else {
map[s.charAt(l++)]--;
return res;
题目描述：
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
Solution：
public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int l = nums1.length + nums2.length + 1 >> 1;
int r = nums1.length + nums2.length + 2 >> 1;
return (find(nums1, nums2, 0, 0, l) + find(nums1, nums2, 0, 0, r)) / 2.0;
private double find(int[] nums1, int[] nums2, int start1, int start2, int k) {
if (start1 >= nums1.length) {
return nums2[start2 + k - 1];
if (start2 >= nums2.length) {
return nums1[start1 + k - 1];
if (k == 1) {
return Math.min(nums1[start1], nums2[start2]);
int mid1 = start1 + k / 2 - 1 >= nums1.length ? Integer.MAX_VALUE : nums1[start1 + k / 2 - 1];
int mid2 = start2 + k / 2 - 1 >= nums2.length ? Integer.MAX_VALUE : nums2[start2 + k / 2 - 1];
return mid1 > mid2 ? find(nums1, nums2, start1, start2 + k / 2, k - k / 2) :
find(nums1, nums2, start1 + k / 2, start2, k - k / 2);
题目描述：
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
Solution：
public class Solution {
private int left;
private int len;
public String longestPalindrome(String s) {
if (s.length() < 2) {
return s;
for (int i = 0; i < s.length(); i++) {
find(s, i, i);
find(s, i - 1, i);
return s.substring(left, left + len);
private void find(String s, int l, int r) {
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
if (r - l + 1 > len) {
left = l;
len = r - l + 1;
r++;
l--;
题目描述：
给定一个字符串 (s) 和一个字符模式 (p)。实现支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符。
'*' 匹配零个或多个前面的元素。
匹配应该覆盖整个字符串 (s) ，而不是部分字符串。
s 可能为空，且只包含从 a-z 的小写字母。p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。示例 1:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
s = "aa"
p = "a*"
输出: true
解释: '*' 代表可匹配零个或多个前面的元素, 即可以匹配 'a' 。因此, 重复 'a' 一次, 字符串可变为 "aa"。
示例 3:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。
示例 4:
s = "aab"
p = "c*a*b"
输出: true
解释: 'c' 可以不被重复, 'a' 可以被重复一次。因此可以匹配字符串 "aab"。
示例 5:
s = "mississippi"
p = "mis*is*p*."
输出: false
Solution：
public class Solution {
public boolean isMatch(String s, String p) {
boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
dp[0][0] = true;
for (int i = 2; i <= p.length(); i++) {
dp[0][i] = dp[0][i - 2] && p.charAt(i - 1) == '*';
for (int i = 0; i < s.length(); i++) {
for (int j = 0; j < p.length(); j++) {
if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') {
dp[i + 1][j + 1] = dp[i][j];
} else if (j > 0 && p.charAt(j) == '*') {
dp[i + 1][j + 1] = dp[i + 1][j - 1];
if (s.charAt(i) == p.charAt(j - 1) || p.charAt(j - 1) == '.') {
dp[i + 1][j + 1] = dp[i + 1][j - 1] || dp[i][j + 1] || dp[i + 1][j];
return dp[s.length()][p.length()];
题目描述：
给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
**说明：**你不能倾斜容器，且 n 的值至少为 2。
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
输入: [1,8,6,2,5,4,8,3,7]
输出: 49
Solution：
public class Solution {
public int maxArea(int[] height) {
int res = 0;
int l = 0, r = height.length - 1;
while (l < r) {
int h = height[l] < height[r] ? height[l++] : height[r--];
res = Math.max(res, h * (r - l + 1));
return res;
题目描述：
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 *a，b，c ，*使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
**注意：**答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[-1, 0, 1],
[-1, -1, 2]
Solution：
public class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length && nums[i] <= 0; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
int l = i + 1, r = nums.length - 1;
while (l < r) {
int sum = nums[l] + nums[r] + nums[i];
if (sum == 0) {
res.add(Arrays.asList(nums[i], nums[l], nums[r]));
while (l < r && nums[l] == nums[++l]) {
while (l < r && nums[r] == nums[--r]) {
} else if (sum < 0) {
l++;
} else {
r--;
return res;
题目描述：
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
Solution：
public class Solution {
private String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
private List<String> res = new ArrayList<>();
public List<String> letterCombinations(String digits) {
if (digits.length() == 0) {
return res;
dfs(digits, 0, new StringBuilder());
return res;
private void dfs(String digits, int index, StringBuilder sb) {
if (index == digits.length()) {
res.add(sb.toString());
return;
char[] chs = map[digits.charAt(index) - '0'].toCharArray();
for (char c : chs) {
sb.append(c);
dfs(digits, index + 1, sb);
sb.deleteCharAt(sb.length() - 1);
题目描述：
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
给定的 n 保证是有效的。
你能尝试使用一趟扫描实现吗？
Solution：
public class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = head;
ListNode slow = dummy;
for (int i = 0; i < n; i++) {
fast = fast.next;
while (fast != null) {
fast = fast.next;
slow = slow.next;
slow.next = slow.next.next;
return dummy.next;
题目描述：
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
Solution：
public class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else if (c == ')' && (stack.isEmpty() || stack.pop() != '(')) {
return false;
} else if (c == ']' && (stack.isEmpty() || stack.pop() != '[')) {
return false;
} else if (c == '}' && (stack.isEmpty() || stack.pop() != '{')) {
return false;
return stack.isEmpty();
题目描述：
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
Solution：
public class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode pre = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
pre.next = l1;
l1 = l1.next;
} else {
pre.next = l2;
l2 = l2.next;
pre = pre.next;
pre.next = l1 == null ? l2 : l1;
return dummy.next;
题目描述：
给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
例如，给出 n = 3，生成结果为：
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
Solution：
public class Solution {
private List<String> res = new ArrayList<>();
public List<String> generateParenthesis(int n) {
generate(0, 0, n, new StringBuilder());
return res;
private void generate(int l, int r, int n, StringBuilder sb) {
if (l == r && l == n) {
res.add(sb.toString());
return;
if (l > r) {
sb.append(')');
generate(l, r + 1, n, sb);
sb.deleteCharAt(sb.length() - 1);
if (l < n) {
sb.append('(');
generate(l + 1, r, n, sb);
sb.deleteCharAt(sb.length() - 1);
题目描述：
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
1->4->5,
1->3->4,
输出: 1->1->2->3->4->4->5->6
Solution：
public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) {
return null;
ListNode dummy = new ListNode(0);
ListNode pre = dummy;
Queue<ListNode> minHeap = new PriorityQueue<>((l1, l2) -> l1.val - l2.val);
for (ListNode list : lists) {
if (list != null) {
minHeap.offer(list);
while (!minHeap.isEmpty()) {
pre.next = minHeap.poll();
pre = pre.next;
if (pre.next != null) {
minHeap.offer(pre.next);
return dummy.next;
题目描述：
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
Solution：
public class Solution {
public void nextPermutation(int[] nums) {
int firstSmall = -1;
for (int i = nums.length - 1; i > 0; i--) {
if (nums[i - 1] < nums[i]) {
firstSmall = i - 1;
break;
if (firstSmall == -1) {
reverse(nums, 0, nums.length - 1);
return;
for (int i = nums.length - 1; i >= i; i--) {
if (nums[i] > nums[firstSmall]) {
swap(nums, firstSmall, i);
reverse(nums, firstSmall + 1, nums.length - 1);
break;
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
private void reverse(int[] nums, int start, int end) {
while (start < end) {
swap(nums, start++, end--);
题目描述：
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"
Solution：
public class Solution {
public int longestValidParentheses(String s) {
Stack<Integer> stack = new Stack<>();
int start = 0;
int res = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(i);
} else {
if (stack.isEmpty()) {
start = i + 1;
} else {
stack.pop();
res = Math.max(res, stack.isEmpty() ? i - start + 1 : i - stack.peek());
return res;
题目描述：
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
示例 2:
输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1
Solution：
public class Solution {
public int search(int[] nums, int target) {
if (nums.length < 1) {
return -1;
int l = 0, r = nums.length - 1;
while (l < r) {
int m = l + r >> 1;
if (nums[m] <= nums[nums.length - 1]) {
r = m;
} else {
l = m + 1;
if (target <= nums[nums.length - 1]) {
r = nums.length - 1;
} else {
r = l - 1;
l = 0;
while (l < r) {
int m = l + r >> 1;
if (nums[m] >= target) {
r = m;
} else {
l = m + 1;
return nums[l] == target ? l : -1;
题目描述：
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]
Solution：
public class Solution {
public int[] searchRange(int[] nums, int target) {
int l = searchFirst(nums, target);
int r = searchLast(nums, target);
if (l >= nums.length || nums[l] != target) {
return new int[]{-1, -1};
return new int[]{l, r};
private int searchFirst(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l < r) {
int m = l + r >> 1;
if (nums[m] < target) {
l = m + 1;
} else {
r = m;
return l;
private int searchLast(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l < r) {
int m = l + r + 1 >> 1;
if (nums[m] > target) {
r = m - 1;
} else {
l = m;
return l;
题目描述：
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例 1:
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[2,2,3]
示例 2:
输入: candidates = [2,3,5], target = 8,
所求解集为:
[2,2,2,2],
[2,3,3],
[3,5]
Solution：
public class Solution {
private List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
dfs(candidates, 0, target, new ArrayList<>());
return res;
private void dfs(int[] candidates, int start, int target, List<Integer> list) {
if (target == 0) {
res.add(new ArrayList<>(list));
return;
for (int i = start; i < candidates.length; i++) {
if (candidates[i] <= target) {
list.add(candidates[i]);
dfs(candidates, i, target - candidates[i], list);
list.remove(list.size() - 1);
题目描述：
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
Solution：
public class Solution {
public int trap(int[] height) {
int res = 0;
int lMax = 0, rMax = 0;
int l = 0, r = height.length - 1;
while (l < r) {
lMax = Math.max(lMax, height[l]);
rMax = Math.max(rMax, height[r]);
if (height[l] < height[r]) {
res += lMax - height[l++];
} else {
res += rMax - height[r--];
return res;
题目描述：
给定一个没有重复数字的序列，返回其所有可能的全排列。
输入: [1,2,3]
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
Solution：
public class Solution {
private List<List<Integer>> res = new ArrayList<>();
private boolean[] visited;
public List<List<Integer>> permute(int[] nums) {
visited = new boolean[nums.length];
permute(nums, new ArrayList<>());
return res;
private void permute(int[] nums, List<Integer> list) {
if (list.size() == nums.length) {
res.add(new ArrayList<>(list));
for (int i = 0; i < nums.length; i++) {
if (!visited[i]) {
visited[i] = true;
list.add(nums[i]);
permute(nums, list);
list.remove(list.size() - 1);
visited[i] = false;
题目描述：
给定一个 n × n 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。
你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
示例 1:
给定 matrix =
[1,2,3],
[4,5,6],
[7,8,9]
原地旋转输入矩阵，使其变为:
[7,4,1],
[8,5,2],
[9,6,3]
示例 2:
给定 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]
Solution：
* 以第一个数据为例分析：
* 1 2 3
* 4 5 6
* 7 8 9
* 先做左右对称翻转，得到：
* 3 2 1
* 6 5 4
* 9 8 7
* 再以副对角线为轴做翻转，得到：
* 7 4 1
* 8 5 2
* 9 6 3
* 此时即为要求的结果
* 故——要先做左右对称翻转，再做一次副对角线翻转即可
public class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < (n >> 1); j++) {
swap(matrix, i, j, i, n - j - 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - i; j++) {
swap(matrix, i, j, n - j - 1, n - i - 1);
private void swap(int[][] matrix, int i, int j, int p, int q) {
int temp = matrix[i][j];
matrix[i][j] = matrix[p][q];
matrix[p][q] = temp;
题目描述：
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
["ate","eat","tea"],
["nat","tan"],
["bat"]
所有输入均为小写字母。
不考虑答案输出的顺序。
Solution：
public class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String str : strs) {
StringBuilder sb = new StringBuilder();
char[] ch = new char[26];
for (int i = 0; i < str.length(); i++) {
ch[str.charAt(i) - 'a']++;
for (char c : ch) {
sb.append(c).append(' ');
String key = sb.toString();
map.putIfAbsent(key, new ArrayList<>());
map.get(key).add(str);
return new ArrayList<>(map.values());
题目描述：
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
Solution：
public class Solution {
public int maxSubArray(int[] nums) {
if (nums.length == 0) {
return 0;
int res = nums[0];
int max = 0;
for (int num : nums) {
max = Math.max(max + num, num);
res = Math.max(res, max);
return res;
题目描述：
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例 1:
输入: [2,3,1,1,4]
输出: true
解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。
示例 2:
输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
Solution：
public class Solution {
public boolean canJump(int[] nums) {
int last = nums.length - 1;
for (int i = nums.length - 1; i >= 0; i--) {
if (nums[i] + i >= last) {
last = i;
return last == 0;
题目描述：
给出一个区间的集合，请合并所有重叠的区间。
示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
Solution：
public class Solution {
public List<Interval> merge(List<Interval> intervals) {
if (intervals == null || intervals.size() < 2) {
return intervals;
List<Interval> list = new ArrayList<>();
intervals.sort(Comparator.comparingInt(interval -> interval.start));
Interval pre = null;
for (Interval interval : intervals) {
if (pre == null || pre.end < interval.start) {
list.add(interval);
pre = interval;
} else {
pre.end = Math.max(pre.end, interval.end);
return list;
题目描述：
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
例如，上图是一个7 x 3 的网格。有多少可能的路径？
说明： m 和 n 的值均不超过 100。
示例 1:
输入: m = 3, n = 2
输出: 3
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3
输出: 28
Solution：
public class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 1;
} else {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
return dp[m - 1][n - 1];
题目描述：
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
**说明：**每次只能向下或者向右移动一步。
[1,3,1],
[1,5,1],
[4,2,1]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
Solution：
public class Solution {
public int minPathSum(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
int m = grid.length;
int n = grid[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 && j == 0) {
continue;
if (i == 0) {
grid[i][j] += grid[i][j - 1];
} else if (j == 0) {
grid[i][j] += grid[i - 1][j];
} else {
grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
return grid[m - 1][n - 1];
题目描述：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
**注意：**给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
Solution：
public class Solution {
public int climbStairs(int n) {
int a = 1;
int b = 1;
for (int i = 2; i <= n; i++) {
int temp = b;
b += a;
a = temp;
return b;
给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
示例 1:
输入: word1 = "horse", word2 = "ros"
输出: 3
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
示例 2:
输入: word1 = "intention", word2 = "execution"
输出: 5
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')
Solution：
public class Solution {
public int minDistance(String word1, String word2) {
int[][] dp = new int[word1.length() + 1][word2.length() + 1];
for (int i = 1; i < dp.length; i++) {
dp[i][0] = i;
for (int i = 0; i < dp[0].length; i++) {
dp[0][i] = i;
for (int i = 0; i < dp.length - 1; i++) {
for (int j = 0; j < dp[0].length - 1; j++) {
if (word1.charAt(i) == word2.charAt(j)) {
dp[i + 1][j + 1] = dp[i][j];
} else {
dp[i + 1][j + 1] = Math.min(Math.min(dp[i][j], dp[i + 1][j]), dp[i][j + 1]) + 1;
return dp[word1.length()][word2.length()];
题目描述：
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
不能使用代码库中的排序函数来解决这道题。
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
Solution：
class Solution {
// 解法一：桶排序
public void sortColors(int[] nums) {
if (nums == null) {
return;
int[] count = new int[3]; // 统计1、2、3出现的次数
for (int num : nums) {
count[num]++;
int index = 0;
for (int i = 0; i < count[0]; i++) {
nums[index++] = 0;
for (int i = 0; i < count[1]; i++) {
nums[index++] = 1;
for (int i = 0; i < count[2]; i++) {
nums[index++] = 2;
// 解法二：三路快排
public void sortColors(int[] nums) {
if (nums == null) {
return;
int zero = -1;// 保证[0, zero]区间内为0
int two = nums.length;// 保证[two, nums.length - 1]区间内为2
for (int i = 0; i < two; ) {
if (nums[i] == 0) {
nums[i++] = nums[++zero];
nums[zero] = 0;
} else if (nums[i] == 2) {
nums[i] = nums[--two];
nums[two] = 2;
} else {
i++;
给定一个字符串 S 和一个字符串 T，请在 S 中找出包含 T 所有字母的最小子串。
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
如果 S 中不存这样的子串，则返回空字符串 ""。
如果 S 中存在这样的子串，我们保证它是唯一的答案。
Solution：
public class Solution {
public String minWindow(String s, String t) {
String res = "";
int l = 0, r = 0;
int[] tFlag = new int[256];
int[] sFlag = new int[256];
int count = t.length();
for (int i = 0; i < t.length(); i++) {
tFlag[t.charAt(i)]++;
while (l <= s.length() - t.length()) {
if (count > 0 && r < s.length()) {
if (sFlag[s.charAt(r)]++ < tFlag[s.charAt(r++)]) {
count--;
} else {
if (count == 0 && (res.length() == 0 || res.length() > r - l)) {
res = s.substring(l, r);
if (tFlag[s.charAt(l)] >= sFlag[s.charAt(l++)]--) {
count++;
return res;
题目描述：
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
**说明：**解集不能包含重复的子集。
输入: nums = [1,2,3]
[1,2,3],
[1,3],
[2,3],
[1,2],
Solution：
public class Solution {
private List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
dfs(nums, 0, new ArrayList<>());
return res;
private void dfs(int[] nums, int index, List<Integer> list) {
if (index == nums.length) {
res.add(new ArrayList<>(list));
return;
dfs(nums, index + 1, list);
list.add(nums[index]);
dfs(nums, index + 1, list);
list.remove(list.size() - 1);
题目描述：
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
board =
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.
Solution：
public class Solution {
private boolean[][] visited;
private int index = 0;
public boolean exist(char[][] board, String word) {
if (board == null || board.length == 0 || board[0].length == 0 || word == null) {
return false;
visited = new boolean[board.length][board[0].length];
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (exit(board, word, i, j)) {
return true;
return false;
private boolean exit(char[][] board, String word, int row, int col) {
if (index == word.length()) {
return true;
boolean flag = false;
if (col >= 0 && col < board[0].length
&& row >= 0 && row < board.length
&& !visited[row][col] && board[row][col] == word.charAt(index)) {
visited[row][col] = true;
index++;
flag = exit(board, word, row + 1, col)
|| exit(board, word, row - 1, col)
|| exit(board, word, row, col + 1)
|| exit(board, word, row, col - 1);
if (!flag) {
index--;
visited[row][col] = false;
return flag;
题目描述：
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
输入: [2,1,5,6,2,3]
输出: 10
Solution：
public class Solution {
public int largestRectangleArea(int[] heights) {
if (heights == null || heights.length == 0) {
return 0;
Stack<Integer> stack = new S tack<>();
int res = 0;
for (int i = 0; i <= heights.length; i++) {
int currentHeight = i == heights.length ? -1 : heights[i];
while (!stack.isEmpty() && currentHeight <= heights[stack.peek()]) {
int stackHeight = heights[stack.pop()];
res = Math.max(res, stackHeight * (stack.isEmpty() ? i : i - stack.peek() - 1));
stack.push(i);
return res;
题目描述：
给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
输出: 6
Solution：
public class Solution {
public int maximalRectangle(char[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return 0;
int res = 0;
int[] height = new int[matrix[0].length];
for (int i = 0; i < matrix.length; i++) {
Stack<Integer> stack = new Stack<>();
for (int j = 0; j <= height.length; j++) {
if (j < height.length) {
height[j] = (matrix[i][j] == '1') ? 1 + height[j] : 0;
int curHeight = j == height.length ? -1 : height[j];
while (!stack.isEmpty() && curHeight <= height[stack.peek()]) {
int stackHeight = height[stack.pop()];
int width = stack.isEmpty() ? j : j - stack.peek() - 1;
res = Math.max(res, width * stackHeight);
stack.push(j);
return res;
public class Solution {
public int maximalRectangle(char[][] matrix) {
if (matrix.length == 0 || matrix[0].length == 0) {
return 0;
int res = 0;
int m = matrix.length;
int n = matrix[0].length;
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == '1') {
dp[i][j] = j == 0 ? 1 : dp[i][j - 1] + 1;
int minWidth = dp[i][j];
for (int k = i; k >= 0; k--) {
minWidth = Math.min(minWidth, dp[k][j]);
res = Math.max(res, minWidth * (i - k + 1));
return res;
题目描述：
给定一个二叉树，返回它的中序 遍历。
输入: [1,null,2,3]
输出: [1,3,2]
Solution：
public class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;
while (!stack.isEmpty() || node != null) {
while (node != null) {
stack.push(node);
node = node.left;
node = stack.pop();
list.add(node.val);
node = node.right;
return list;
题目描述：
给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
输入: 3
输出: 5
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
Solution：
public class Solution {
public int numTrees(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 0; j < i; j++) {
dp[i] += dp[j] * dp[i - j - 1];
return dp[n];
题目描述：
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
1 3
输出: true
示例 2:
1 4
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。
Solution：
public class Solution {
public boolean isValidBST(TreeNode root) {
TreeNode pre = null;
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;
while (!stack.isEmpty() || node != null) {
while (node != null) {
stack.push(node);
node = node.left;
node = stack.pop();
if (pre != null && pre.val >= node.val) {
return false;
pre = node;
node = node.right;
return true;
题目描述：
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
2 2
\ \
3 3
Solution：
public class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
return isSymmetric(root.left, root.right);
private boolean isSymmetric(TreeNode left, TreeNode right) {
if (left == null && right == null) {
return true;
if (left == null || right == null) {
return false;
return left.val == right.val && isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
public class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node1 = queue.poll();
TreeNode node2 = queue.poll();
if (node1 == null && node2 == null) {
continue;
if (node1 == null || node2 == null || node1.val != node2.val) {
return false;
queue.offer(node1.left);
queue.offer(node2.right);
queue.offer(node1.right);
queue.offer(node2.left);
return true;
题目描述：
给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。
给定二叉树: [3,9,20,null,null,15,7],
9 20
15 7
返回其层次遍历结果：
[9,20],
[15,7]
Solution：
public class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> list = new ArrayList<>();
while (size-- > 0) {
TreeNode node = queue.poll();
list.add(node.val);
if (node.left != null) {
queue.offer(node.left);
if (node.right != null) {
queue.offer(node.right);
res.add(list);
return res;
题目描述：
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
给定二叉树 [3,9,20,null,null,15,7]，
9 20
15 7
返回它的最大深度 3 。
Solution：
public class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
题目描述：
根据一棵树的前序遍历与中序遍历构造二叉树。
你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
9 20
15 7
Solution：
public class Solution {
private Map<Integer, Integer> map = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length == 0 || preorder.length != inorder.length) {
return null;
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
return build(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
private TreeNode build(int[] preorder, int[] inorder, int ps, int pe, int is, int ie) {
if (ps > pe || is > ie) {
return null;
TreeNode root = new TreeNode(preorder[ps]);
int index = map.get(preorder[ps]);
root.left = build(preorder, inorder, ps + 1, index - is + ps, is, index - 1);
root.right = build(preorder, inorder, index - is + ps + 1, pe, index + 1, ie);
return root;
题目描述：
给定一个二叉树，原地将它展开为链表。
例如，给定二叉树
2 5
/ \ \
3 4 6
将其展开为：
Solution：
public class Solution {
private TreeNode last = new TreeNode(0);
public void flatten(TreeNode root) {
if (root == null) {
return;
last.right = root;
last.left = null;
last = last.right;
TreeNode temp = root.right;
flatten(root.left);
flatten(temp);
题目描述：
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
Solution：
public class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
int res = 0;
int curMin = prices[0];
for (int price : prices) {
res = Math.max(res, price - curMin);
curMin = Math.min(price, curMin);
return res;
题目描述：
给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
示例 1:
输入: [1,2,3]
2 3
输出: 6
示例 2:
输入: [-10,9,20,null,null,15,7]
9 20
15 7
输出: 42
Solution：
public class Solution {
private int res = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
helper(root);
return res;
private int helper(TreeNode root) {
if (root == null) {
return 0;
int left = Math.max(0, helper(root.left));
int right = Math.max(0, helper(root.right));
res = Math.max(res, left + right + root.val);
return root.val + Math.max(left, right);
题目描述：
给定一个未排序的整数数组，找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
Solution：
public class Solution {
public int longestConsecutive(int[] nums) {
int res = 0;
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
if (map.containsKey(num)) {
continue;
map.put(num, 1 + map.getOrDefault(num + 1, 0));
while (map.containsKey(num - 1)) {
map.put(num - 1, map.get(num--) + 1);
for (int key : map.keySet()) {
res = Math.max(res, map.get(key));
return res;
题目描述：
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
Solution：
public class Solution {
public int singleNumber(int[] nums) {
int res = 0;
for (int num : nums) {
res ^= num;
return res;
题目描述：
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
注意你可以重复使用字典中的单词。
示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
Solution：
public class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
if (s == null || "".equals(s)) {
return true;
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
String sub = s.substring(j, i);
if (dp[j] && wordDict.contains(sub)) {
dp[i] = true;
break;
return dp[s.length()];
题目描述：
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
Solution：
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
break;
return fast != null && fast.next != null;
题目描述：
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
**说明：**不允许修改给定的链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：tail connects to node index 0
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：no cycle
解释：链表中没有环。
Solution：
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
break;
if (fast == null || fast.next == null) {
return null;
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
return fast;
题目描述：
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
你是否可以在 O(1) 时间复杂度内完成这两种操作？
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
Solution：
public class LRUCache {
private LinkedHashMap<Integer, Integer> map;
private int capacity;
public LRUCache(int capacity) {
map = new LinkedHashMap<Integer, Integer>(16, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > LRUCache.this.capacity;
this.capacity = capacity;
public int get(int key) {
return map.getOrDefault(key, -1);
public void put(int key, int value) {
map.put(key, value);
题目描述：
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
示例 1:
输入: 4->2->1->3
输出: 1->2->3->4
示例 2:
输入: -1->5->3->4->0
输出: -1->0->3->4->5
Solution：
public class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
ListNode mid = getMid(head);
ListNode next = mid.next;
mid.next = null;
return mergeSort(sortList(head), sortList(next));
private ListNode mergeSort(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode pre = dummy;
while (l1 != null && l2 != null) {
if (l1.val > l2.val) {
pre.next = l2;
l2 = l2.next;
} else {
pre.next = l1;
l1 = l1.next;
pre = pre.next;
pre.next = l1 == null ? l2 : l1;
return dummy.next;
private ListNode getMid(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
return slow;
题目描述：
给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
Solution：
public class Solution {
public int maxProduct(int[] nums) {
int res = nums[0];
int max = 1;
int min = 1;
for (int num : nums) {
if (num < 0) {
int temp = min;
min = max;
max = temp;
max = Math.max(max * num, num);
min = Math.min(min * num, num);
res = Math.max(max, res);
return res;
题目描述：
设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) -- 将元素 x 推入栈中。
pop() -- 删除栈顶的元素。
top() -- 获取栈顶元素。
getMin() -- 检索栈中的最小元素。
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
Solution：
public class MinStack {
private Stack<Integer> stack = new Stack<>();
private Stack<Integer> minStack = new Stack<>();
/** initialize your data structure here. */
public MinStack() {
public void push(int x) {
stack.push(x);
if (minStack.isEmpty() || minStack.peek() > x) {
minStack.push(x);
} else {
minStack.push(minStack.peek());
public void pop() {
minStack.pop();
stack.pop();
public int top() {
return stack.peek();
public int getMin() {
return minStack.peek();
题目描述：
编写一个程序，找到两个单链表相交的起始节点。
如下面的两个链表**：**
在节点 c1 开始相交。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
示例 2：
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。
如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
Solution：