# Leetcode Top100题目和答案（Java完整版 面试必备）

2019年12月05日 阅读数：169

——leetcode数据库 19道题
——剑指Offer 66道题html

java

### 1.两数之和

``````给定 nums = [2, 7, 11, 15], target = 9

``````

Solution:面试

``````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;
}
}
``````

### 2.两数相加

``````输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)

``````

``````public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
``````

Solution:

``````class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);

int sum = 0; // 结果
int more = 0; // 进位
ListNode pre = dummy;
while (l1 != null || l2 != null || more > 0) {
sum = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + more;
more = sum / 10;
sum %= 10;
ListNode node = new ListNode(sum);
pre.next = node;
pre = node;
l1 = l1 == null ? null : l1.next;
l2 = l2 == null ? null : l2.next;
}
return dummy.next;
}
}
``````

### 3.无重复字符的最长子串

``````输入: "abcabcbb"

``````

``````输入: "bbbbb"

``````

``````输入: "pwwkew"

请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
``````

Solution:

``````class Solution {
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() < 1) {
return 0;
}

int[] map = new int[256];
int l = 0;
int r = 0; // 滑动窗口为[l, r)，其间为不重复的元素
int res = 0;
while (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;
}
}
``````

### 4.寻找两个有序数组的中位数

``````nums1 = [1, 3]
nums2 = [2]

``````

``````nums1 = [1, 2]
nums2 = [3, 4]

``````

Solution：

``````public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// 保证nums1不是最长的，时间复杂度可转化为O(log(Min(m, n)))
if (nums1.length > nums2.length) {
return findMedianSortedArrays(nums2, nums1);
}

int left = 0;
int right = nums1.length;
int halfLen = (nums1.length + nums2.length + 1) >> 1;

while (left <= right) {
int i = (left + right) >> 1; // nums1[i, nums1.length)为要分割的右半部分
int j = halfLen - i; // nums2[j, nums2.length)为要分割的右半部分
if (i < right && nums2[j - 1] > nums1[i]) { // nums1分割点此时须要右移
left++;
} else if (i > left && nums1[i - 1] > nums2[j]) { // nums1 分割点此时须要左移
right--;
} else {
int leftMax = (i == 0) ? nums2[j - 1] :
(j == 0 ? nums1[i - 1] : Math.max(nums1[i - 1], nums2[j - 1]));
if (((nums1.length + nums2.length) & 1) == 1) {
return leftMax * 1.0;
}
int rightMin = (i == nums1.length) ? nums2[j] :
(j == nums2.length ? nums1[i] : Math.min(nums1[i], nums2[j]));
return (leftMax + rightMin) / 2.0;
}
}
return 0.0;
}
}
``````

### 5.最长回文子串

``````输入: "babad"

``````

``````输入: "cbbd"

``````

Solution：

``````/**
* 中心扩展法
*/
public class Solution {
private int left;
private int len;

public String longestPalindrome(String s) {
if (s == null || s.length() < 2) {
return s;
}

for (int i = 0; i < s.length(); i++) {
find(s, i, i); // 奇数长度
find(s, i, i + 1); // 偶数长度
}
return s.substring(left, left + len);
}

private void find(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
if (right - left + 1 > len) {
len = right - left + 1;
this.left = left;
}
right++;
left--;
}
}
}
``````

### 10.正则表达式匹配

``````'.' 匹配任意单个字符。
'*' 匹配零个或多个前面的元素。
``````

• `s` 可能为空，且只包含从 `a-z` 的小写字母。
• `p` 可能为空，且只包含从 `a-z` 的小写字母，以及字符 `.``*`

``````输入:
s = "aa"
p = "a"

``````

``````输入:
s = "aa"
p = "a*"

``````

``````输入:
s = "ab"
p = ".*"

``````

``````输入:
s = "aab"
p = "c*a*b"

``````

``````输入:
s = "mississippi"
p = "mis*is*p*."

``````

Solution：

``````public class Solution {
public boolean isMatch(String s, String p) {
if (s == null || p == null) {
return false;
}

return isMatch(s, p, 0, 0);
}

private boolean isMatch(String str, String pattern, int s, int p) {
// 正则表达式已用尽，若是字符串还未匹配完，则返回false
if (p == pattern.length()) {
return str.length() == s;
}
// 正则表达式下一位为*，此时考虑两种状况
if (p + 1 < pattern.length() && pattern.charAt(p + 1) == '*') {
// 若正则表达式当前位字符与字符串当前位置相匹配，则匹配1位或者0位
if (s < str.length() && (str.charAt(s) == pattern.charAt(p) || pattern.charAt(p) == '.')) {
return isMatch(str, pattern, s, p + 2) || isMatch(str, pattern, s + 1, p);
}
// 若正则表达式当前位字符与字符串当前位置不匹配，则匹配0位
return isMatch(str, pattern, s, p + 2);
}

// 匹配1位
if (s < str.length() && (str.charAt(s) == pattern.charAt(p) || pattern.charAt(p) == '.')) {
return isMatch(str, pattern, s + 1, p + 1);
}
return false;
}
}
``````

### 11.盛最多水的容器

**说明：**你不能倾斜容器，且 n 的值至少为 2。

``````输入: [1,8,6,2,5,4,8,3,7]

``````

Solution：

``````/**
* 利用滑动窗口解决
*/
public class Solution {
public int maxArea(int[] height) {
int res = 0;
int left = 0;
int right = height.length - 1;

while (left < right) {
res = Math.max(res, Math.min(height[left], height[right]) * (right - left));
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}

return res;
}
}
``````

### 15.三数之和

**注意：**答案中不能够包含重复的三元组。

``````例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

[
[-1, 0, 1],
[-1, -1, 2]
]
``````

Solution：

``````/**
* 采用滑动窗口，时间复杂度为：O(n log(n))
*/
public class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
if (nums == null || nums.length < 3) {
return list;
}

// 先排序，同时避免求重复解
Arrays.sort(nums);

for (int i = 0; i < nums.length - 2 && nums[i] <= 0;) {
int l = i + 1;
int r = nums.length - 1;
while (l < r) {
int sum = nums[i] + nums[l] + nums[r];
if (sum == 0) {
while (l < r && nums[l] == nums[l - 1]) {
l++;
}
while (r > l && nums[r] == nums[r + 1]) {
r--;
}
} else if (sum < 0) {
l++;
} else {
r--;
}
}
i++;
while (i < nums.length - 2 && nums[i] == nums[i - 1]) {
i++;
}
}
return list;
}
}
``````

### 17.电话号码的字母组合

