# LeetCode刷题指南(Java版)

+关注继续查看

## 数组和矩阵

283. Move Zeroes (Easy)

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].
public void moveZeroes(int[] nums) {
int idx = 0;
for (int num : nums) {
if (num != 0) {
nums[idx++] = num;
}
}
while (idx 

## 字符串

242. Valid Anagram (Easy)

s = "anagram", t = "nagaram", return true.
s = "rat", t = "car", return false.

public boolean isAnagram(String s, String t) {
int[] cnts = new int[26];
for (char c : s.toCharArray()) {
cnts[c - 'a']++;
}
for (char c : t.toCharArray()) {
cnts[c - 'a']--;
}
for (int cnt : cnts) {
if (cnt != 0) {
return false;
}
}
return true;
}

409. Longest Palindrome (Easy)

Input : "abccccdd"
Output : 7
Explanation : One longest palindrome that can be built is "dccaccd", whose length is 7.

public int longestPalindrome(String s) {
int[] cnts = new int[256];
for (char c : s.toCharArray()) {
cnts[c]++;
}
int palindrome = 0;
for (int cnt : cnts) {
palindrome += (cnt / 2) * 2;
}
if (palindrome 

## 哈希表

Java 中的 HashSet 用于存储一个集合，可以查找元素是否在集合中。

Java 中的 HashMap 主要用于映射关系，从而把两个元素联系起来。

HashMap 也可以用来对元素进行计数统计，此时键为元素，值为计数。和 HashSet 类似，如果元素有穷并且范围不大，可以用整型数组来进行统计。

1. Two Sum (Easy)

public int[] twoSum(int[] nums, int target) {
HashMap

## 贪心算法

455.分发饼干：

public int findContentChildren(int[] g, int[] s) {
int count = 0;
Arrays.sort(g);
Arrays.sort(s);
int i = 0,j = 0;
while (i < g.length && j < s.length) {
if (g[i] <= s[j]) {
i ++;
j ++;
count ++;
}else {
j ++;
}
}
return count;
}

1. 无重叠区间：给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

/**
* Definition for an interval.
* public class Interval {
*     int start;
*     int end;
*     Interval() { start = 0; end = 0; }
*     Interval(int s, int e) { start = s; end = e; }
* }
*/
import java.util.*;
class Solution {
public int eraseOverlapIntervals(Interval[] intervals) {
int len = intervals.length;
if (len <= 1)return 0;
Arrays.sort(intervals, (a,b) -> a.end - b.end);
int count = 1;
int end = intervals[0].end;
for (int i = 1;i < intervals.length;i ++) {
if (intervals[i].start < end) {
continue;
}
count ++;
end = intervals[i].end;
}
return len - count;
}
}


1 需要用一个值标识起始值的end，然后再往后找一个符合条件的end。由于是顺序查找，所以只需要一个变量i。并且使用end标识起始元素。

2 默认的count应该为1，因为自己本身就是不重叠的。所以找到其他不重叠的区域，使用n-count才对。

1. 用最少数量的箭引爆气球
在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以y坐标并不重要，因此只要知道开始和结束的x坐标就足够了。开始坐标总是小于结束坐标。平面内最多存在104个气球。

Example:

[[10,16], [2,8], [1,6], [7,12]]

2

import java.util.*;
class Solution {
public int findMinArrowShots(int[][] points) {
if (points.length <= 1){
return points.length;
}
Arrays.sort(points, (a, b) -> a[1] - b[1]);
int end = points[0][1];
int cnt = 1;
for (int i = 1;i < points.length;i ++) {
if (points[i][0] <= end) {
continue;
}
end = points[i][1];
cnt ++;
}
return cnt;
}
}


1.本题是求不重叠区域的个数，而上一题是求要删除重叠区域的个数。
2.本题中[1,2][2,3]也算是重叠区域

1. 根据身高重建队列

1. 划分字母区间

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。

示例 1:

输出: [9,7,8]
解释:
划分结果为 “ababcbaca”, “defegde”, “hijhklij”。
每个字母最多出现在一个片段中。
注意:

S的长度在[1, 500]之间。
S只包含小写字母’a’到’z’。

import java.util.*;
class Solution {
public List<Integer> partitionLabels(String S) {
int []arr = new int[26];
List<Integer> list = new ArrayList<>();
for (int i = 0;i < S.length();i ++) {
arr[S.charAt(i) - 'a'] = i;
}
int start = 0;
int end = arr[S.charAt(0) - 'a'];
for (int i = 0;i < S.length();i ++) {
end =  Math.max(arr[S.charAt(i) - 'a'], end);
if (i < end) {
continue;
}else {
start = i + 1;
}
}
return list;
}
}


1. 种花问题
假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

n 是非负整数，且不会超过输入数组的大小。

class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
int cnt = 0;
if (flowerbed.length == 1 && flowerbed[0] == 0) {
return n <= 1;
}
if (flowerbed.length >= 2) {
if (flowerbed[0] == 0 && flowerbed[1] == 0) {
flowerbed[0] = 1;
cnt ++;
}
if (flowerbed[flowerbed.length - 1] == 0 && flowerbed[flowerbed.length - 2] == 0) {
flowerbed[flowerbed.length - 1] = 1;
cnt ++;
}
}
for (int i = 1;i < flowerbed.length - 1;) {
if (flowerbed[i - 1] == 0 && flowerbed[i] == 0 && flowerbed[i + 1] == 0 ) {
cnt ++;
flowerbed[i] = 1;
i = i + 2;
}else {
i ++;
}
}
return cnt >= n;
}
}


1. 判断子序列

s = “abc”, t = “ahbgdc”

s = “axc”, t = “ahbgdc”

import java.util.*;
class Solution {
public boolean isSubsequence(String s, String t) {
return LCS(s,t);
}
public boolean LCS(String s, String t) {
int [][]dp = new int[s.length() + 1][t.length() + 1];
for (int i = 1;i <= s.length();i ++) {
for (int j = 1;j <= t.length();j ++) {
if (s.charAt(i - 1) == t.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
int len = dp[s.length()][t.length()];
return len == s.length();
}
}


import java.util.*;
class Solution {
public boolean isSubsequence(String s, String t) {
int index = -1;
for (int i = 0;i < s.length();i ++) {
index = t.indexOf(s.charAt(i), index + 1);
if (index == -1) {
return false;
}
}
return true;
}
}

1. 非递减数列 这题暂时没有想到比较好的方法

1. 买卖股票的最佳时机 II
题意：

## 双指针

1. 两数之和 II - 输入有序数组

class Solution {
public int[] twoSum(int[] numbers, int target) {
int left = 0,right = numbers.length - 1;
int []arr = new int[2];
while (left < right) {
if (numbers[left] + numbers[right] < target) {
left ++;
}else if (numbers[left] + numbers[right] > target) {
right --;
}else {
arr[0] = left + 1;
arr[1] = right + 1;
return arr;
}
}
return arr;
}
}

1. 平方数之和

import java.util.*;
class Solution {
public boolean judgeSquareSum(int c) {
double n = Math.sqrt(c);
for (double i = 0;i <= n;i ++) {
double diff = c - i * i;
int j = (int) Math.sqrt(diff);
if (j * j == diff) {
return true;
}
}
return false;
}
}

1. 反转字符串中的元音字母
编写一个函数，以字符串作为输入，反转该字符串中的元音字母。

import java.util.*;
class Solution {
public String reverseVowels(String s) {
char[] arr = s.toCharArray();
int left = 0,right = s.length() - 1;
while (left < right){
while (left < right && !isVowels(arr[left])) {
left ++;
}
while (left < right && !isVowels(arr[right])) {
right --;
}
char temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left ++;
right --;
}
return String.valueOf(arr);
}
public boolean isVowels(char c) {
char[]arr = {'a', 'i', 'e', 'u', 'o', 'A', 'I', 'E', 'U', 'O'};
for (int k = 0;k < arr.length;k ++) {
if (c == arr[k]) {
return true;
}
}
return false;
}
}

1. 验证回文字符串 Ⅱ

class Solution {
public boolean validPalindrome(String s) {
int left = 0,right = s.length() - 1;
while (left < right) {
if (s.charAt(left) == s.charAt(right)) {
left ++;
right --;
}else {
return valid(s, left + 1,right) || valid(s, left, right - 1);
}
}
return true;
}

public boolean valid(String s, int i, int j) {
int left = i,right = j;
while (left < right) {
if (s.charAt(left) == s.charAt(right)) {
left ++;
right --;
}
else return false;
}
return true;
}
}

1. 合并两个有序数组

1. 环形链表

1. 通过删除字母匹配到字典里最长单词
给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。

s = “abpcplea”, d = [“ale”,”apple”,”monkey”,”plea”]

“apple”

s = “abpcplea”, d = [“a”,”b”,”c”]

“a”

import java.util.*;
class Solution {
public String findLongestWord(String s, List<String> d) {
Collections.sort(d, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
if (o1.length() != o2.length()) {
return o2.length() - o1.length();
} else {
return o1.compareTo(o2);
}
}
});
for (String str : d) {
int i = 0,j = 0;
while (i < s.length() && j < str.length()) {
if (s.charAt(i) == str.charAt(j)) {
i ++;
j ++;
}else {
i ++;
}
}
if (j == str.length()) {
return str;
}
}
return "";
}
}


## 排序

排序 ：时间复杂度 O(NlogN)，空间复杂度 O(1)

public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}

public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>(); // 小顶堆
for (int val : nums) {
if (pq.size() > k) // 维护堆的大小为 K
pq.poll();
}
return pq.peek();
}

class Solution {
public int findKthLargest(int[] nums, int k) {
k = nums.length - k;
int l = 0, r = nums.length - 1;
while (l < r) {
int pos = partition(nums, l , r);
if (pos == k) return nums[pos];
else if (pos < k) {
l = pos + 1;
}else {
r = pos - 1;
}
}
return nums[k];
}
public int partition(int[] nums, int left, int right) {
int l = left, r = right;
int temp = nums[l];
while (l < r) {
while (l < r && nums[r] >= temp) {
r --;
}
while (l < r && nums[l] <= temp) {
l ++;
}
if (l < r) {
int tmp = nums[l];
nums[l] = nums[r];
nums[r] = tmp;
}
}
nums[left] = nums[l];
nums[l] = temp;
return l;
}
}


1. 前K个高频元素

解析：

import java.util.*;
class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for (int i : nums) {
if (map.containsKey(i)) {
map.put(i, map.get(i) + 1);
}else {
map.put(i, 1);
}
}
ArrayList<Integer>[] timesMap = new ArrayList[nums.length + 1];
for (int key : map.keySet()) {
int times = map.get(key);
if (timesMap[times] == null) {
timesMap[times] = new ArrayList<>();
}
else {
}
}
List<Integer> top = new ArrayList<Integer>();
for (int i = timesMap.length - 1;i > 0 && top.size() < k;i --) {
if (timesMap[i] != null) {
}
}
}
}

