大厂社招3年-力扣热点高频刷题记录（已更新100+道热点题）

前言：
最近从大厂出来看机会，大厂面试基本都考察算法，于是维护此文档，一是查缺补漏，确保整体热点算法题目的应知应会，与思路的灵活理解；二是分享出来给其他同学朋友做一个参考借鉴，共同学习成长

目前刷题方向侧重于各大厂热点题，以及力扣的Hot 100

此笔记持续更新。

一、菜单

未分类

序号	题目链接	题目类型	来源	备注
	1. 两数相加	哈希	力扣Hot 100	一刷20240906、二刷20241006 ； 水题 、一二刷直接秒
	49. 字母异位词分组	哈希&异位词	力扣Hot 100	一刷20241006 、二刷20241016； 水题 、一二刷直接秒
	128. 最长连续序列	哈希&技巧	力扣Hot 100	一刷20241006 、 二刷20241016； 思路很精彩，一刷完全看题解，二刷花了点时间，思考明白了时间复杂度为什么是On 。建议隔一个月三刷
	283. 移动零	双指针&技巧	力扣Hot 100	一刷20241006、二刷20241016； 做法多样，思路很精彩，尤其是二刷思路 ；建议隔十五天三刷
	11. 盛最多水的容器	贪心&双指针	力扣Hot 100	一刷20241006、二刷10141016； 一刷看了题解，二刷直接秒
	15. 三数之和	双指针	力扣Hot 100	一刷时间20241006、二刷时间20241015； 一刷看了题解，二刷花了点时间做出来了，建议隔一个月三刷
	3. 无重复字符的最长子串	滑动窗口	力扣Hot 100	一刷20240912、二刷20240917、三刷20241015 一刷题解，二刷花时间，三刷秒杀，建议隔一个月四刷
	438. 找到字符串中所有字母异位词	滑动窗口&异位词	力扣Hot 100	一刷20241016； 滑动窗口裸题，建议隔一个月二刷
	560. 和为k的子数组	前缀和&哈希	力扣Hot 100	一刷20241009、二刷20241017 经典前缀和，一刷二刷都卡了很久，建议隔十五天三刷
	53. 最大子数组和	贪心	力扣Hot 100	一刷20240928、二刷20241017 直接秒，解出不难，难得是面试时可能用例不可见，需要处理细节，可以三刷
	56. 合并区间	数组	力扣Hot 100	一刷20240929、二刷20241017 一二刷都看题解了，一是排序函数，二是一些细节处理，建议隔一个月三刷
	189. 轮转数组	数组&技巧	力扣Hot 100	一刷20240929、二刷20241017 一刷看题解，二刷直接秒
	238. 除自身以外数组的乘积	数组&技巧	力扣Hot 100	一刷20240929、二刷20241017 一刷看题解，二刷想了会秒杀，可以三刷
	41. 缺失的第一个正数	数组&技巧	力扣Hot 100	一刷20240929、二刷20241017 一刷看题解，二刷想了会秒杀，可以三刷
	54. 螺旋矩阵	矩阵	力扣Hot 100	一刷20241009、二刷20241017 一刷看题解，二刷有调试，整体秒掉了，可以三刷
	48. 旋转图像	矩阵&规律	力扣Hot 100	一刷20241017 一刷看了下题解，核心掌握矩阵对角、水平、垂直翻转，建议隔一个月三刷
	240. 搜索二维矩阵二	矩阵&规律	力扣Hot 100	一刷20241017 偏技巧题，建议隔一个月二刷
	160. 相交链表	链表	力扣Hot 100	一刷20240917、二刷20241011 一刷看题解，二刷直接秒
	206. 反转链表	链表	力扣Hot 100	一刷20240919、二刷20241011、三刷20241018 直接秒
	234. 回文链表	链表	力扣Hot 100	一刷20240919、二刷20241011、三刷20241017 一刷二刷都比较费劲，三刷比较轻松，这个题锻炼链表的边界感很好，建议隔三个月三刷
	141. 环形链表	链表&技巧	力扣Hot 100	一刷20240908、二刷20241011 懂快慢指针思路，直接秒
	21. 合并两个有序链表	链表	力扣Hot 100	一刷20240921、二刷20242012 裸题，直接秒
	2. 两数相加	链表	力扣Hot 100	一刷20240921、二刷20241017 有大数运算、链表合并的影子，直接秒
	19. 删除链表的倒数第n个节点	链表	力扣Hot 100	一刷20240921、二刷20241017 一刷看题解，二刷直接秒
	24. 两两交换链表中的节点	链表	力扣Hot 100	一刷20241005、二刷20241017 裸题，直接秒
	25. k个一组翻转链表	链表	力扣Hot 100	一刷20241018 hard，反转链表的变形题，细节更多，需进一步熟练，建议隔2天3刷
	23. 合并k个升序链表	链表&归并	力扣Hot 100	一刷20241018、二刷20241023 hard，但是归并+链表裸题，二刷直接秒了，建议隔一个月三刷
	146. LRU	链表	力扣Hot 100	一刷20240915、二刷20240917、三刷20241018 三刷略微调试了一下过的，但是忘记put和get都需要moveToHead了，建议隔一个月四刷

树

序号	题目链接	标签	来源	备注
	94. 二叉树的中序遍历	树&递归	力扣Hot 100	一刷20240919、二刷202040921、三刷20241018 前中后序遍历无脑递归，直接秒，递归感不够的话只能多看多写
	104. 二叉树的最大深度	树&层序遍历	力扣Hot 100	一刷20240910、二刷20240921、三刷20240929、四刷20241018 前两次还有点磕绊，现在层序遍历直接秒
	226. 翻转二叉树	树&递归	力扣Hot 100	一刷20240929、二刷20241007、三刷20241018 对树，我一般是除了层序遍历都用递归，前两刷应该还看了题解，三刷直接秒，极致丝滑
	101. 对称二叉树	树&递归	力扣Hot 100	一刷20240929、二刷20241007、三刷20241018 一二刷应该看了题解，三刷直接秒，递归做多自然就推出来了，还是很丝滑
	543. 二叉树的直径	树&递归	力扣Hot 100	一刷20240930、二刷20241018 一刷看题解，二刷看了些提示，建议隔一个月三刷
	102. 二叉树的层序遍历	树&层序遍历	力扣Hot 100	一刷20240921 层序遍历裸题，直接秒
	108. 将有序数组转换为二叉搜索树	搜索树&递归&二分	力扣Hot 100	一刷20240930、二刷20241007、三刷20241018 二分+递归，三刷直接秒，比较丝滑
	98. 验证二叉搜索树	搜索树&递归	力扣Hot 100	一刷20240921、二刷20241019 二刷递归直接秒，很丝滑
	230. 二叉搜索树中第k小的元素	搜索树&递归	力扣Hot 100	一刷20240922 思路完全同上，直接秒
	199. 二叉树的右视图	树&层序遍历	力扣Hot 100	一刷20240930 层序遍历裸题，直接秒
	114. 二叉树展开为链表	树&模拟	力扣Hot 100	一刷202040930、二刷20241029 二刷看了思路，可以三刷
	236. 二叉树的最近公共祖先	树&递归	力扣Hot 100	一刷20241001、二刷20241019 二刷还是看了题解，对最近公共祖先的理解不到位，建议15天内三刷
	124. 二叉树中的最大路径和	树&递归	力扣Hot 100	一刷20241019 hard，类似二叉树直径，更复杂，建议15天内二刷

栈

序号	题目链接	标签	来源	备注
	20. 有效的括号	栈	力扣Hot 100	一刷20240919、二刷20241022 一刷看了思路，二刷直接秒
	155. 最小栈	栈	力扣Hot 100	一刷20240919、二刷20241029 二刷秒

回溯

序号	题目链接	标签	来源	备注
	46. 全排列	回溯	力扣Hot 100	一刷20241003、二刷20241029 二刷debug了，还是不太熟练
	131. 分割回文串	回溯	力扣Hot 100	一刷20241006、二刷20241029 二刷秒杀

二分

序号	题目链接	标签	来源	备注
	35. 搜索插入位置	二分	力扣Hot 100	一刷20240917、二刷20241029 二分模板题，直接秒
	34. 在排序数组中查找元素的第一个和最后一个位置	二分	力扣Hot 100	一刷20240921、二刷20241029 二刷秒杀
	33. 搜索旋转排序数组	二分&技巧	力扣Hot 100	一刷20241003、二刷20241029 二刷秒杀

双指针

序号	题目链接	标签	来源	备注
	27. 移除元素	双指针	字节高频题	一刷20241022 一刷看了思路，建议隔一个月二刷

双指针

序号	题目链接	标签	来源	备注
	215. 数组中第k个最大元素	堆	Hot 100	一刷20240922、二刷20240928、三刷20241031 根堆裸题，三刷秒杀
	347. 前k个高频元素	堆	Hot 100	一刷20240928 根堆裸题

DP

序号	题目链接	标签	来源	备注
	70. 爬楼梯	DP	力扣Hot 100	一刷20241007、二刷20241109 DP裸题， 二刷秒
	72. 编辑距离	二维DP	力扣Hot100&字节高频题	一刷20241008、二刷20241022 一二刷都看了思路，建议隔一个月三刷
	118. 杨辉三角	DP	力扣Hot 100	一刷20241007、二刷20241109 二刷秒，需注意边界处理
	198. 打家劫舍	DP	力扣Hot 100	一刷20241007、二刷20241109 DP裸题，二刷秒
	718. 最长重复子数组	DP	字节高频题	一刷20241023 一刷看了思路，建议隔一个月二刷

贪心

序号	题目链接	标签	来源	备注
	121. 买卖股票的最佳时机	贪心	力扣Hot100	一刷20240928、二刷20241031 二刷秒
	55. 跳跃游戏	贪心	力扣Hot 100	一刷20240928、二刷20241031 二刷想了想思路，做掉的

二、刷题记录

1. 两数相加——哈希——一刷

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

---

利用Hash表来同时存储值和下标，值作为key，下标作为value，考虑到可能存在相同的数， 所以value是List类型，如下

但是这样遗漏了一个有效条件，也就是只能存在两数之和相加， 所以我们直接在第一遍循环里做判断， 可以节省一部分空间， 即：

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        int[] res = new int[2];
        for (int i = 0; i < nums.length; i++) {
            int temp = target - nums[i];
            if (map.containsKey(temp)) {
                res[0] = i;
                res[1] = map.get(temp);
            } else {
                map.put(nums[i], i);
            }
        }
        return res;
    }
}

2. 两数相加——链表——二刷

https://leetcode.cn/problems/add-two-numbers/?envType=study-plan-v2&envId=top-100-liked

思路：分成几个部分，分别实现，然后拼接在一起

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 1. 定义头结点
        ListNode pre = new ListNode(-1);
        ListNode res = pre;

        // 2. 两个链表共长部分，相加
        int temp = 0;
        while (l1 != null && l2 != null) {
            int val = (l1.val + l2.val + temp) % 10;
            temp = (l1.val + l2.val + temp) / 10;
            ListNode n = new ListNode(val);
            pre.next = n;
            pre = pre.next;

            l1 = l1.next;
            l2 = l2.next;
        }

        // 3. 两个链表各自其他部分，相加
        while (l1 != null) {
            ListNode n1 = new ListNode((l1.val + temp) % 10);
            temp = (l1.val + temp) / 10;
            pre.next = n1;
            pre = pre.next;

            l1 = l1.next;
        }
        while (l2 != null) {
            ListNode n2 = new ListNode((l2.val + temp) % 10);
            temp = (l2.val + temp) / 10;
            pre.next = n2;
            pre = pre.next;

            l2 = l2.next;
        }

        // 4. temp处理
        if (temp != 0) {
            ListNode n3 = new ListNode(temp);
            pre.next = n3;
        }

        return res.next;
    }
}

二刷：更丝滑，直接秒杀， 类似大数+链表合并的题型

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, w next) { this.val = val; this.next = next; }
 * }
 */

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 解题思路，有点类似链表合并，注意最后进位的赋值
        ListNode l3 = new ListNode(-1);
        ListNode res = l3;

        int upNum = 0;
        while (l1 != null || l2 != null) {
            // 值处理
            int v1 = l1 == null ? 0 : l1.val;
            int v2 = l2 == null ? 0 : l2.val;

            int v = (v1 + v2 + upNum) % 10;
            upNum = (v1 + v2 + upNum) / 10;

            // 新节点声明
            ListNode newNode = new ListNode(v);
            l3.next = newNode;
            l3 = l3.next;

            // 节点遍历
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }

        // 进位处理
        if (upNum > 0) {
            ListNode newNode = new ListNode(upNum);
            l3.next = newNode;
        }
        return res.next;
    }
}

3. 无重复字符的最长子串——滑动窗口——三刷

模板

//外层循环扩展右边界，内层循环扩展左边界
for (int l = 0, r = 0 ; r < n ; r++) {
	//当前考虑的元素
	while (l <= r && check()) {//区间[left,right]不符合题意
        //扩展左边界
    }
    //区间[left,right]符合题意，统计相关信息
}

一刷代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        //滑动窗口
        char[] ss = s.toCharArray();
        Set<Character> set = new HashSet<>();//去重
        int res = 0;//结果
        for(int left = 0, right = 0; right < s.length(); right++) {//每一轮右端点都扩一个。
            char ch = ss[right];//right指向的元素，也是当前要考虑的元素
            while(set.contains(ch)) {//set中有ch，则缩短左边界，同时从set集合出元素
                set.remove(ss[left]);
                left++;
            }
            set.add(ss[right]);//别忘。将当前元素加入。
            res = Math.max(res, right - left + 1);//计算当前不重复子串的长度。
        }
        return res;
    }
}

二刷代码（20241006）：

class Solution {
    public int lengthOfLongestSubstring(String s) {

        // 解题思路：指针滑动，不重复则加入， 重复则去掉第一个元素， 一直去，直到不重复为止
        int res = 0;
        char[] ss = s.toCharArray();
        int len = ss.length;
        Set<Character> set = new HashSet<>();

        for (int left = 0, right = 0; right < len; right++) {
            // 当前要处理的值
            char c = ss[right];
            
            // left滑动的条件
            while (left < right && set.contains(c)) {
                set.remove(ss[left]);
                left++;
            }
            set.add(c);

            res = Math.max(res, right - left + 1);
        }
        return res;
    }
}

三刷代码：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        if (len == 0) {
            return 0;
        }

        char[] ss = s.toCharArray();
        Set<Character> isContain = new HashSet<>();

        int res = 0;

        for (int l = 0, r = 0; r < len; r++) {
            char c = ss[r];
            while (l <= r && isContain.contains(c)) {
                isContain.remove(ss[l]);
                l++;
            }
            res = Math.max(res, r - l + 1);
            isContain.add(c);
        }
        return res;
    }
}

5.最长回文串——数组

https://leetcode.cn/problems/longest-palindromic-substring/description/?envType=study-plan-v2&envId=top-100-liked

给你一个字符串 s，找到 s 中最长的回文串。

示例 1：
输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。

示例 2：
输入：s = “cbbd”
输出：“bb”

提示：
1 <= s.length <= 1000
s 仅由数字和英文字母组成

思路分析：脑海中的第一解法一定是纯暴力解法，即双重for循环遍历，i>j，第三重循环里对从i到j的数据判断，是否符合回文串，记录最大值即可
时间复杂度：On^3

但是这样显然不优雅， 而且没有用到回文串本身的特性来帮助解题