``````输入："23"

``````

Solution：

``````public class Solution {
private List<String> res = new ArrayList<>();
private String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

public List<String> letterCombinations(String digits) {
if (digits == null || digits.length() < 1) {
return res;
}

dfs(digits, 0, "");
return res;
}

private void dfs(String digits, int index, String str) {
if (index == digits.length()) {
return;
}

String dict = map[digits.charAt(index) - '0'];
for (int i = 0; i < dict.length(); i++) {
dfs(digits, index + 1, str + dict.charAt(i));
}
}
}
``````

### 19.删除链表的倒数第N个节点

``````给定一个链表: 1->2->3->4->5, 和 n = 2.

``````

Solution：

``````/*
* 双指针
*/
public class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
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;
}
}
``````

### 20有效的括号

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。

``````输入: "()"

``````

``````输入: "()[]{}"

``````

``````输入: "(]"

``````

``````输入: "([)]"

``````

``````输入: "{[]}"

``````

Solution：

``````public class Solution {
public static boolean isValid(String s) {
if (s == null || (s.length() & 1) == 1) {
return false;
}

Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '[' || s.charAt(i) == '{' || s.charAt(i) == '(') {
stack.push(s.charAt(i));
} else if (s.charAt(i) == ']' && (stack.isEmpty() || stack.pop() != '[')) {
return false;
} else if (s.charAt(i) == '}' && (stack.isEmpty() || stack.pop() != '{')) {
return false;
} else if (s.charAt(i) == ')' && (stack.isEmpty() || stack.pop() != '(')) {
return false;
}
}
return stack.isEmpty();
}
}
``````

### 21.合并两个有序链表

``````输入：1->2->4, 1->3->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;
}
}
``````

### 22.生成括号

``````[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
``````

Solution：

``````public class Solution {
private List<String> list = new ArrayList<>();

public List<String> generateParenthesis(int n) {
if (n < 1) {
return list;
}

generate(n, 0, 0, "");
return list;
}

private void generate(int n, int left, int right, String str) {
if (left == right && left == n) {
}
if (left < n) {
generate(n, left + 1, right, str + "(");
}
if (left > right) {
generate(n, left, right + 1, str + ")");
}
}
}
``````

### 23.合并K个排序链表

``````输入:
[
1->4->5,
1->3->4,
2->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<>(Comparator.comparingInt(node -> node.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;
}
}
``````

### 31.下一个排列

`1,2,3``1,3,2`
`3,2,1``1,2,3`
`1,1,5``1,5,1`

Solution：

``````/**
* 求下一个全排列，可分为两种状况：
* 1.例如像 5 4 3 2 1这样的序列，已是最大的排列，即每一个位置上的数非递增，这时只须要翻转整个序列便可
* 2.例如像 1 3 5 4 2这样的序列，要从后往前找到第一个比后面一位小的元素的位置，即第二个位置的3，而后与其后第一个比它大的元素交换位置，获得 1 4 5 3 2，再将 5 3 2翻转获得 1 4 2 3 5便可
*/

public class Solution {
public void nextPermutation(int[] nums) {
if (nums == null || nums.length == 0) {
return;
}

int firstSmall = -1;
for (int i = nums.length - 2; i >= 0; i--) {
if (nums[i] < nums[i + 1]) {
firstSmall = i;
break;
}
}

if (firstSmall == -1) {
reverse(nums, 0, nums.length - 1);
return;
}

for (int i = nums.length - 1; i > firstSmall; i--) {
if (nums[i] > nums[firstSmall]) {
swap(nums, i, firstSmall);
reverse(nums, firstSmall + 1, nums.length - 1);
return;
}
}
}

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--);
}
}
}
``````

### 32.最长有效括号

``````输入: "(()"

``````

``````输入: ")()())"

``````

Solution：

``````public class Solution {
public int longestValidParentheses(String s) {
if (s == null || s.length() < 2) {
return 0;
}

int res = 0;
int start = 0;
Stack<Integer> stack = new Stack<>();
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 = stack.isEmpty() ? Math.max(res, i - start + 1) : Math.max(res, i - stack.peek());
}
}
}
return res;
}
}
``````

### 33.搜索旋转排序数组

( 例如，数组 `[0,1,2,4,5,6,7]` 可能变为 `[4,5,6,7,0,1,2]` )。

``````输入: nums = [4,5,6,7,0,1,2], target = 0

``````

``````输入: nums = [4,5,6,7,0,1,2], target = 3

``````

Solution：

``````public class Solution {
public int search(int[] nums, int target) {
if (nums == null
|| nums.length < 1
|| (target < nums[0] && target > nums[nums.length - 1])) {
return -1;
}

int low = 0;
int high = nums.length - 1;
while (low <= high) {
int mid = (low + high) >> 1;
if (nums[mid] == target) {
return mid;
}

if (nums[mid] >= nums[low]) {// 左边有序
if (nums[mid] > target && nums[low] <= target) {// 在有序边
high = mid - 1;
} else{// 在无序边
low = mid + 1;
}
} else {// 右边有序
if (nums[mid] < target && nums[high] >= target) {// 在有序边
low = mid + 1;
} else {// 在无序边
high = mid - 1;
}
}
}

return -1;
}
}
``````

### 34.在排序数组中查找元素的第一个和最后一个位置

``````输入: nums = [5,7,7,8,8,10], target = 8

``````

``````输入: nums = [5,7,7,8,8,10], target = 6

``````

Solution：

``````public class Solution {
public int[] searchRange(int[] nums, int target) {
if (nums == null || nums.length < 1) {
return new int[]{-1, -1};
}

int low = 0;
int high = nums.length - 1;
while (low <= high) {
int mid = (low + high) >> 1;
if (nums[mid] < target) {
low = mid + 1;
} else if (nums[mid] > target) {
high = mid - 1;
} else {
int left = mid;
int right = mid;
while (left >= low && nums[left] == target) {
left--;
}
while (right <= high && nums[right] == target) {
right++;
}
return new int[]{left + 1, right -1};
}
}

return new int[]{-1, -1};
}
}
``````

### 39.组合总和

`candidates` 中的数字能够无限制重复被选取。

• 全部数字（包括 `target`）都是正整数。
• 解集不能包含重复的组合。

``````输入: candidates = [2,3,6,7], target = 7,

[
[7],
[2,2,3]
]

``````

``````输入: 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) {
if (candidates == null || candidates.length == 0) {
return res;
}
dfs(candidates, 0, target, new ArrayList<>());
return res;
}