1本题的难点在于先用hashmap存储数据得到每个数的频率，再用数组存储每个频率对应哪些数。

2最后再通过频率数组的最后一位开始往前找，找到k个数为之，就是出现频率最高的k个数了。

1. 根据字符出现频率排序

“tree”

“eert”

‘e’出现两次，’r’和’t’都只出现一次。

。因为char是1一个字节长度，也就是8位，2的8次方是256，考虑正数的话就是128。

public static String frequencySort(String s) {
int []arr = new int[26];
char []crr = s.toCharArray();
for (char c : crr) {
arr[c - 'a']++;
}

List<Character>[]times = new ArrayList[s.length() + 1];
for (int i = 0;i < arr.length;i ++) {
if (times[arr[i]] == null) {
times[arr[i]] = new ArrayList<>();
}else {
}
}
StringBuilder sb = new StringBuilder();
for (int i = times.length - 1;i > 0 ;i --) {
if (times[i] != null) {
for (char c : times[i]) {
int time = 0;
while (time < i) {
sb.append(c);
time ++;
}
}
}
}
return sb.toString();
}


class Solution {
public static String frequencySort(String s) {
int []arr = new int[128];
char []crr = s.toCharArray();
for (char c : crr) {
arr[c]++;
}

List<Character>[]times = new ArrayList[s.length() + 1];
for (int i = 0;i < arr.length;i ++) {
if (times[arr[i]] == null) {
times[arr[i]] = new ArrayList<>();
}else {
}
}
StringBuilder sb = new StringBuilder();
for (int i = times.length - 1;i > 0 ;i --) {
if (times[i] != null) {
for (char c : times[i]) {
int time = 0;
while (time < i) {
sb.append(c);
time ++;
}
}
}
}
return sb.toString();
}
}

1. 分类颜色
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