第二种思路是：中心扩散法
即以某个下标为中心，向两侧扩散，记录符合最大长度的回文串即可
这里需要注意的是，回文串的判断分两部分，第一部分是中心相同字符的数量，第二部分是非中心两侧相等字符的数量， 需要拆开来算

class Solution {
    public static String longestPalindrome(String s) {

        // 入参校验
        if (s == null || s.length() == 0) {
            return null;
        }

        // 回文串遍历
        int len = s.length();
        int maxLeftIndex = 0;
        int maxRightIndex = 0;
        for (int i = 0; i < len; i++) {

            // 声明左右遍历下标
            int leftIndex = i;
            int rightIndex = i;

            // 中心区域处理-左遍历
            for (int j = leftIndex; j >= 0; j--) {
                if (s.charAt(leftIndex) != s.charAt(j)) {
                    break;
                }
                leftIndex = j;
            }
            // 中心区域处理-右遍历
            for (int j = rightIndex; j < len; j++) {
                if (s.charAt(rightIndex) != s.charAt(j)) {
                    break;
                }
                rightIndex = j;
            }

            // 回文区域处理
            while (s.charAt(leftIndex) == s.charAt(rightIndex)) {
                // 存储最大回文串下标
                if (rightIndex - leftIndex > maxRightIndex - maxLeftIndex) {
                    maxLeftIndex = leftIndex;
                    maxRightIndex = rightIndex;
                }

                leftIndex -= 1;
                rightIndex += 1;
                // 终止条件
                if (leftIndex < 0 || rightIndex >= len) {
                    break;
                }
            }

        }
        return s.substring(maxLeftIndex, maxRightIndex + 1);
    }
}

二刷，代码更得心应手：

class Solution {
    public String longestPalindrome(String s) {
        String resStr = "";
        int resLen = 0;
        // for循环，对每个节点分为中心区域和回文区域，中心区域判断是否相等（偶数回文串）

        int len = s.length();
        char ss[] = s.toCharArray();
        for (int i = 0; i < len; i++) {
            
            // 中间区域处理
            int left = i, right = i;
            char c = ss[i];
            while (left >= 0 && ss[left] == c) {
                left--;
            }
            while (right < len && ss[right] == c) {
                right++;
            }

            // 回文区域处理
            while (left >= 0 && right < len && ss[left] == ss[right]) {
                left--; right++;
            }

            // 结果处理
            if (right - left + 1 > resLen) {
                resLen = right - left + 1;
                resStr = s.substring(left + 1, right);
            }
        }
        return resStr;
    }
}

三刷：直接秒了

class Solution {
    public String longestPalindrome(String s) {
        // 中心扩散法，主注意处理中心区域和回文区域
        int len = s.length();
        if (len <= 1) {
            return s;
        }

        char[] cc = s.toCharArray();

        int resLen = 1;
        String resStr = s.substring(0, 1);

        for (int i = 0; i < len; i++) {
            int left = i, right = i;
            int c = cc[i];
            while (left >= 0 && cc[left] == c) {
                left--;
            }
            while (right < len && cc[right] == c) {
                right++;
            }

            while (left >= 0 && right < len && cc[left] == cc[right]) {
                left--;
                right++;
            }
            if (resLen < right - left - 1) {
                resLen = right - left - 1;
                resStr = s.substring(left + 1, right);
            }
        }
        return resStr;
    }
}

11. 盛水最多的容器——双指针——二刷

https://leetcode.cn/problems/container-with-most-water/submissions/570462070/?envType=study-plan-v2&envId=top-100-liked

解题思路：见代码，也可以参考力扣题解

class Solution {
    public int maxArea(int[] height) {
        // 核心思想：假设x位于最左侧， y位于最右侧， 储水面积取决于较短的柱子长度*二者距离， 假设固定较短的柱子x，y向左移动，那么储水面积一定没有原来大， 但是假设固定住较长的柱子y，x向右移动，那么储水面积可能比原来大，也可能比原来小， 每一步都这么处理，最后就能求出最大的储水面积
        int maxArea = -1;
        int i = 0, j = height.length - 1;
        while (i < j) {
            maxArea = Math.max(maxArea, (j - i) * Math.min(height[i], height[j]));
            if (height[i] > height[j]) {
                j--;
            } else {
                i++;
            }
        }
        return maxArea;
    }
}

二刷：贪心+双指针，秒了

class Solution {
    public int maxArea(int[] height) {
        // 遍历方向有两个，一是按照板子长度，二是按照坐标间隔，板子长度无法预知，只能从长倒短遍历坐标间隔
        // 然后，每次缩短长度，可以缩短左边一次，也可以缩短右边一次，取决于二者之间的最大值。
        // 贪心的原因，假如左边板子长度小于右边板子长度， 如果选择固定左边板子，则剩余所有遍历，高度一定不会高于左边板子，而如果固定右边板子，则剩余所有遍历，高度一定不会高于右边板子， 右边板子高于左边，所以保留右边

        int len = height.length;
        int i = 0, j = len - 1;

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

        return res;
    }
}

15. 三数之和——数组——二刷

https://leetcode.cn/problems/3sum/?envType=study-plan-v2&envId=top-100-liked

一刷，时间：20241006

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {

        Arrays.sort(nums);

        // 1. 保证下标没有重复（i < j < k）
        // 2. 保证数字集合不重复（Set）
        
        List<List<Integer>> res = new ArrayList<>();
        Set<List<Integer>> isRepeat = new HashSet<>();
        Map<Integer, List<Integer>> isContain = new HashMap<>();

        int len = nums.length;
        for (int i = 0; i < len; i++) {
            List list;
            if (isContain.containsKey(nums[i])) {
                list =isContain.get(nums[i]);
            } else {
                list = new ArrayList<>();
            }
            list.add(i);
            isContain.put(nums[i], list);
        }

        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                int sum = nums[i] + nums[j];
                if (isContain.containsKey(-sum) && isContain.get(-sum).getLast() > j) {
                    List<Integer> cur = new ArrayList<>(Arrays.asList(nums[i], nums[j], -sum));
                    if (!isRepeat.contains(cur)) {
                        res.add(cur);
                        isRepeat.add(cur);
                    }
                }
            }
        }

        return res;
    }
}

二刷时间：20241015

排序那里处理的还是有点问题，其他的比较流利
其实更优解，是初始排序， 这样时间复杂度更低

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // 核心思路，固定一个，另外两个按照两数之和来求，保证ijk不重复

        List<List<Integer>> res = new ArrayList<>();
        Set<List<Integer>> isContain = new HashSet<>();

        int len = nums.length;
        for (int i = 0; i < len; i++) {
            int n1 = nums[i];
            Set<Integer> set = new HashSet<>();
            for (int j = i + 1; j < len; j++) {
                int n2 = nums[j];
                int n3 = 0 - n1 - n2;
                if (set.contains(n3)) {
                    int[] list = new int[] {n1, n2, n3};
                    Arrays.sort(list);

                    List<Integer> tempList = new ArrayList<>();
                    tempList.add(list[0]);  tempList.add(list[1]); tempList.add(list[2]);
                    if (!isContain.contains(tempList)) {
                        res.add(tempList);
                        isContain.add(tempList);
                    }

                } else {
                    set.add(n2);
                }
            }
        }
        return res;
    }
}

19. 删除链表的倒数第n个节点——链表

https://leetcode.cn/problems/remove-nth-node-from-end-of-list/?envType=study-plan-v2&envId=top-100-liked

1. 定义哑结点
2. 注意边界场景，最好先根据极限场景手推一遍

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 1. 哑结点
        ListNode pre = new ListNode(-1);
        pre.next = head;

        // 2. second节点，先走n-1步（n-1是根据极限情况推出来的）
        ListNode first = pre, second = head;
        for (int i = 0; i < n-1; i++) {
            second = second.next;
        }
        
        // 3. First和second同时走，直到second遍历到最后一位
        while (second.next != null) {
            second = second.next;
            first = first.next;
        }
        
        // 4. 直接删除对应节点即可
        first.next = first.next.next;
        return pre.next;
    }
}

二刷：直接秒，这时已经做了不少链表题了，写的很舒服

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 这是预处理链表长度的解法， 还有一种是双指针，指针2先走n步，指针2到尾部时，指针1刚好到倒数第n个位置，删除即可
        if (head == null) {
            return null;
        }

        // 1. 求长度
        int len = 0;
        ListNode h1 = head;
        while (h1 != null) {
            len++;
            h1 = h1.next;
        }

        // 2. 删除：定义哑结点，删除后直接break即可。
        ListNode n1 = new ListNode(-1), n2 = head;
        n1.next = head;
        ListNode res = n1;

        int target = len - n + 1;
        int cur = 1;
        while (n2 != null) {
            if (cur == target) {
                n1.next = n2.next;
                n2.next = null;
                break;
            }
            n1 = n1.next;
            n2 = n2.next;
            cur++;
        }

        return res.next;

    }
}

20. 有效的括号——栈——二刷

https://leetcode.cn/problems/valid-parentheses/?envType=study-plan-v2&envId=top-100-liked

解题思路：栈进左括号， 如果遇到右括号，就依次出栈， 如果中途栈空，或不匹配，或还剩右括号，都属于false

class Solution {
    public boolean isValid(String s) {
        List<Character> stack = new LinkedList<Character>();
        Map<Character, Character> map = new HashMap<Character, Character>();
        map.put('(', ')');
        map.put('[', ']');
        map.put('{', '}');

        char[] ss = s.toCharArray();
        for (char c : ss) {
            if (map.containsKey(c)) {
                // 左括号入栈
                stack.addFirst(c);
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                char rc = stack.removeFirst();
                if (map.get(rc) != c) {
                    return false;
                }
            }
        }
        
        return stack.isEmpty();


    }
} 

二刷：直接秒

class Solution {
    public boolean isValid(String s) {
        // 思路 ：如果是左括号，全部存入栈，如果是右括号，从栈中取一个数据，如果不匹配，或栈里有数据，false， 最后如果栈没有被清空，false
        List<Character> stack = new LinkedList<>();
        Map<Character, Character> map = new HashMap<>();
        map.put('(', ')');
        map.put('[', ']');
        map.put('{', '}');

        char[] cc = s.toCharArray();
        for (Character c : cc) {
            if (c == '(' || c == '[' || c == '{') {
                stack.addFirst(c);
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                Character stackChar = stack.removeFirst();
                if (c != map.get(stackChar)) {
                    return false;
                }
            }
        }
        if (!stack.isEmpty()) {
            return false;
        }
        return true;
    }
}

21. 合并两个有序链表——链表-二刷

https://leetcode.cn/problems/merge-two-sorted-lists/description/?envType=study-plan-v2&envId=top-100-liked

核心思路：
第一步，构造一个哑结点，从头声明结果链表，循环两个链表，哪个小就放入哪个
第二步，如果某个循环完了，另一个还没完，那直接把另一个剩下的节点，接到结果链表后面即可。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode pre = new ListNode(-1);
        ListNode res = pre;

        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                pre.next = list1;
                list1 = list1.next;
            } else {
                pre.next = list2;
                list2 = list2.next;
            }
            pre = pre.next;
        }

        if (list1 != null) {
            pre.next = list1;
        } else {
            pre.next = list2;
        }

        return res.next;
    }
}

二刷，秒了

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null && list2 == null) {
            return null;
        }

        ListNode newList = new ListNode(-1);
        ListNode res = newList;

        // 两个链表都有值的之后，需要比较
        while (list1 != null && list2 != null) {
            int val = -1;
            if (list1.val < list2.val) {
                val = list1.val;
                list1 = list1.next;
            } else {
                val = list2.val;
                list2 = list2.next;
            }
            
            ListNode newNode = new ListNode(val);
            newList.next = newNode;
            newList = newList.next;
        }

        // 两个链表各自剩下的部分
        if (list1 != null) {
            newList.next = list1;
        }
        if (list2 != null) {
            newList.next = list2;
        }

        return res.next;
    }
}

22. 括号生成——DFS&回溯*

https://leetcode.cn/problems/generate-parentheses/?envType=study-plan-v2&envId=top-100-liked

解题思路：核心限制是， 某个位置如果写入右括号，则必须满足该位置之前的左括号数量 > 右括号数量， 用两个变量做标记即可。

class Solution {
    // 全局变量声明
    int maxl = 0, maxr = 0;
    String s = "";
    List<String> res = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        dfs(n);
        return res;
    }

    public void dfs (int n) {
        // 终值条件
        if (maxl == n && maxr == n) {
            res.add(new String(s));
            return;
        }
  
        // 左括号
        if (maxl < n) {
            s += "(";
            maxl += 1;
            dfs(n);
            s = s.substring(0, s.length() - 1);
            maxl -= 1;
        }

        // 右括号
        if (maxr < n && maxr < maxl) {
            s += ")";
            maxr += 1;
            dfs(n);
            s = s.substring(0, s.length() - 1);
            maxr -= 1;
        }

    }
}

23. 合并k个升序链表——链表&归并——二刷

https://leetcode.cn/problems/merge-k-sorted-lists/?envType=study-plan-v2&envId=top-100-liked

解题思路：见代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // 归并 + 链表合并的裸题 
        // 暴力合并，时间复杂度 k * kn，其中，k是每轮遍历的个数，kn是节点个数
        // 归并合并，时间复杂度 logk * kn
        // 整体思路就是两两归并，最后返回一个有序的链表
        if (lists.length == 0) {
            return null;
        }

        return merge(lists, 0, lists.length - 1);
    }

    public ListNode merge(ListNode[] lists, int l, int r) {
        // 递归抽象不好理解， 这里可以思考如果List中只有1个或2个或3个链表，即只递归0次或1次，整体怎么运转和设计。
        if (l == r) {
            return lists[l];
        }
        if (l > r) {
            return null;
        }

        int mid = (l + r) >> 1;
        ListNode n1 = merge(lists, l, mid);
        ListNode n2 = merge(lists, mid + 1, r);
        return mergeTwoLink(n1, n2);
    }

    public ListNode mergeTwoLink(ListNode n1, ListNode n2) {
        if (n1 == null && n2 == null) {
            return null;
        }

        ListNode n3 = new ListNode(-1);
        ListNode res = n3;
        while (n1 != null && n2 != null) {
            int v = 0;
            if (n1.val < n2.val) {
                v = n1.val;
                n1 = n1.next;
            } else {
                v = n2.val;
                n2 = n2.next;
            }

            ListNode newNode = new ListNode(v);
            n3.next = newNode;
            n3 = n3.next;
        }

        if (n1 != null) {
            n3.next = n1;
        }
        if (n2 != null) {
            n3.next = n2;
        }

        return res.next;
    }

}

二刷，直接秒了，丝滑

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // 归并 + 合并，时间复杂度 m*n*logk
        if (lists.length == 0) {
            return null;
        }

        return merge(lists, 0, lists.length - 1);
    }
    
    public ListNode merge(ListNode[] lists, int l, int r) {
        if (l > r) {
            return null;
        }
        if (l == r) {
            return lists[l];
        }

        int mid = (l + r) >> 1;
        ListNode n1 = merge(lists, l, mid);
        ListNode n2 = merge(lists, mid + 1, r);
        return mergeTwoList(n1, n2);
    }

    public ListNode mergeTwoList(ListNode n1, ListNode n2) {
        if (n1 == null && n2 == null) {
            return null;
        }
        ListNode n3 = new ListNode(-1);
        ListNode res = n3;
        while (n1 != null && n2 != null) {
            int val = 0;
            if (n1.val < n2.val) {
                val = n1.val;
                n1 = n1.next;
            } else {
                val = n2.val;
                n2 = n2.next;
            }
            ListNode newNode = new ListNode(val);
            n3. next = newNode;
            n3 = n3.next;
        }
        if (n1 != null) {
            n3.next = n1;
        }
        if (n2 != null) {
            n3.next = n2;
        }
        return res.next;
    }
}