private void dfs(int[] candidates, int start, int target, List<Integer> list) {
if (target == 0) {
return;
}

for (int i = start; i < candidates.length; i++) {
if (target >= candidates[i]) {
dfs(candidates, i, target - candidates[i], list);
list.remove(list.size() - 1);
}
}
}
}
``````

### 42.接雨水

``````输入: [0,1,0,2,1,0,1,3,2,1,2,1]

``````

Solution：

``````public class Solution {
public int trap(int[] height) {
if (height == null || height.length < 3) {
return 0;
}

int low = 0;
int high = height.length - 1;
int res = 0;
int lowMax = 0;
int highMax = 0;
while (low < high) {
if (height[low] < height[high]) {
lowMax = Math.max(lowMax, height[low]);
res += lowMax - height[low];
low++;
} else {
highMax = Math.max(highMax, height[high]);
res += highMax - height[high];
high--;
}
}

return res;
}
}
``````

### 46.全排列

``````输入: [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) {
if (nums == null) {
return res;
}

visited = new boolean[nums.length];
permute(0, nums, new ArrayList());
return res;
}

private void permute(int index, int[] nums, List<Integer> list) {
if (index == nums.length) {
return;
}

for (int i = 0; i < nums.length; i++) {
if (!visited[i]) {
visited[i] = true;
permute(index + 1, nums, list);
list.remove(list.size() - 1);
visited[i] = false;
}
}
}
}
``````

### 48.旋转图像

``````给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],

[
[7,4,1],
[8,5,2],
[9,6,3]
]

``````

``````给定 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) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return;
}

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 + i + 1 < n; j++) {
swap(matrix, i, j, n - 1 - j, n - 1 - i);
}
}
}

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;
}
}
``````

### 49.字母异位词分组

``````输入: ["eat", "tea", "tan", "ate", "nat", "bat"],

[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]

``````

• 全部输入均为小写字母。
• 不考虑答案输出的顺序。

Solution：

``````public class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> res = new ArrayList<>();
if (strs == null || strs.length == 0) {
return res;
}

Map<String, List<String>> map = new HashMap<>();
for (String str : strs) {
int[] counts = new int[26];
for (int i = 0; i < str.length(); i++) {
counts[str.charAt(i) - 'a']++;
}

StringBuilder sb = new StringBuilder();
for (int count : counts) {
sb.append(' ').append(count);
}
String key = sb.toString();
if (!map.containsKey(key)) {
map.put(key, new ArrayList<>());
}
}
return new ArrayList<>(map.values());
}
}
``````

### 53.最大子序和

``````输入: [-2,1,-3,4,-1,2,1,-5,4],

``````

Solution：

``````public class Solution {
public int maxSubArray(int[] nums) {
if (nums == null || 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;
}
}
``````

### 55.跳跃游戏

``````输入: [2,3,1,1,4]

``````

``````输入: [3,2,1,0,4]

``````

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;
}
}
``````

### 56.合并区间

``````输入: [[1,3],[2,6],[8,10],[15,18]]

``````

``````输入: [[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) {
pre = interval;
} else {
pre.end = Math.max(pre.end, interval.end);
}
}
return list;
}
}
``````

### 62.不一样路径

``````输入: m = 3, n = 2

1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

``````

``````输入: m = 7, n = 3

``````

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];
}
}
``````

### 64.最小路径和

**说明：**每次只能向下或者向右移动一步。

``````输入:
[
[1,3,1],
[1,5,1],
[4,2,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];
}
}
``````

### 70.爬楼梯

**注意：**给定 n 是一个正整数。

``````输入： 2

1.  1 阶 + 1 阶
2.  2 阶

``````

``````输入： 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;
}
}
``````

### 72.编辑距离

1. 插入一个字符
2. 删除一个字符
3. 替换一个字符

``````输入: word1 = "horse", word2 = "ros"

horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

``````

``````输入: word1 = "intention", word2 = "execution"

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) {
if (word1 == null || word2 == null) {
return 0;
}

int[][] dp = new int[word1.length() + 1][word2.length() + 1];
for (int i = 1; i <= word1.length(); i++) {
dp[i][0] = i;
}
for (int i = 1; i <= word2.length(); i++) {
dp[0][i] = i;
}
for (int i = 0; i < word1.length(); i++) {
for (int j = 0; j < word2.length(); 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()];
}
}
``````

### 75.颜色分类

``````输入: [2,0,2,1,1,0]

``````

Solution：

``````class Solution {
// 解法一：桶排序
public void sortColors(int[] nums) {
if (nums == null) {
return;
}
int[] count = new int[3]; // 统计一、二、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++;
}
}
}
}
``````

### 76.最小覆盖子串

``````输入: S = "ADOBECODEBANC", T = "ABC"

``````

• 若是 S 中不存这样的子串，则返回空字符串 `""`
• 若是 S 中存在这样的子串，咱们保证它是惟一的答案。

Solution：

``````public class Solution {
public String minWindow(String s, String t) {
if (s == null || t == null || s.length() < t.length()) {
return "";
}

String res = "";
int[] sFlag = new int[256];
int[] tFlag = new int[256];
for (int i = 0; i < t.length(); i++) {
tFlag[t.charAt(i)]++;
}
int count = t.length();
int l = 0;
int r = 0;
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 || r - l < res.length())) {
res = s.substring(l, r);
}
if (sFlag[s.charAt(l)]-- <= tFlag[s.charAt(l++)]) {
count++;
}
}
}
return res;
}
}
``````

### 78.子集

**说明：**解集不能包含重复的子集。

``````输入: nums = [1,2,3]

[
[3],
[1],
[2],
[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) {
if (nums == null || nums.length == 0) {
return res;
}

dfs(nums, 0, new ArrayList<>());
return res;
}

private void dfs(int[] nums, int index, List<Integer> list) {
if (index == nums.length) {
return;
}

dfs(nums, index + 1, list);
dfs(nums, index + 1, list);
list.remove(list.size() - 1);
}
}
``````

### 79.单词搜索

``````board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]

``````

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;
}
}
``````

### 84.柱状图中最大的矩形

``````输入: [2,1,5,6,2,3]

``````

Solution：

``````/**
* 单调栈
*/
public class Solution {
public int largestRectangleArea(int[] heights) {
if (heights == null || heights.length == 0) {
return 0;
}

Stack<Integer> stack = new Stack<>();
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;
}
}
``````

### 85.最大矩形

``````输入:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]

``````

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;
}
}
``````

### 94.二叉树的中序遍历

``````输入: [1,null,2,3]
1
\
2
/
3

``````

Solution：

``````public class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = 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();
node = node.right;
}