class Solution {
public void sortColors(int[] nums) {
if (nums.length <= 1)return;
int zero = -1, one = 0,two = nums.length;
while (one < two) {
if (nums[one] == 0) {
swap(nums, ++zero, one++);
}else if (nums[one] == 2) {
swap(nums, --two, one);
}else {
one ++;
}
}
}
public void swap(int []nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}


## 二分查找

public int binarySearch(int[] nums, int key) {
int l = 0, h = nums.length - 1;
while (l <= h) {
int m = l + (h - l) / 2;
if (nums[m] == key) {
return m;
} else if (nums[m] > key) {
h = m - 1;
} else {
l = m + 1;
}
}
return -1;
}


m 计算

m = (l + h) / 2
m = l + (h - l) / 2
l + h 可能出现加法溢出，最好使用第二种方式。

-1：以一个错误码表示没有查找到 key
l：将 key 插入到 nums 中的正确位置

public int binarySearch(int[] nums, int key) {
int l = 0, h = nums.length - 1;
while (l < h) {
int m = l + (h - l) / 2;
if (nums[m] >= key) {
h = m;
} else {
l = m + 1;
}
}
return l;
}


h 的赋值表达式为 h = m

nums = {0, 1, 2}, key = 1
l m h
0 1 2 nums[m] >= key
0 0 1 nums[m] < key
1 1 1 nums[m] >= key
1 1 1 nums[m] >= key

1. x 的平方根

public int mySqrt(int x) {
if (x <= 1) {
return x;
}
int l = 1, h = x;
while (l <= h) {
int mid = l + (h - l) / 2;
int sqrt = x / mid;
if (sqrt == mid) {
return mid;
} else if (mid > sqrt) {
h = mid - 1;
} else {
l = mid + 1;
}
}
return h;
}


744. 寻找比目标字母大的最小字母

letters = [“c”, “f”, “j”]
target = “a”

letters = [“c”, “f”, “j”]
target = “c”

letters = [“c”, “f”, “j”]
target = “d”

letters = [“c”, “f”, “j”]
target = “g”

letters = [“c”, “f”, “j”]
target = “j”

letters = [“c”, “f”, “j”]
target = “k”

letters长度范围在[2, 10000]区间内。
letters 仅由小写字母组成，最少包含两个不同的字母。

1 与上一题相反，本题的要找的是比指定值大一点的数，所以此时l > r满足时，l就是比指定值大一点的数了。

2 注意可能有连续重复的数字，所以一直往右找到一个数大于指定值

class Solution {
public char nextGreatestLetter(char[] letters, char target) {
if (letters == null || letters.length == 0) return 'a';
int l = 0,r = letters.length - 1;
while (l <= r) {
int m = l + (r - l)/2;
if (letters[m] <= target ) {
l = m + 1;
}else {
r = m - 1;
}
}

if (l <= letters.length - 1) {
return letters[l];
}else {
return letters[0];
}

}
}

1. 有序数组中的单一元素

public int singleNonDuplicate(int[] nums) {
int l = 0, h = nums.length - 1;
while (l < h) {
int m = l + (h - l) / 2;
if (m % 2 == 1) {
m--;   // 保证 l/h/m 都在偶数位，使得查找区间大小一直都是奇数
}
if (nums[m] == nums[m + 1]) {
l = m + 2;
} else {
h = m;
}
}
return nums[l];
}


153. 寻找旋转排序数组中的最小值

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

public int findMin(int[] nums) {
int l = 0, h = nums.length - 1;
while (l < h) {
int m = l + (h - l) / 2;
if (nums[m] <= nums[h]) {
h = m;
} else {
l = m + 1;
}
}
return nums[l];
}

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

1 首先通过二分查找找到该数出现的最左边位置（与例题一样）

2 然后通过二分查找找到比该数大1的数出现的位置，如果不存在，则刚好在所求数右边一位，再减1即可。

3 边界条件判断

public int[] searchRange(int[] nums, int target) {
int first = binarySearch(nums, target);
int last = binarySearch(nums, target + 1) - 1;
if (first == nums.length || nums[first] != target) {
return new int[]{-1, -1};
} else {
return new int[]{first, Math.max(first, last)};
}
}

private int binarySearch(int[] nums, int target) {
int l = 0, h = nums.length; // 注意 h 的初始值
while (l < h) {
int m = l + (h - l) / 2;
if (nums[m] >= target) {
h = m;
} else {
l = m + 1;
}
}
return l;
}


## 搜索

### BFS

• 0 -> {6,2,1,5};

• 6 -> {4}
• 2 -> {}
• 1 -> {}
• 5 -> {3}

• 4 -> {}
• 3 -> {}

• 队列：用来存储每一轮遍历得到的节点；
• 标记：对于遍历过的节点，应该将它标记，防止重复遍历。

[[1,1,0,1],
[1,0,1,0],
[1,1,1,1],
[1,0,1,1]]

1 表示可以经过某个位置，求解从 (0, 0) 位置到 (tr, tc) 位置的最短路径长度。
2 由于每个点需要保存x坐标，y坐标以及长度，所以必须要用一个类将三个属性封装起来。
3 由于bfs每次只将距离加一，所以当位置抵达终点时，此时的距离就是最短路径了。

private static class Position {
int r, c, length;
public Position(int r, int c, int length) {
this.r = r;
this.c = c;
this.length = length;
}
}

public static int minPathLength(int[][] grids, int tr, int tc) {
int[][] next = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int m = grids.length, n = grids[0].length;
while (!queue.isEmpty()) {
Position pos = queue.poll();
for (int i = 0; i < 4; i++) {
Position nextPos = new Position(pos.r + next[i][0], pos.c + next[i][1], pos.length + 1);
if (nextPos.r < 0 || nextPos.r >= m || nextPos.c < 0 || nextPos.c >= n) continue;
if (grids[nextPos.r][nextPos.c] != 1) continue;
grids[nextPos.r][nextPos.c] = 0;
if (nextPos.r == tr && nextPos.c == tc) return nextPos.length;
}
}
return -1;
}

1. 完全平方数

1 可以将每个整数看成图中的一个节点，如果两个整数之差为一个平方数，那么这两个整数所在的节点就有一条边。

2 要求解最小的平方数数量，就是求解从节点 n 到节点 0 的最短路径。

3 首先生成平方数序列放入数组，然后通过队列，每次减去一个平方数，把剩下的数加入队列，也就是通过bfs的方式，当此时的数刚好等于平方数，则满足题意，由于每次循环level加一，所以最后输出的level就是需要的平方数个数。

public int numSquares(int n) {
List<Integer> squares = generateSquares(n);
boolean[] marked = new boolean[n + 1];
marked[n] = true;
int level = 0;
while (!queue.isEmpty()) {
int size = queue.size();
level++;
while (size-- > 0) {
int cur = queue.poll();
for (int s : squares) {
int next = cur - s;
if (next < 0) {
break;
}
if (next == 0) {
return level;
}
if (marked[next]) {
continue;
}
marked[next] = true;
}
}
}
return n;
}

/**
* 生成小于 n 的平方数序列
* @return 1,4,9,...
*/
private List<Integer> generateSquares(int n) {
List<Integer> squares = new ArrayList<>();
int square = 1;
int diff = 3;
while (square <= n) {
square += diff;
diff += 2;
}
return squares;
}


127. 单词接龙

beginWord = “hit”,
endWord = “cog”,
wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]

beginWord = “hit”
endWord = “cog”
wordList = [“hot”,”dot”,”dog”,”lot”,”log”]

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
//注意此处把首个单词放到了list的最后面，所以start才会是N-1。别搞错了。
int N = wordList.size();
int start = N - 1;
int end = 0;
while (end < N && !wordList.get(end).equals(endWord)) {
end++;
}
if (end == N) {
return 0;
}
List<Integer>[] graphic = buildGraphic(wordList);
return getShortestPath(graphic, start, end);
}

private List<Integer>[] buildGraphic(List<String> wordList) {
int N = wordList.size();
List<Integer>[] graphic = new List[N];
for (int i = 0; i < N; i++) {
graphic[i] = new ArrayList<>();
for (int j = 0; j < N; j++) {
if (isConnect(wordList.get(i), wordList.get(j))) {
}
}
}
return graphic;
}

private boolean isConnect(String s1, String s2) {
int diffCnt = 0;
for (int i = 0; i < s1.length() && diffCnt <= 1; i++) {
if (s1.charAt(i) != s2.charAt(i)) {
diffCnt++;
}
}
return diffCnt == 1;
}

private int getShortestPath(List<Integer>[] graphic, int start, int end) {
boolean[] marked = new boolean[graphic.length];
marked[start] = true;
int path = 1;
while (!queue.isEmpty()) {
int size = queue.size();
path++;
while (size-- > 0) {
int cur = queue.poll();
for (int next : graphic[cur]) {
if (next == end) {
return path;
}
if (marked[next]) {
continue;
}
marked[next] = true;
}
}
}
return 0;
}


## DFS

1. 岛屿的最大面积

[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]

[[0,0,0,0,0,0,0,0]]

//只需要从每个1出发，然后遍历相连的所有1，得到总和，更新最大值即可。

public static int maxAreaOfIsland(int[][] grid) {
int [][]visit = new int[grid.length][grid[0].length];
int max = 0;
for (int i = 0;i < grid.length;i ++) {
for (int j = 0;j < grid[0].length;j ++) {
if (grid[i][j] == 1) {
max = Math.max(max, dfs(grid, i, j, visit, 0));
}
}
}
return max;
}

//通过递归进行了各个方向的可达性遍历，于是可以遍历到所有的1，然后更新最大值。

public static int dfs(int [][]grid, int x, int y, int [][]visit, int count) {
if (x < 0 || x > grid.length - 1 || y < 0 || y > grid[0].length - 1) {
return count;
}
if (visit[x][y] == 1 || grid[x][y] == 0) {
return count;
}

visit[x][y] = 1;
count ++;

count += dfs(grid, x + 1, y, visit, 0);
count += dfs(grid, x - 1, y, visit, 0);
count += dfs(grid, x, y + 1, visit, 0);
count += dfs(grid, x, y - 1, visit, 0);
return count;
}