24. 两两交换链表中的节点——链表——二刷

https://leetcode.cn/problems/s+wap-nodes-in-pairs/?envType=study-plan-v2&envId=top-100-liked

解题思路：定义哑结点，然后置换即可。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode pre = new ListNode(-1);
        pre.next = head;

        ListNode res = pre;

        while (pre.next != null && pre.next.next != null) {
            ListNode n1 = pre, n2 = pre.next, n3 = pre.next.next;\

            n2.next = n3.next;
            n3.next = n2;
            n1.next = n3;

            pre = pre.next.next;
        }

        return res.next;
    }
}

二刷：完全不用定义哑结点，直接干，秒杀题，比较丝滑

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode n1 = head, n2 = head.next;
        while (n2 != null) {
            int t = n1.val;
            n1.val = n2.val;
            n2.val = t;

            if (n2.next != null) {
                n1 = n1.next.next;
                n2 = n2.next.next;
            } else {
                break;
            }
        }

        return head;
    }
}

25. k个一组翻转链表——链表*——一刷

https://leetcode.cn/problems/reverse-nodes-in-k-group/?envType=study-plan-v2&envId=top-100-liked

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 解题思路：
        // 1. 保存每一组的前缀节点
        // 2. 循环获取每一组的范围，如果遍历到链表末尾，则直接break
        // 3. 保存下一组的头节点， 并切断与当前组的联系
        // 4. 反转当前组， 然后当前组的头尾节点分别重新连接进链表
        // 5. 更新前缀节点
        if (head == null || head.next == null || k == 1) {
            return head;
        }

        // 哑结点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        // 每一组的前缀节点
        ListNode preGroup = dummy;
        while(true) {
            // 每组的起始节点和结束节点
            ListNode start = preGroup.next;
            ListNode end = start;
            for (int i = 0; i < k - 1 && end != null; i++) {
                end = end.next;
            }

            // 终止条件
            if (end == null) {
                break;
            }

            // 记录下一组的开始节点，并断裂与下一组的联系
            ListNode nextStart = end.next;
            end.next = null;

            // 反转当前数组
            ListNode curGroupEnd = reserve(start);

            // 连接
            preGroup.next = curGroupEnd;
            start.next = nextStart;
            
            // 更新前缀节点
            preGroup = start;
        }
        return dummy.next;
    }
    
    public ListNode reserve(ListNode head) {
        ListNode n1 = null, n2 = head, n3 = head.next;
        while (n2 != null) {
            n2.next = n1;
            if (n3 == null) {
                break;
            }
            n1 = n2;
            n2 = n3;
            n3 = n3.next;
        }
        return n2;
    } 
}

27. 移除元素——双指针——一刷

https://leetcode.cn/problems/remove-element/

class Solution {
    public int removeElement(int[] nums, int val) {
        // 解题思路：双指针，确保左指针左侧全部不等于value，最后返回长度即可
        int len = nums.length;
        if (len == 0) {
            return 0;
        }

        int i = 0, j = 0;
        while (i <= j && j < len) {
            if (nums[j] != val) {
                nums[i] = nums[j];
                i++;
            }
            j++;
        }

        return i;
    }
}

33. 搜索旋转排序数组——二分*

解题思路：对于二分出来的左子数组和右子数组， 先判断出哪个数组是连续的（另一个数组必然不连续），然后在连续的数组内，根据边界条件判断目标元素是否在其中，如果不在其中， 那无脑遍历另一半数组， 一直继续即可。

注意：

1. 边界条件的处理：nums[0] <= nums[mid]，为什么要加等于号， 如果左半区间只有一个数组，那么是等于的， 一个数组理论上也是有序的。
2. target < nums[mid] && target >= nums[0]：对于左半区间的判断，为什么要判断开始和结束，而不是只判断mid， 因为有可能是翻转数组，比如target是1， 数组是4567123，那么nums[mid]也是小于target的， 但是target并不在左半区间

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

        int res = -1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (nums[mid] == target) {
                return mid;
            }

            if (nums[0] <= nums[mid]) {
                if (target < nums[mid] && target >= nums[0]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if (target <= nums[r] && target > nums[mid]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return res;
    }
}

二刷：直接秒杀，思路理清很简单

class Solution {
    public int search(int[] nums, int target) {
        // 思路：数组二分， 必定一段有序一段无序， 因为转折点只有一个；  这样只需要判断有序的那边，是不是存在target，如果不存在，无脑转另一边，如果存在，则继续缩减即可。
        int len = nums.length;
        int l = 0, r = len - 1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (target == nums[mid]) {
                return mid;
            }
            // 这里要注意，等于说明只有一个元素，只有一个元素也算有序
            if (nums[l] <= nums[mid]) {
                if (target <= nums[mid] && target >= nums[l]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if (target >= nums[mid] && target <= nums[r]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }
}

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

https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/solutions/504484/zai-pai-xu-shu-zu-zhong-cha-zhao-yuan-su-de-di-3-4/?envType=study-plan-v2&envId=top-100-liked

思路：两次二分， 第一次是大于等于， 第二次是小于等于， 找左边界和右边界，当等于的时候， 赋值

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int n = nums.length;
        int[] res = new int[2];
        int left = -1, right = -1;

        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (nums[mid] >= target) {
                if (nums[mid] == target) {
                    left = mid;
                }
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }


        l = 0; r = n - 1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (nums[mid] <= target) {
                if (nums[mid] == target) {
                    right = mid;
                }
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        res[0] = left;
        res[1] = right;
        return res;
        
    }
}

二刷：比较丝滑

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] res = new int[] {-1, -1};
        // 这里就是先偏向左边还是先偏向右边即可
        int len = nums.length;
        int l1 = 0, r1 = len - 1;
        while (l1 <= r1) {
            int mid1 = (l1 + r1) >> 1;
            if (target <= nums[mid1]) {
                if (target == nums[mid1]) {
                    res[0] = mid1;
                }
                r1 = mid1 - 1;
            } else {
                l1 = mid1 + 1;
            }
        }
        
        int l2 = 0, r2 = len - 1;
        while (l2 <= r2) {
            int mid2 = (l2 + r2) >> 1;
            if (target >= nums[mid2]) {
                if (target == nums[mid2]) {
                    res[1] = mid2;
                }
                l2 = mid2 + 1;
            } else {
                r2 = mid2 - 1;
            }
        }

        return res;
    }
}

35. 搜索插入位置——二分——二刷

https://leetcode.cn/problems/search-insert-position/description/?envType=study-plan-v2&envId=top-100-liked

class Solution {
    public int searchInsert(int[] nums, int target) {
        int l = 0, r = nums.length-1;
        while(l <= r) {
            int mid = (l + r) >> 1;
            if (nums[mid] == target) {
                return mid;
            }

            if (nums[mid] > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

41. 缺失的第一个正数——数组——二刷

https://leetcode.cn/problems/first-missing-positive/?envType=study-plan-v2&envId=top-100-liked

思想：替换，因为缺失的正数一定在1-n之间，所以直接替换，让下标=值，然后遍历， 第一个值不等于下标的， 一定是数组中没有的最小正整数

class Solution {
    public int firstMissingPositive(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            while (nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i]) {
                int t = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = t;
            }
        }
        for (int i = 0; i < len; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return len+1;
    }
}

二刷，卡了两个用例，改了改代码过了，整体看更娴熟了

class Solution {
    public int firstMissingPositive(int[] nums) {
        int len = nums.length;

        for (int i = 0; i < len; i++) {
            // while循环放置位置
            while (nums[i] != i + 1 && nums[i] > 0 && nums[i] < len) {
                // 终止条件， 相同就别换了， 换就死循环
                if (nums[i] == nums[nums[i] - 1]) {
                    break;
                }
                swap(nums, i, nums[i] - 1);
            }
        }

        for (int i = 0; i < len; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return len + 1;
    }

    public void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

45. 跳跃游戏二——贪心*

https://leetcode.cn/problems/jump-game-ii/?envType=study-plan-v2&envId=top-100-liked

解题思路：见注释，很巧妙

class Solution {
    public int jump(int[] nums) {
        int len = nums.length;
        // 特判
        if (len == 1) {
            return 0;
        }
        int res = 0; 
        int tempEndPos = 0;   
        int maxPos = 0;
        for (int i = 0; i < len; i++) {
            // 贪心策略，获取每一步的最优解
            if (i + nums[i] > maxPos) {
                maxPos = i + nums[i];
            }
            // 当i遍历到上一步的最优解后， 把值更新到下一步的最优解
            if (i == tempEndPos) {
                res++;
                tempEndPos = maxPos;

                // 判定
                if (maxPos >= len - 1) {
                    return res;
                }
            }
        }
        return res;
    }
}

46. 全排列——回溯&DFS——二刷

地址：https://leetcode.cn/problems/permutations/?envType=study-plan-v2&envId=top-100-liked

解题思路：第一个位置有n种变化，第二个位置有n-1种变化… 以此类推，用数组标记变换即可。

class Solution {
    int[] flag;
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();

        List<Integer> cur = new ArrayList<Integer>();
        for (int i = 0; i < nums.length; i++) {
            cur.add(nums[i]);
        }

        dfs(res, cur, 0, nums.length); 

        return res;
    }

    public void dfs(List<List<Integer>> res, List<Integer> cur, Integer first, Integer len) {
        if (first == len) {
            // 这里要注意， 一定要重新声明地址， 否则更改的是同一个位置
            res.add(new ArrayList<Integer>(cur));
        }

        for (int i = first; i < len; i++) {
            swap(cur, i, first);
            dfs(res, cur, first + 1, len);
            swap(cur, i, first);
        }
    }

    public void swap(List<Integer> cur, Integer i, Integer j) {
        int t = cur.get(i);
        cur.set(i, cur.get(j));
        cur.set(j, t);
    }
}

二刷：debug了，整体还是有点不熟练

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    Set<Integer> flag = new HashSet<>();
    public List<List<Integer>> permute(int[] nums) {
        int len = nums.length;
        List<Integer> curList = new ArrayList<>();

        dfs(curList, nums, len);

        return res;
    }

    public void dfs(List<Integer> curList, int[] nums, int len) {
        int curLen = curList.size();

        if (curLen == len) {
            res.add(new ArrayList<>(curList));
            return;
        }
        for (int i = 0; i < len; i++) {
            int t = nums[i];
            if (!flag.contains(t)) {
                curList.add(t);
                flag.add(t);

                dfs(curList, nums, len);
                
                curList.remove(curLen);
                flag.remove(t);
            }
        }
    }
}

48. 旋转图像——矩阵——一刷

https://leetcode.cn/problems/rotate-image/?envType=study-plan-v2&envId=top-100-liked

解题思路：见代码

class Solution {
    public void rotate(int[][] matrix) {
        // 思路：观察可得，旋转90度后，第1行的数据，会被作为最后一列， 此时考虑对角线翻折，但是如果用对角线，第i行的第一个数据，会被放在n-i列的最后一位，但是旋转后，应该是放在第一位的， 那此时，再对矩阵进行水平翻转，即可。
        int len = matrix.length;

        // 对角线翻转
        for (int i = 0; i < len; i++) {
             for (int j = 0; j < i; j++) {
                int t = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = t;
            }
        }

        // 垂直翻转
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len / 2; j++) {
                int t = matrix[i][j];
                matrix[i][j] = matrix[i][len - j - 1];
                matrix[i][len - j - 1] = t;
            }
        }
    }
}

49. 字母异位词分组——哈希——二刷

https://leetcode.cn/problems/group-anagrams/?envType=study-plan-v2&envId=top-100-liked

解题思路：水题直接秒

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

        for (String str : strs) {
            // 排序确保唯一性
            char[] ss = str.toCharArray();
            Arrays.sort(ss);
            String newStr = new String(ss);

            List list;
            if (!map.containsKey(newStr)) {
                list = new ArrayList<String>();
            } else {
                list = map.get(newStr);
            }
            list.add(str);

            map.put(newStr, list);
        }

        for (List<String> strList : map.values()) {
            res.add(strList);
        }
        return res;
    }
}

二刷：

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 核心思路：排序后的String做key，分组即可
        Map<String, List<String>> map = new HashMap<>();
        
        for (String str : strs) {
            char[] cc = str.toCharArray();
            Arrays.sort(cc);
            String orderStr = new String(cc);
            if (map.containsKey(orderStr)) {
                List<String> list = map.get(orderStr);
                list.add(str);
                map.put(orderStr, list);
            } else {
                List<String> list = new ArrayList<>();
                list.add(str);
                map.put(orderStr, list);
            }
        }

        List<List<String>> res = new ArrayList<>();
        for (List<String> value : map.values()) {
            res.add(value);
        }

        return res;
    }
}

53. 最大子数组和——贪心

https://leetcode.cn/problems/maximum-subarray/solutions/228009/zui-da-zi-xu-he-by-leetcode-solution/?envType=study-plan-v2&envId=top-100-liked

思想：贪心，如果子数组和大于0就继续贪，如果小于0 ，就从0开始继续贪

class Solution {
    public int maxSubArray(int[] nums) {
        int maxNums = -100000;
        int tMaxNums = 0;
        for (int i = 0; i < nums.length; i++) {
            tMaxNums += nums[i];
            if (tMaxNums > maxNums) {
                maxNums = tMaxNums;
            }
            if (tMaxNums < 0) {
                tMaxNums = 0;
            }
        }
        return maxNums;
    }
}

二刷：细节处理要注意

class Solution {
    public int maxSubArray(int[] nums) {
        int res = -Integer.MAX_VALUE;
        int tmp = 0;
        for (int i = 0; i < nums.length; i++) {
            tmp += nums[i];
            res = Math.max(res, tmp);
            // 顺序注意一下
            if (tmp < 0) {
                tmp = 0;
            }
        }
        return res;
    }
}

54. 螺旋矩阵——矩阵——二刷

https://leetcode.cn/problems/spiral-matrix/?envType=study-plan-v2&envId=top-100-liked

解题思路：硬写怎么都能写出来， 但是如果有限时间场景， 就要有良好的设计和结构， 如下所示， 定义上下左右四个变量， 每个边遍历一次就缩减一次，直到上下边界相交或左右边界相交。

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        int m = matrix.length, n = matrix[0].length;
        int left = 0, right = n - 1, top = 0, bottom = m - 1;

        while (left <= right && top <= bottom) {
            for (int i = left; i <= right; i++) {
                res.add(matrix[top][i]);
            }
            top++;

            for (int i = top; i <= bottom; i++) {
                res.add(matrix[i][right]);
            }
            right--;

            // 为什么这两个要if，上面两个不要if，因为上面两个在while处判断过了
            if (top <= bottom) {
                for (int i = right; i >= left; i--) {
                    res.add(matrix[bottom][i]);
                }
                bottom--;
            }

            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    res.add(matrix[i][left]);
                }
                left++;
            }
        }

        return res;
    }
}

