leetcode刷题记录

# 重点记录

135. 分发糖果 - 困难
 224. 基本计算器 - 困难
 222. 完全二叉树的节点个数 - 简单（完全二叉树性质）
236. 二叉树的最近公共祖先 - 中等
 530. 二叉搜索树的最小绝对差 - 简单（二叉搜索树性质）
130. 被围绕的区域 - 中等（图，特殊情况入手）

没做：
399. 除法求值（带权并查集）
210. 课程表 II

# 88. 合并两个有序数组 - 简单

两个非递减数列 num1 和 num2 合并为一个非递减数列 num1
思路是：三个下标，从右往左移动，比较大小，大的移动；注意 nums2 剩余的情况

	class Solution {
	public void merge(int[] nums1, int m, int[] nums2, int n) {
	int cur = m + n - 1;
	m -= 1;
	n -= 1;

	while (m >= 0 && n >= 0){
	if (nums1[m] <= nums2[n]){
	nums1[cur--] = nums2[n--];
	}else {
	nums1[cur--] = nums1[m--];
	}
	}

	while (n >= 0){
	nums1[cur--] = nums2[n--];
	}
	}
	}

# 27. 移除元素 - 简单

去除数组 nums 中的 val，输出剩余数量 k 和处理后的数组，要求 原地算法
思路是：双指针分别指向头尾，向中移动，将右边的非 val 赋值给左边的 val

	class Solution {
	public int removeElement(int[] nums, int val) {
	int l = 0, r = nums.length - 1;
	int res = 0;

	while (l < r){
	while (l < r && nums[l] != val){
	l++;
	res++;
	}
	while (l < r && nums[r] == val){
	r--;
	}
	if (l < r){
	nums[l++] = nums[r--];
	res++;
	}
	}

	if (l == r && nums[l] != val){
	res++;
	}

	return res;
	}
	}

# 80. 删除有序数组中的重复项 II - 中等

有序数组 nums 去除重复元素，重复超过两次，输出剩余数量 k 和处理后的数组，要求 原地算法
思路：一个下标指向待处理的数，另一个下标遍历数组，判断是否重复以及是否超过两次

	class Solution {
	public int removeDuplicates(int[] nums) {
	boolean flag = true;
	int pre = 1;

	for (int i = 1; i < nums.length; i++){
	if (flag && nums[i] == nums[i-1]){
	nums[pre] = nums[i];
	pre++;
	flag = false;
	}else if (nums[i] != nums[i-1]){
	nums[pre] = nums[i];
	pre++;
	flag = true;
	}
	}

	return pre;
	}
	}

# 169. 多数元素 - 简单

返回 nums 中次数多于 n/2 的元素
思路： Boyer-Moore 投票算法 ，遍历，相同 + 1，不同 - 1，维护一个众数

	class Solution {
	public int majorityElement(int[] nums) {
	int n = nums[0], count = 1;

	for (int i = 1; i < nums.length; i++){
	if (nums[i] == n){
	count++;
	}else {
	count--;
	}

	if (count == 0){
	n = nums[i];
	count = 1;
	}
	}

	return n;
	}
	}

# 189. 轮转数组 - 简单

将数组右轮转 k 个位置
思路：可以看成先逆转整个数组，再分别逆转两边，注意 k 的处理

	class Solution {
	public void rotate(int[] nums, int k) {
	k %= nums.length;

	rev(nums, 0, nums.length - 1);
	rev(nums, 0, k - 1);
	rev(nums, k, nums.length - 1);
	}

	public void rev(int[] nums, int l, int r){
	int tmp;
	while (l < r){
	tmp = nums[l];
	nums[l++] = nums[r];
	nums[r--] = tmp;
	}
	}
	}

# 122. 买卖股票的最佳时机 II - 中等

prices[i] 表示某支股票第 i 天的价格，同一天选择买入或卖出，可多次，最多持有一支，求最大利润
思路：I 是只能一次，维护前 n 个数的最小值，计算最大差；II 是多次，直接遍历，求前后差值

	class Solution {
	public int maxProfit(int[] prices) {
	int res = 0;

	for (int i = 1; i < prices.length; i++){
	if (prices[i] > prices[i - 1]){
	res += prices[i] - prices[i - 1];
	}
	}
	return res;
	}
	}

# 55. 跳跃游戏 - 中等

nums 数组的值表示从当前位置可以跳跃的最大距离，从 nums[0] 开始，判断是否能到达最后一个下标
思路：维护一个最远距离，判断是否超过数组长度

	class Solution {
	public boolean canJump(int[] nums) {
	int res = 0;

	for (int i = 0; i <= res && i < nums.length; i++){
	if (i + nums[i] > res){
	res = i + nums[i];
	}
	if (res >= nums.length - 1){
	return true;
	}
	}

	return false;
	}
	}

# 45. 跳跃游戏 II - 中等

nums[i] 表示从 i 向右跳转的最大长度，求从 0 到 n-1 的最小跳转次数
思路：每次跳转在上次最远距离中遍历，维护下一个最远距离，判断是否超过数组长度

	class Solution {
	public int jump(int[] nums) {
	if (nums.length == 1){
	return 0;
	}
	int count = 0, currMax = 0, nextMax = 0;

	for (int i = 0; i < nums.length;){
	nextMax = 0;
	for (; i <= currMax; i++){
	nextMax = Math.max(nextMax, i + nums[i]);

	if (nextMax >= nums.length - 1){
	return count + 1;
	}
	}
	currMax = nextMax;
	count += 1;
	}
	return count;
	}
	}

# 274. H 指数 - 中等

求 h 指数：至少有 h 篇论文被引用次数大于等于 h，h 为最大值
思路：从大到小排序，遍历，判断当前值是否大于个数

	class Solution {
	public int hIndex(int[] citations) {
	Arrays.sort(citations);
	int len = citations.length;
	for (int i = len - 1; i >= 0; i--){
	if (citations[i] < len - i){
	return len - i - 1;
	}
	}
	return len;
	}
	}

# 238. 除自身以外数组的乘积 - 中等

result[i] 等于 nums 中除 nums[i] 以外的所有数乘积
思路：两次遍历，第一次从左到右，用 result 存储前 i-1 个数之积；第二次从右到左，用 tmp 存储后 n-i-1 个数之积，相乘得到最终结果

	class Solution {
	public int[] productExceptSelf(int[] nums) {
	int[] result = new int[nums.length];
	result[0] = 1;
	for (int i = 1; i < nums.length; i++){
	result[i] = result[i - 1] * nums[i - 1];
	}
	int tmp = 1;
	for (int i = nums.length - 2; i >= 0; i--){
	tmp *= nums[i + 1];
	result[i] *= tmp;
	}
	return result;
	}
	}

# 134. 加油站 - 中等

gas[i] 表示在 i 获得汽油， cost[i] 表示从 i 到 i+1 消耗汽油，现在需要环绕一圈，求从哪里出发
思路：如果能从 i 到 j，且 i-1 能到 i，则 i-1 必能到 j。维护一个 res，大于 0 时 r 继续右移，否则 l 左移，为了不作取余操作，l 为末尾，r 为开头

	class Solution {
	public int canCompleteCircuit(int[] gas, int[] cost) {
	int len = gas.length, l = len - 1, r = 0, res = 0;
	for (int i = 0; i < len; i++){
	if (res >= 0){
	res += gas[r] - cost[r];
	r += 1;
	}else {
	res += gas[l] - cost[l];
	l -= 1;
	}
	}
	return res>=0?(l+1)%len:-1;
	}
	}

# 135. 分发糖果 - 困难