return res;
}
}
``````

### 96.不一样的二叉搜索树

``````输入: 3

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];
}
}
``````

### 98.验证二叉搜索树

• 节点的左子树只包含小于当前节点的数。
• 节点的右子树只包含大于当前节点的数。
• 全部左子树和右子树自身必须也是二叉搜索树。

``````输入:
2
/ \
1   3

``````

``````输入:
5
/ \
1   4
/ \
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;
}
}
``````

### 101.对称二叉树

``````    1
/ \
2   2
/ \ / \
3  4 4  3

``````

``````    1
/ \
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);
}
}
``````

### 102.二叉树的层序遍历

``````    3
/ \
9  20
/  \
15   7

``````

``````[
[3],
[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<>();
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> list = new ArrayList<>();
while (size-- > 0) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}

return res;
}
}
``````

### 104.二叉树的最大深度

``````    3
/ \
9  20
/  \
15   7

``````

Solution：

``````public class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
}
``````

### 105.从前序遍历和中序遍历序列构造二叉树

``````前序遍历 preorder = [3,9,20,15,7]

``````

``````    3
/ \
9  20
/  \
15   7
``````

Solution：

``````public class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || inorder == null || preorder.length != inorder.length || preorder.length == 0) {
return null;
}
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 node = new TreeNode(preorder[ps]);
for (int i = is; i <= ie; i++) {
if (inorder[i] == preorder[ps]) {
node.left = build(preorder, inorder, ps + 1, i - is + ps, is, i - 1);
node.right = build(preorder, inorder, i - is + ps + 1, pe, i + 1, ie);
return node;
}
}
return node;
}
}
``````

### 114.二叉树展开为链表

``````    1
/ \
2   5
/ \   \
3   4   6

``````

``````1
\
2
\
3
\
4
\
5
\
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);
}
}
``````

### 121.买卖股票的最佳时机

``````输入: [7,1,5,3,6,4]

注意利润不能是 7-1 = 6, 由于卖出价格须要大于买入价格。

``````

``````输入: [7,6,4,3,1]

``````

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;
}
}
``````

### 124.二叉树中的最大路径和

``````输入: [1,2,3]

1
/ \
2   3

``````

``````输入: [-10,9,20,null,null,15,7]

-10
/ \
9  20
/  \
15   7

``````

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);
}
}
``````

### 128.最长连续序列

``````输入: [100, 4, 200, 1, 3, 2]

``````

Solution：

``````public class Solution {
public int longestConsecutive(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}

// 以key开始，连续序列长度为value
Map<Integer, Integer> map = new HashMap<>();
int res = 0;
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 (Map.Entry<Integer, Integer> entry : map.entrySet()) {
res = Math.max(res, entry.getValue());
}
return res;
}
}
``````

### 136.只出现一次的数字

``````输入: [2,2,1]

``````

``````输入: [4,1,2,1,2]

``````

Solution：

``````public class Solution {
public int singleNumber(int[] nums) {
int res = 0;
for (int num : nums) {
res ^= num;
}
return res;
}
}
``````

### 139.单词拆分

• 拆分时能够重复使用字典中的单词。
• 你能够假设字典中没有重复的单词。

``````输入: s = "leetcode", wordDict = ["leet", "code"]

``````

``````输入: s = "applepenapple", wordDict = ["apple", "pen"]

注意你能够重复使用字典中的单词。

``````

``````输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]

``````

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()];
}
}
``````

### 141.环形链表

``````输入：head = [3,2,0,-4], pos = 1

``````

``````输入：head = [1,2], pos = 0

``````

``````输入：head = [1], pos = -1

``````

Solution：

``````public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null) {
return false;
}

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;
}
}
``````

### 142.环形链表Ⅱ

**说明：**不容许修改给定的链表。

``````输入：head = [3,2,0,-4], pos = 1

``````

``````输入：head = [1,2], pos = 0

``````

``````输入：head = [1], pos = -1

``````

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;
}

while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return fast;
}
}
``````

### 146.LRU缓存机制

``````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);
}
}
``````

### 148.排序链表

O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

``````输入: 4->2->1->3

``````

``````输入: -1->5->3->4->0

``````

Solution：

``````public class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
}
ListNode mid = getMid(head);
ListNode second = mid.next;
mid.next = null;
}

private ListNode merge(ListNode first, ListNode second) {
ListNode dummy = new ListNode(0);
ListNode pre = dummy;
while (first != null && second != null) {
if (first.val > second.val) {
pre.next = second;
second = second.next;
} else {
pre.next = first;
first = first.next;
}
pre = pre.next;
}
pre.next = first == null ? second : first;
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;
}
}
``````

### 152.伺机最大子序列

``````输入: [2,3,-2,4]

``````

``````输入: [-2,0,-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;
}
}
``````

### 155.最小栈

• 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();
}
}
``````

### 160.相交链表

``````输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3

``````

``````输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1

``````

``````输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2

``````

• 若是两个链表没有交点，返回 `null`.
• 在返回结果后，两个链表仍须保持原有的结构。
• 可假定整个链表结构中没有循环。
• 程序尽可能知足 O(n) 时间复杂度，且仅用 O(1) 内存。

Solution：

``````public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}

ListNode a = headA;
ListNode b = headB;
while (a != b) {
a = a == null ? headB : a.next;
b = b == null ? headA : b.next;
}
return a;
}
}
``````

### 169.求众数

``````输入: [3,2,3]

``````

``````输入: [2,2,1,1,1,2,2]

``````

Solution：

``````/**
* 摩尔投票法
*/
public class Solution {
public int majorityElement(int[] nums) {
int count = 1;
int res = nums[0];
for (int num : nums) {
if (num == res) {
count++;
} else {
if (count == 1) {
res = num;
} else {
count--;
}
}
}
return res;
}
}
``````

### 198.打家劫舍

``````输入: [1,2,3,1]

偷窃到的最高金额 = 1 + 3 = 4 。

``````

``````输入: [2,7,9,3,1]

偷窃到的最高金额 = 2 + 9 + 1 = 12 。
``````

Solution：

``````public class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
if (nums.length == 1) {
return nums[0];
}

int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[nums.length - 1];
}
}
``````

### 200.岛屿的个数

``````输入:
11110
11010
11000
00000

``````

``````输入:
11000
11000
00100
00011

``````

Solution：

``````public class Solution {
private boolean[][] visited;

public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}

int res = 0;
visited = new boolean[grid.length][grid[0].length];
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == '1' && !visited[i][j]) {
res++;
dfs(grid, i, j);
}
}
}

return res;
}