1. 岛屿的个数

11110
11010
11000
00000

11000
11000
00100
00011

public class 图的连通分量个数 {
static int count = 0;
public int findCircleNum(int[][] M) {
count = 0;
int []visit = new int[M.length];
Arrays.fill(visit, 0);
for (int i = 0;i < M.length;i ++) {
if (visit[i] == 0) {
dfs(M, i, visit);
count ++;
}
}

return count;
}

//每次访问把能到达的点标记为1，并且访问结束时计数加一。最终得到岛屿个数。
public void dfs (int [][]M, int j, int []visit) {
for (int i = 0;i < M.length;i ++) {
if (M[j][i] == 1 && visit[i] == 0) {
visit[i] = 1;
dfs(M, i, visit);
}
}
}

}

1. 朋友圈

[[1,1,0],
[1,1,0],
[0,0,1]]

[[1,1,0],
[1,1,1],
[0,1,1]]

N 在[1,200]的范围内。

private int n;

public int findCircleNum(int[][] M) {
n = M.length;
int circleNum = 0;
boolean[] hasVisited = new boolean[n];
for (int i = 0; i < n; i++) {
if (!hasVisited[i]) {
dfs(M, i, hasVisited);
circleNum++;
}
}
return circleNum;
}

private void dfs(int[][] M, int i, boolean[] hasVisited) {
hasVisited[i] = true;
for (int k = 0; k < n; k++) {
if (M[i][k] == 1 && !hasVisited[k]) {
dfs(M, k, hasVisited);
}
}
}


//    private static int n;
//    public static int findCircleNum(int[][] M) {
//        n = M.length;
//        int cnt = 0 ;
//        int []visit = new int[n];
//        for (int i = 0;i < M.length;i ++) {
//            if(visit[i] == 0)  {
//                dfs(M, visit, i);
//                cnt ++;
//            }
//        }
//        return cnt;
//    }
//    public static void dfs(int[][]M, int[] visit, int i) {
//        visit[i] = 1;
//        for (int j = 0;j < M.length;j ++) {
//            if(visit[j] == 0 && M[i][j] == 1)  {
//                dfs(M, visit, i);
//            }
//        }
//    }

1. 被围绕的区域

X X X X
X O O X
X X O X
X O X X

X X X X
X X X X
X X X X
X O X X

1 我们是要把X包围的O变成X但是有一个很麻烦的问题就是，如何判断O被X完全包住，这是非常难解决的。

2 于是换一种思路，把不被X包住的那些O找出来，剩下的不就是X了吗。

3 不被X包住的O，首先它们的起点一定是在边缘处，所以我们从边缘处找出一个O，然后从O出发，找到所有相连的O，把它们变成T（为了不跟里面的O混淆）

4 最后遍历一次棋盘，把T变成O，把O变成X，就搞定了。妙啊，妙啊。

private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
private int m, n;

public void solve(char[][] board) {
if (board == null || board.length == 0) {
return;
}

m = board.length;
n = board[0].length;

for (int i = 0; i < m; i++) {
dfs(board, i, 0);
dfs(board, i, n - 1);
}
for (int i = 0; i < n; i++) {
dfs(board, 0, i);
dfs(board, m - 1, i);
}

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'T') {
board[i][j] = 'O';
} else if (board[i][j] == 'O') {
board[i][j] = 'X';
}
}
}
}

private void dfs(char[][] board, int r, int c) {
if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != 'O') {
return;
}
board[r][c] = 'T';
for (int[] d : direction) {
dfs(board, r + d[0], c + d[1]);
}
}


417.能到达的太平洋和大西洋的区域

1. Pacific Atlantic Water Flow (Medium)

Given the following 5x5 matrix:

Pacific ~ ~ ~ ~ ~
~ 1 2 2 3 (5) *
~ 3 2 3 (4) (4) *
~ 2 4 (5) 3 1 *
~ (6) (7) 1 4 5 *
~ (5) 1 1 2 4 *
* * * * * Atlantic

Return:
[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).

1 如果说上一题已经很有趣了，这一题可以说是更奇葩了。

2 首先，在大西洋和 太平洋两边的水一定可以分别流入这两个海洋。

3 然后从海洋边上的水开始进行dfs，遇到海拔比自己高的水就把它也设置成canreach即可，于是我们就可以得到两个数组。最后遍历两个数组，都满足的点就是结果了。

private int m, n;
private int[][] matrix;
private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

public List<int[]> pacificAtlantic(int[][] matrix) {
List<int[]> ret = new ArrayList<>();
if (matrix == null || matrix.length == 0) {
return ret;
}

m = matrix.length;
n = matrix[0].length;
this.matrix = matrix;
boolean[][] canReachP = new boolean[m][n];
boolean[][] canReachA = new boolean[m][n];

for (int i = 0; i < m; i++) {
dfs(i, 0, canReachP);
dfs(i, n - 1, canReachA);
}
for (int i = 0; i < n; i++) {
dfs(0, i, canReachP);
dfs(m - 1, i, canReachA);
}

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (canReachP[i][j] && canReachA[i][j]) {
}
}
}

return ret;
}

private void dfs(int r, int c, boolean[][] canReach) {
if (canReach[r][c]) {
return;
}
canReach[r][c] = true;
for (int[] d : direction) {
int nextR = d[0] + r;
int nextC = d[1] + c;
if (nextR < 0 || nextR >= m || nextC < 0 || nextC >= n
|| matrix[r][c] > matrix[nextR][nextC]) {

continue;
}
dfs(nextR, nextC, canReach);
}
}


## Backtracking

Backtracking（回溯）属于 DFS。

1. 电话号码的字母组合

1 本题需要把数字键盘和字母做一个映射，使用数组是一个不错的办法。而使用hashmap可能会显得有点臃肿。

2 接着我们可以使用String或者Stringbuilder保存结果，由于string不会被改变，所以我们不需要维持其状态，直接递归即可。

class Solution {
public List<String> letterCombinations(String digits) {
if (digits.equals("")) {
return new ArrayList();
}
List<String> list = new ArrayList<>();
String []arr = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
dfs(list, arr, new StringBuilder(), 0, digits);
return list;
}

public void dfs(List<String> list, String []arr, StringBuilder sb, int cur, String digits) {
if (cur == digits.length()) {
return;
}
int num = Integer.parseInt(digits.substring(cur, cur + 1));

for (int i = 0;i < arr[num].length();i ++) {
sb.append(arr[num].charAt(i));
dfs(list, arr, sb, cur + 1, digits);
sb.deleteCharAt(sb.length() - 1);
}
}
}

1. 复原IP地址

public List<String> restoreIpAddresses(String s) {
int i,j,k,m;
ArrayList <String> list = new ArrayList<>();
int len = s.length();
for (i = 1;i< 4 && i < len - 2;i ++) {
for (j = i + 1;j < i + 4 && j < len - 1;j ++) {
for (m = j + 1;m < j + 4 && m < len;m ++) {
//substring后面的下标是不算在内的。
String s1 = s.substring(0,i);
String s2 = s.substring(i,j);
String s3 = s.substring(j,m);
String s4 = s.substring(m,len);
if(isValid(s1) && isValid(s2) && isValid(s3) && isValid(s4))
{
list.add(s1 + '.' + s2 + '.' + s3 + '.' + s4);
}
}
}
}
return list;
}

public boolean isValid(String s) {
if (s.length() == 0 || s.length() > 3 || s.charAt(0) == '0' && s.length() > 1
|| Integer.parseInt(s) > 255) {
return false;
}else return true;
}