ratings 表示评分，每个孩子至少一个糖果，相邻两个孩子评分高的数量更多
思路：拆分成左右规则，左右两次遍历，取结果最大值
规则定义：设学生 A 和学生 B 左右相邻，A 在 B 左边；
・左规则：当 ratings B >ratings A 时，B 的糖比 A 的糖数量多。
・右规则：当 ratings A >ratings B 时，A 的糖比 B 的糖数量多。

	class Solution {
	public int candy(int[] ratings) {
	int res = 0;
	int[] arr = new int[ratings.length];
	arr[0] = 1;

	for (int i = 1; i < ratings.length; i++){
	if (ratings[i] > ratings[i - 1]){
	arr[i] = arr[i - 1] + 1;
	}else {
	arr[i] = 1;
	}
	}

	int tmp = 1;
	res = arr[ratings.length - 1];
	for (int i = ratings.length - 2; i >= 0; i--){
	if (ratings[i] > ratings[i + 1]){
	tmp += 1;
	res += Math.max(arr[i], tmp);
	}else{
	tmp = 1;
	res += arr[i];
	}
	}
	return res;
	}
	}

# 42. 接雨水 - 困难

height[i] 表示高度，求可存储的雨水
接雨水
思路：存储雨水取决于当前格高度和当前格左右两边最高高度中的较小值，所以分别从两边出发，较矮的一边往中间移动，维护左右两边的最大值，同时移动后所处的格子雨水量只取决于移动边的最大值

	class Solution {
	public int trap(int[] height) {
	int l = 0, r = height.length - 1, result = 0;
	int l_max = height[l], r_max = height[r];

	while (l < r){
	if (height[l] < height[r]){
	l += 1;

	if (height[l] < l_max){
	result += l_max - height[l];
	}else {
	l_max = height[l];
	}
	}else {
	r -= 1;

	if (height[r] < r_max){
	result += r_max - height[r];
	}else {
	r_max = height[r];
	}
	}
	}
	return result;
	}
	}

# 13. 罗马数字转整数 - 简单

思路：从右到左遍历，判断是否小于上一个数，是就减去，否则加上

	class Solution {
	private static final char[] rom = {'I', 'V', 'X', 'L', 'C', 'D', 'M'};
	private static final int[] num = {1, 5, 10, 50, 100, 500, 1000};
	private Map<Character, Integer> map = new HashMap<>();

	public Solution(){
	for (int i = 0; i < rom.length; i++){
	map.put(rom[i], i);
	}
	}
	public int romanToInt(String s) {
	char[] charArray = s.toCharArray();
	int pre = map.get(charArray[charArray.length - 1]), curr = 0;
	int result = num[pre];
	for (int i = charArray.length - 2; i >= 0; i--){
	curr = map.get(charArray[i]);
	if (curr >= pre){
	result += num[curr];
	}else {
	result -= num[curr];
	}
	pre = curr;
	}
	return result;
	}
	}

# 12. 整数转罗马数字 - 中等

思路：从大到小整除，转换

	class Solution {
	private static final String[] ROM = {"I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M"};
	private static final int[] NUM = {1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000};

	public String intToRoman(int num) {
	int index = 12, count = 0;
	StringBuilder result = new StringBuilder();

	while (num > 0){
	result.append(ROM[index].repeat(num / NUM[index]));
	num %= NUM[index];
	index -= 1;
	}
	return result.toString();
	}
	}

# 151. 反转字符串中的单词 - 中等

反转字符串中的单词顺序，每个单词用空格隔开
思路：遍历读取每个单词，逆序输出

	class Solution {
	public String reverseWords(String s) {
	List<String> words = new ArrayList<>();
	int pre = 0, curr = 0;

	while (pre < s.length()){
	while (pre < s.length() && s.charAt(pre) == ' '){
	pre++;
	}
	curr = pre;
	while (curr < s.length() && s.charAt(curr) != ' '){
	curr++;
	}
	if (pre < s.length()){
	words.add(s.substring(pre, curr));
	pre = curr;
	}
	}

	StringBuilder stringBuilder = new StringBuilder();
	for (int i = words.size() - 1; i >= 0; i--){
	stringBuilder.append(words.get(i));
	if (i != 0){
	stringBuilder.append(' ');
	}
	}
	return stringBuilder.toString();
	}
	}

# 6. Z 字形变换 - 中等

将给定的字符串和行数，从上往下、从左到右进行 Z 字排序，再从左往右顺序输出
比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
P A H N
A P L S I I G
Y I R
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
思路：观察移动步数规律，第 i 行每次移动 2*i 或 2*numRows - 2 - 2*i ，不为 0

	class Solution {
	public String convert(String s, int numRows) {
	if (numRows == 1){
	return s;
	}

	int step = 0;
	StringBuilder stringBuilder = new StringBuilder();
	for (int i = 0; i < numRows; i++){
	step = 2 * i;
	for (int j = i; j < s.length();j = j + step){
	stringBuilder.append(s.charAt(j));
	step = 2 * numRows - 2 - step;
	if (step == 0){
	step = 2 * numRows - 2;
	}
	}
	}
	return stringBuilder.toString();
	}
	}

# 28. 找出字符串中第一个匹配项的下标 - 简单

思路：KMP 算法，构造子串的前缀数组 next

	class Solution {
	public int strStr(String haystack, String needle) {
	int[] next = new int[needle.length()];
	getNext(needle, next);
	return kmp(haystack, needle, next);
	}

	public void getNext(String s, int[] next){
	next[0] = -1;
	for (int i = 0, j = -1; i < s.length() - 1;){
	if (j == -1 \|\| s.charAt(i) == s.charAt(j)){
	i++;
	j++;
	next[i] = j;
	}else{
	j = next[j];
	}
	}
	}

	public int kmp(String s, String p, int[] next){
	int m = s.length(), n = p.length();
	int i = 0, j = 0;

	while (i < m){
	if(j == n - 1 && s.charAt(i) == p.charAt(j)){
	return i - j;
	}else if(s.charAt(i) == p.charAt(j)){
	i++;
	j++;
	}else{
	j = next[j];
	if(j == -1){
	i++;
	j++;
	}
	}
	}
	return -1;
	}
	}

# 68. 文本左右对齐 - 困难

保证每行长度都为 maxWidth，左侧空格数大于右侧，最后一行左对齐，用一个空格隔开
思路：计算从 i 到 j 的单词长度，加上间隔为一空格，超过 maxWidth 则将前面的单词转换为一行；按情况添加空格，以及最后一句

	class Solution {
	public List<String> fullJustify(String[] words, int maxWidth) {
	int i = 0, j = 0, len = words.length, count = 0;
	int blank = 0, res = 0;
	StringBuilder stringBuilder = new StringBuilder();
	List<String> result = new ArrayList<>();

	while (j < len){
	count += words[j].length();

	if (count + j - i < maxWidth){
	j++;
	}else{
	if (count + j - i > maxWidth){
	count -= words[j].length();
	j--;
	}

	if (i == j){
	stringBuilder.append(words[j]).append(" ".repeat(maxWidth - count));
	}else {
	blank = (maxWidth - count) / (j - i);
	res = maxWidth - count - blank * (j - i);

	for (int t = i; t < j; t++){
	stringBuilder.append(words[t]);
	stringBuilder.append(" ".repeat(blank));
	if (res > 0){
	stringBuilder.append(" ");
	res--;
	}
	}
	stringBuilder.append(words[j]);
	}
	result.add(stringBuilder.toString());
	stringBuilder = new StringBuilder();
	j++;
	i = j;
	count = 0;
	}
	}
	if (i != len){
	for (int t = i; t < j; t++){
	stringBuilder.append(words[t]).append(" ");
	}
	stringBuilder.append(" ".repeat(maxWidth - count - j + i));
	result.add(stringBuilder.toString());
	}
	return result;
	}
	}