二刷，基本算秒杀，但是调试了一下，做了很多题脑力跟不上了， 正常应该能解出的， 还可以。

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        // 核心是良好的代码结构
        int lenx = matrix.length, leny = matrix[0].length;
        int top = 0, bottom = lenx - 1, left = 0, right = leny - 1;

        List<Integer> res = new ArrayList<>();

        while (left <= right && top <= bottom) {
            for (int i = left; i <= right; i++) {
                res.add(matrix[top][i]);
            }
            top++;

            for (int i = top; i <= bottom; i++) {
                res.add(matrix[i][right]);
            }
            right--;

            if (top <= bottom) {
                for (int i = right; i >= left; i--) {
                    res.add(matrix[bottom][i]);
                }
                bottom--;
            }

            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    res.add(matrix[i][left]);
                }
                left++;
            }
        }
        return res;

    }
}

55. 跳跃游戏——贪心——二刷

https://leetcode.cn/problems/jump-game/?envType=study-plan-v2&envId=top-100-liked

贪心核心思路：当前最优策略，然后对比新一轮的最优策略，是否优于之前记录的， 如果是，则替换

本题思路：第i轮最优策略， 在于前i轮能走出的最大步数； 同时， 如果i的遍历，超过了能走的最大步数，说明不可达，返回false； 如果最大步数，大于等于数组长度， 说明可达，返回true

class Solution {
    public boolean canJump(int[] nums) {
        int len = nums.length;
        // 记录前i轮能走出的最大步数
        int curLen = 0;
        for (int i = 0; i < len; i++) {
            // 如果i > 能走出的最大步数，说明不可达
            if (i > curLen) {
                return false;
            }
            // 对比每一轮的 步长，如果超过当前最大步数，则说明是更优解， 替换
            if (i + nums[i] > curLen) {
                curLen = i + nums[i];
            }
            // 可达场景
            if (curLen >= len - 1) {
                return true;
            }
        }
        return false;
    }
}

二刷，想了想思路，秒掉的

class Solution {
    public boolean canJump(int[] nums) {
        // 记录一个目前为止能走到的最大步数，即可
        int len = nums.length;
        int maxNum = 0;
        for (int i = 0; i < len; i++) {
            // 断路
            if (maxNum < i) {
                return false;
            }
            // 记录最大值
            maxNum = Math.max(i + nums[i], maxNum);
            // 可通过
            if (maxNum >= len - 1) {
                return true;
            }
        }
        return true;
    }
}

56. 合并区间——数组*——二刷

https://leetcode.cn/problems/merge-intervals/?envType=study-plan-v2&envId=top-100-liked

解题思路：二维数组的遍历，感觉思路不难，更难的是二维数组的声明，自定义排序这些， 因为平时Idea写代码，直接copy了，很少能背下来

class Solution {
    public int[][] merge(int[][] intervals) {
        // 1. 排序
        Arrays.sort(intervals, Comparator.comparingInt(interval -> interval[0]));
        int n = intervals.length;
        int i = 0;
        List<int[]> ranges = new ArrayList<>(n);

        // 2. 遍历 + 合并
        while(i < n) {
            int start = intervals[i][0], end = intervals[i][1];
            int j = i + 1;
            while (j < n && end >= intervals[j][0]) {
                end = Math.max(end, intervals[j][1]);
                j++;
            }
            ranges.add(new int[] {start, end});
            i = j;
        }

        // 3. 动态数组转二维数组
        int resLen = ranges.size();
        int[][] res = new int[resLen][2];
        for (int t = 0; t < resLen; t++) {
            res[t] = ranges.get(t);
        }
        return res;
    }
}

二刷，细节处理要注意，右区间的边界赋值要注意。 可以定义一个start和end，动态替换

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(interval -> interval[0]));
        List<int[]> list = new ArrayList<>(); 

        int len = intervals.length;
        int i = 0;
        while (i < len) {
            int start = intervals[i][0], end = intervals[i][1];
            int j = i + 1;
            while (j < len) {
                if (end >= intervals[j][0]) {
                    // 核心代码，两个区间合并后，右区间值取决于两个区间中，右区间的较大者
                    end = Math.max(end, intervals[j][1]);
                    j++;
                } else {
                    break;
                }
            }

            int[] tmpNums = new int[] {start, end};
            list.add(tmpNums);

            i = j;
        }
        int[][] res = new int[list.size()][2];
        for (i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
}

70. 爬楼梯——DP——二刷

https://leetcode.cn/problems/climbing-stairs/submissions/570587960/?envType=study-plan-v2&envId=top-100-liked

解题思路：基础动态规划

class Solution {
    public int climbStairs(int n) {
        // 转移方程： fn = fn-1 + fn-2;
        // 边界条件： f0 = 1； f1 = 1； f2 = 2

        int p = 0, q = 0, r = 1;
        for (int i = 0; i < n; i++) {
            p = q;   // fn-2
            q = r;   // fn-1
            r = p + q; // fn
        }

        return r;
    }
}

二刷：两个变量解决，直接秒

class Solution {
    public int climbStairs(int n) {
        // 边界条件n=1， res = 1;
        // 边界条件n=2， res = 2;
        // n = 3时， 总步数 = (n为2时种类数) + (n为1时种类数)，即fn = fn-1 + fn-2

        if (n == 1) {
            return 1;
        } else if (n == 2) {
            return 2;
        }

        int n1 = 1, n2 = 2;
        for (int i = 3; i <= n; i++) {
            if (n1 < n2) {
                n1 = n1 + n2;
            } else {
                n2 = n1 + n2;
            }
        }

        return Math.max(n1, n2);
    }
}

72. 编辑距离——二维DP——二刷

https://leetcode.cn/problems/edit-distance/?envType=study-plan-v2&envId=top-100-liked

解题思路：参考题解和代码

class Solution {
    public int minDistance(String word1, String word2) {
        // 问题一：为什么只在末尾插入和修改？ 因为本质上在中间或末尾修改不影响最终的操作次数

        // 解题思路：
        // 1. 对a串删除数据，可以看做是对b串增加数据， 这样三种操作就转换为了：
            // 对a串增加数据， 对b串增加数据， 修改a串的值
        // 2. 理论上如果要查询 abc 和 d的最最小距离， 只需要查询ab和d的最小距离 + 1即可， 因此问题就可以
            // 转化为基于边界条件开始的遍历
        // 3. 边界条件， a串为abc，b串为空的前提下， a串和b串相同的最短距离就是3， 依次类推，此为边界条件

        // 公式：
            // 如果a串和b串最后一个字符相同，则dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1])
            // 如果a串和b串最后一个字符不同，则dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+1)
        
        int len1 = word1.length(), len2 = word2.length();
        char[] ss1 = word1.toCharArray(), ss2 = word2.toCharArray();

        int dp[][] = new int[len1+1][len2+1];

        // 边界条件
        for (int i = 0; i <= len1; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= len2; j++) {
            dp[0][j] = j;
        }

        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                int d1 = dp[i-1][j] + 1;
                int d2 = dp[i][j-1] + 1;
                int d3 = dp[i-1][j-1];
                if (ss1[i-1] != ss2[j-1]) {
                    d3 += 1;
                }

                dp[i][j] = Math.min(d1, Math.min(d2, d3));
            }
        }

        return dp[len1][len2];
    }
}

二刷， 还是看了思路，但是实现更丝滑

class Solution {
    public int minDistance(String word1, String word2) {
        // 1. 对a串删除 = 对b串增加， 因此操作转换为：   对a串增加、对b串增加、对a串或b串修改
        // 2. 边界条件的构造： 例如a串为abc，b串为空，a经过3步可以变为b
        // 3. 递推公式：如果需要查询abc到c的最小距离， 只需要查询ab到b的最短距离 + 1；  如果要查询ab到b的最短距离，只需查询a到b的最短距离 + 1
            // 如果二者最后一个字母相同， 则dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1])
            // 如果二者最后一个字母不同， 则dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+1)
        char[] cc1 = word1.toCharArray(), cc2 = word2.toCharArray();
        int len1 = cc1.length, len2 = cc2.length;
        int[][] dp = new int[len1 + 1][len2 + 1];

        if (len1 == 0 && len2 == 0) {
            return 0;
        }
        if (len1 == 0) {
            return len2;
        }
        if (len2 == 0) {
            return len1;
        }

        for (int i = 0; i <= len1; i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i <= len2; i++) {
            dp[0][i] = i;
        }
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (cc1[i - 1] == cc2[j - 1]) {
                    dp[i][j] = Math.min(dp[i-1][j] + 1, Math.min(dp[i][j-1] + 1, dp[i-1][j-1]));
                } else {
                    dp[i][j] = Math.min(dp[i-1][j] + 1, Math.min(dp[i][j-1] + 1, dp[i-1][j-1] + 1));
                }
            }
        }
        return dp[len1][len2];
    }
}

74. 搜索二维矩阵

https://leetcode.cn/problems/search-a-2d-matrix/?envType=study-plan-v2&envId=top-100-liked

解题思路：两次二分即可
注意命名的清晰， 以及边界的考虑， 比如第一次二分没有找到结果，直接返回就可以了

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        
        int xleft = 0, xright = matrix.length - 1, yleft = 0, yright = matrix[0].length - 1;
        int x = -1, y = -1;
        while (xleft <= xright) {
            int midx = (xleft + xright) >> 1;
            if (matrix[midx][yleft] <= target && matrix[midx][yright] >= target) {
                x = midx;
                break;
            } else if (target > matrix[midx][yright]) {
                xleft = midx + 1;
            } else if (target < matrix[midx][yleft]) {
                xright = midx - 1;
            }
        }

        if (x == -1) {
            return false;
        }

        while (yleft <= yright) {
            int midy = (yleft + yright) >> 1;
            if (matrix[x][midy] == target) {
                y = midy;
                break;
            } else if (target > matrix[x][midy]) {
                yleft = midy + 1;
            } else if (target < matrix[x][midy]) {
                yright = midy - 1;
            }
        }

        if (y == -1) {
            return false;
        }

        return true;

    }
}

75. 颜色分类——技巧*

https://leetcode.cn/problems/sort-colors/?envType=study-plan-v2&envId=top-100-liked

class Solution {
    public void sortColors(int[] nums) {
        // 技巧题，思考一下正常排序最低基本是Onlogn，这道题哪里可以优化？  答案是给定了只有三种数字
        // 定义左指针，左指针及其左边都是0（初始指向-1），定义右指针，右指针及其右边都是2（初始指向len），遍历一遍即可
        // 限定条件：l<i<r
        int len = nums.length;
        int l = -1, r = len;
        int i = 0;
        while(i < r) {
            if (nums[i] == 1) {
                i++;
            } else if (nums[i] == 0) {
                swap(nums, l + 1, i);
                l++;

                if (l >= i) {
                    i = l + 1;
                }
            } else {
                swap(nums, r - 1, i);
                r--;
            }
        }
    }

    public void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

78. 子集——DFS&回溯*

https://leetcode.cn/problems/subsets/?envType=study-plan-v2&envId=top-100-liked

解题思路：每个位置的元素，都有add 或 不add两种情况， 比如都add，就是所有元素的集合， 都不add，就是空集合， 把这个思想量化即可。

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> curList = new ArrayList<>();

    public List<List<Integer>> subsets(int[] nums) {
        dfs(nums, 0);
        return res;
    }

    public void dfs(int[] nums, Integer curLen) {
        if (curLen == nums.length) {
            res.add(new ArrayList<Integer>(curList));
            return;
        }
        
        curList.add(nums[curLen]);
        dfs(nums, curLen + 1);
        curList.remove(curList.size() - 1);
        dfs(nums, curLen + 1);
    }
}

79. 单词搜索——DFS&回溯*

https://leetcode.cn/problems/word-search/submissions/570382049/?envType=study-plan-v2&envId=top-100-liked

解题思路：标记flag数组，记录哪些方向可以被访问， 如果上一个字母是向右+1， 那么下一个字母的遍历方向就不能是左， 依次向4个方向回溯即可。

class Solution {
    boolean res = false;
    // 上，下，左，右
    boolean flag[][];
    int leni = -1, lenj = -1;



    public boolean exist(char[][] board, String word) {
        leni = board.length;
        lenj = board[0].length;
        flag = new boolean[leni][lenj];

        for (int i = 0; i < leni; i++) {
            for (int j = 0; j < lenj; j++) {
                if (res == true) {
                    return res;
                }
                if (board[i][j] == word.charAt(0)) {
                    flag[i][j] = true;
                    dfs(board, word, 1, i, j);
                    flag[i][j] = false;
                }
            }
        }
        return res;
    }

    public void dfs(char[][] board, String word, int curLen, int curi, int curj) {
        if (res || curLen == word.length()) {
            res = true;
            return;
        }

        if (curi + 1 < leni && flag[curi + 1][curj] == false && word.charAt(curLen) == board[curi + 1][curj]) {
            flag[curi + 1][curj] = true;
            dfs(board, word, curLen + 1, curi + 1, curj);
            flag[curi + 1][curj] = false;
        }
        if (curi - 1 >= 0 && flag[curi - 1][curj] == false && word.charAt(curLen) == board[curi - 1][curj]) {
            flag[curi - 1][curj] = true;
            dfs(board, word, curLen + 1, curi - 1, curj);
            flag[curi - 1][curj] = false;
        }
        if (curj + 1 < lenj && flag[curi][curj + 1] == false && word.charAt(curLen) == board[curi][curj + 1]) {
            flag[curi][curj + 1] = true;
            dfs(board, word, curLen + 1, curi, curj + 1);
            flag[curi][curj + 1] = false;
        }
        if (curj - 1 >= 0 && flag[curi][curj - 1] == false && word.charAt(curLen) == board[curi][curj - 1]) {
            flag[curi][curj - 1] = true;
            dfs(board, word, curLen + 1, curi, curj - 1);
            flag[curi][curj - 1] = false;
        }

        
    }
}

82. 删除链表中的重复元素2

https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/description/

1. 确保有一个哑结点，始终置身事外
2. 做好判npe

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode pre = new ListNode(-1000);
        pre.next = head;
        ListNode res = pre;

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

        return res.next;

    }
}

83. 删除链表中的重复元素1

https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/description/

解题思路：
当前节点与下一个节点比对， 如果值相等，直接去掉中间节点， while条件是中间节点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head;
        }
        
        ListNode cur = head;
        while(cur.next != null) {
            if (cur.val == cur.next.val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }
}

94. 二叉树的中序遍历——树——三刷

https://leetcode.cn/problems/binary-tree-inorder-traversal/?envType=study-plan-v2&envId=top-100-liked

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        inorder(root, res);
        return res;
    }

    public void inorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        inorder(root.left, res);
        res.add(root.val);
        inorder(root.right, res);
    }
}

迭代写法：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {

        List<Integer> res = new ArrayList<Integer>();
        List<TreeNode> queue = new LinkedList<TreeNode>();

        while (root != null || !queue.isEmpty()) {
            while (root != null) {
                queue.addLast(root);
                root = root.left;
            }
            root = queue.getLast();
            queue.removeLast();
            res.add(root.val);
            root = root.right;
        }

        return res;
    }
}

三刷，直接秒的

class Solution {
    List<Integer> res = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        // 左根右
        traversal(root);
        return res;
    }

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

        traversal(root.left);
        res.add(root.val);
        traversal(root.right);
    }
}

98. 验证二叉搜索树——树&递归——二刷

二叉搜索树的中序遍历，一定是递增的，基于此来校验
这里核心要理解层序遍历的底层原理，多理解