private void dfs (char[][] grid, int row, int col) {
if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] == '0' || visited[row][col]) {
return;
}

visited[row][col] = true;
dfs(grid, row + 1, col);
dfs(grid, row - 1, col);
dfs(grid, row, col + 1);
dfs(grid, row, col - 1);
}
}
``````

### 206.反转链表

``````输入: 1->2->3->4->5->NULL

``````

Solution：

``````public class Solution {
// 解法一
public ListNode reverseList(ListNode head) {
ListNode dummy = new ListNode(0);
while (head != null) {
ListNode next = head.next;
}
return dummy.next;
}
// 解法二
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
}
}
}
``````

### 207.课程表

``````输入: 2, [[1,0]]

``````

``````输入: 2, [[1,0],[0,1]]

``````

1. 输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法
2. 你能够假定输入的先决条件中没有重复的边。

1. 这个问题至关于查找一个循环是否存在于有向图中。若是存在循环，则不存在拓扑排序，所以不可能选取全部课程进行学习。
2. 经过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程（21分钟），介绍拓扑排序的基本概念。
3. 拓扑排序也能够经过 BFS 完成。

Solution：

``````public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
// 邻接表图
Map<Integer, List<Integer>> map = new HashMap<>();
// 保存入度
int[] degree = new int[numCourses];
//构建有向图
for (int[] pre : prerequisites) {
if (map.containsKey(pre[1])) {
} else {
map.put(pre[1], new ArrayList<>(Arrays.asList(pre[0])));
}
degree[pre[0]]++;
}

Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (degree[i] == 0) {
queue.offer(i);
}
}
// BFS
while (!queue.isEmpty()) {
int i = queue.poll();
List<Integer> l = map.get(i);
if(l == null) {
continue;
}
for (int j = 0; j < l.size(); j++) {
int p = l.get(j);
degree[p]--;
if(degree[p] == 0) {
queue.offer(p);
}
}
}
for (int i = 0; i < numCourses; i++) {
if (degree[i] != 0) {
return false;
}
}
return true;
}
}
``````

### 208.实现Trie(前缀树)

``````Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // 返回 true
trie.search("app");     // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");
trie.search("app");     // 返回 true

``````

• 你能够假设全部的输入都是由小写字母 `a-z` 构成的。
• 保证全部输入均为非空字符串。

Solution：

``````public class Trie {
// 指向全部存在的下一个字符
private Map<Character, Map> map;

/**
* Initialize your data structure here.
*/
public Trie() {
map = new HashMap<>();
}

/**
* Inserts a word into the trie.
*/
public void insert(String word) {
Map<Character, Map> ws = map;
for (int i = 0; i < word.length(); i++) {
ws.putIfAbsent(word.charAt(i), new HashMap<>());
ws = ws.get(word.charAt(i));
}
ws.put('.', null);
}

/**
* Returns if the word is in the trie.
*/
public boolean search(String word) {
Map<Character, Map> ws = map;
for (int i = 0; i < word.length(); i++) {
ws = ws.get(word.charAt(i));
if (ws == null) {
return false;
}
}
return ws.containsKey('.');
}

/**
* Returns if there is any word in the trie that starts with the given prefix.
*/
public boolean startsWith(String prefix) {
Map<Character, Map> ws = map;
for (int i = 0; i < prefix.length(); i++) {
ws = ws.get(prefix.charAt(i));
if (ws == null) {
return false;
}
}
return true;
}
}
``````

### 215.数组中的第K个最大元素

``````输入: [3,2,1,5,6,4] 和 k = 2

``````

``````输入: [3,2,3,1,2,4,5,5,6] 和 k = 4

``````

Solution：

``````public class Solution {
public int findKthLargest(int[] nums, int k) {
Queue<Integer> queue = new PriorityQueue<>(Comparator.reverseOrder());
for (int num : nums) {
queue.offer(num);
}
for (int i = 1; i < k; i++) {
queue.poll();
}
return queue.peek();
}
}
``````

### 221.最大正方形

``````输入:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

``````

Solution：

``````public class Solution {
public int maximalSquare(char[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return 0;
}

int res = 0;
int[] heights = new int[matrix[0].length];
for (int i = 0; i < matrix.length; i++) {
Stack<Integer> stack = new Stack<>();
for (int j = 0; j <= heights.length; j++) {
if (j < heights.length) {
heights[j] = (matrix[i][j] == '1') ? 1 + heights[j] : 0;
}
int height = (j == heights.length) ? -1 : heights[j];
while (!stack.isEmpty() && height <= heights[stack.peek()]) {
int stackHeight = heights[stack.pop()];
int width = stack.isEmpty() ? j : j - stack.peek() - 1;
int min = Math.min(width, stackHeight);
res = Math.max(res, min * min);
}
stack.push(j);
}
}
return res;
}
}
``````

### 226.翻转二叉树

``````     4
/   \
2     7
/ \   / \
1   3 6   9

``````

``````     4
/   \
7     2
/ \   / \
9   6 3   1

``````

Solution：

``````public class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return root;
}

TreeNode left = root.left;
root.left = invertTree(root.right);
root.right = invertTree(left);
return root;
}
}
``````

### 234.回文链表

``````输入: 1->2

``````

``````输入: 1->2->2->1

``````

Solution：

``````public class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}

// 第一步运用快慢指针找到中间结点
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}

// 此时slow即为中间结点，将其后链表逆序
ListNode secHead = slow.next;
slow.next = null;
while (secHead != null) {
ListNode next = secHead.next;
}
slow.next = null;
// 依次比较
while (slow != null && secHead != null) {
if (slow.val != secHead.val) {
return false;
}
slow = slow.next;
}
return slow == null || slow.next == null;
}
}
``````

### 236.二叉树的最近公共祖先

``````输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1

``````

``````输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4

``````

• 全部节点的值都是惟一的。
• p、q 为不一样节点且均存在于给定的二叉树中。

Solution：

``````public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//  根节点都已是了还找个屁
if (root == null || root == p || root == q) {
return root;
}
// 找左边
TreeNode left = lowestCommonAncestor(root.left, p, q);
// 找右边
TreeNode right = lowestCommonAncestor(root.right, p, q);
// 根节点、左节点、右节点都没有，gg
if (left == null && right == null) {
return null;
}
// 左节点、右节点都有，证实各1个，此时根节点就是最近公共祖先
if (left != null && right != null) {
return root;
}
// 都在一边
return left == null ? right : left;
}
}
``````

### 238.除自身之外数组的乘积

``````输入: [1,2,3,4]

``````

Solution：