# 167. 两数之和 II - 输入有序数组 - 中等

非递减数列，返回两数之和为 target 的下标（从 1 开始），要求常量级空间
思路：双指针，指向头尾，两数之和大于 target 则右指针向左移，否则左指针右移

	class Solution {
	public int[] twoSum(int[] numbers, int target) {
	int l = 0, r = numbers.length - 1;

	while (l < r){
	if (numbers[l] + numbers[r] == target){
	break;
	}else if (numbers[l] + numbers[r] > target){
	r--;
	}else{
	l++;
	}
	}
	return new int[]{l + 1, r + 1};
	}
	}

# 11. 盛最多水的容器 - 中等

height[i] 表示 i 的高度，求两条线组成的容器最大装水容量
思路：双指针，指向头尾，高度小的移动，计算容量最大值

	class Solution {
	public int maxArea(int[] height) {
	int l = 0, r = height.length - 1;
	int result = 0;

	while (l < r){
	if (height[l] > height[r]){
	result = Math.max(result, (r - l) * height[r]);
	r--;
	}else{
	result = Math.max(result, (r - l) * height[l]);
	l++;
	}
	}
	return result;
	}
	}

# 15. 三数之和 - 中等

求三数之和为 0 的所有情况，不包含重复情况
思路：排序，固定一个数，头尾双指针搜索剩余两个数；在移动时注意去除重复情况

	class Solution {
	public List<List<Integer>> threeSum(int[] nums) {
	Arrays.sort(nums);
	int len = nums.length, l = 0, m = 1, r = len - 1;
	List<List<Integer>> result = new ArrayList<>();
	int tmp;
	while (l < len){
	m = l + 1;
	r = len - 1;
	while (m < r){
	tmp = nums[m] + nums[r] + nums[l];
	if (tmp == 0){
	result.add(Arrays.asList(nums[l], nums[m], nums[r]));
	do{
	m++;
	}while (m < r && nums[m] == nums[m - 1]);
	do{
	r--;
	}while (m < r && nums[r] == nums[r + 1]);
	}else if(tmp > 0){
	r--;
	}else{
	m++;
	}
	}
	do {
	l++;
	}while (l < len && nums[l] == nums[l - 1]);
	}
	return result;
	}
	}

# 209. 长度最小的子数组 - 中等

求总和大于等于 target 的子数组的最小长度
思路：滑动窗口，扩大到总和大于等于 target，再缩小求最小长度；注意全数组总和小于 target 的情况

	class Solution {
	public int minSubArrayLen(int target, int[] nums) {
	int l = 0, r = 0, sum = 0, len = nums.length, result = len + 1;

	while (r < len){
	while (r < len && sum < target){
	sum += nums[r];
	r++;
	}
	while (l < r && sum >= target){
	result = Math.min(result, r - l);
	sum -= nums[l];
	l++;
	}
	}
	return result == len + 1 ? 0 : result;
	}
	}

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

思路：滑动窗口，用集合存储窗口内的值，根据长度和容量判断是否重复；注意在不重复下窗口到达边界的情况

	class Solution {
	public int lengthOfLongestSubstring(String s) {
	int l = 0, r = 0, len = s.length(), result = 0;
	Set<Character> set = new HashSet<>();

	while (r < len){
	while (r < len && set.size() == r - l){
	result = Math.max(result, r - l);
	set.add(s.charAt(r));
	r++;
	}
	if (r == len && set.size() == r - l){
	result = Math.max(result, r - l);
	break;
	}
	r--;

	while (l < r && s.charAt(l) != s.charAt(r)){
	set.remove(s.charAt(l));
	l++;
	}
	l++;
	r++;
	}
	return result;
	}
	}

# 30. 串联所有单词的子串 - 困难

给定一个字符串 s 和一个字符串数组 words，words 中所有字符串长度相同，返回所有串联子串在 s 中的开始索引。
s 中的串联子串是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
思路：固定大小的滑动窗口，words 中字符串长度为 n，可分为 n 种情况，
从 s 的 0 到 n-1 位置开始，将字符串拆分为长度为 n 的单词，用哈希表存储，根据哈希表是否为空判断是否符合条件

	class Solution {
	public List<Integer> findSubstring(String s, String[] words) {
	int len = s.length(), m = words.length, n = words[0].length();
	Map<String, Integer> diff = new HashMap<>();
	List<Integer> result = new ArrayList<>();
	String tmp;

	if (len < m * n){
	return result;
	}

	//n 种起始位置，按长度 n 拆分单词
	for (int k = 0; k < n; k++){
	diff.clear();
	for (int i = k; i < m * n + k && i < len - n + 1; i += n){
	tmp = s.substring(i, i + n);
	diff.put(tmp, diff.getOrDefault(tmp, 0) + 1);
	}
	for (String word : words) {
	diff.put(word, diff.getOrDefault(word, 0) - 1);
	if (diff.get(word) == 0){
	diff.remove(word);
	}
	}
	// 根据 diff 是否为空，判断是否为串联子串
	if (diff.isEmpty()){
	result.add(k);
	}

	for (int i = m * n + k; i < len - n + 1; i += n){
	tmp = s.substring(i, i + n);
	diff.put(tmp, diff.getOrDefault(tmp, 0) + 1);
	if (diff.get(tmp) == 0){
	diff.remove(tmp);
	}

	tmp = s.substring(i - m * n, i - m * n + n);
	diff.put(tmp, diff.getOrDefault(tmp, 0) - 1);
	if (diff.get(tmp) == 0){
	diff.remove(tmp);
	}

	if (diff.isEmpty()){
	result.add(i - m * n + n);
	}
	}
	}
	return result;
	}
	}

# 76. 最小覆盖子串 - 困难

返回 s 中包含 t 所有字符的最小子串
思路：滑动窗口，从 0 开始，右边界移动直到满足条件，左边界移动缩小长度，哈希表存储进行判断

	class Solution {
	public String minWindow(String s, String t) {
	Map<Character, Integer> map = new HashMap<>();
	for (char c : t.toCharArray()) {
	map.put(c, map.getOrDefault(c, 0) + 1);
	}

	int l = 0, r = 0, len = s.length(), count = map.size();
	int start = 0, resultLen = s.length() + 1;
	Character c;
	while (r < len){
	while (r < len && count > 0){
	c = s.charAt(r);
	if (map.containsKey(c)){
	map.put(c, map.get(c) - 1);
	if (map.get(c) == 0){
	count--;
	}
	}
	r++;
	}
	while (l < r && count == 0){
	c = s.charAt(l);
	if (map.containsKey(c)){
	if (map.get(c) == 0){
	count++;
	}
	map.put(c, map.get(c) + 1);
	}
	l++;
	}
	if (r - l + 1 < resultLen){
	start = l - 1;
	resultLen = r - l + 1;
	}
	}

	if (resultLen == len + 1){
	return "";
	}
	return s.substring(start, start + resultLen);
	}
	}

# 36. 有效的数独 - 中等

只用判断已给的数字是否符合 9*9 数独规则
思路：遍历一次，存储对应行、列、九宫格，判断是否大于 1

	class Solution {
	public boolean isValidSudoku(char[][] board) {
	int[][] row = new int[9][9];
	int[][] col = new int[9][9];
	int[][][] sub = new int[3][3][9];
	int index;
	for (int i = 0; i < 9; i++) {
	for (int j = 0; j < 9; j++) {
	if (board[i][j] != '.'){
	index = board[i][j] - '0' - 1;
	if (row[i][index]++ == 1 \|\| col[j][index]++ == 1 \|\| sub[i/3][j/3][index]++ == 1){
	return false;
	}
	}
	}
	}
	return true;
	}
	}