class Solution {
    public boolean isValidBST(TreeNode root) {
        
        List<TreeNode> list = new LinkedList<TreeNode>();
        long val = -Long.MAX_VALUE;

        while (!list.isEmpty() || root != null) {
            while (root != null) {
                list.addLast(root);
                root = root.left;
            }
            root = list.getLast();
            list.removeLast();

            if (root.val <= val) {
                return false;
            }
            val = root.val;

            root = root.right;
        }
        return true;
    }
}

二刷：递归实现中序遍历，进而判断，直接秒，我个人的习惯：前中后序用递归，层序用遍历

class Solution {
    boolean res = true;
    Long min = -Long.MAX_VALUE;

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        midCircle(root);
        return res;
    }

    public void midCircle(TreeNode root) {
        // 边界条件
        if (root == null) {
            return;
        }
        if (!res) {
            return;
        }

        // 中序-左节点
        midCircle(root.left);
        // 中序-根节点
        if (root.val <= min) {
            res = false;
            return;
        }
        min = Math.max(min, root.val);
        // 中序-右节点
        midCircle(root.right);
    }
}

101. 对称二叉树——递归&树

https://leetcode.cn/problems/symmetric-tree/?envType=study-plan-v2&envId=top-100-liked

思路：深搜， 缺节点false，不缺节点但是val不同false， 其他场景true

核心处理点在于参数是某个节点的左子树和右子树，root可以重复写入。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root, root);
    }

    public boolean check(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }

        return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
    }
}

二刷实现：
思考：分类讨论各种场景， 对我个人而言更直观简单清晰

class Solution {
    boolean res = true;
    public boolean isSymmetric(TreeNode root) {

        solution(root, root);
        return res;
    }

    public void solution(TreeNode leftNode, TreeNode rightNode) {
        if (res == false) {
            return;
        }
        if (leftNode == null && rightNode == null) {
            return;
        }
        if (leftNode == null && rightNode != null) {
            res = false;
            return;
        }
        if (leftNode != null && rightNode == null) {
            res = false;
            return;
        }
        if (leftNode != null && rightNode != null) {
            // 1. 值是否相等
            if (leftNode.val != rightNode.val) {
                res = false;
                return;
            }
            // 2. 左右子树是否对称
            solution(leftNode.left, rightNode.right);
            solution(leftNode.right, rightNode.left);
        }
        return;
    }
}

三刷：直接秒，递归做多了，顺其自然理出来逻辑，更丝滑了

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }

        return symmetric(root, root);
    }

    public boolean symmetric(TreeNode n1, TreeNode n2) {
        if (n1 == null && n2 == null) {
            return true;
        }
        if (n1 == null || n2 == null) {
            return false;
        }
        if (n1.val != n2.val) {
            return false;
        }

        return symmetric(n1.left, n2.right) && symmetric(n1.right, n2.left);
    }
}

102. 二叉树的层序遍历——树的广搜*

https://leetcode.cn/problems/binary-tree-level-order-traversal/?envType=study-plan-v2&envId=top-100-liked

解题思路：直接广搜，注意二位数组的构造方式， 以及双向链表的出入等

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (root == null) {
            return res;
        }
        List<TreeNode> list = new LinkedList<TreeNode>();

        list.addFirst(root);
        while (!list.isEmpty()) {

            int size = list.size();
            List<Integer> tempRes = new ArrayList<Integer>();

            while (size != 0) {
                TreeNode node = list.getFirst();
                list.removeFirst();
                size--;
                tempRes.add(node.val);

                if (node.left != null) {
                    list.addLast(node.left);
                }
                if (node.right != null) {
                    list.addLast(node.right);
                }
            }
            res.add(tempRes);
        }
        return res;
    }
}

104. 二叉树的最大深度——广搜——三刷

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例：输入：root = [3,9,20,null,null,15,7]
输出：3
示例 2：

解法思考：对于二叉树遍历，很自然的就想到深搜和广搜，但是对于实际生产中，递归并不常用，因为其性能开销较大，可能会导致栈溢出， 所以先尝试使用广搜来解题：

另外，这道题笔者认为用广搜更舒服

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {

        // 判空
        if (root == null) {
            return 0;
        }
        
        List<TreeNode> queue = new LinkedList<TreeNode>();
        queue.addFirst(root);

        int res = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size > 0) {
                TreeNode node = queue.getFirst();
                queue.removeFirst();
                if (node.left != null) {
                    queue.addLast(node.left);
                }
                if (node.right != null) {
                    queue.addLast(node.right);
                }
                size--;
            }
            res++;
        }
        return res;


    }
}

同样附深搜解法吧

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {

        // 判空
        if (root == null) {
            return 0;
        } else {
            int leftHeight = maxDepth(root.left);
            int rightHeight = maxDepth(root.right);
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }
}

二刷：层序遍历直接秒

class Solution {
    public int maxDepth(TreeNode root) {
        // 最大深度，层序遍历秒了
        if (root == null) {
            return 0;
        }

        int res = 0;
        List<TreeNode> deque = new LinkedList<>();
        
        deque.addLast(root);
        while (!deque.isEmpty()) {
            // 每层的遍历
            res++;
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = deque.removeFirst();
                if (node.left != null) {
                    deque.addLast(node.left);
                }
                if (node.right != null) {
                    deque.addLast(node.right);
                }
            }
        }
        return res;
    }
}

105. 从前序与中序遍历序列构造二叉树——树&递归*

https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/submissions/569351084/?envType=study-plan-v2&envId=top-100-liked

解题思路：前序序列第一个节点是根节点， 去中序序列中找到对应位置， 位置左侧就是左子树，位置右侧就是右子树， 然后根据中序序列的左子树数量， 定位前序序列中左子树和右子树区间， 然后递归向下

边界场景是，l > r

注意对细节的处理

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    Map<Integer, Integer> indexMap = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = inorder.length;
        for (int i = 0; i < n; i++) {
            indexMap.put(inorder[i], i);
        }

        TreeNode node = build(preorder, inorder, 0, n - 1, 0, n - 1);
        return node;
    }
    public TreeNode build(int[] preList, int[] inList, int pl, int pr, int il, int ir) {
        if (pl > pr) {
            return null;
        }

        // 1. 获取、构造根节点
        int rootPreIndex = pl;
        int rootInIndex = indexMap.get(preList[rootPreIndex]);
        TreeNode rootNode = new TreeNode(preList[rootPreIndex]);

        // 2. 计算左子树数据长度
        int lsize = rootInIndex - il;

        // 3. 构造左右子树
        rootNode.left = build(preList, inList, pl + 1, pl + lsize, il, rootInIndex - 1);
        rootNode.right = build(preList, inList, pl + lsize + 1, pr, rootInIndex + 1, ir);


        return rootNode;
    }
}

108. 将有序数组转换为二叉搜索树——树&递归&二分——三刷

https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/?envType=study-plan-v2&envId=top-100-liked

核心思路：无论数组内有多少个null节点，数组中间的数，一定是根节点， 同理，中间的数左边子数组，以及中间的数右边子数组，也遵循这个规律， 按照递归构建即可。

什么情况下某个节点为null呢？ 当子数组内数据量为0时，进一步的， 当l > r时。

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        // 本题核心逻辑，不管数组怎么变化，中间的数字一定是根节点，  用递归的思想考虑，前者同样适用于根节点左侧的子数组和右侧的子数组
        // 递归终止条件：l > r，说明区间内已经没有数据，自然返回0

        TreeNode node = buildSearchTree(nums, 0, nums.length - 1);
        return node;
    }

    public TreeNode buildSearchTree(int[] nums, int l, int r) {
        if (l > r) {
            return null;
        }

        int mid = (l + r) >> 1;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = buildSearchTree(nums, l, mid - 1);
        node.right = buildSearchTree(nums, mid + 1, r);

        return node;
    }
}

二刷：

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        // 1. 中间节点一定是根节点
        // 2. 只有左小于右时有值，否则是null
        int l = 0, r = nums.length - 1;

        TreeNode node = build(nums, l, r);
        return node;
    }


    public TreeNode build(int[] nums, int l, int r) {
        if (l > r) {
            return null;
        }
        int mid = (l + r) >> 1;
        TreeNode node = new TreeNode(nums[mid]);

        node.left = build(nums, l, mid - 1);
        node.right = build(nums, mid + 1, r);

        return node;
    }
}

三刷：比较丝滑，直接秒

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        // 二叉搜索树，左节点小于根节点，右节点大于根节点， 基于有序数组，二分构造二叉搜索树即可
        if (nums.length == 0) {
            return null;
        }
        return build(nums, 0, nums.length - 1);
    }
    public TreeNode build(int[] nums, int l, int r) {
        // 边界条件
        if (l > r) {
            return null;
        }
        if (l == r) {
            return new TreeNode(nums[l]);
        }

        // 递归构造搜索树
        int mid = (l + r) >> 1;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = build(nums, l, mid - 1);
        root.right = build(nums, mid + 1, r);
        return root;
    }
}

114. 二叉树展开为链表——树&规律——二刷

https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/?envType=study-plan-v2&envId=top-100-liked

解题思路：我认为是规律推导题， 具体见官方题解第三种解法，动画非常清晰。

class Solution {
    public void flatten(TreeNode root) {
        TreeNode node = root;
        while (node != null) {
            if (node.left != null) {
                TreeNode n1 = node.left;
                TreeNode n2 = n1;
                while (n2.right != null) {
                    n2 = n2.right;
                }
                n2.right = node.right;
                node.left = null;
                node.right = n1;
            }
            node = node.right;
        }
    }
}

二刷：看了思路，本质就是模拟，先序遍历下，右子树一定是等左子树全部遍历完，在遍历，所以就可以把右子树接到左子树的最右节点的右侧，再把左子树挪到右子树这里， 循环即可。

class Solution {
    public void flatten(TreeNode root) {
        build(root);
    }

    public void build(TreeNode root) {
        if (root == null) {
            return;
        }
        while (root != null) {
            if (root.left != null && root.right != null) {
                TreeNode left = root.left;
                TreeNode right = root.right;
                // 获取右子树，插入到左子树的最右侧
                TreeNode leftLastRoot = root.left;
                while (leftLastRoot.right != null) {
                    leftLastRoot = leftLastRoot.right;
                }
                leftLastRoot.right = right;
                // 左子树挪到右子树的位置
                root.right = root.left;
                root.left = null;
            } else if (root.left != null) {
                root.right = root.left;
                root.left = null;
            }
            root = root.right;
        }
    }
}

118. 杨辉三角——DP——二刷

https://leetcode.cn/problems/pascals-triangle/?envType=study-plan-v2&envId=top-100-liked

看图找规律即可。

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> cur = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                if (i == 0 || j == 0 || j == i) {
                    cur.add(1);
                } else {
                    cur.add(res.get(i-1).get(j-1) + res.get(i-1).get(j));
                }
            }
            res.add(cur);
        }
        return res;
    }
}

二刷代码：写的稍微不流畅，这里需要注意边界处理

class Solution {
    public List<List<Integer>> generate(int numRows) {
        if (numRows == 0) {
            return null;
        }

        List<Integer> firstNums = new ArrayList<>();
        firstNums.add(1);
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<Integer>(firstNums));

        for (int i = 2; i <= numRows; i++) {
            List<Integer> newNums = new ArrayList<>();
            for (int j = 1; j <= i; j++) {
                if (j == 1 || j == i) {
                    newNums.add(1);
                } else {
                    newNums.add(res.get(i - 2).get(j - 1) + res.get(i - 2).get(j - 2));
                }
            }
            res.add(newNums);
        }
        return res;
    }
}

121. 买卖股票的最佳时机

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/?envType=study-plan-v2&envId=top-100-liked

解题思路：贪心（贪心本质是当前最优策略， 每次遍历，都考虑新一次的最优策略，是否优于当前最优策略，如果是，则替换最优策略）， 遍历一遍， 记录到每个元素时，最小的值， 然后用当前元素减去最小值， 获取过程中最大差值返回即可。
PS：有点像最小栈的思路

class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxValue = 0;

        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            } else {
                maxValue = Math.max(prices[i] - minPrice, maxValue);
            }
        }

        return maxValue;
    }
}

124. 二叉树中的最大路径和——树&递归——一刷

https://leetcode.cn/problems/binary-tree-maximum-path-sum/?envType=study-plan-v2&envId=top-100-liked

自己做出80%case，但还是看了题解，需要二刷

class Solution {
    int res = -Integer.MAX_VALUE;
    public int maxPathSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        getMaxNum(root);
        return res;
    }

    public int getMaxNum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftNum = getMaxNum(root.left);
        int rightNum = getMaxNum(root.right);

        // 左右根节点的负数处理
        int finLeftNum = leftNum > 0 ? leftNum : 0;
        int finRightNum = rightNum > 0 ? rightNum : 0;

        res = Math.max(res, finLeftNum + finRightNum + root.val);

        return Math.max(finLeftNum, finRightNum) + root.val;
    }
}

128. 最长连续序列——技巧*

https://leetcode.cn/problems/longest-consecutive-sequence/submissions/570503268/?envType=study-plan-v2&envId=top-100-liked

遍历每个元素， 如果这个元素-1不存在，那么说明这个元素是起始元素，然后向后逐个遍历，并更新最大长度， 这个-1很巧妙

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

        int maxLen = 0;
        for (Integer num : set) {
            int curLen = 0;
            if (!set.contains(num - 1)) {
                int j = num;
                while (set.contains(j)) {
                    j++;
                    curLen++;
                }
                maxLen = Math.max(maxLen, curLen);
            }

        }
        return maxLen;
    }
}

二刷：
时间复杂度为什么是On？

• 如果num-1不存在，那么说明是序列头，遍历，这里看似最差时间复杂度是On，并且在循环内， 但是遍历过的元素，都属于第二种情况，也就是不需要重复遍历的
• 如果num-1存在，那么说明不是序列头，不遍历，O1

因此整体时间复杂度是On

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

        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], 1);
        }
        
        int res = 1;
        for (Integer num : map.keySet()) {
            if (!map.containsKey(num - 1)) {
                int t = 0;
                int tmpNum = num;
                while (map.containsKey(tmpNum)) {
                    tmpNum++;
                    t++;
                }
                res = Math.max(res, t);
            }
        }
        return res;
    }
}

131. 分割回文串——回溯——二刷

解题思路：经典回溯思路， dfs中， 对每一个位置+1，+2，…，+n进行全排列的遍历，然后回溯下一个位置也按照此思路，直到遍历完， 其中用回文方法判断是否符合即可。

https://leetcode.cn/problems/palindrome-partitioning/?envType=study-plan-v2&envId=top-100-liked

class Solution {
    List<List<String>> res = new ArrayList<>();
    List<String> cur = new ArrayList<>();
    public List<List<String>> partition(String s) {
        dfs(s, 0);
        return res;
    }

    public void dfs(String s, int curLen) {
        if (s.length() == curLen) {
            res.add(new ArrayList(cur));
            return;
        }

        for (int i = curLen + 1; i <= s.length(); i++) {
            String t = s.substring(curLen, i);
            if (isRequest(t)) {
                cur.add(t);
                dfs(s, i);
                cur.remove(cur.size() - 1);
            }
        }

    }

    public boolean isRequest(String s) {
        int i = 0, j = s.length() - 1;
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
            i++; j--;
        }
        return true;

    }
}

类似全排列的思路，换成字符串就行

class Solution {
    List<List<String>> res = new ArrayList<>();

    public List<List<String>> partition(String s) {
        // 思路：类似全排列， 每次都从curLen开始，从1到len逐个分割，如果到len了，就add进去
        List<String> curList = new ArrayList<>();
        dfs(curList, 0, s);
        return res;
    }