``````public class Solution {
public int[] productExceptSelf(int[] nums) {
if (nums == null || nums.length == 0) {
return null;
}

int[] res = new int[nums.length];
for (int i = 0, product = 1; i < nums.length; i++) {
res[i] = product;
product *= nums[i];
}

for (int i = nums.length - 1, product = 1; i >= 0; i--) {
res[i] *= product;
product *= nums[i];
}
return res;
}
}
``````

### 239.滑动窗口的最大值

``````输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3

滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
1 [3  -1  -3] 5  3  6  7       3
1  3 [-1  -3  5] 3  6  7       5
1  3  -1 [-3  5  3] 6  7       5
1  3  -1  -3 [5  3  6] 7       6
1  3  -1  -3  5 [3  6  7]      7

``````

Solution：

``````public class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length == 0 || k > nums.length) {
return new int[0];
}

int[] res = new int[nums.length - k + 1];
for (int i = 0; i < k - 1; i++) {
while (!queue.isEmpty() && nums[queue.peekLast()] < nums[i]) {
queue.pollLast();
}
queue.offerLast(i);
}

for (int i = k - 1; i < nums.length; i++) {
while (!queue.isEmpty() && nums[queue.peekLast()] < nums[i]) {
queue.pollLast();
}
queue.offerLast(i);
if (i - queue.peekFirst() >= k) {
queue.pollFirst();
}
res[i - k + 1] = nums[queue.peekFirst()];
}
return res;
}
}
``````

### 240.搜索二维矩阵Ⅱ

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

``````[
[1,   4,  7, 11, 15],
[2,   5,  8, 12, 19],
[3,   6,  9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]

``````

Solution：

``````public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}

int i = matrix.length - 1;
int j = 0;
while (i >= 0 && j < matrix[0].length) {
if (matrix[i][j] == target) {
return true;
}

if (matrix[i][j] > target) {
i--;
} else {
j++;
}
}
return false;
}
}
``````

### 279.彻底平方数

``````输入: n = 12

``````

``````输入: n = 13

``````

Solution：

``````public class Solution {
public int numSquares(int n) {
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
for (int i = 1; i * i <= n; i++) {
dp[i * i] = 1;
}

for (int i = 1; i < n; i++) {
for (int j = 0; j * j + i <= n; j++) {
dp[i + j * j] = Math.min(dp[i + j * j], dp[i] + 1);
}
}
return dp[n];
}
}
``````

### 283.移动零

``````输入: [0,1,0,3,12]

``````

1. 必须在原数组上操做，不能拷贝额外的数组。
2. 尽可能减小操做次数。
``````public class Solution {
public void moveZeroes(int[] nums) {
if (nums == null) {
return;
}

int k = 0;
for (int num : nums) {
if (num != 0) {
nums[k++] = num;
}
}

for (int i = k; i < nums.length; i++) {
nums[i] = 0;
}
}
}
``````

### 287.寻找重复数

``````输入: [1,3,4,2,2]

``````

``````输入: [3,1,3,4,2]

``````

1. 不能更改原数组（假设数组是只读的）。
2. 只能使用额外的 O(1) 的空间。
3. 时间复杂度小于 O(n2) 。
4. 数组中只有一个重复的数字，但它可能不止重复出现一次。

Solution：

``````/**
* 把数组当作链表，采用快慢指针法，寻找环的入口
*/
public class Solution {
public int findDuplicate(int[] nums) {
int fast = 0;
int slow = 0;
while (true) {
fast = nums[nums[fast]];
slow = nums[slow];
if (fast == slow) {
slow = 0;
while (nums[fast] != nums[slow]) {
fast = nums[fast];
slow = nums[slow];
}
return nums[slow];
}
}
}
}
``````

### 297.二叉树的序列化和反序列化

``````你能够将如下二叉树：

1
/ \
2   3
/ \
4   5

``````

Soution：

``````public class Codec {
private int index = -1;

// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) {
return "#,";
}

StringBuilder sb = new StringBuilder();
sb.append(root.val).append(',').append(serialize(root.left)).append(serialize(root.right));
return sb.toString();
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data == null) {
return null;
}
return helper(data.split(","));
}

private TreeNode helper(String[] strs) {
index++;
if ("#".equals(strs[index])) {
return null;
}
TreeNode node = new TreeNode(Integer.valueOf(strs[index]));
node.left = helper(strs);
node.right = helper(strs);
return node;
}
}
``````

### 300.最长上升子序列

``````输入: [10,9,2,5,3,7,101,18]

``````

• 可能会有多种最长上升子序列的组合，你只须要输出对应的长度便可。
• 你算法的时间复杂度应该为 O(n2) 。

Solution：

``````public class Solution {
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}

// dp[i]表示以nums中第i个元素结尾的最长上升子序列长度
int[] dp = new int[nums.length];
int res = 1;
Arrays.fill(dp, 1);
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j <= i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[j] + 1, dp[i]);
res = Math.max(res, dp[i]);
}
}
}
return res;
}
}
``````

### 309.最佳买卖股票时期含冷冻期

• 你不能同时参与多笔交易（你必须在再次购买前出售掉以前的股票）。
• 卖出股票后，你没法在次日买入股票 (即冷冻期为 1 天)。

``````输入: [1,2,3,0,2]

``````

Solution：

``````public class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length < 2) {
return 0;
}
int buy = Integer.MIN_VALUE;
int sale = 0;
int rest = 0;
for (int price : prices) {
int salePre = sale;
sale = Math.max(buy + price, sale);// 卖或者冻结
buy = Math.max(buy, rest - price); // 什么都不干或者卖
rest = Math.max(rest, Math.max(salePre, buy));
}
return sale;
}
}
``````

### 312.戳气球

`n` 个气球，编号为`0``n-1`，每一个气球上都标有一个数字，这些数字存在数组 `nums` 中。

• 你能够假设 `nums[-1] = nums[n] = 1`，但注意它们不是真实存在的因此并不能被戳破。
• 0 ≤ `n` ≤ 500, 0 ≤ `nums[i]` ≤ 100

``````输入: [3,1,5,8]

coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167
``````

Solution：

``````public class Solution {
public int maxCoins(int[] iNums) {
int n = iNums.length;
int[] nums = new int[n + 2];
for (int i = 0; i < n; i++) {
nums[i + 1] = iNums[i];
}
nums[0] = nums[n + 1] = 1;
// dp[i][j]表示戳爆[i, j]区间气球获得的最大硬币个数
int[][] dp = new int[n + 2][n + 2];
for (int k = 1; k <= n; k++) { // k表示长度
for (int i = 1; i <= n - k + 1; i++) {// i表示起始位置
int j = i + k - 1; // j表示结束位置
for (int x = i; x <= j; x++) {
// 戳爆 [i, x - 1] 、 x 、 [x + 1, j]
dp[i][j] = Math.max(dp[i][j], dp[i][x - 1] + nums[i - 1] * nums[x] * nums[j + 1] + dp[x + 1][j]);
}
}
}
return dp[1][n];
}
}
``````