# 54. 螺旋矩阵 - 中等

顺时针螺旋输出矩阵数字
思路：按四种方向移动，维护边界

	class Solution {
	public List<Integer> spiralOrder(int[][] matrix) {
	int xMin = 0, xMax = matrix[0].length - 1;
	int yMin = 0, yMax = matrix.length - 1;
	int[] xMove = {1, 0, -1, 0}, yMove = {0, 1, 0, -1};
	int x = 0, y = 0, choice = 0;
	List<Integer> res = new ArrayList<>();
	while (xMin <= xMax && yMin <= yMax){
	while (x >= xMin && x <= xMax && y >= yMin && y <= yMax){
	res.add(matrix[y][x]);
	x += xMove[choice];
	y += yMove[choice];
	}

	x -= xMove[choice];
	y -= yMove[choice];
	if (xMove[choice] == 1){
	yMin++;
	}else if (xMove[choice] == -1){
	yMax--;
	}else if (yMove[choice] == 1){
	xMax--;
	}else {
	xMin++;
	}
	choice = (choice + 1) % 4;
	x += xMove[choice];
	y += yMove[choice];
	}
	return res;
	}
	}

# 48. 旋转图像 - 中等

图像顺时针旋转 90 度，要求 原地 算法

	class Solution {
	public void rotate(int[][] matrix) {
	int n = matrix.length, tmp;

	for (int i = 0; i <= n / 2; i++) {
	for (int j = i; j < n - i - 1; j++) {
	tmp = matrix[i][j];
	matrix[i][j] = matrix[n - j - 1][i];
	matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
	matrix[n - i - 1][n - j - 1] = matrix[j][n - i -1];
	matrix[j][n - i - 1] = tmp;
	}
	}
	}
	}

# 73. 矩阵置零 - 中等

0 所在行和列都置为 0，要求 原地 算法
思路：第一次遍历，用第一行和第一列存储各列、各行 0 的情况，用额外变量存储第一行 0 的情况；第二次遍历，从后往前根据第一行第一列情况，置为 0

	class Solution {
	public void setZeroes(int[][] matrix) {
	boolean row0 = false;
	int m = matrix.length, n = matrix[0].length;
	for (int i = 0; i < n; i++) {
	if (matrix[0][i] == 0){
	row0 = true;
	break;
	}
	}

	for (int i = 1; i < m; i++) {
	for (int j = 0; j < n; j++) {
	if (matrix[i][j] == 0){
	matrix[0][j] = 0;
	matrix[i][0] = 0;
	}
	}
	}

	for (int i = 1; i < m; i++) {
	for (int j = n - 1; j >= 0; j--) {
	if (matrix[0][j] == 0 \|\| matrix[i][0] == 0){
	matrix[i][j] = 0;
	}
	}
	}
	if (row0){
	for (int i = 0; i < n; i++) {
	matrix[0][i] = 0;
	}
	}
	}
	}

# 289. 生命游戏 - 中等

1 为活细胞，0 为死细胞，有以下规则：

如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
如果死细胞周围正好有三个活细胞，则该位置死细胞复活

同一时间发生改变
思路：用额外数值表示发生转变的细胞

	class Solution {
	public boolean check(int i, int j, int m, int n, int[][] board){
	return i >= 0 && i < m && j >= 0 && j < n && (board[i][j] == 1 \|\| board[i][j] == 3);
	}
	public void gameOfLife(int[][] board) {
	int m = board.length, n = board[0].length;
	int count = 0;
	int[] i1 = {-1, -1, -1, 0, 0, 1, 1, 1};
	int[] j1 = {-1, 0, 1, -1, 1, -1, 0, 1};

	for (int i = 0; i < m; i++) {
	for (int j = 0; j < n; j++) {
	count = 0;
	for (int t = 0; t < 8; t++) {
	if (check(i + i1[t], j + j1[t], m, n, board)){
	count++;
	}
	}
	if (board[i][j] == 1 && (count < 2 \|\| count > 3)){
	board[i][j] = 3;
	}
	if (board[i][j] == 0 && count == 3){
	board[i][j] = 4;
	}
	}
	}
	for (int i = 0; i < m; i++) {
	for (int j = 0; j < n; j++) {
	if (board[i][j] == 3){
	board[i][j] = 0;
	}
	if (board[i][j] == 4){
	board[i][j] = 1;
	}
	}
	}
	}
	}

# 49. 字母异位词分组 - 中等

字母异位词：相同字母组成，顺序不同
小写字母组成，同样的字母异位词放在一组
思路：将每个字符串用一个特定的 key 表示，可以是直接排序（abb），也可以是计算每个字母个数（a1b2）

	class Solution {
	public List<List<String>> groupAnagrams(String[] strs) {
	Map<String, List<String>> map = new HashMap<>();

	for(String str: strs){
	char[] cArray = str.toCharArray();
	Arrays.sort(cArray);
	String key = new String(cArray); // 这样写快一点
	List<String> list = map.getOrDefault(key, new ArrayList<String>());
	list.add(str);
	map.put(key, list);
	}

	return new ArrayList<>(map.values());
	}
	}

# 128. 最长连续序列 - 中等

找出数字连续的最长序列的长度，不要求在数组中连续，时间复杂度为 O (n)
思路：set 去重，遍历每个数 i ，循环判断是否存在 i+1 ，存在 i-1 就跳过，避免重复计算

	class Solution {
	public int longestConsecutive(int[] nums) {
	Set<Integer> set = new HashSet<>();
	for (int num : nums) {
	set.add(num);
	}

	int ans = 0;
	for (Integer i : set) {
	if (!set.contains(i - 1)){
	int next = i + 1;
	while (set.contains(next)){
	next++;
	}
	ans = Math.max(ans, next - i);
	}
	}
	return ans;
	}
	}

# 56. 合并区间 - 中等

若干个区间 $intervals[i] = [start_i, end_i]$ ，要返回不重叠的区间范围
思路：先按 $start_i$ 进行排序，再进行遍历，判断 $start_i$ 是否在前一个区间范围内，是的话合并，计算右边界，否则将前一个区间范围添加到答案中

	class Solution {
	public int[][] merge(int[][] intervals) {
	Arrays.sort(intervals, new Comparator<int[]>() {
	@Override
	public int compare(int[] o1, int[] o2) {
	return o1[0] - o2[0];
	}
	});
	int len = intervals.length;
	int l = 0, r = 0;
	List<int[]> ans = new ArrayList<>();

	while (r < len){
	int tmp = intervals[l][1];
	while (r < len && intervals[r][0] <= tmp){
	tmp = Math.max(tmp, intervals[r][1]);
	r++;
	}
	ans.add(new int[]{intervals[l][0], tmp});
	l = r;
	}

	return ans.toArray(new int[ans.size()][]);
	}
	}

# 57. 插入区间 - 中等

