• 链表中环的入口节点:些许卡顿
    • 最长无重复子串:还要练习
    • 用两个栈实现队列:不够熟悉
    • 链表中的节点每k个一组翻转:重点掌握
    • 最近公共祖先:重点掌握

    思路

    • 首先总体上这道题采用深度优先遍历解决
    • 我们需要查找两个节点或者值的最近公共祖先节点
    • 有两种情况满足条件:
      • 当前节点的左子树与右子树中分别包含着两个节点
      • 当前节点为这两个节点中的其中一个,剩下的子树中包含这两个节点的另一个节点

    这道题是一道比较抽象的题,我们要查找到所给两个节点的最近公共祖先,也就是找到两个节点最近的根节点,我们首先采用深度优先遍历这棵树。

    遍历的过程中记录当前节点的左右子节点是否包含所给的节点,如果当前节点的左右子节点都包含所给节点那么毫无疑问当前节点就是最近的公共祖先节点。

    如果当前节点是所给节点的其中一个那么,判断其左右子节点中是否存在所给的目标节点的其中一个,如果有那么当前节点就是最近的公共祖先节点。

    那么怎么确定最近呢?我们采用深度优先遍历这样得到的结果自然而然就是最近的公共祖先节点。


    • 子数组的最大累加和问题:利用for循环解决
    • 两个链表生成相加链表:很好的链表题重点掌握
    • 最长公共子串不会
    • 求平方根:数学题目,记住方法便好。

    思路

    • 对于求一个数x的平方根,我们首先在0-x这个区间内找到一个中位数
    • 然后判断这个数的平方是否大于或小于x
    • 如果大于我们就缩小右边的区间,为mid-1否则我们就缩小左边的区间为mid+1
    • 最后如果left>right就退出循环,注意需要包含等于的情况

    • 最长递增子序列:技巧性比较强的一道题,不够熟练,多加练习
    • 螺旋矩阵:这道题本质上的概念就是顺时针打印矩阵

    思路

    • 创建变量m,n记录矩阵行与列
    • 创建res数组记录结果,创建visited对象记录走过的位置,创建setKey方法生成对象的key
    • 创建direction数组控制走的方向
    • 使用for循环进行矩阵的遍历
    • 开始将矩阵的row与col放入res中
    • 在对象中将当前位置设置为走过
    • 之后计算出新的row与col判断是否走出边界,如果走出让dIndex+1,否则将row = newRow ,对于列也是一样的

    • 合并k个已排序的链表:这道题有很多的解法,我还是用比较原始的,将所有的链表划分为节点放入数组中,然后将

    节点进行排序,然后在复原成链表

    • 重建二叉树
    • 字符串的排列:这道题还是比较难的,需要用到回溯,还是总结一下方法吧

    思路

    • 首先创建一个字符串模板,存放所有字符串的种类,创建一个字典,存放所有字符串以及其出现的次数
    • 之后我们需要创建一个backTrack回溯方法,传入一个空字符串作为参数,首先我们需要判断这个字符串的长度是否等于我们所需要字符串的长度,并且我们的结果数组里还没有该字符串,那么我们就将其放入数组
    • 之后就是最重要的部分,我们利用for循环遍历字符串模板进行回溯
    • 首先取出字典里当前字符的数量,然后保存当前字符串用于后续的回溯
    • 如果当前字符的数量大于0,那么我们就让其加上当前遍历得到的字符
    • 然后让字典中对应的字符数量减一
    • 之后继续进行递归
    • 然后就是回溯部分,我们需要让当前字符串回归到之前形态
    • 然后字典中的数量也是之前形态

    • 容器盛水问题:出过原题,要重点掌握

    思路

    • 这道题的核心观点是贪心
    • 我们创建两个指针,在容器的两端
    • 首先找出两端中更短的那一个记录下来
    • 然后使用while循环,指向更短那边的指针向容器内部移动一个单位
    • 接下来核心点就来了,如果更短那边的指针移动后短于之前的指针指向的高度,像这样

      1. ![image.png](https://cdn.nlark.com/yuque/0/2021/png/2378335/1611720730168-68a6252c-8698-4f84-b815-d21872f78787.png#align=left&display=inline&height=299&margin=%5Bobject%20Object%5D&name=image.png&originHeight=299&originWidth=478&size=6061&status=done&style=none&width=478)
    • 那么两者的差值加到我们盛水的体积上便好

    • 否则更新最短的部分便好

    • [ ] 盛最多水的容器盛最多水的容器与牛客上容器盛水问题完全不一样,只需要计算出盛最多水的方式便好不需要考虑其他,以两边的高度为标准不断的比较得出最多盛水的情况便好。

    • [ ] 在转动过的有序数组中查找目标值:很好的一道关于二分查找的题,要重点掌握


    最核心代码

                    while(A[left] > A[right]) {
                let mid = (left + right) >> 1;
                if(A[mid] < A[left]) {
                    left = mid;
                }else {
                    right = mid;
                }
            }
    

    • [ ] 数组中相加和为0的三元组:

    • [x] 股票买卖的最佳时机:比较经典的一道动态规划的题目,可以使用暴力法,也可通过创建一个dp数组来解决。dp方案的思路是,设置一个最小值默认为数组的第一个数,在数组遍历的过程中一直更新最小值,创建一个dp数组,数组的第i个值dp[i] = Math.max(dp[i-1],minValue-prices[i]);,也就是让数组的第i个不断的与最小值相比较然后存入到dp数组中,这样也可以防止无论怎么操作收益都为负数的情况。

    • 设计LRU缓存结很好的一道题我们只需利用一个map便可以完成。