    public void dfs(List<String> curList, int curLen, String s) {
        int len = s.length();
        if (curLen == len) {
            res.add(new ArrayList<>(curList));
            return;
        }

        for (int i = curLen + 1; i <= len; i++) {
            String curS = s.substring(curLen, i);
            if (isReserve(curS)) {
                curList.add(curS);
                dfs(curList, i, s);
                curList.remove(curList.size() - 1);
            }
        }
    }

    public boolean isReserve(String s) {
        char[] cc = s.toCharArray();
        int l = 0, r = cc.length - 1;
        while (l < r) {
            if (cc[l] != cc[r]) {
                return false;
            }
            l++; r--;
        }
        return true;
    }
}

136. 只出现一次的数字——技巧

https://leetcode.cn/problems/single-number/submissions/571042669/?envType=study-plan-v2&envId=top-100-liked

解题思路：异或。

class Solution {
    public int singleNumber(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }

        for (int i = 1; i < nums.length; i++) {
            nums[i] ^= nums[i - 1];
        }
        return nums[nums.length - 1];
    }
}

139. 单词拆分——DP*

https://leetcode.cn/problems/word-break/?envType=study-plan-v2&envId=top-100-liked

解题思路：如下，有点类似背包，运用还不太熟练

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // 解题思路：设目标字符串为abcde
        // 字符串是否符合，取决于i+1-j是单词， 并且0-i是若干单词
        // 怎么判断0-i是单词？排列组合，符合任意条件，则说明是

        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < wordDict.size(); i++) {
            map.put(wordDict.get(i), 1);
        }

        int len = s.length();
        boolean[] dp = new boolean[len + 1];
        dp[0] = true;
        for (int i = 1; i <= len; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] == true && map.containsKey(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[len];
    }
}

141. 环形链表——链表-二刷

https://leetcode.cn/problems/linked-list-cycle/

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

---

第一思路，显然是使用Hash来判断节点是否被重复访问过，
时间复杂度On，空间复杂度On

让我们看一个「龟兔赛跑」的故事
如果我们设置一个fast指针，一个slow指针，fast指针每次移动2步，slow指针每次移动1步，如果链表内部有环，那么一定存在某次循环中，fast指针域slow指针指向同一个内存地址，这就是弗洛伊德算法（Floyd），也叫快慢指针。

让我们思考一下循环停止需要的条件：

1. 存在环的场景：快慢指针相遇
2. 不存在环的场景：遍历到null（即结尾）

于是代码如下：

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        // 入参校验
        if (head == null || head.next == null) {
            return false;
        }
        // 定义快慢指针
        ListNode slowNode = head;
        ListNode fastNode = head.next;
        // 终止条件1：快慢指针相遇，返回true
        while(slowNode != fastNode) {
            // 终止条件2：快指针null，代表遍历到头，返回false
            if (fastNode == null || fastNode.next == null) {
                return false;
            }
            slowNode = slowNode.next;
            fastNode = fastNode.next.next;
        }
        return true;
    }
}

快慢指针解法的实现，注意以下几个细节：
5. 循环终止条件只有两个（要么快慢指针相遇，要么快指针跑到头），即最少有2个return，多了的都可以优化
6. 入参的空值校验
7. 合理的注释
8. 对于变量的合理命名（如slowNode是比slow更好的）

二刷：

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        // 定义快慢指针，快指针每次走两步，慢指针每次走一步，如果存在环，必然相交
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast != null && fast == slow) {
                return true;
            }
        }
        return false;
    }
}

146. LRU

https://leetcode.cn/problems/lru-cache/?envType=study-plan-v2&envId=top-100-liked

1 5 1 4 2
1（6）-一个DLinkedNode结构
5-5个初始变量
1（6）-一个初始化
4-4个基本方法
2-get和put

class LRUCache {

    public class DLinkedNode {
        // 这里一定要有key，否则不知道move哪个
        private int key;
        private int value;
        private DLinkedNode prev;
        private DLinkedNode next;
        private DLinkedNode() {}
        private DLinkedNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    public int size = 0;
    public int capacity;
    public Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
    public DLinkedNode head;
    public DLinkedNode tail;


    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }


    // addToHead  moveToHead removeNode removeTail
    public void addToHead(DLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        // 这里顺序一定一定要注意， 一定是先next.prev，否则next指向变了，next.prev指向也变了
        head.next.prev = node;
        head.next = node;
    }

    public void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    public void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    public DLinkedNode removeTail() {
        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }
    
    public int get(int key) {
        // 获取不到，返回-1， 获取到，返回+调整链表结构
        DLinkedNode node = cache.get(key);
        if (node == null) {
            return -1;
        } else {
            moveToHead(node);
            return node.value;
        }
    }
    
    public void put(int key, int value) {
        // 存在，直接替换； 不存在，插入链表头，插入map， 同时判断容量，超过容量剔除队尾
        DLinkedNode node = cache.get(key);
        if (node == null) {
            DLinkedNode newNode = new DLinkedNode(key, value);
            addToHead(newNode);
            cache.put(key, newNode);
            size++;
            if (size > capacity) {
                DLinkedNode tail = removeTail();
                cache.remove(tail.key);
                size--;
            }
        } else {
            node.value = value;
            moveToHead(node);
        }
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

三刷代码：调试了一下， 然后忘记put时也要moveToHead了

class LRUCache {
    // 1 5 1 4 2
    // map作用是取数据O1，链表作用是，判断最久未使用
    public class DLinkNode {
        int key;
        int value;
        DLinkNode next;
        DLinkNode pre;
        DLinkNode() {}
        DLinkNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    int size;
    int capacity;
    DLinkNode head;
    DLinkNode tail;
    Map<Integer, DLinkNode> map;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        this.head = new DLinkNode();
        this.tail = new DLinkNode();
        head.next = tail;
        tail.pre = head;
        map = new HashMap<>();
    }

    // moveToHead, removeNode, removeTail, addToHead
    public void addToHead(DLinkNode node) {
        head.next.pre = node;
        node.next = head.next;
        head.next = node;
        node.pre = head;
    }

    public void moveToHead(DLinkNode node) {
        removeNode(node);
        addToHead(node);
    }

    public void removeNode(DLinkNode node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    public DLinkNode removeTail() {
        DLinkNode node = tail.pre;
        removeNode(node);
        return node;
    }
    
    public int get(int key) {
        // 如果有，返回，并moveToHead
        if (map.containsKey(key)) {
            DLinkNode node = map.get(key);
            moveToHead(node);
            return node.value;
        } else {
            return -1;
        }
        
    }
    
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            // 如果包含，直接替换value，同时moveToHead
            DLinkNode node = map.get(key);
            node.value = value;

            moveToHead(node);
        } else {
            DLinkNode newNode = new DLinkNode(key, value);
            if (size == capacity) {
                // 链表中逐出旧的，添加新的； map中移除旧的，再添加新的
                DLinkNode oldNode = removeTail();
                addToHead(newNode);

                map.remove(oldNode.key);
                map.put(newNode.key, newNode);
            } else {
                // 链表和map增加对应的值即可
                size += 1;
                addToHead(newNode);
                map.put(key, newNode);
            }
        }
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

153. 寻找旋转排序数组中的最小值——二分*

https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/?envType=study-plan-v2&envId=top-100-liked

解题思路：二分数组，最小值，一定在非递增的那半边（因为最小值是转折点的起始），按照这个思路找即可

需要注意对边界条件的判断，我这里取了巧

class Solution {
    public int findMin(int[] nums) {
        int res = 6000;
        // 解题思路：二分数组，最小值，一定在非递增的那半边（因为最小值是转折点的起始），按照这个思路找即可
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            res = Math.min(res, nums[l]);
            res = Math.min(res, nums[r]);
            res = Math.min(res, nums[mid]);
            
            if (nums[l] <= nums[mid]) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return res;
    }
}

155. 最小栈——栈——二刷

https://leetcode.cn/problems/min-stack/description/?envType=study-plan-v2&envId=top-100-liked

核心思路：维护一个最小栈，每次入栈，都判断最小栈栈顶元素是否小于当前值，如果小于，则把当前元素压入， 如果大于，则重复压入当前栈顶元素

class MinStack {

    List<Integer> stack;
    List<Integer> minStack;


    public MinStack() {
        stack = new LinkedList<Integer>();
        minStack = new LinkedList<Integer>();
        minStack.addFirst(Integer.MAX_VALUE);
    }
    
    public void push(int val) {
        stack.addFirst(val);
        if (minStack.get(0) > val) {
            minStack.addFirst(val);
        } else {
            // 这句话非常重要
            minStack.addFirst(minStack.get(0));
        }
    }
    
    public void pop() {
        stack.removeFirst();
        minStack.removeFirst();
    }
    
    public int top() {
        return stack.get(0);
    }
    
    public int getMin() {
        return minStack.get(0);
    }
}

class MinStack {
    List<Integer> stack;
    List<Integer> minStack;

    public MinStack() {
        stack = new LinkedList<>();
        minStack = new LinkedList<>();
        Integer minNum = Integer.MAX_VALUE;
        minStack.addFirst(minNum);
    }
    
    public void push(int val) {
        stack.addFirst(val);
        if (val < minStack.getFirst()) {
            minStack.addFirst(val);
        } else {
            minStack.addFirst(minStack.getFirst());
        }
    }
    
    public void pop() {
        stack.removeFirst();
        minStack.removeFirst();
    }
    
    public int top() {
        return stack.getFirst();
    }
    
    public int getMin() {
        return minStack.getFirst();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

160. 相交链表——链表

https://leetcode.cn/problems/intersection-of-two-linked-lists/?envType=study-plan-v2&envId=top-100-liked
A+B = B+A

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
 
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

        ListNode firstHeadA = headA;
        ListNode firstHeadB = headB;

        boolean headAChange = false, headBChange = false;
        while (headA != null && headB != null) {
            if (headA == headB) {
                return headA;
            }
            headA = headA.next;
            headB = headB.next;

            if (headA == null && !headAChange) {
                headA = firstHeadB;
                headAChange = true;
            }
            if (headB == null) {
                headB = firstHeadA;
                headBChange = true;
            }

        }
        return null;
    }
}

二刷：直接秒了

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 解题思路：A+B = B+A，  A和B一起遍历，如果A到头就从B处开始，如果B到头就从A处开始，直到两个节点相等

        // 记录首节点
        ListNode headA1 = headA, headB1 = headB;

        // 记录遍历到末尾的次数
        int countTail = 0;
        while (countTail <= 2) {
            if (headA == headB) {
                return headA;
            }
            headA = headA.next;
            if (headA == null) {
                headA = headB1;
                countTail++;
            }

            headB = headB.next;
            if (headB == null) {
                headB = headA1;
                countTail++;
            }
        }
        return null;
    }
}

169. 多数元素——技巧*

https://leetcode.cn/problems/majority-element/solutions/146074/duo-shu-yuan-su-by-leetcode-solution/?envType=study-plan-v2&envId=top-100-liked

解题思路：见代码

class Solution {
    public int majorityElement(int[] nums) {
        // 思考一个类似打擂台的思路，如果两个数相同， 则count+1，如果不同，则-1，如果count为0，则换另一个数，如果某一个数大于半数， 那么最后剩下的值一定是这个数
        Integer res = null;
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (count == 0) {
                res = nums[i];
            }

            
            if (res == nums[i]) {
                count += 1;
            } else {
                count -= 1;
            }

        }
        return res;
    }
}

189. 轮转数组——数组——二刷

最简单的思路：声明一个新数组来存储，然后赋值即可。

第二种思路，数组翻转， 由于移动k位，则代表最后k个数字一定出现在数组的前k个位置，因此先整体翻转数组，这样最后k个数字就到了前k个位置，然后对这k个数字翻转， 这样顺序转正， 再然后对k-n个数字翻转，完成。

下面给出两种思路的代码：

class Solution {
    public void rotate(int[] nums, int k) {
        int len = nums.length;
        k = k % len;
        if (k == 0) {
            return;
        }

        int[] res = new int[len]; 
        for (int i = 0; i < len; i++) {
            int move = (i + k) % len;
            res[move] = nums[i];
        }

        for (int i = 0; i < len; i++) {
            nums[i] = res[i];
        }
    }
}

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

        reserve(nums, 0, len - 1);
        reserve(nums, 0, k - 1);
        reserve(nums, k, len - 1);
    }

    public void reserve(int[] nums, int l, int r) {
        for (; l < r; l++, r--) {
            int t = nums[l];
            nums[l] = nums[r];
            nums[r] = t;
        }
    }
}

二刷：更圆融如意，直接秒

class Solution {
    public void rotate(int[] nums, int k) {
        // 1. k取余， 三次翻转
        int len = nums.length;
        k = k % len;
        reserve(nums, 0, len);
        reserve(nums, 0, k);
        reserve(nums, k, len);
    }

    public void reserve(int[] nums, int i, int j) {
        j -= 1;
        while (i < j) {
            swap(nums, i, j);
            i++; j--;
        }
    }
    
    public void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

198. 打家劫舍——DP——二刷

https://leetcode.cn/problems/house-robber/solutions/263856/da-jia-jie-she-by-leetcode-solution/?envType=study-plan-v2&envId=top-100-liked

解题思路：见代码，推出边界条件+状态转移方程

另外，还有更优化的解法是用两个变量代替数组

class Solution {
    public int rob(int[] nums) {
        // 如果只有一间房屋，偷窃最大额是房屋1金额
        // 如果有两间房屋，偷窃最大额是max(房屋1金额, 房屋2金额)
        // 如果有k间房屋，那么有两种情况
            // 情况1，偷第k间，最大偷窃金额 = 第k间金额 + 前k-2间最大金额
            // 情况2，不偷第k间，最大偷窃金额 = 前k-1间最大金额
        
        int len = nums.length;
        int[] maxMoneyList = new int[len];
        for (int i = 0; i < len; i++) {
            if (i == 0) {
                // 边界场景1
                maxMoneyList[i] = nums[i];   
            } else if (i == 1) {
                // 边界场景2
                maxMoneyList[i] = Math.max(nums[i-1], nums[i]);
            } else {
                // 状态转移公式
                maxMoneyList[i] = Math.max(nums[i] + maxMoneyList[i - 2], maxMoneyList[i - 1]);
            }
        }

        return maxMoneyList[len - 1];
    }
}

二刷：DP裸题，丝滑秒杀

class Solution {
    public int rob(int[] nums) {
        // DP裸题
        // 边界条件： 只有一间房时，最高金额为该房屋金额；   有两间房屋时，最高金额为两间中更高的一间
        // DP公式：有n间房屋时， 
            // 场景1：偷第n间房屋，最高金额为第n间房屋金额 + 前n-2个房屋总最高金额
            // 场景2：不偷第n间房屋，最高金额为 前n-1个房屋总最高金额
        // 因此DP公式：fn = max(n+fn-2, fn-1);

        int len = nums.length;
        if (len == 0) {
            return 0;
        } else if (len == 1) {
            return nums[0];
        } else if (len == 2) {
            return Math.max(nums[0], nums[1]);
        }

        int dp[] = new int[len + 1];
        dp[1] = nums[0];
        dp[2] = Math.max(nums[0], nums[1]);

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

199. 二叉树的右视图

https://leetcode.cn/problems/binary-tree-right-side-view/?envType=study-plan-v2&envId=top-100-liked

解题思路：层序遍历，每层取最后一个节点即可。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        List<TreeNode> list = new LinkedList<>();
        list.addLast(root);
        
        while (!list.isEmpty()) {
            int size = list.size();
            TreeNode last = list.getLast();
            res.add(last.val);
            while (size-- > 0) {
                TreeNode node = list.removeFirst();
                if (node.left != null) {
                    list.addLast(node.left);
                }
                if (node.right != null) {
                    list.addLast(node.right);
                }
            }
        }
        return res;
    }
}

206. 反转链表——链表-三刷

https://leetcode.cn/problems/reverse-linked-list/?envType=study-plan-v2&envId=top-100-liked

解题思路：见代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        // 解题思路：定义哑结点，三个指针互相走，第三个节点是引路的作用，同时定义哑结点，作用是把首节点当做普通节点一样处理， 最后哑结点置null即可。
        if (head == null || head.next == null) {
            return head;
        }