当然在for循环中，i 从0到2进行遍历。然后更新当前结果。

}

if (k == 4 || s.length() == 0) {
if (k == 4 && s.length() == 0) {
}
return;
}
for (int i = 0; i < s.length() && i <= 2; i++) {
if (i != 0 && s.charAt(0) == '0') {
break;
}
String part = s.substring(0, i + 1);
if (Integer.valueOf(part) <= 255) {
part = "." + part;
}
}
}
}

1. 单词搜索

board =
[
[‘A’,’B’,’C’,’E’],
[‘S’,’F’,’C’,’S’],
[‘A’,’D’,’E’,’E’]
]

private final static int[][] direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
private int m;
private int n;

public boolean exist(char[][] board, String word) {
if (word == null || word.length() == 0) {
return true;
}
if (board == null || board.length == 0 || board[0].length == 0) {
return false;
}

m = board.length;
n = board[0].length;
boolean[][] hasVisited = new boolean[m][n];

for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (backtracking(0, r, c, hasVisited, board, word)) {
return true;
}
}
}

return false;
}

private boolean backtracking(int curLen, int r, int c, boolean[][] visited, final char[][] board, final String word) {
if (curLen == word.length()) {
return true;
}
if (r < 0 || r >= m || c < 0 || c >= n
|| board[r][c] != word.charAt(curLen) || visited[r][c]) {

return false;
}

visited[r][c] = true;

for (int[] d : direction) {
//此处完成了剪枝，如果分支i满足则不会走后续分支。
if (backtracking(curLen + 1, r + d[0], c + d[1], visited, board, word)) {
return true;
}
}

visited[r][c] = false;

return false;
}


class Solution {
static class StopMsgException extends RuntimeException {

}

static boolean flag;

public boolean exist(char[][] board, String word) {
if (word.equals("")) {
return true;
}
int [][]visit = new int[board.length][board[0].length];
flag = false;
try {
for (int i = 0;i < board.length;i ++) {
for (int j = 0;j < board[0].length;j ++) {
if (word.charAt(0) == board[i][j]) {
dfs(board, word, visit, i, j);
}
}
}
} catch (StopMsgException e) {
System.out.println(e);
}
return flag;
}

public void dfs(char[][] board, String word, int [][]visit, int i, int j) {
if (word.equals("")) {
flag = true;
throw new StopMsgException();
}
if (i > board.length - 1 || i < 0 || j > board[0].length - 1 || j < 0) {
return;
}
if (visit[i][j] == 1) {
return;
}

if (word.charAt(0) == board[i][j]) {
visit[i][j] = 1;
//没有进行剪枝，效率比较低，于是在递归判断条件中进行剪枝，避免后续不必要的递归。

dfs(board, word.length() == 1 ? "" : word.substring(1, word.length()), visit, i + 1, j);
dfs(board, word.length() == 1 ? "" : word.substring(1, word.length()), visit, i - 1, j);
dfs(board, word.length() == 1 ? "" : word.substring(1, word.length()), visit, i, j - 1);
dfs(board, word.length() == 1 ? "" : word.substring(1, word.length()), visit, i, j + 1);
visit[i][j] = 0;
}
}
}

1. 全排列

[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

class Solution {
static List<List<Integer>> Alllist = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
Alllist.clear();
List<Integer> list = new ArrayList<>();
int []visit = new int[nums.length];
dfs(list, nums, visit);
return Alllist;
}
public void dfs(List<Integer> list, int []nums, int []visit) {
if (list.size() == nums.length) {
return;
}

for (int i = 0;i < nums.length;i ++) {
if (visit[i] == 0) {
visit[i] = 1;
dfs(list, nums, visit);
visit[i] = 0;
list.remove(list.size() - 1);
}
}
}
}

1. 全排列 II

[
[1,1,2],
[1,2,1],
[2,1,1]
]

解析：本题在上一题的基础上加上了一个条件，数组中有重复数字，但是结果集返回的是不同的排列。

class Solution {
static List<List<Integer>> Alllist = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
Alllist.clear();
List<Integer> list = new ArrayList<>();
int []visit = new int[nums.length];
Arrays.sort(nums);
dfs(list, nums, visit);
return Alllist;
}
public void dfs(List<Integer> list, int []nums, int []visit) {
if (list.size() == nums.length) {
return;
}

for (int i = 0;i < nums.length;i ++) {
if(i - 1 >= 0 && nums[i] == nums[i - 1] && visit[i - 1] == 0) {
continue;
}
if (visit[i] == 0) {
visit[i] = 1;
dfs(list, nums, visit);
visit[i] = 0;
list.remove(list.size() - 1);
}
}
}
}

1. 组合

[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

class Solution {
static List<List<Integer>> Alllist = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
Alllist.clear();
List<Integer> list = new ArrayList<>();
dfs(list, n, k, 1);
return Alllist;
}
public void dfs(List<Integer> list, int n, int k, int cur) {
if (list.size() == k) {
return;
}
for (int i = cur;i <= n;i ++) {
dfs(list, n, k, i + 1);
list.remove(list.size() - 1);
}
}
}


### 39. 组合总和

candidates 中的数字可以无限制重复被选取。

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

[
[2,2,2,2],
[2,3,3],
[3,5]
]

class Solution {
static List<List<Integer>> Alllist = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Alllist.clear();
List<Integer> list = new ArrayList<>();
Arrays.sort(candidates);
dfs(list, candidates, 0, target, 0);
return Alllist;
}
public void dfs(List<Integer> list, int [] candidates, int sum, int target, int cur) {
if (sum == target) {
return;
}
for (int i = cur;i < candidates.length;i ++) {
if (sum + candidates[i] <= target) {
dfs(list, candidates, sum + candidates[i], target, i);
list.remove(list.size() - 1);
}
}
}


### 40. 组合总和 II

candidates 中的每个数字在每个组合中只能使用一次。

[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]

[
[1,2,2],
[5]
]

class Solution {
static List<List<Integer>> Alllist = new ArrayList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Alllist.clear();
List<Integer> list = new ArrayList<>();
int []visit = new int[candidates.length];
Arrays.sort(candidates);
dfs(list, candidates, 0, target, 0, visit);
return Alllist;
}
public void dfs(List<Integer> list, int [] candidates, int sum, int target, int cur, int[] visit) {
if (sum == target) {
return;
}
for (int i = cur;i < candidates.length;i ++) {
if (i - 1 >= 0 && candidates[i] == candidates[i - 1] && visit[i - 1] == 0) {
continue;
}
if (sum + candidates[i] <= target) {
visit[i] = 1;
dfs(list, candidates, sum + candidates[i], target, i + 1, visit);
list.remove(list.size() - 1);
visit[i] = 0;
}
}
}
}


### 216. 组合总和 III

class Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
Alllist.clear();
List<Integer> list = new ArrayList<>();
dfs(list, 0, n, k, 1);
return Alllist;
}
static List<List<Integer>> Alllist = new ArrayList<>();
public void dfs(List<Integer> list, int sum, int n, int k, int cur) {
if (sum == n && list.size() == k) {
return;
}
for (int i = cur;i <= 9;i ++) {
if (sum + i <= n && list.size() < k) {
dfs(list, sum + i, n, k, i + 1);
list.remove(list.size() - 1);
}
}
}
}


### 78. 子集

[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

class Solution {
List<List<Integer>> Alllist = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
List<Integer> list = new ArrayList<>();
dfs(nums, 0, list);
return Alllist;
}

public void dfs(int []nums, int cur, List<Integer> list) {
if (cur <= nums.length) {
} else {
return;
}
for (int i = cur;i < nums.length;i ++) {
dfs(nums, i + 1, list);
list.remove(list.size() - 1);
}
}
}