不重叠的若干个区间， $start_i$ 升序排列，插入新区间 newInterval ，保证插入后的区间不重叠
思路：
遍历，判断 newInterval 是否与区间重叠，是就合并，赋值给 newInterval ，合并后继续遍历
若不重叠，则将当前区间添加到 ans，继续遍历
如果 newInterval 在两区间中间，则直接插入 newInterval
注意特殊情况：原数组长度为 0； newInterval 插入到数组头（插入到末尾包含在正常情况中，写的话也可以，提升速度😉）；到达边界时 newInterval 未插入

	class Solution {
	public int[][] insert(int[][] intervals, int[] newInterval) {
	int len = intervals.length;
	int i = 0;
	boolean change = false, append = false;
	List<int[]> ans = new ArrayList<>();

	// 特殊情况：原数组长度为 0；插入数组前
	if (len == 0){
	return new int[][]{newInterval};
	}
	if (newInterval[1] < intervals[0][0]){
	ans.add(newInterval);
	Collections.addAll(ans, intervals);
	return ans.toArray(new int[len + 1][]);
	}

	while (i < len){
	//newInterval 位于两区间中间
	if (i < len - 1 && intervals[i][1] < newInterval[0] && intervals[i + 1][0] > newInterval[1]){
	ans.add(intervals[i]);
	ans.add(newInterval);
	append = true;
	}
	//newInterval 与 intervals [i] 不重叠
	else if (intervals[i][1] < newInterval[0] \|\| intervals[i][0] > newInterval[1]){
	// 如果 newInterval 已经合并过，说明数组后面的不会再重叠了，直接退出循环，添加剩余
	if (change){
	ans.add(newInterval);
	append = true;
	break;
	}
	//newInterval 没合并过，就正常添加
	ans.add(intervals[i]);
	}else{
	// 重叠，求合并区间
	newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
	newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
	change = true;
	}
	i++;
	}
	// 到达边界，但 newInterval 还未添加时，添加 newInterval
	if (!append){
	ans.add(newInterval);
	}
	// 添加剩余区间
	while (i < len){
	ans.add(intervals[i]);
	i++;
	}

	return ans.toArray(new int[ans.size()][]);
	}
	}

# 452. 用最少数量的箭引爆气球 - 中等

有若干气球在 xy 平面上， $points[i] = [x_{start}, x_{end}]$ 表示在 $x_{start}$ 和 $x_{end}$ 之间，一支箭可以垂直于 x 轴射出，无限前进，求射爆所有气球的箭数最小值。
思路：合并区间，过程与 56. 合并区间 - 中等的一致，但要求的是重叠区间，右边界取两者最小值。不需要求具体区间范围，所以直接忽略左边界
注意：自定义排序时用 Integer.compare 防止相减时数值溢出

	class Solution {
	public int findMinArrowShots(int[][] points) {
	Arrays.sort(points, new Comparator<int[]>() {
	@Override
	public int compare(int[] o1, int[] o2) {
	return Integer.compare(o1[0], o2[0]);
	}
	});

	int len = points.length, pre, index = 0, count = 0;
	while (index < len){
	pre = points[index][1];
	while (index < len && points[index][0] <= pre){
	pre = Math.min(pre, points[index][1]);
	index++;
	}
	count++;
	}
	return count;
	}
	}

# 71. 简化路径 - 中等

linux 绝对路径， . 表示当前目录， .. 返回上级目录，多个 / 看作单个，以 / 开头，输出简化后的路径
思路：按 / 拆分，栈存储，根据值判断存入或排出

	class Solution {
	public String simplifyPath(String path) {
	String[] split = path.split("/");
	Stack<String> stack = new Stack<>();

	for (String s : split) {
	if (s.isEmpty() \|\| s.equals(".")){
	continue;
	}
	if (s.equals("..")){
	if (!stack.empty()){
	stack.pop();
	}
	}else{
	stack.push(s);
	}
	}

	if (stack.empty()){
	return "/";
	}
	StringBuilder sb = new StringBuilder();
	for (String s : stack) {
	sb.append('/').append(s);
	}
	return sb.toString();
	}
	}

# 150. 逆波兰表达式求值 - 中等

数字在前，运算符在后
思路：栈存储，遇到运算符，排出两个数字进行计算

	class Solution {
	public int evalRPN(String[] tokens) {
	Stack<Integer> stack = new Stack<>();
	int tmp;
	for (String token : tokens) {
	if (token.equals("+")){
	tmp = stack.pop();
	stack.push(stack.pop() + tmp);
	}else if(token.equals("-")){
	tmp = stack.pop();
	stack.push(stack.pop() - tmp);
	}else if(token.equals("*")){
	tmp = stack.pop();
	stack.push(stack.pop() * tmp);
	}else if(token.equals("/")){
	tmp = stack.pop();
	stack.push(stack.pop() / tmp);
	}else{
	stack.push(Integer.valueOf(token));
	}
	}
	return stack.pop();
	}
	}

# 224. 基本计算器 - 困难

包含 + 、 - 、 ( 、 ) 四种符号，空格和数字，计算表达式结果，其中 - 能用作负号表示， + 不行
思路：大致可以看成，去除全部括号后，获取真正的运算符
用栈存储当前符号的正负 sign ，默认为正，遇到 - 取反，此时遇到左括号，则将 sign 压入栈中，使括号内的符号取反，遇到右括号则排出，恢复到原来正负。

	import java.util.Stack;

	class Solution {
	public int calculate(String s) {
	Stack<Integer> ops = new Stack<>();
	ops.push(1);
	int sign = 1, len = s.length(), i = 0, ans = 0, tmp = 0;
	char c;
	while (i < len){
	c = s.charAt(i);
	if (c == '+'){
	sign = ops.peek();
	}else if(c == '-'){
	sign = -ops.peek();
	}else if(c == '('){
	ops.push(sign);
	}else if(c == ')'){
	ops.pop();
	}else if(c != ' '){
	tmp = 0;
	while (i < len && (c = s.charAt(i)) >= '0' && c <= '9'){
	tmp = tmp * 10 + c - '0';
	i++;
	}
	ans += sign * tmp;
	i--;
	}
	i++;
	}
	return ans;
	}
	}

# 141. 环形链表 - 简单

判断链表是否存在环
思路：快慢指针，fast 每次移动两步，slow 移动一步，如果存在环，fast 和 slow 会相遇

	public class Solution {
	public boolean hasCycle(ListNode head) {
	ListNode fast = head, slow = head;

	while (fast != null){
	fast = fast.next;
	slow = slow.next;
	if (fast != null){
	fast = fast.next;
	}

	if (fast != null && fast == slow){
	return true;
	}
	}
	return false;
	}
	}

# 2. 两数相加 - 中等

链表逆序存储，每节点存储一位数字
思路：遍历相加，判断进位

	public class Solution {
	public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
	ListNode head = new ListNode();
	ListNode tmp = head;
	int sum, next = 0;

	while (l1 != null \|\| l2 != null){
	sum = next;
	if (l1 != null){
	sum += l1.val;
	l1 = l1.next;
	}
	if (l2 != null){
	sum += l2.val;
	l2 = l2.next;
	}

	next = sum / 10;
	sum %= 10;
	tmp.next = new ListNode(sum);
	tmp = tmp.next;
	}
	if (next == 1){
	tmp.next = new ListNode(1);
	}
	return head.next;
	}
	}

# 138. 随机链表的复制 - 中等

Node 有 val、next 和 random 三个属性，深拷贝，next 和 random 要指向拷贝后的对应 Node
思路：遍历一遍，用哈希表存储旧新两个 Node 的映射，再遍历一遍，完成 random 的赋值

	public class Solution {
	public Node copyRandomList(Node head) {
	Node ans = new Node(0);
	Node curNew = ans, curOld = head, rand;
	Map<Node, Node> map = new HashMap<>();

	while (curOld != null){
	curNew.next = new Node(curOld.val);
	map.put(curOld, curNew.next);
	curNew = curNew.next;
	curOld = curOld.next;
	}
	curNew = ans.next;
	curOld = head;
	while (curOld != null){
	curNew.random = map.get(curOld.random);
	curNew = curNew.next;
	curOld = curOld.next;
	}
	return ans.next;
	}
	}

# 92. 反转链表 II - 中等