        ListNode n1 = head, n2 = head.next, n3 = head.next.next;
        n1.next = head;
        ListNode head1 = head;

        while (n2 != null) {
            n2.next = n1;

            if (n3 == null) {
                break;
            }
            n1 = n2;
            n2 = n3;
            n3 = n3.next;
        }
        head1.next = null;
        return n2;
    }
}

三刷：优化了代码，整体更丝滑

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        // 解题思路：定义哑结点，三个指针互相走，第三个节点是引路的作用，同时定义哑结点，作用是把首节点当做普通节点一样处理， 最后哑结点置null即可。
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode n1 = null, n2 = head, n3 = head.next;
        while (n2 != null) {
            n2.next = n1;
            if (n3 == null) {
                break;
            }
            n1 = n2;
            n2 = n3;
            n3 = n3.next;
        }

        return n2;
    }
}

215. 数组中第K个最大的元素——堆*

https://leetcode.cn/problems/kth-largest-element-in-an-array/description/?envType=study-plan-v2&envId=top-100-liked

核心思路：理解堆的构建过程，调整过程

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        // 建堆
        build(nums, len);
        // 找到第k个最大的元素，每移除一个元素，要重新调整堆
        for (int i = 1; i < k; i++) {
            swap(nums, 0, len-1);
            len--;
            adjust(nums, 0, len);
        }
        
        return nums[0];
    }

    public void build(int[] nums, int len) {
        // 遍历所有节点，从后往前调整，确保逐步有序
        for (int i = (len >> 1); i >= 0; i--) {
            adjust(nums, i, len);
        }
    }

    public void adjust(int[] nums, int cur, int len) {
        // 每次调整，保证了三个节点范围内根节点是最大的， 然后再逐步往下调整
        int i = cur;
        int l = cur * 2 + 1, r = cur * 2 + 2;

        if (l < len && nums[l] > nums[cur]) {
            cur = l;
        }
        if (r < len && nums[r] > nums[cur]) {
            cur = r;
        }

        if (i != cur) {
            swap(nums, i, cur);
            adjust(nums, cur, len);
        }
    } 

    public void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

二刷：

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 1. 建堆，从大到小依次遍历
        // 2. 调整堆，根节点是最大的， 如果不是，则调整， 然后把调整的哪个节点继续调整（因为扰动了该节点下的所有左右子树）
        int len = nums.length;
        buildHeap(nums, len);

        for (int i = 1; i < k; i++) {
            swap(nums, 0, len - 1);
            len--;
            modifyHeap(nums, 0, len);
        }

        return nums[0];
    }

    public void buildHeap(int[] nums, int len) {
        for (int i = (len >> 1); i >= 0; i--) {
            modifyHeap(nums, i, len);
        }
    }

    public void modifyHeap(int[] nums, int cur, int len) {
        if (cur >= len) {
            return;
        }
        int oCur = cur;
        int l = cur * 2 + 1;
        int r = cur * 2 + 2;
        if (l < len && nums[cur] < nums[l]) {
            cur = l;
        }
        if (r < len && nums[cur] < nums[r]) {
            cur = r;
        }
        if (oCur != cur) {
            swap(nums, oCur, cur);
            modifyHeap(nums, cur, len);
        }
    }

    public void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

226. 翻转二叉树——树&递归——三刷

https://leetcode.cn/problems/invert-binary-tree/?envType=study-plan-v2&envId=top-100-liked

解题思路：递归，没什么好说的

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;

        return root;
    }
}

二刷：更符合我个人的思考习惯，代码如下：

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        TreeNode t = root.left;
        root.left = root.right;
        root.right = t;

        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

三刷：二刷应该还看了题解的，三刷纯手推，更丝滑

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

    public void invert(TreeNode node) {
        if (node == null) {
            return;
        }
        TreeNode t = node.left;
        node.left = node.right;
        node.right = t;

        invert(node.left);
        invert(node.right);
    }
}

230. 二叉搜索树中第k小的元素

https://leetcode.cn/problems/kth-smallest-element-in-a-bst/?envType=study-plan-v2&envId=top-100-liked

相关hot100题型：

1. 二叉树的中序遍历
2. 验证二叉搜索树

核心思路：二叉搜索树的中序遍历，是递增的，以此找第k小的元素
这里最好要学会中序遍历的迭代写法

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        List<TreeNode> list = new LinkedList<TreeNode>();

        int num = 1;
        // 遍历所有节点
        while (root != null || !list.isEmpty()) {
            // 左遍历
            while (root != null) {
                list.addFirst(root);
                root = root.left;
            }
            // 获取最近塞入的一个节点
            root = list.getFirst();
            list.removeFirst();

            // 判断操作
            if (num == k) {
                return root.val;
            }
            num++;
            
            // 这个节点的左子树已经遍历完， 转而遍历这个节点的右子树
            root = root.right;
        }

        return -1;
    }
}

234. 回文链表——链表*——三刷

https://leetcode.cn/problems/palindrome-linked-list/?envType=study-plan-v2&envId=top-100-liked

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        
        // 1. 求长度
        int len = 0;
        ListNode head1 = head, head2 = head;
        while (head != null) {
            head = head.next;
            len++;
        }

        // 2. 获取节点长度是奇数还是偶数
        boolean isOu = false;
        if ((len % 2) == 0) {
            isOu = true;
        }

        // 3. 链表前半段反转
        // 前半段反转
        int time = 0;
        ListNode n1 = new ListNode(-1), n2 = head1, n3 = head1.next;
        n1.next = n2;
        // 遍历len/2次，包含哑结点的反转
        while (time < len / 2) {
            n2.next = n1;
            if (n3 == null) {
                break;
            }
            n1 = n2;
            n2 = n3;
            n3 = n3.next;

            time++;
        }
        // 去掉哑结点
        head1.next = null;


        // 4. 判断是否回文
        ListNode two = (isOu ? n2 : n3);
        ListNode one = n1;
        // 两个链表长度一定相等，所以不用复杂判定
        while (one != null) {
            if (one.val != two.val) {
                return false;
            }
            one = one.next;
            two = two.next;
        }
        return true;
    }
}

二刷：整体代码更清爽，更顺畅

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }

        // 1. 求长度，判断奇数还是偶数
        int len = 0;
        ListNode h1 = head;
        while (h1 != null) {
            len++;
            h1 = h1.next;
        }
        boolean isOu = (len % 2 == 0 ? true : false);

        // 2. 反转链表的前半部分，定义哑结点，头结点标准化
        ListNode n1 = new ListNode(-1);
        n1.next = head;
        ListNode n2 = head, n3 = head.next;

        int t = 0;
        while (t < len / 2) {
            if (t == 0) {
                n1.next = null;
            }
            n2.next = n1;
            n1 = n2;
            n2 = n3;
            n3 = n3.next;

            t++;
        }
        
        // 3. 前半部分和后半部分对比
        ListNode one = n1;
        ListNode two = isOu ? n2 : n3;
        while (one != null && two != null) {
            if (one.val != two.val) {
                return false;
            }
            one = one.next;
            two = two.next;
        }
        return true;
        
    }
}

236. 二叉树的最近公共祖先——树&递归——二刷

https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/submissions/569498073/?envType=study-plan-v2&envId=top-100-liked

解题思路：

1. DFS：使用DFS可以确保找到的第一个公共祖先是最近公共祖先，因为DFS是自底向上
2. 节点满足条件：左子树包含目标节点、右子树包含目标节点、本身是目标节点， 三者满足其二，就说明是最近公共祖先，记录并返回即可

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    TreeNode res;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 找到共同祖先的唯一场景：左子树包含、右子树包含、自身是一个节点， 三个条件满足其二
        // 为什么DFS遍历出来的第一个一定是最近公共祖先？ 因为DFS是从叶子节点开始遍历的

        dfs(root, p, q);
        return res;
    }

    public int dfs(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return 0;
        }

        int a = (root.val == p.val || root.val == q.val) ? 1 : 0;
        int b = dfs(root.left, p, q);
        int c = dfs(root.right, p, q);

        if (a + b + c == 2) {
            res = root;
        }

        return (a + b + c) == 0 ? 0 : 1;
    }
}

二刷，还是看题解了，这个还需要三刷，核心是对最近公共祖先的理解不到位，最近公共祖先的要求，只能是左孩子+右孩子是， 或自身是+(左孩子是or右孩子是)

class Solution {
    TreeNode res = null;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 最近公共祖先条件：左孩子+右孩子是， 或自身是+(左孩子是or右孩子是)
        dfs(root, p, q);
        return res;
    }

    public boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return false;
        }

        boolean selfHave = (root == p || root == q);
        boolean leftHave = dfs(root.left, p, q);
        boolean rightHave = dfs(root.right, p, q);

        // res赋值条件
        if ((leftHave && rightHave) || ((leftHave || rightHave) && selfHave)) {
            res = root;
            return true;
        }

        // 返回值：该root是否为true
        return selfHave || leftHave || rightHave;
    }
}

238. 除自身以外数组的乘积——数组——二刷

https://leetcode.cn/problems/product-of-array-except-self/?envType=study-plan-v2&envId=top-100-liked

解题思路：定义双指针，新数组初始值为1，左指针负责某个位置的值*左边乘积； 右指针负责某个位置的值*右边乘积

点评：巧妙， 通过初值为1，解决了不能乘以本值的问题， 通过左右指针，将乘积拆分为左半边和右半边两个连续的部分，然后遍历

class Solution {
    public int[] productExceptSelf(int[] nums) {
        // 核心思路：声明一个数组，初始值为1， 然后双指针，左指针的作用是这个位置左遍的乘积，右指针的作用是这个位置右边的乘积
        int len = nums.length;
        int[] res = new int[len];
        for (int i = 0; i < len; i++) {
            res[i] = 1;
        }

        int ls = 1, rs = 1;
        for (int l = 0, r = len - 1; l <= len - 1 && r >= 0; l++, r--) {
            res[l] *= ls;
            res[r] *= rs;
            ls *= nums[l];
            rs *= nums[r];
        }
        return res;
    }
}

二刷，想了一会直接秒，思路还是挺巧妙

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int len = nums.length;

        // ans初始化为1
        int[] res = new int[len];
        for (int i = 0; i < len; i++) {
            res[i] = 1;
        }

        // 第一遍遍历，先乘左边的
        int lnum = 1, rnum = 1;
        for (int i = 0; i < len; i++) {
            res[i] = res[i] * lnum;
            lnum *= nums[i];
        }

        // 第二遍遍历，乘右边的
        for (int i = len - 1; i >= 0; i--) {
            res[i] *= rnum;
            rnum *= nums[i];
        }

        return res;
    }
}

240. 搜索二维矩阵二——矩阵&技巧——一刷

https://leetcode.cn/problems/search-a-2d-matrix-ii/solutions/?envType=study-plan-v2&envId=top-100-liked

解题思路：见代码

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // 第一种解法二分，每次可以排除半行或者半列，时间复杂度Onlogn
        // 第二种解法，设想初始查找位置在右上角，该元素左侧所有树都小于他，该元素右侧所有树都大于他，所以每次可以排除整行或整列的数，时间复杂度Om+n
        // 其实还有第三种解法，前两种解法综合，时间复杂度Ologm+Ologn
        int lenx = matrix.length, leny = matrix[0].length;
        int x = 0, y = leny - 1;
        while (x < lenx && y >= 0) {
            if (matrix[x][y] == target) {
                return true;
            }
            if (matrix[x][y] > target) {
                y--;
            } else {
                x++;
            }
        }

        return false;
    }
}

279. 完全平方数——DP*

https://leetcode.cn/problems/perfect-squares/?envType=study-plan-v2&envId=top-100-liked

解题思路：见代码，就是一个完全背包

class Solution {
    public int numSquares(int n) {
        // 解题思路：假设n为12，最小次数的计算只有三种结果：
            // 因为 11 + 1*1 = 12， 因此结果 = 达到11的最小次数 + 1
            // 因为 8 + 2*2 = 12，  因此结果 = 达到8的最小次数 + 1
            // 因为 3 + 3*3 = 12，  因此结果 = 达到3的最小次数 + 1
                // 对11、8、3的最小次数的求法，重复上述计算过程
        int[] t = new int[n + 1];
        t[0] = 0;

        for (int i = 1; i <= n; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 1; j * j <= i; j++) {
                min = Math.min(min, t[i-j*j] + 1);
            }
            t[i] = min;
        }
        return t[n];
    }
}

283. 移动零——双指针

https://leetcode.cn/problems/move-zeroes/?envType=study-plan-v2&envId=top-100-liked

一刷代码：

class Solution {
    public void moveZeroes(int[] nums) {
        int len = nums.length;
        // 双指针， 一个指针标记为0的， 一个指针标记不为0的，指针二永远在指针一后面
        int l1 = 0, l2 = 0;
        while (l1 < len && l2 < len) {
            while (l1 < len && nums[l1] != 0) {
                l1++;
            }
            l2 = l1 + 1;
            while (l2 < len && nums[l2] == 0) {
                l2++;
            }
            if (l2 < len) {
                swap(nums, l1, l2);
            }
        }
    }

    public void swap(int[] nums, int l1, int l2) {
        int t = nums[l1];
        nums[l1] = nums[l2];
        nums[l2] = t;
    }
}

二刷代码：
有一个非常牛逼的思路，即i不动，遍历j，如果j不等于0，就和i换位置，i++，这样保证所有非0的数字，都按顺序出现在前面，后面的自然就是0了

class Solution {
    public void moveZeroes(int[] nums) {
        // 遍历，如果发现，基于0的位置，向后遍历，遇到第一个非0的数据，交换
        int len = nums.length;
        int i = 0, j = 0;
        while (j < len) {
            if (nums[j] != 0) {
                swap(nums, i, j);
                i++;
            }
            j++;
        }
    }

    public void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

// class Solution {
//     public void moveZeroes(int[] nums) {
//         // 遍历，如果发现，基于0的位置，向后遍历，遇到第一个非0的数据，交换
//         int len = nums.length;
//         for (int i = 0; i < len; i++) {
//             if (nums[i] == 0) {
//                 for (int j = i + 1; j < len; j++) {
//                     if (nums[j] != 0) {
//                         swap(nums, i, j);
//                         break;
//                     }
//                 }
//             }
//         }
//     }

//     public void swap(int[] nums, int i, int j) {
//         int t = nums[i];
//         nums[i] = nums[j];
//         nums[j] = t;
//     }
// }

287. 寻找重复数——二分*-2

https://leetcode.cn/probl
ems/find-the-duplicate-number/?envType=study-plan-v2&envId=top-100-liked

class Solution {
    public int findDuplicate(int[] nums) {
        // 根据第一个用例倒推， 遍历数组，如果 <= n/2的值的数量， > n/2， 那么说明重复数据值在0-n/2之间，然后通过二分逐渐缩小范围
        int n = nums.length;
        int l = 1, r = n - 1, ans = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                if (nums[i] <= mid) {
                    cnt ++;
                }
            }
            if (cnt > mid) {
                r = mid - 1;
                ans = mid;
            } else {
                l = mid + 1;
            }
        }
        return ans;
    }
}