### 90. 子集 II

[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

class Solution {
List<List<Integer>> Alllist = new ArrayList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<Integer> list = new ArrayList<>();
Arrays.sort(nums);
int []visit = new int[nums.length];
dfs(nums, 0, visit, list);
return Alllist;
}
public void dfs(int []nums, int cur, int []visit, List<Integer> list) {
if (cur <= nums.length) {
} else {
return;
}
for (int i = cur;i < nums.length;i ++) {
if (i > 0 && visit[i - 1] == 0 && nums[i] == nums[i - 1]) {
continue;
}
if (visit[i] == 0) {
visit[i] = 1;
dfs(nums, i + 1,visit, list);
list.remove(list.size() - 1);
visit[i] = 0;
}
}
}
}


### 131. 分割回文串

[
[“aa”,”b”],
[“a”,”a”,”b”]
]

1 要把字符串分割成回文字符串组合，那么我们要存的其实还是所有的字符串，所以返回条件还是当cur = s.length()。

2 字符串分割，首先在循环中遍历满足回文的第一个子串，在此基础上找下一个回文子串，达到了剪枝的目的。

class Solution {
List<List<String>> allList = new ArrayList<>();
public List<List<String>> partition(String s) {
List<String> list = new ArrayList<>();
dfs(s, 0, list);
return allList;
}
public void dfs(String s, int cur, List<String> list) {
if (cur == s.length()) {
return;
}
for (int i = cur;i < s.length();i ++) {
String str = s.substring(cur, i + 1);
if (legal(str)) {
dfs(s, i + 1, list);
list.remove(list.size() - 1);
}
}
}
public boolean legal(String s) {
int i = 0,j = s.length() - 1;
while (i < j) {
if (s.charAt(i) == s.charAt(j)) {
i ++;
j --;
}else {
return false;
}
}
return true;
}
}


## 动态规划

### 70. Climbing Stairs (Easy)

dp[N] 即为所求。

public int climbStairs(int n) {
if (n <= 2) {
return n;
}
int pre2 = 1, pre1 = 2;
for (int i = 2; i < n; i++) {
int cur = pre1 + pre2;
pre2 = pre1;
pre1 = cur;
}
return pre1;
}


### 198. 打家劫舍

public static int rob(int[] nums) {
if (nums == null || nums.length == 0) return 0;
if (nums.length == 1)return nums[0];
if (nums.length == 2)return nums[0] > nums[1] ? nums[0] : nums[1];
int []dp = new int[nums.length + 1];
//dp代表最右只抢到第n家时的总钱数。
dp[1] = nums[0];
dp[2] = nums[0] > nums[1] ? nums[0] : nums[1];
for (int i = 3;i <= nums.length;i ++) {
dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1]);
}
return dp[nums.length];
}


### 213. 打家劫舍 II

public static int rob(int[] nums) {

if (nums == null || nums.length == 0) return 0;
if (nums.length == 1)return nums[0];
if (nums.length == 2)return nums[0] > nums[1] ? nums[0] : nums[1];
int []dp = new int[nums.length + 1];
//dp代表最右只抢到第n家时的总钱数。
//如果抢了第一家
dp[1] = nums[0];
dp[2] = nums[0] > nums[1] ? nums[0] : nums[1];
for (int i = 3;i < nums.length;i ++) {
dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1]);
}
int max = dp[nums.length - 1];
//如果不抢第一家
dp[1] = 0;
dp[2] = nums[1];
for (int i = 3;i <= nums.length;i ++) {
dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1]);
}

if (dp[nums.length]  > max)max = dp[nums.length];
return max;
}


i==k，交换 i 和 k 的信后，它们的信和信封在正确的位置，但是其余 i-2 封信有 dp[i-2] 种错误装信的方式。由于 j 有 i-1 种取值，因此共有 (i-1)*dp[i-2] 种错误装信方式。
i != k，交换 i 和 j 的信后，第 i 个信和信封在正确的位置，其余 i-1 封信有 dp[i-1] 种错误装信方式。由于 j 有 i-1 种取值，因此共有 (i-1)*dp[i-1] 种错误装信方式。

dp[N] 即为所求。

### 64. 最小路径和

[
[1,3,1],
[1,5,1],
[4,2,1]
]

class Solution {
public int minPathSum(int[][] grid) {
int [][]dp = new int[grid.length][grid[0].length];
dp[0][0] = grid[0][0];
for (int i = 1;i < grid.length;i ++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
for (int i = 1;i < grid[0].length;i ++) {
dp[0][i] = dp[0][i - 1] + grid[0][i];
}
for (int i = 1;i < grid.length;i ++) {
for (int j = 1;j < grid[0].length;j ++) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[grid.length - 1][grid[0].length - 1];
}
}


### 62. 不同路径

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

class Solution {
public int uniquePaths(int m, int n) {
int [][]dp = new int[m][n];
for (int i = 0; i < m;i ++) {
dp[i][0] = 1;
}
for (int i = 0; i < n;i ++) {
dp[0][i] = 1;
}
for (int i = 1;i < m;i ++) {
for (int j = 1;j < n;j ++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
}


### 53. 最大子序和

class Solution {
public int maxSubArray(int[] nums) {
if (nums.length == 0) {
return 0;
}
if (nums.length == 1) {
return nums[0];
}
int []dp = new int[nums.length];
dp[0] = nums[0];
for (int i = 1;i < nums.length;i ++) {
dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
}
int max = nums[0];
for (int i = 0;i < dp.length;i ++) {
max = Math.max(max, dp[i]);
}
return max;
}
}


### 343. 整数拆分

public int integerBreak(int n) {
int[] dp = new int[n + 1];
dp[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i - 1; j++) {
dp[i] = Math.max(dp[i], Math.max(j * dp[i - j], j * (i - j)));
}
}
return dp[n];
}

1. 完全平方数

dp[1] = 1。所以对于每个i,我们都要遍历所有小于等于它的平方数，以便找到所需个数最少的个数。

min = Math.min(min, dp[i - square] + 1);

public int numSquares(int n) {
List<Integer> squareList = generateSquareList(n);
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
int min = Integer.MAX_VALUE;
for (int square : squareList) {
if (square > i) {
break;
}
min = Math.min(min, dp[i - square] + 1);
}
dp[i] = min;
}
return dp[n];
}

private List<Integer> generateSquareList(int n) {
List<Integer> squareList = new ArrayList<>();
int diff = 3;
int square = 1;
while (square <= n) {
square += diff;
diff += 2;
}
return squareList;
}


### 第五类：最长递增子序列

dp数组代表以第i个元素作为序列结尾时的最大递增序列，由于之前的序列是可选的，所以我们遍历之前所有满足情况的点（也就是满足nums[i] > nums[j]点），找到前面最长的递增序列即可。

dp[i] = Math.max(dp[j] + 1, dp[i]);

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

for (int i = 1;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]);
}else {
dp[i] = Math.max(dp[i], 1);
}
}
}

int max = 0;
for (int i = 0;i < dp.length;i ++) {
max = Math.max(max, dp[i]);
}
return max;
}
}


### 第六类：最长公共子序列

if (nums1[i - 1] == nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}