给出 left 和 right，反转该范围内的链表
思路：cur 记录 left 前一个节点，originhead 记录 cur 的下一个节点，即待反转链表头节点，first、second、third 进行链表反转，之后将分别指向头尾；left 和 right 相同时不反转

	public class Solution {
	public ListNode reverseBetween(ListNode head, int left, int right) {
	if (left == right){
	return head;
	}

	ListNode cur = new ListNode(0, head);
	head = cur;
	int count = 0;
	while (count != left - 1){
	cur = cur.next;
	count++;
	}
	ListNode originhead = cur.next;
	ListNode first = originhead, second = first.next, third = null;
	count++;
	while (count != right){
	third = second.next;
	second.next = first;
	first = second;
	second = third;
	count++;
	}
	cur.next = first;
	originhead.next = second;
	return head.next;
	}
	}

# 25. K 个一组翻转链表 - 困难

k 个一组反转链表，不满 k 个保持原样
思路：同 92 - 反转链表 - ii - 中等，外面多一层循环，记录反转前后的节点，pre 表示反转链表前一个节点，originHead 表示反转链表原头节点

	public class Solution {
	public ListNode reverseKGroup(ListNode head, int k) {
	ListNode ans = new ListNode(0, head), pre = ans, cur = ans;
	ListNode first = null, second = null, third = null, originHead = null;
	int count = 0;

	while (true){
	count = 0;
	while (cur.next != null && count != k){
	cur = cur.next;
	count++;
	}
	if (count != k){
	break;
	}

	originHead = pre.next;
	first = originHead;
	second = first.next;
	while (first != cur){
	third = second.next;
	second.next = first;
	first = second;
	second = third;
	}
	pre.next = first;
	originHead.next = second;
	pre = originHead;
	cur = pre;
	}
	return ans.next;
	}
	}

# 19. 删除链表的倒数第 N 个结点 - 中等

思路：先遍历一遍统计个数，再删除对应结点；新增一个头节点，便于管理

	public class Solution {
	public ListNode removeNthFromEnd(ListNode head, int n) {
	int count = 0;
	ListNode ans = new ListNode(0, head), cur = ans;

	while (cur.next != null){
	cur = cur.next;
	count++;
	}
	cur = ans;
	while (count != n){
	cur = cur.next;
	count--;
	}
	cur.next = cur.next.next;
	return ans.next;
	}
	}

# 82. 删除排序链表中的重复元素 II - 中等

已排序链表，删除其中的重复元素节点
思路：遍历，用 cur 比较当前和下一个节点元素是否相同，相同则向后移动，最后根据情况拼接

	public class Solution {
	public ListNode deleteDuplicates(ListNode head) {
	if (head == null){
	return null;
	}
	ListNode ans = new ListNode(head.val + 1, head), pre = ans, cur = ans;

	while (cur.next != null){
	cur = pre.next;
	while (cur.next != null && cur.val == cur.next.val){
	cur = cur.next;
	}
	if (cur == pre.next) {
	pre = cur;
	}else{
	pre.next = cur.next;
	}
	}
	return ans.next;
	}
	}

# 61. 旋转链表 - 中等

将每个节点向右移动 k 个位置
思路：遍历，统计节点个数 count，并将头尾相连，再从 head 开始，移动 count-k-1 次（k 取模于 count），断开，得到结果链表

	public class Solution {
	public ListNode rotateRight(ListNode head, int k) {
	if (head == null){
	return null;
	}

	int count = 1;
	ListNode cur = head;
	while (cur.next != null){
	cur = cur.next;
	count++;
	}
	cur.next = head;
	cur = head;
	k %= count;
	while (count != k + 1){
	cur = cur.next;
	count--;
	}
	head = cur.next;
	cur.next = null;
	return head;
	}
	}

# 86. 分隔链表 - 中等

给定 k，保证小于 k 的节点在前面，同时要保持原链表的相对顺序
思路：分成两个链表，遍历原链表，根据值大小拼接到对应链表，最后合并

	public class Solution {
	public ListNode partition(ListNode head, int x) {
	ListNode ans1 = new ListNode(), ans2 = new ListNode();
	ListNode cur1 = ans1, cur2 = ans2, cur = head;

	while (cur != null){
	if (cur.val < x){
	cur1.next = cur;
	cur1 = cur1.next;
	}else{
	cur2.next = cur;
	cur2 = cur2.next;
	}
	cur = cur.next;
	}
	cur1.next = ans2.next;
	cur2.next = null;
	return ans1.next;
	}
	}

# 105. 从前序与中序遍历序列构造二叉树 - 中等

元素不重复
思路：从先序序列获取根节点值，再从中序序列获取对应下标，左右两边划分为左右子树，递归构造

	class Solution {
	Map<Integer, Integer> map;

	public TreeNode dfs(int[] preorder, int index, int[] inorder, int start, int end){
	if (start == end){
	return null;
	}

	TreeNode node = new TreeNode(preorder[index]);
	Integer i = map.get(preorder[index]);
	node.left = dfs(preorder, index + 1, inorder, start, i);
	node.right = dfs(preorder, index + i - start + 1, inorder, i + 1, end);
	return node;
	}
	public TreeNode buildTree(int[] preorder, int[] inorder) {
	map = new HashMap<>();
	for (int i = 0; i < inorder.length; i++) {
	map.put(inorder[i], i);
	}
	return dfs(preorder, 0, inorder, 0, inorder.length);
	}
	}

# 106. 从中序与后序遍历序列构造二叉树 - 中等

思路：同 105 - 从前序与中序遍历序列构造二叉树 - 中等，从先序序列从左往右遍历，改成从后序序列从右往左遍历，递归构造的范围区间改变

	class Solution {
	Map<Integer, Integer> map;

	public TreeNode dfs(int[] postorder, int index, int[] inorder, int start, int end){
	if (start == end){
	return null;
	}
	TreeNode node = new TreeNode(postorder[index]);
	Integer i = map.get(postorder[index]);
	node.right = dfs(postorder, index - 1, inorder, i + 1, end);
	node.left = dfs(postorder, index - (end - i), inorder, start, i);
	return node;
	}
	public TreeNode buildTree(int[] inorder, int[] postorder) {
	map = new HashMap<>();
	for (int i = 0; i < inorder.length; i++) {
	map.put(inorder[i], i);
	}
	return dfs(postorder, postorder.length - 1, inorder, 0, inorder.length);
	}
	}

# 117. 填充每个节点的下一个右侧节点指针 II - 中等

让每个节点的 next 指向下一个右侧节点，不存在右侧节点则指向 null
思路：两个队列，交替存储一行节点，遍历连接

	class Solution {
	public void bfs(Queue<Node> q1, Queue<Node> q2){
	Node pre;
	while (!q1.isEmpty()){
	pre = q1.poll();
	if (q1.isEmpty()){
	pre.next = null;
	}else{
	pre.next = q1.peek();
	}

	if (pre.left != null){
	q2.add(pre.left);
	}
	if (pre.right != null){
	q2.add(pre.right);
	}
	}
	}

	public Node connect(Node root) {
	if (root == null){
	return null;
	}

	Queue<Node> q1 = new ArrayDeque<>(), q2 = new ArrayDeque<>();
	q1.add(root);
	while (!q1.isEmpty() \|\| !q2.isEmpty()){
	bfs(q1, q2);
	bfs(q2, q1);
	}
	return root;
	}
	}

# 114. 二叉树展开为链表 - 中等

按先序遍历顺序，将子节点拼接到节点的右侧
思路：递归遍历，将左节点拼接到右侧，然后遍历拼接后的右节点，将原来的右节点拼接到末尾

	class Solution {
	public TreeNode dfs(TreeNode node){
	if (node.left != null){
	TreeNode tmp = node.right;
	node.right = dfs(node.left);
	if (tmp != null){
	TreeNode cur = node.right;
	while (cur.right != null){
	cur = cur.right;
	}
	cur.right = dfs(tmp);
	}
	node.left = null;
	}else if (node.right != null){
	node.right = dfs(node.right);
	}
	return node;
	}

	public void flatten(TreeNode root) {
	if (root == null){
	return;
	}
	dfs(root);
	}
	}