### 322.零钱兑换

``````输入: coins = [1, 2, 5], amount = 11

``````

``````输入: coins = [2], amount = 3

``````

Solution：

``````public class Solution {
public int coinChange(int[] coins, int amount) {
if (coins == null || coins.length == 0 || amount < 0) {
return -1;
}

int res = 0;
int[] dp = new int[amount + 1];
for (int i = 1; i <= amount; i++) {
dp[i] = amount + 1;
for (int j = 0; j < coins.length; j++) {
if (i >= coins[j]) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}
``````

### 337.打家劫舍Ⅲ

``````输入: [3,2,3,null,3,null,1]

3
/ \
2   3
\   \
3   1

``````

``````输入: [3,4,5,1,3,null,1]

3
/ \
4   5
/ \   \
1   3   1

``````

Solution：

``````public class Solution {
public int rob(TreeNode root) {
int[] res = helper(root);
return Math.max(res[0], res[1]);
}

private int[] helper(TreeNode root) {
int[] res = new int[2];
if (root == null) {
return res;
}
int[] left = helper(root.left);
int[] right = helper(root.right);
res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]); // 不打劫当前节点
res[1] = root.val + left[0] + right[0]; // 打劫当前节点和左右子树的子树
return res;
}
}
``````

### 338.比特位计数

``````输入: 2

``````

``````输入: 5

``````

Solution：

``````public class Solution {
public int[] countBits(int num) {
int[] res = new int[num + 1];
for (int i = 1; i <= num; i++) {
// 将i表示的二进制数的最后一位1变成0即为 i & (i - 1)
res[i] = res[i & (i - 1)] + 1;
}
return res;
}
}
``````

### 347.前K个高频元素

``````输入: nums = [1,1,1,2,2,3], k = 2

``````

``````输入: nums = [1], k = 1

``````

• 你能够假设给定的 k 老是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
• 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。

Solution：

``````public class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
List<Integer> res = new ArrayList<>();
if (nums == null || nums.length == 0 || k <= 0) {
return res;
}
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
Queue<Integer> queue = new PriorityQueue<>(((o1, o2) -> map.get(o2) - map.get(o1)));
for (Integer key : map.keySet()) {
queue.offer(key);
}
for (int i = 0; i < k; i++) {
}
return res;
}
}
``````

### 394.字符串解码

``````s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".
``````

Solution：

``````public class Solution {
private int i = 0;

public String decodeString(String s) {
if (s == null || s.length() == 0) {
return "";
}

StringBuilder sb = new StringBuilder();
for (; i < s.length() && s.charAt(i) != ']'; i++) {
if ((s.charAt(i) >= 'a' && s.charAt(i) <= 'z') || (s.charAt(i) >= 'A' && s.charAt(i) <= 'Z')) {
sb.append(s.charAt(i));
continue;
}
int count = 0;
while (s.charAt(i) <= '9' && s.charAt(i) >= '0') {
count = count * 10 + s.charAt(i++) - '0';
}
i++; // 越过'['或
String temp = decodeString(s);
while (count-- > 0) {
sb.append(temp);
}
}
return sb.toString();
}
}
``````

### 406.根据身高重建队列

``````输入:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
``````

Solution：

``````public class Solution {
public int[][] reconstructQueue(int[][] people) {
if (people == null || people.length == 0 || people[0].length == 0) {
return new int[0][0];
}

Arrays.sort(people, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0]);
List<int[]> list = new ArrayList<>();
for (int[] i : people) {
}
return list.toArray(new int[list.size()][]);
}
}
``````

### 416.分割等和子集

1. 每一个数组中的元素不会超过 100
2. 数组的大小不会超过 200

``````输入: [1, 5, 11, 5]

``````

``````输入: [1, 2, 3, 5]

``````

Solution:

``````public class Solution {
public boolean canPartition(int[] nums) {
if (nums == null || nums.length == 0) {
return true;
}

int sum = 0;
for (int num : nums) {
sum += num;
}
if ((sum & 1) == 1) {
return false;
}
int c = (sum >> 1) + 1;
// dp[i] 表示nums可否装下容量为i的背包
boolean[] dp = new boolean[c];
dp[0] = true;
for (int i = 1; i < nums.length; i++) {
for (int j = c - 1; j >= nums[i]; j--) {
dp[j] = dp[j] || dp[j - nums[i]];
}
}
return dp[c - 1];
}
}
``````

### 437.路径总和Ⅲ

``````root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

10
/  \
5   -3
/ \    \
3   2   11
/ \   \
3  -2   1

1.  5 -> 3
2.  5 -> 2 -> 1
3.  -3 -> 11
``````

Solution：

``````public class Solution {
public int pathSum(TreeNode root, int sum) {
if (root == null) {
return 0;
}

return pathSumCount(root, sum)
+ pathSum(root.left, sum)
+ pathSum(root.right, sum);
}

public int pathSumCount(TreeNode root, int sum) {
if (root == null) {
return 0;
}

return (root.val == sum ? 1 : 0)
+ pathSumCount(root.left, sum - root.val)
+ pathSumCount(root.right, sum - root.val);
}
}
``````

### 438.找到字符串中全部字母异位词

• 字母异位词指字母相同，但排列不一样的字符串。
• 不考虑答案输出的顺序。

``````输入:
s: "cbaebabacd" p: "abc"

[0, 6]

``````

``````输入:
s: "abab" p: "ab"

[0, 1, 2]

``````

Solution：

``````public class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
if (s == null || p == null || s.length() < p.length()) {
return res;
}
int[] map = new int[26];
for (int i = 0; i < p.length(); i++) {
map[p.charAt(i) - 'a']++;
}
int count = p.length();
int l = 0;
int r = 0;
while (r < s.length()) {
if (map[s.charAt(r++) - 'a']-- > 0) {
count--;
}
if (count == 0) {
}
if (r - l == p.length()) {
if (map[s.charAt(l++) - 'a']++ >= 0) {
count++;
}
}
}
return res;
}
}
``````

### 448.找到全部数组中消失的数字

``````输入:
[4,3,2,7,8,2,3,1]

[5,6]
``````

Solution：