public int lengthOfLCS(int[] nums1, int[] nums2) {
int n1 = nums1.length, n2 = nums2.length;
int[][] dp = new int[n1 + 1][n2 + 1];
for (int i = 1; i <= n1; i++) {
for (int j = 1; j <= n2; j++) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[n1][n2];
}


### 第七类：01背包

0-1 背包

public int knapsack(int W, int N, int[] weights, int[] values) {
int[][] dp = new int[N + 1][W + 1];
for (int i = 1; i <= N; i++) {
int w = weights[i - 1], v = values[i - 1];
for (int j = 1; j <= W; j++) {
if (j >= w) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w] + v);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[N][W];
}


public int knapsack(int W, int N, int[] weights, int[] values) {
int[] dp = new int[W + 1];
for (int i = 1; i <= N; i++) {
int w = weights[i - 1], v = values[i - 1];
for (int j = W; j >= 1; j–) {
if (j >= w) {
dp[j] = Math.max(dp[j], dp[j - w] + v);
}
}
}
return dp[W];
}

0-1 背包问题无法使用贪心算法来求解，也就是说不能按照先添加性价比最高的物品来达到最优，这是因为这种方式可能造成背包空间的浪费，从而无法达到最优。考虑下面的物品和一个容量为 5 的背包，如果先添加物品 0 再添加物品 1，那么只能存放的价值为 16，浪费了大小为 2 的空间。最优的方式是存放物品 1 和物品 2，价值为 22.

id w v v/w
0 1 6 6
1 2 10 5
2 3 12 4

1. Partition Equal Subset Sum (Medium)

Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

public boolean canPartition(int[] nums) {
int sum = computeArraySum(nums);
if (sum % 2 != 0) {
return false;
}
int W = sum / 2;
boolean[] dp = new boolean[W + 1];
dp[0] = true;
Arrays.sort(nums);
for (int num : nums) {                 // 0-1 背包一个物品只能用一次
for (int i = W; i >= num; i--) {   // 从后往前，先计算 dp[i] 再计算 dp[i-num]
dp[i] = dp[i] || dp[i - num];
}
}
return dp[W];
}

private int computeArraySum(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
return sum;
}


1. Coin Change (Medium)

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

public int coinChange(int[] coins, int amount) {
if (coins == null || coins.length == 0) {
return 0;
}
int[] minimum = new int[amount + 1];
Arrays.fill(minimum, amount + 1);
minimum[0] = 0;
Arrays.sort(coins);
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length && coins[j] <= i; j++) {
minimum[i] = Math.min(minimum[i], minimum[i - coins[j]] + 1);
}
}
return minimum[amount] > amount ? -1 : minimum[amount];
}


### 第八类：股票买卖

1. Best Time to Buy and Sell Stock IV (Hard)

public int maxProfit(int k, int[] prices) {
int n = prices.length;
if (k >= n / 2) { // 这种情况下该问题退化为普通的股票交易问题
int maxProfit = 0;
for (int i = 1; i < n; i++) {
if (prices[i] > prices[i - 1]) {
maxProfit += prices[i] - prices[i - 1];
}
}
return maxProfit;
}
int[][] maxProfit = new int[k + 1][n];
for (int i = 1; i <= k; i++) {
int localMax = maxProfit[i - 1][0] - prices[0];
for (int j = 1; j < n; j++) {
maxProfit[i][j] = Math.max(maxProfit[i][j - 1], prices[j] + localMax);
localMax = Math.max(localMax, maxProfit[i - 1][j] - prices[j]);
}
}
return maxProfit[k][n - 1];
}

1. Best Time to Buy and Sell Stock III (Hard)

public int maxProfit(int[] prices) {
int firstBuy = Integer.MIN_VALUE, firstSell = 0;
int secondBuy = Integer.MIN_VALUE, secondSell = 0;
for (int curPrice : prices) {
}
if (firstSell < firstBuy + curPrice) {
}
if (secondBuy < firstSell - curPrice) {
}
if (secondSell < secondBuy + curPrice) {
}
}
return secondSell;
}

1. Best Time to Buy and Sell Stock with Cooldown(Medium)

public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
int N = prices.length;
int[] s1 = new int[N];
int[] sell = new int[N];
int[] s2 = new int[N];
sell[0] = s2[0] = 0;
for (int i = 1; i < N; i++) {
buy[i] = s2[i - 1] - prices[i];
s1[i] = Math.max(buy[i - 1], s1[i - 1]);
sell[i] = Math.max(buy[i - 1], s1[i - 1]) + prices[i];
s2[i] = Math.max(s2[i - 1], sell[i - 1]);
}
return Math.max(sell[N - 1], s2[N - 1]);
}


1. Best Time to Buy and Sell Stock with Transaction Fee (Medium)

Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:
Selling at prices[3] = 8
Selling at prices[5] = 9
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

public int maxProfit(int[] prices, int fee) {
int N = prices.length;
int[] s1 = new int[N];
int[] sell = new int[N];
int[] s2 = new int[N];
sell[0] = s2[0] = 0;
for (int i = 1; i < N; i++) {
buy[i] = Math.max(sell[i - 1], s2[i - 1]) - prices[i];
s1[i] = Math.max(buy[i - 1], s1[i - 1]);
sell[i] = Math.max(buy[i - 1], s1[i - 1]) - fee + prices[i];
s2[i] = Math.max(s2[i - 1], sell[i - 1]);
}
return Math.max(sell[N - 1], s2[N - 1]);
}


1. Best Time to Buy and Sell Stock (Easy)

public int maxProfit(int[] prices) {
int n = prices.length;
if (n == 0) return 0;
int soFarMin = prices[0];
int max = 0;
for (int i = 1; i < n; i++) {
if (soFarMin > prices[i]) soFarMin = prices[i];
else max = Math.max(max, prices[i] - soFarMin);
}
return max;
}


### 第九类：字符串编辑

1. Delete Operation for Two Strings (Medium)

Input: “sea”, “eat”
Output: 2
Explanation: You need one step to make “sea” to “ea” and another step to make “eat” to “ea”.

public int minDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
continue;
}
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
}
}
}
return m + n - 2 * dp[m][n];
}


1. 2 Keys Keyboard (Medium)

Input: 3
Output: 3
Explanation:
Intitally, we have one character ‘A’.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get ‘AA’.
In step 3, we use Paste operation to get ‘AAA’.

public int minSteps(int n) {
if (n == 1) return 0;
for (int i = 2; i <= Math.sqrt(n); i++) {
if (n % i == 0) return i + minSteps(n / i);
}
return n;
}
public int minSteps(int n) {
int[] dp = new int[n + 1];
int h = (int) Math.sqrt(n);
for (int i = 2; i <= n; i++) {
dp[i] = i;
for (int j = 2; j <= h; j++) {
if (i % j == 0) {
dp[i] = dp[j] + dp[i / j];
break;
}
}
}
return dp[n];
}


## 数学

x 和 y 的最大公约数为：gcd(x,y) = 2min(m0,n0) * 3min(m1,n1) * 5min(m2,n2) * …

x 和 y 的最小公倍数为：lcm(x,y) = 2max(m0,n0) * 3max(m1,n1) * 5max(m2,n2) * …

## 分治

1. 为运算表达式设计优先级

((2-1)-1) = 0
(2-(1-1)) = 2