二刷，依旧没做出来，卡在ans的赋值上， 很巧妙， 更熟练了

class Solution {
    public int findDuplicate(int[] nums) {
        // 二分，每次二分，都遍历
        int l = 1, r = nums.length - 1; 
        int ans = -1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            int count = 0;
            for (int i = 0; i <= nums.length - 1; i++) {
                if (nums[i] <= mid) {
                    count++;
                }
            }
            if (count > mid) {
                r = mid - 1;
                // 这个ans巧妙， 因为如果不-1，会死循环， 如果-1，下次循环的mid可能不是正确结果，所以先记录下来
                ans = mid;

            } else {
                l = mid + 1;
            }
        }
        return ans;
    }
}

300. 最长递增子序列——DP*

https://leetcode.cn/problems/longest-increasing-subsequence/?envType=study-plan-v2&envId=top-100-liked

class Solution {
    public int lengthOfLIS(int[] nums) {
        // 解题思路：声明记忆数组DP，记录每个位置上最长子序列，然后新遍历的位置，依次和前面每一个元素比较，如果大于这个元素，就在这个元素最长子序列的基础上+1
        // 边界条件：dp[0] = 1
        int len = nums.length;
        int dp[] = new int[len];
        dp[0] = 1;

        int res = 1;

        for (int i = 1; i < len; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            res = Math.max(dp[i], res);
        }

        return res;
    }
}

322. 零钱兑换——DP*

https://leetcode.cn/problems/coin-change/?envType=study-plan-v2&envId=top-100-liked

经典完全背包，注意考虑边界条件

class Solution {
    public int coinChange(int[] coins, int amount) {
        // 例如总金额11，面额为1,2,5
            // 可能性1：10 + 1：凑面额10的最小数量 + 1
            // 可能性2: 9 + 2： 凑面额9的最小数量 + 1
            // 可能性3: 6 + 5： 凑面额6的最小数量 + 1
            // 结果为以上三种可能性的最大值
            // 特殊场景：case2，要特殊判定

        int f[] = new int[amount + 1];
        f[0] = 0;

        for (int i = 1; i <= amount; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < coins.length; j++) {
                int subIndex = i - coins[j];
                if (subIndex >= 0 && f[subIndex] != -1) {
                    min = Math.min(min, f[subIndex] + 1);
                }
            }

            // fi赋值
            if (min == Integer.MAX_VALUE) {
                min = -1;
            }
            f[i] = min;
        }
        return f[amount];
    }
}

347. 前k个高频元素

https://leetcode.cn/problems/top-k-frequent-elements/?envType=study-plan-v2&envId=top-100-liked

思路：手动构建大根堆，大小按照出现次数来排， 同时构建结构体，存储每个数字值与出现次数

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        
        // 构建map，统计次数
        Map<Integer, Integer> map1 = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            if (map1.containsKey(nums[i])) {
                map1.put(nums[i], map1.get(nums[i]) + 1);
            } else {
                map1.put(nums[i], 1);
            }
        }
        
        // 构建nodes
        int len = map1.keySet().size();
        Node[] nodes = new Node[len];
        int t = 0;
        for (int key : map1.keySet()) {
            nodes[t++] = new Node(key, map1.get(key));
        }

        // 构建大根堆
        buildMaxHeap(nodes, len);

        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = nodes[0].num;
            swap(nodes, 0, len - 1);
            len--;
            modifyMaxHeap(nodes, 0, len);
        }
        return res;
    }

    public void buildMaxHeap(Node[] nodes, int len) {
        for (int i = (len >> 1); i >= 0; i--) {
            modifyMaxHeap(nodes, i, len);
        } 
    }

    public void modifyMaxHeap(Node[] nodes, int cur, int len) {
        if (cur >= len) {
            return;
        }
        int ocur = cur;
        int left = cur * 2 + 1;
        int right = cur * 2 + 2;

        if (left < len && nodes[left].count > nodes[cur].count) {
            cur = left;
        }
        if (right < len && nodes[right].count > nodes[cur].count) {
            cur = right;
        }

        if (ocur != cur) {
            swap(nodes, ocur, cur);
            modifyMaxHeap(nodes, cur, len);
        }
    }

    public void swap(Node[] nodes, int ocur, int cur) {
        Node t = nodes[ocur];
        nodes[ocur] = nodes[cur];
        nodes[cur] = t;
    }

    class Node {
        public int num;
        public int count;

        public Node(int num, int count) {
            this.num = num;
            this.count = count;
        }
    }

}

415. 字符串相加——大数——一刷

模拟

class Solution {
    public String addStrings(String num1, String num2) {
        int i = num1.length() - 1, j = num2.length() - 1;
        
        int upNum = 0;
        String res = "";
        while (i >= 0 || j >= 0) {
            int n1 = (i >= 0 ? num1.charAt(i) - '0' : 0);
            int n2 = (j >= 0 ? num2.charAt(j) - '0' : 0);

            int tmpRes = (n1 + n2 + upNum) % 10;
            upNum = (n1 + n2 + upNum) / 10;

            res = ((char)(tmpRes + '0')) + res;

            i--; j--;
        }

        if (upNum > 0) {
            res = (char)(upNum + '0') + res;
        }

        return res;
    }
}

437. 路径总和三——树&DFS*

https://leetcode.cn/problems/path-sum-iii/submissions/569489131/?envType=study-plan-v2&envId=top-100-liked

解题思想：首先遍历每一个节点，然后对于每一个节点都执行dfs，即获取路径总和， 最后相加即可
DFS的设计思想：把他想象成是一次遍历即可，其他递归完成。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        // 首先要遍历所有节点，这个过程通过递归完成； 其次针对每个节点，都做一次DFS
        if (root == null) {
            return 0;
        }

        int res = 0;
        res = dfs(root, targetSum);
        res += pathSum(root.left, targetSum);
        res += pathSum(root.right, targetSum);

        return res;
    }

    public Integer dfs(TreeNode root, long targetSum) {
        if (root == null) {
            return 0;
        }

        int ret = 0;

        if (targetSum == root.val) {
            ret += 1;
        }

        ret += dfs(root.left, targetSum - root.val);
        ret += dfs(root.right, targetSum - root.val);

        return ret;

    }
}

438. 找到字符串中所有字母异位词——滑动窗口&异位词——一刷

https://leetcode.cn/problems/find-all-anagrams-in-a-string/?envType=study-plan-v2&envId=top-100-liked

滑动窗口裸题，核心在于异位词的判断，用char[]，结合Arrays.equals

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        // set记录，滚动数组，如果不在里面，直接清空，并且进行下一次循环， 如果在里面，+1，进行下一次循环
        // 涉及到异位词的，直接排序伺候
        List<Integer> res = new ArrayList<>();

        char[] ss = s.toCharArray(), pp = p.toCharArray();
        int len1 = s.length(), len2 = p.length();

        int[] order = new int[26];
        for (int i = 0; i < len2; i++) {
            order[pp[i] - 'a']++;
        }

        int curLen = 0;
        int[] curNums = new int[26];
        for (int l = 0, r = 0; r < len1; r++) {
            int index = ss[r] - 'a';
            curNums[index]++;
            while (curNums[index] > order[index]) {
                curNums[ss[l] - 'a']--;
                l++;
            }
            if (Arrays.equals(order, curNums)) {
                res.add(l);
            }
        }
        return res;
    }
}

543. 二叉树的直径——递归——二刷

https://leetcode.cn/problems/diameter-of-binary-tree/?envType=study-plan-v2&envId=top-100-liked

解题思路：不论哪条路径最长，最长路径一定符合左子树长度+右子树长度+1的特征， 然后根据这个特征用DFS遍历深度即可。

class Solution {
    int res = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        // 不论哪条路径最长，一定是左子树长度+右子树长度+1
        nodeDepth(root);
        return res - 1;
    }

    public int nodeDepth(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int left = nodeDepth(node.left);
        int right = nodeDepth(node.right);
        res = Math.max(res, (left + right + 1));
        return Math.max(left, right) + 1;
    }
}

二刷：还是看了题解，推了一会才推出来，需要三刷

class Solution {
    int res = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        // 每个节点的最大深度，可以理解为该节点左子树最大长度 + 右子树最大长度 + 1， 据此递归即可
        // 变量怎么保存？ 用全局变量
        if (root == null) {
            return 0;
        }

        getMaxNum(root);
        return res - 1;
    }
    public int getMaxNum(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int leftNum = getMaxNum(root.left);
        int rightNum = getMaxNum(root.right);

        res = Math.max(res, (leftNum + rightNum + 1));
        return Math.max(leftNum, rightNum) + 1;
    }
}

560. 和为k的子数组——前缀和*——二刷

https://leetcode.cn/problems/subarray-sum-equals-k/?envType=study-plan-v2&envId=top-100-liked

class Solution {
    public int subarraySum(int[] nums, int k) {
        // 维护一个前缀和数组，  如果i-j的连续子串和为k， 可以转换为j的前缀和-k=i的前缀和；
        // 把所有前缀和维护在map中，就可以o1的检测出是否有这个和了（这里要考虑前缀和出现多次的情况，用value来记录）
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();

        // pre-k恰好为0的场景
        map.put(0, 1);

        int pre = 0;
        int res = 0;

        boolean first = true;
        for (int i = 0;  i < nums.length; i++) {
            pre += nums[i];

            // 要先判断，再插入， 如果先put， k=0的场景下会多算
            if (map.containsKey(pre - k)) {
                res += map.get(pre - k);
            }
            if (map.containsKey(pre)) {
                map.put(pre, map.get(pre) + 1);
            } else {
                map.put(pre, 1);
            }
        }

        return res;
    }
}


// 暴力
// class Solution {
//     public int subarraySum(int[] nums, int k) {
//         int len = nums.length;
//         int[] sumList = new int[len];
//         sumList[0] = nums[0];
//         for (int i = 1; i < len; i++) {
//             sumList[i] = sumList[i - 1] + nums[i];
//         }

//         int res = 0;

//         for (int i = -1; i < len; i++) {
//             for (int j = i + 1; j < len; j++) {
//                 int t = 0;
//                 if (i != -1) {
//                     t = sumList[i];
//                 }
//                 if (sumList[j] - t == k) {
//                     res++;
//                 }
//             }
//         }
//         return res;
//     }
// }

二刷：还是卡了很长时间，这里对+=的理解不够深刻

class Solution {
    public int subarraySum(int[] nums, int k) {
        // 滑动窗口没法处理负数场景
        Map<Integer, Integer> map = new HashMap<>();
        int pre = 0, res = 0;
        // put的作用是，可能出现数组自身的前缀和就是k
        map.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            pre += nums[i];

            // += 的作用是，pre-k的前缀和出现了多少次，就有多少种构造结果，res就增加对应的数值
            if (map.containsKey(pre - k)) {
                res += map.get(pre - k);
            }

            // 每次遍历都记录这次遍历的前缀和的次数
            if (map.containsKey(pre)) {
                map.put(pre, map.get(pre) + 1);
            } else {
                map.put(pre, 1);
            }

        }
        return res;
    }
}

718. 最长重复子串——DP——一刷

https://leetcode.cn/problems/maximum-length-of-repeated-subarray/

// class Solution {
//     public int findLength(int[] nums1, int[] nums2) {
//         // DP思路： 当nums1[i] = nums2[j]时，dp[i][j] + dp[i-1][j-1]+1； ans取最大值， 时间复杂度Omn，空间复杂度Omn
//         int len1 = nums1.length, len2 = nums2.length;
//         int dp[][] = new int[len1 + 1][len2 + 1];
//         int res = 0;
//         for (int i = 1; i <= len1; i++) {
//             for (int j = 1; j <= len2; j++) {
//                 if (nums1[i - 1] == nums2[j - 1]) {
//                     dp[i][j] = dp[i - 1][j - 1] + 1;
//                     res = Math.max(res, dp[i][j]);
//                 }
//             }
//         }
//         return res;
//     }
// }

// 滚动数组， 其实每一个dp[i][j]，只依赖dp[i-1][j-1]，优化成一维，只突出j，每一次新的循环，dp数组都是上一次的值，这样就达到了滚动的效果
class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int len1 = nums1.length, len2 = nums2.length;
        int dp[] = new int[len2 + 1];
        int res = 0;
        for (int i = 1; i <= len1; i++) {
            for (int j = len2; j >= 1; j--) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[j] = dp[j - 1] + 1;
                    res = Math.max(res, dp[j]);
                } else {
                    // 初始化
                    dp[j] = 0;
                }
            }
        }
        return res;
    }
}

763. 划分字母区间——贪心*

https://leetcode.cn/problems/partition-labels/?envType=study-plan-v2&envId=top-100-liked

解题思路：贪心，见代码，只能说很巧妙，很好的贯彻了贪心的思想。

class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> res = new ArrayList<Integer>();

        // 1. 记录每一个字母最后一次出现的位置
        // 2. 如果该字母最后一次出现的位置之前，所有的字母，最后一次出现的位置，都在它之前，则证明是一个区间，反之，获取到更远的位置
        // 3. 总之每一次遍历，都是当下看的最优策略，即贪心
        char[] ss = s.toCharArray();
        int endIndex = 0;

        int[] endPosList = new int[26];
        for (int i = 0; i < ss.length; i++) {
            endPosList[ss[i] - 'a'] = i;
        }

        int sum = 0;
        for (int i = 0; i < ss.length; i++) {
            if (endPosList[ss[i] - 'a'] > endIndex) {
                endIndex = endPosList[ss[i] - 'a'];
            }
            if (i == endIndex) {
                res.add(i + 1 - sum);
                sum = i+1;
            }
        }
        return res;
    }
}

1143. 最长公共子序列——二维DP*

https://leetcode.cn/problems/longest-common-subsequence/?envType=study-plan-v2&envId=top-100-liked

解题思路：核心在于理解公式，具体看代码

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        // 解题思路：对于a串，如果text1[i] = text2[j] ，则dp[i][j] = dp[i-1][j-1] + 1
        // 否则，dp[i][j] = max(dp[i-1][k], dp[i][j-1])
        int len1 = text1.length(), len2 = text2.length();
        int dp[][] = new int[len1 + 1][len2 + 1];

        // 这里要注意，遍历1-n，不是0-n-1，因为0是给长度为0的字符串准备的，不算在字符串长度遍历里
        char[] ss1 = text1.toCharArray(), ss2 = text2.toCharArray();
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {

                if (ss1[i-1] == ss2[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 dp[len1][len2];
    }
}

三、大公司高频题

字节

四、高频题分类

链表高频题

PS：LRU好好练。。频率高的都快冒出来了，我本人也是多次遇到LRU，的确很考验算法功底，在面试较高压场景下，正确写出不容易

树高频题

PS：感觉树整体频率不高

回溯高频题

PS：整体出题频率也不太高

Hot 100 + 高频题的前三名： 全排列、分割回文串、N皇后、组数总和、子集

二分高频题

Hot 100的高频题：4、33、34、35、74

栈高频题

Hot 100中的高频题：