# 112. 路径总和 - 简单

是否存在，从根节点到叶子节点的路径之和等于指定值
思路：递归

	class Solution {
	public boolean dfs(TreeNode node, int sum, int target){
	if (node.left == null && node.right == null){
	return sum + node.val == target;
	}

	return (node.left != null && dfs(node.left, sum + node.val, target))
	\|\| (node.right != null && dfs(node.right, sum + node.val, target));
	}
	public boolean hasPathSum(TreeNode root, int targetSum) {
	if (root == null){
	return false;
	}
	return dfs(root, 0, targetSum);
	}
	}

# 129. 求根节点到叶节点数字之和 - 中等

节点 val 为 0-9，根节点到叶子节点路径组成的数字，求全部数字之和
思路：递归，sum 存储到当前节点形成的数字

	class Solution {
	public int dfs(TreeNode node, int sum){
	if (node == null){
	return 0;
	}

	sum = sum * 10 + node.val;
	if (node.left == null && node.right == null){
	return sum;
	}

	return dfs(node.left, sum) + dfs(node.right, sum);
	}
	public int sumNumbers(TreeNode root) {
	return dfs(root, 0);
	}
	}

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

二叉树中的路径被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定经过根节点。
路径和是路径中各节点值的总和，求最大路径和。
思路：递归，对左右子树求最大路径和，分别为 l 和 r，本节点值为 val，则当前最大路径和可能为 l+val、r+val、l+r+val 和 val，与存储的最大值比较，维护最大路径和 ans，同时，因为构造的是一条路径，所以返回给上一级不包含 l+r+val 这条。

	class Solution {
	int ans;
	public int dfs(TreeNode node){
	if (node == null){
	return 0;
	}

	int l = dfs(node.left);
	int r = dfs(node.right);
	ans = Math.max(ans, node.val);
	ans = Math.max(ans, l + node.val);
	ans = Math.max(ans, r + node.val);
	ans = Math.max(ans, l + r + node.val);

	return Math.max(Math.max(l + node.val, r + node.val), node.val);
	}
	public int maxPathSum(TreeNode root) {
	ans = Integer.MIN_VALUE;
	dfs(root);
	return ans;
	}
	}

# 222. 完全二叉树的节点个数 - 简单

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（从第 0 层开始），则该层包含 1~2^h 个节点。
思路：求左右子树的高度（从 1 开始），分别为 1 和 r，l 必然大于等于 r。若 l 大于 r，则左子树为满二叉树，递归求右子树；若相等，则右子树为满二叉树，递归求左子树。
高度为 h 的满二叉子树节点个数，再加上根节点，总数为

$1 + \sum_{i=0}^{h-1} 2^i = 1 + 2^0 + 2^1 + 2^2 + \cdots + 2^{h-1} = 2^h$

用位运算，即为 1 << h

	class Solution {
	public int dfs(TreeNode node){
	if (node == null){
	return 0;
	}

	int l = getHeight(node.left);
	int r = getHeight(node.right);
	if (l == r){
	return (1 << l) + dfs(node.right);
	}else{
	return (1 << r) + dfs(node.left);
	}
	}

	public int getHeight(TreeNode node){
	int height = 0;
	while (node != null){
	height++;
	node = node.left;
	}
	return height;
	}
	public int countNodes(TreeNode root) {
	return dfs(root);
	}
	}

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

祖先的定义：p 在 root 的左右子树中，或 p 是 root 本身，称 root 是 p 的祖先。
求 p、q 最近公共祖先，也就是求最深的公共祖先
思路：p、q 可能位于左右子树异侧，也可能其中一个是另一个的祖先。递归，找到 p 或 q 返回，否则返回 null。
若左右子树返回值不为 null，则说明根节点为公共祖先，并且由于是从底向上，所以该节点也是最近公共祖先；
若左右子树都为 null，说明不存在 p、q，继续返回 null；
若存在一边返回值不为 null，可能指向公共祖先或 p、q 某个值，此时返回非 null 值。

	class Solution {
	public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
	if (root == null \|\| root == p \|\| root == q){
	return root;
	}
	TreeNode l = lowestCommonAncestor(root.left, p, q);
	TreeNode r = lowestCommonAncestor(root.right, p, q);
	if (l == null) return r;
	if (r == null) return l;
	return root;
	}
	}

# 199. 二叉树的右视图 - 中等

从右侧看向二叉树，从上到下返回看到的节点值
思路：递归，先右子树再左子树，每一层第一个遍历到的值即为答案

	class Solution {
	List<Integer> ans;
	int depth;
	public void dfs(TreeNode node, int step){
	if (node == null){
	return;
	}

	if (step == depth){
	ans.add(node.val);
	depth++;
	}
	dfs(node.right, step + 1);
	dfs(node.left, step + 1);
	}
	public List<Integer> rightSideView(TreeNode root) {
	ans = new ArrayList<>();
	depth = 0;
	dfs(root, 0);
	return ans;
	}
	}

# 103. 二叉树的锯齿形层序遍历 - 中等

一层从左到右，一层从右到左，交替遍历
思路：双端队列，按标记决定插入列表顺序

	class Solution {
	public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
	if (root == null){
	return new ArrayList<>();
	}

	Deque<TreeNode> queue = new ArrayDeque<>();
	List<List<Integer>> ans = new ArrayList<>();
	queue.offer(root);
	int isLeft = 1;
	while (!queue.isEmpty()){
	int size = queue.size();
	Integer[] arr = new Integer[size];
	for (int i = 0; i < size; i++) {
	TreeNode t = queue.pollFirst();
	if (isLeft % 2 == 1){
	arr[i] = t.val;
	}else{
	arr[size - i - 1] = t.val;
	}

	if (t.left != null){
	queue.offerLast(t.left);
	}
	if (t.right != null){
	queue.offerLast(t.right);
	}
	}
	ans.add(Arrays.asList(arr));
	isLeft++;
	}
	return ans;
	}
	}

# 530. 二叉搜索树的最小绝对差 - 简单

求任意两个节点值绝对差的最小值
思路：二叉搜索树中序遍历是递增序列，求两节点绝对差最小值，就是序列中相邻两点间差的最小值。
递归，中序遍历，用 pre 记录前一节点，计算相邻两节点的差最小值

	class Solution {
	int ans = Integer.MAX_VALUE;
	TreeNode pre = null;

	public void dfs(TreeNode node){
	if (node == null){
	return;
	}

	dfs(node.left);
	if (pre != null){
	ans = Math.min(ans, node.val - pre.val);
	}
	pre = node;
	dfs(node.right);
	}

	public int getMinimumDifference(TreeNode root) {
	dfs(root);
	return ans;
	}
	}

# 230. 二叉搜索树中第 K 小的元素 - 中等

从 1 开始计数，求二叉搜索树中第 k 小的元素
思路：二叉搜索树中序遍历为递增序列，递归计算 count，得到第 k 个数

	class Solution {
	int ans = -1, count = 0;

	public void dfs(TreeNode node, int k){
	if (node == null \|\| ans != -1){
	return;
	}

	dfs(node.left, k);
	count++;
	if (count == k){
	ans = node.val;
	}
	dfs(node.right, k);
	}

	public int kthSmallest(TreeNode root, int k) {
	dfs(root, k);
	return ans;
	}
	}

# 98. 验证二叉搜索树 - 中等