(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10

### Trie

Trie，又称前缀树或字典树，用于判断字符串是否存在或者是否具有某种字符串前缀。

208. Implement Trie (Prefix Tree) (Medium)

class Trie {

private class Node {
Node[] childs = new Node[26];
boolean isLeaf;
}

private Node root = new Node();

public Trie() {
}

public void insert(String word) {
insert(word, root);
}

private void insert(String word, Node node) {
if (node == null) return;
if (word.length() == 0) {
node.isLeaf = true;
return;
}
int index = indexForChar(word.charAt(0));
if (node.childs[index] == null) {
node.childs[index] = new Node();
}
insert(word.substring(1), node.childs[index]);
}

public boolean search(String word) {
return search(word, root);
}

private boolean search(String word, Node node) {
if (node == null) return false;
if (word.length() == 0) return node.isLeaf;
int index = indexForChar(word.charAt(0));
return search(word.substring(1), node.childs[index]);
}

public boolean startsWith(String prefix) {
return startWith(prefix, root);
}

private boolean startWith(String prefix, Node node) {
if (node == null) return false;
if (prefix.length() == 0) return true;
int index = indexForChar(prefix.charAt(0));
return startWith(prefix.substring(1), node.childs[index]);
}

private int indexForChar(char c) {
return c - 'a';
}
}

677. Map Sum Pairs (Medium)

Input: insert("apple", 3), Output: Null
Input: sum("ap"), Output: 3
Input: insert("app", 2), Output: Null
Input: sum("ap"), Output: 5
class MapSum {

private class Node {
Node[] child = new Node[26];
int value;
}

private Node root = new Node();

public MapSum() {

}

public void insert(String key, int val) {
insert(key, root, val);
}

private void insert(String key, Node node, int val) {
if (node == null) return;
if (key.length() == 0) {
node.value = val;
return;
}
int index = indexForChar(key.charAt(0));
if (node.child[index] == null) {
node.child[index] = new Node();
}
insert(key.substring(1), node.child[index], val);
}

public int sum(String prefix) {
return sum(prefix, root);
}

private int sum(String prefix, Node node) {
if (node == null) return 0;
if (prefix.length() != 0) {
int index = indexForChar(prefix.charAt(0));
return sum(prefix.substring(1), node.child[index]);
}
int sum = node.value;
for (Node child : node.child) {
sum += sum(prefix, child);
}
return sum;
}

private int indexForChar(char c) {
return c - 'a';
}
}

## 图

### 二分图

785. Is Graph Bipartite? (Medium)

Input: [[1,3], [0,2], [1,3], [0,2]]
Output: true
Explanation:
The graph looks like this:
0----1
|    |
|    |
3----2
We can divide the vertices into two groups: {0, 2} and {1, 3}.
Example 2:
Input: [[1,2,3], [0,2], [0,1,3], [0,2]]
Output: false
Explanation:
The graph looks like this:
0----1
| \  |
|  \ |
3----2
We cannot find a way to divide the set of nodes into two independent subsets.
public boolean isBipartite(int[][] graph) {
int[] colors = new int[graph.length];
Arrays.fill(colors, -1);
for (int i = 0; i 

### 拓扑排序

207. Course Schedule (Medium)

2, [[1,0]]
return true
2, [[1,0],[0,1]]
return false

public boolean canFinish(int numCourses, int[][] prerequisites) {
List[] graphic = new List[numCourses];
for (int i = 0; i 

### 并查集

684. Redundant Connection (Medium)

Input: [[1,2], [1,3], [2,3]]
Output: [2,3]
Explanation: The given undirected graph will be like this:
1
/ \
2 - 3

public int[] findRedundantConnection(int[][] edges) {
int N = edges.length;
UF uf = new UF(N);
for (int[] e : edges) {
int u = e[0], v = e[1];
if (uf.connect(u, v)) {
return e;
}
uf.union(u, v);
}
return new int[]{-1, -1};
}

private class UF {
private int[] id;

UF(int N) {
id = new int[N + 1];
for (int i = 0; i 

## 位运算

1. 基本原理

0s 表示一串 0，1s 表示一串 1。

x ^ 0s = x      x & 0s = 0      x | 0s = x
x ^ 1s = ~x     x & 1s = x      x | 1s = 1s
x ^ x = 0       x & x = x       x | x = x

• 利用 x ^ 1s = ~x 的特点，可以将位级表示翻转；利用 x ^ x = 0 的特点，可以将三个数中重复的两个数去除，只留下另一个数。
• 利用 x & 0s = 0 和 x & 1s = x 的特点，可以实现掩码操作。一个数 num 与 mask ：00111100 进行位与操作，只保留 num 中与 mask 的 1 部分相对应的位。
• 利用 x | 0s = x 和 x | 1s = 1s 的特点，可以实现设值操作。一个数 num 与 mask：00111100 进行位或操作，将 num 中与 mask 的 1 部分相对应的位都设置为 1。

• n&(n-1) 去除 n 的位级表示中最低的那一位。例如对于二进制表示 10110 100 ，减去 1 得到 10110**011**，这两个数相与得到 10110**000**。
• n&(-n) 得到 n 的位级表示中最低的那一位。-n 得到 n 的反码加 1，对于二进制表示 10110 100 ，-n 得到 01001**100**，相与得到 00000**100**。
• n-n&(~n+1) 去除 n 的位级表示中最高的那一位。

• >> n 为算术右移，相当于除以 2n
• >>> n 为无符号右移，左边会补上 0。
• << n 为算术左移，相当于乘以 2n

3. Java 中的位操作

static int Integer.bitCount();           // 统计 1 的数量
static int Integer.highestOneBit();      // 获得最高位
static String toBinaryString(int i);     // 转换为二进制表示的字符串

461. Hamming Distance (Easy)

Input: x = 1, y = 4

Output: 2

Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
↑   ↑

The above arrows point to positions where the corresponding bits are different.

public int hammingDistance(int x, int y) {
int z = x ^ y;
int cnt = 0;
while(z != 0) {
if ((z & 1) == 1) cnt++;
z = z >> 1;
}
return cnt;
}

public int hammingDistance(int x, int y) {
int z = x ^ y;
int cnt = 0;
while (z != 0) {
z &= (z - 1);
cnt++;
}
return cnt;
}

public int hammingDistance(int x, int y) {
return Integer.bitCount(x ^ y);
}

136. Single Number (Easy)

Input: [4,1,2,1,2]
Output: 4

public int singleNumber(int[] nums) {
int ret = 0;
for (int n : nums) ret = ret ^ n;
return ret;
}

268. Missing Number (Easy)

Input: [3,0,1]
Output: 2

public int missingNumber(int[] nums) {
int ret = 0;
for (int i = 0; i 

|
9月前
|

【LeetCode】初级算法案例+java代码实现（数学篇）
【LeetCode】初级算法案例+java代码实现（数学篇）
68 0
|
9月前
|

【LeetCode】初级算法案例+java代码实现（排序和搜索篇）
【LeetCode】初级算法案例+java代码实现（排序和搜索篇）
41 0
|
9月前
|

【LeetCode】初级算法案例+java代码（设计问题篇）
【LeetCode】初级算法案例+java代码（设计问题篇）
93 0
|
9月前
|

【LeetCode】初级算法案例+java代码（树篇）
【LeetCode】初级算法案例+java代码（树篇）
56 0
|
9月前
|

【LeetCode】初级算法案例+java代码（数组篇）
【LeetCode】初级算法案例+java代码（数组篇）
46 0
|
10月前
|
Java
java学习第四天笔记-流程控制语句-分支结构82-判断和循环次数-回文数leetcode求商和余数
java学习第四天笔记-流程控制语句-分支结构82-判断和循环次数-回文数leetcode求商和余数
38 0
|
10月前
|
Java
java学习第四天笔记-流程控制语句-分支结构81-判断和循环次数-回文数leetcode
java学习第四天笔记-流程控制语句-分支结构81-判断和循环次数-回文数leetcode
36 0
|
10月前
|

89 1
|
11月前
|
Java
(Java)链表OJ题---LeetCode 138 复制带随机指针的链表

38 0
|
11月前
|

LeetCode第二题：两数相加（Java）
LeetCode第二题：两数相加（Java）
64 0