``````public class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> res = new ArrayList<>();
if (nums == null || nums.length == 0) {
return res;
}
for (int i = 0; i < nums.length; i++) {
if (nums[Math.abs(nums[i]) - 1] > 0) {
nums[Math.abs(nums[i]) - 1] *= -1;
}
}
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) {
}
}
return res;
}
}
``````

### 461.汉明距离

0 ≤ `x`, `y` < 231.

``````输入: x = 1, y = 4

1   (0 0 0 1)
4   (0 1 0 0)
↑   ↑

``````

Solution：

``````public class Solution {
public int hammingDistance(int x, int y) {
int res = 0;
int temp =  x ^ y;
while (temp != 0) {
res += temp & 1;
temp >>>= 1;
}
return res;
}
}
``````

### 494.目标和

``````输入: nums: [1, 1, 1, 1, 1], S: 3

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

``````

1. 数组的长度不会超过20，而且数组中的值全为正数。
2. 初始的数组的和不会超过1000。
3. 保证返回的最终结果为32位整数。

Solution：

``````public class Solution {
private int res = 0;

public int findTargetSumWays(int[] nums, int S) {
helper(nums, 0, S);
return res;
}

private void helper(int[] nums, int index, int S) {
if (index == nums.length) {
if (S == 0) {
res++;
}
return;
}
helper(nums, index + 1, S - nums[index]);
helper(nums, index + 1, S + nums[index]);
}
}
``````

### 538.把二叉搜索树转换为累加树

``````输入: 二叉搜索树:
5
/   \
2     13

18
/   \
20     13
``````

Solution：

``````/**
* 按照 右子树 -> 根节点 ->  左子树 的顺序遍历，统计以前节点值的和，加到当前节点上
*/
public class Solution {
public TreeNode convertBST(TreeNode root) {
if (root == null) {
return null;
}

int sum = 0;
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;
while (!stack.isEmpty() || node != null) {
while (node != null) {
stack.push(node);
node = node.right;
}
node = stack.pop();
int val = node.val;
node.val += sum;
sum += val;
node = node.left;
}
return root;
}
}
``````

### 543.二叉树的直径

``````          1
/ \
2   3
/ \
4   5

``````

**注意：**两结点之间的路径长度是以它们之间边的数目表示。

Solution：

``````public class Solution {
private int res = 0;

public int diameterOfBinaryTree(TreeNode root) {
helper(root);
return res;
}

private int helper(TreeNode root) {
if (root == null) {
return 0;
}

int left = helper(root.left);
int right = helper(root.right);
res = Math.max(res, left + right);
return 1 + Math.max(left, right);
}
}
``````

### 560.和为K的子数组

``````输入:nums = [1,1,1], k = 2

``````

1. 数组的长度为 [1, 20,000]。
2. 数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。

Solution：

``````public class Solution {
public int subarraySum(int[] nums, int k) {
if (nums == null || nums.length <= 0) {
return 0;
}

int res = 0;
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
int sum = 0;

for (int num : nums) {
sum += num;
// map.get(sum - k)表示从头开始，和为 sum - k的子数组个数
// 那么子数组后面到当前位置的元素和即为 sum - (sum - k) = k
res += map.getOrDefault(sum - k, 0);
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
return res;
}
}
``````

### 572.另外一个树的子树

``````     3
/ \
4   5
/ \
1   2

``````

``````   4
/ \
1   2

``````

``````     3
/ \
4   5
/ \
1   2
/
0

``````

``````   4
/ \
1   2

``````

Solution：

``````public class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {
if (s == null && t == null) {
return true;
}
if (s == null || t == null) {
return false;
}
return isSametree(s, t)
|| isSubtree(s.left, t)
|| isSubtree(s.right, t);
}

private boolean isSametree(TreeNode s, TreeNode t) {
if (s == null && t == null) {
return true;
}
if (s == null || t == null) {
return false;
}
return s.val == t.val && isSametree(s.left, t.left) && isSametree(s.right, t.right);
}
}
``````

### 581.最短无序连续子数组

``````输入: [2, 6, 4, 8, 10, 9, 15]

``````

1. 输入的数组长度范围在 [1, 10,000]。
2. 输入的数组可能包含重复元素 ，因此升序的意思是**<=。**

Solution：

``````public class Solution {
public int findUnsortedSubarray(int[] nums) {
if (nums == null || nums.length < 2) {
return 0;
}

int min = nums[nums.length - 1];
int max = nums[0];
int start = 0;
int end = -1;
for (int i = 1; i < nums.length; i++) {
if (max > nums[i]) {
end = i;
} else {
max = nums[i];
}

if (min < nums[nums.length - i - 1]) {
start = nums.length - i - 1;
} else {
min = nums[nums.length - i - 1];
}
}
return end - start + 1;
}
}
``````

### 617.合并二叉树

``````输入:
Tree 1                     Tree 2
1                         2
/ \                       / \
3   2                     1   3
/                           \   \
5                             4   7

3
/ \
4   5
/ \   \
5   4   7
``````

Solution：

``````public class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null || t2 == null) {
return t1 != null ? t1 : t2;
}

t1.val += t2.val;
t1.left = mergeTrees(t1.left, t2.left);
t1.right = mergeTrees(t1.right, t2.right);
return t1;
}
}
``````

### 647.回文子串

``````输入: "abc"

``````

``````输入: "aaa"

``````

1. 输入的字符串长度不会超过1000。

Solution：

``````public class Solution {
private int res = 0;

public int countSubstrings(String s) {
if (s == null || s.length() < 1) {
return 0;
}

for (int i = 0; i < s.length(); i++) {
find(s, i, i);
find(s, i, i + 1);
}
return res;
}

private void find(String s, int i, int j) {
while (i >= 0 && i < s.length() && j >= 0 && j < s.length() && s.charAt(i--) == s.charAt(j++)) {
res++;
}
}
}
``````

### 771.宝石与石头

`J` 中的字母不重复，`J``S`中的全部字符都是字母。字母区分大小写，所以`"a"``"A"`是不一样类型的石头。

``````输入: J = "aA", S = "aAAbbbb"

``````

``````输入: J = "z", S = "ZZ"

``````

• `S``J` 最多含有50个字母。
• `J` 中的字符不重复。

Solution：

``````public class Solution {
public int numJewelsInStones(String J, String S) {
int res = 0;
Set<Character> set = new HashSet<>();
for (int i = 0; i < J.length(); i++) {
}
for (int i = 0; i < S.length(); i++) {
if (set.contains(S.charAt(i)))
res++;
}
return res;
}
}
``````