给你一个二叉树的根节点 root，判断其是否是一个有效的二叉搜索树，左子树小于当前节点，右子树大于当前节点。
思路：中序遍历，判断是否为递增序列

	class Solution {
	TreeNode pre = null;
	boolean flag = true;

	public void dfs(TreeNode node){
	if (node == null \|\| !flag){
	return;
	}

	dfs(node.left);
	if (pre != null && pre.val >= node.val){
	flag = false;
	return;
	}
	pre = node;
	dfs(node.right);
	}

	public boolean isValidBST(TreeNode root) {
	dfs(root);
	return flag;
	}
	}

# 200. 岛屿数量 - 中等

二维网格，0 表示海洋，1 表示陆地，岛屿只能由垂直或水平方向的陆地组成，求岛屿数量
思路：递归，遍历二维数组，遇到陆地时，递归向四周遍历，将遍历过的陆地标记为 2

	class Solution {
	int count = 0;

	public void dfs(char[][] grid, int n, int m, int x, int y){
	if (x < 0 \|\| x >= n \|\| y < 0 \|\| y >= m \|\| grid[x][y] == '0' \|\| grid[x][y] == '2'){
	return;
	}

	grid[x][y] = '2';
	dfs(grid, n, m, x - 1, y);
	dfs(grid, n, m, x, y - 1);
	dfs(grid, n, m, x + 1, y);
	dfs(grid, n, m, x, y + 1);
	}

	public int numIslands(char[][] grid) {
	int n = grid.length, m = grid[0].length;
	count = 0;

	for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
	if (grid[i][j] == '1'){
	count++;
	dfs(grid, n, m, i, j);
	}
	}
	}
	return count;
	}
	}

# 130. 被围绕的区域 - 中等

二维数组，垂直或水平方向的 O 连接成一个区域，如果该区域被 X 包围，则会转换为 X
思路：从边界入手，边界的 O 不能转换为 X，与之同一区域的 O 同样不能转换为 X，递归 dfs 将其标记为 A，剩下的就是 X

	class Solution {
	public void dfs(char[][] board, int n, int m, int x, int y){
	if (x < 0 \|\| x >= n \|\| y < 0 \|\| y >= m \|\| board[x][y] == 'X' \|\| board[x][y] == 'A'){
	return ;
	}

	board[x][y] = 'A';
	dfs(board, n, m, x - 1, y);
	dfs(board, n, m, x, y - 1);
	dfs(board, n, m, x + 1, y);
	dfs(board, n, m, x, y + 1);
	}

	public void solve(char[][] board) {
	int n = board.length, m = board[0].length;

	for (int i = 0; i < n; i ++) {
	for (int j = 0; j < m; j++) {
	if ((i == 0 \|\| i == n - 1 \|\| j == 0 \|\| j == m - 1) && board[i][j] == 'O'){
	dfs(board, n, m, i, j);
	}
	}
	}

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

# 133. 克隆图 - 中等

无向连通图深拷贝，不存在重复边和环
思路：哈希表 visted 存储已访问的节点，以及新旧节点的对应关系。如果节点已访问过，则直接返回；否则，插入节点，遍历节点的全部子节点，递归调用
相对于克隆树，需要考虑死循环的问题

	class Solution {
	Map<Node, Node> visted = new HashMap<>();
	public Node dfs(Node node){
	if (visted.containsKey(node)){
	return visted.get(node);
	}

	Node newNode = new Node(node.val);
	visted.put(node, newNode);
	node.neighbors.forEach(n -> newNode.neighbors.add(dfs(n)));

	return newNode;
	}

	public Node cloneGraph(Node node) {
	if (node == null){
	return null;
	}
	return dfs(node);
	}
	}

# 207. 课程表 - 中等

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses-1。
在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i]=[ai,bi] ，表示如果要学习课程 ai 则必须先学习课程 bi。判断是否能完成全部课程。
思路：有向图，判断是否存在环。递归 dfs，标记已经访问过的节点，重复访问就返回 false。
标记 0 表示未访问，1 表示当前序列中已经访问过，标记 2 表示之前序列访问过且不存在环。

	class Solution {
	List<Integer>[] lists;
	int[] mark;

	public boolean dfs(int n){
	if (mark[n] == 1){
	return false;
	}else if (mark[n] == 2){
	return true;
	}

	mark[n] = 1;
	for (Integer i : lists[n]) {
	if (!dfs(i)){
	return false;
	}
	}
	mark[n] = 2;
	return true;
	}

	public boolean canFinish(int numCourses, int[][] prerequisites) {
	mark = new int[numCourses];
	lists = new ArrayList[numCourses];
	for (int i = 0; i < numCourses; i++) {
	lists[i] = new ArrayList();
	}

	for (int[] prerequisite : prerequisites) {
	lists[prerequisite[0]].add(prerequisite[1]);
	}

	for (int i = 0; i < numCourses; i++) {
	if (!dfs(i)){
	return false;
	}
	}
	return true;
	}
	}

# 909. 蛇梯棋 - 中等

n*n 的二维数组，从左下角出发，编号为 1，向右移动，遇到拐角向左移动，蛇形前行，终点为右上角。每次移动 1 到 6 步，如果移动到值为非 -1 的格子，会直接传送到对应编号的格子。求从起点到终点的最小步数，无法到达返回 - 1。
思路：将编号转换为二维数组坐标；
bfs，队列存储当前步数和编号，判断每一步移动的情况，直接到达或传送到达终点，直接返回步数；否则，将没访问过的编号存入队列。

	class Solution {
	public int[] trans(int n, int k){
	k--;
	int x = k / n, y = k % n;
	if (x % 2 == 1){
	y = n - 1 - y;
	}
	return new int[]{n - 1 - x, y};
	}

	public int snakesAndLadders(int[][] board) {
	int n = board.length;
	boolean[] visted = new boolean[n * n + 1];
	Deque<int[]> deque = new ArrayDeque<>();
	deque.offerLast(new int[]{0, 1});

	while (!deque.isEmpty()){
	int[] cur = deque.pollFirst();

	for (int i = 1; i <= 6; i++) {
	int next = cur[1] + i;
	if (next >= n * n){
	return cur[0] + 1;
	}
	int[] t = trans(n, next);
	if (board[t[0]][t[1]] != -1){
	next = board[t[0]][t[1]];
	}
	if (next >= n * n){
	return cur[0] + 1;
	}
	if (!visted[next]) {
	visted[next] = true;
	deque.offerLast(new int[]{cur[0] + 1, next});
	}
	}
	}
	return -1;
	}
	}

# 433. 最小基因变化 - 中等

基因序列由 ACGT 组成，每次只能变换一个，且变换后的基因必须在 bank 中，求从 startGene 到 endGene 的最小变化次数。
思路：按 bank 全排列顺序遍历，每次判断是否相差一个字母，是就标记并递归遍历

	class Solution {
	int ans;
	int[] mark;

	public void dfs(String startGene, String endGene, String[] bank, int step){
	if (startGene.equals(endGene)){
	ans = Math.min(ans, step);
	}

	if (step >= ans){
	return;
	}

	for (int i = 0; i < bank.length; i++) {
	if (mark[i] == 0){
	if (count(startGene, bank[i]) == 1){
	mark[i] = 1;
	dfs(bank[i], endGene, bank, step + 1);
	mark[i] = 0;
	}
	}
	}
	}

	public int count(String s1, String s2){
	int sum = 0;
	for (int i = 0; i < s1.length(); i++) {
	if (s1.charAt(i) != s2.charAt(i)){
	sum++;
	}
	}
	return sum;
	}

	public int minMutation(String startGene, String endGene, String[] bank) {
	ans = startGene.length() + 1;
	mark = new int[bank.length];
	dfs(startGene, endGene, bank, 0);
	return ans == startGene.length() + 1 ? -1 : ans;
	}
	}

Java