力扣刷题记录以及自己对于解法的理解

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

双指针解法

设置一个快慢指针，通过检测nums[fast]和nums[slow-2]的值是否相等来判断是否重复。 若不相等，则fast指针向右移动一位，并把nums[fast]的值赋给nums[slow]，slow指针向右移动一位。 否则只有快指针移动。

快指针用于扫描整个数组，慢指针用于记录处理后的数组长度。

121. 买卖股票的最佳时机

类似动态规划

通过遍历数组，记录之前的最低价格，并把每天都当作售卖的日子计算利润并与当前最大值比较 这样可以达到O(n)的时间复杂度

55. 跳跃游戏

贪心算法

遍历数组，每到达一个index，记录当前位置能到达的最远距离，并与当前的最远距离比较，若当前位置能到达的最远距离比当前位置大，则更新最远距离，同时通过当前最远距离来束缚遍历的范围。

若当前的范围大于最远距离，直接返回false;若当前的最远距离大于length-1，则返回true;

45. 跳跃游戏 II

贪心算法

这个需要求到达目的地的最小步数，所以需要有一个边界问题，思路和上面大致一样，但是不能直接返回，但是需要额外增加一个边界变量，一旦遍历到边界，则将边界自动移动到当前最远距离，并返回步数+1，注意，若终点不可达，则可以发现，边界和可达的最大值相等，通过这个来表示不可达

274. H 指数

数学原理

h指数为：h 代表“高引用次数” ，一名科研人员的 h 指数i 是指他（她）至少发表了 h 篇论文，并且 至少 有 h 篇论文被引用次数大于等于 h 。如果 h 有多种可能的值，h 指数 是其中最大的那个。

数学原理为：对数组进行升序排序，再遍历数组，只要当前值大于等于数组长度-i，则数组长度-i为h指数。

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

前后缀和

该题需要用到一定的动态规划，但主要是前后缀和，即创建一个左乘数组，其递推表达式为 left[i] = left[i-1] * nums[i-1]，再创建一个右乘数组，其递推表达式为 right[i] = right[i+1] * nums[i+1]，其中left[0]=1,right[n-1]=1，最后左右乘数组对应位置元素相乘即可。

134. 加油站

逻辑推断

该题首先要明白一点，即只要加油的总和大于耗油的总和，则一定可以完成一圈，通过该逻辑，我们就可以遍历该数组，如果从start到end的加油和耗油之和小于0，则说明start无法完成一圈，则将start移动到end+1，并重新开始计算。

14. 最长公共前缀

二维数组

将字符串数组看成一个二维数组即可方便计算，通过纵向对比，很容易得出

6. Z 字形变换

模拟

创建一个字符串数组，通过行数的变换来分别给每行的字符串加上对应的字符即可

68. 文本左右对齐

空格的计算

通过最大宽度减去单词长度，计算出本行的空格总数，再通过空格总数除以空隙并向下取整，获得基础空格数，再通过空格总数整除空隙，得到前面的几个空隙需要额外添加一个空格

空格的高效添加

’ ’.repeat(num) 此方法可以高效添加空格，避免超时

11. 盛最多水的容器

双指针

通过双指针，一个指针指向数组的开始，一个指针指向数组的末尾，通过比较两个指针指向的数值，移动短边，并计算当前两个指针之间的能装水的量，并更新最大装水量。

15. 三数之和

暴力解法

直接就是三重循环，但是要注意去重问题，通过将要加入的数组排序，并额外定义一个set来进行数组的去重，该方法超时(为O(n^3))。

双指针解法

将数组从小到大排序，然后固定第一个数，通过双指针，第一个指针j=i+1，第二个指针k=n-1，通过比较两个指针的数值，从而判定j++还是k–，若满足条件，则将结果加入数组中 去重逻辑为三重去重，即当nums[i]===nums[i+1]时，i++，当nums[j]===nums[j+1]时，j++，当nums[k]===nums[k-1]时，k–，因为数组是排序过的，所以能够做到精准去重

209. 长度最小的子数组

滑动窗口

维护一个双指针，left和right，left为滑动窗口的左边界，right为滑动窗口的右边界，通过right向右移动，子数组的总和大于target时，则将left持续向右移动，直到sum小于target，此时left和right之间的长度+1为最小长度

30. 串联所有单词的子串

滑动窗口+数学原理

先创建一个map，用来表示words数组中单词出现的次数，然后通过一个二重循环来遍历s，注意，外层为i=0，i小于单个单词的长度(这里为了规避掉起始位置不为单个单词长度的倍数)，在外层中，定义一个临时map，计数器和left=i(窗口起始位置)

在内层循环中，定义j=left，j小于等于s的长度减去单个单词的长度，因为要通过substring(j,j+singleWordLength)来截取单词，如果这个单词在map中出现过，则将临时map中的次数加1，并计数器加1，当临时map中的值大于wordmap的值，就要进行滑动窗口的移动，left移动相应的wordLen，同时count减去对应的数值，如果计数器等于words数组的长度，则说明该子串满足要求，将left保存到结果数组中，并left加singleWordLength，临时map对应的键减1，计数器减1；若这个单词没有在map中出现过，则直接跳过，并left加singleWordLength，临时map清空，计数器清0.

54. 螺旋矩阵

模拟

顺时针螺旋本质上就一个顺序，左下右上，通过一个变量来调控，并在触及边界时转变方向并回溯到上一步，再进行正确的一步即可。

73. 矩阵置零

O(1)空间复杂度解法

通过常数空间来解决，需要将输入数组的第一排和第一列作为标记符，解法为：

1. 先遍历第一排和第一列，将firstZeroRow和firstZeroCol标记为true，表示第一排和第一列有0
2. 遍历除去第一排和第一列的数组，如果当前元素为0，将matrix[i][0]和matrix[0][j]标记为0，表示当前行和列有0
3. 遍历第一排和第一列除去[0][0]的元素，若当前元素为0，将这一排或这一列的元素标记为0
4. 通过firstZeroRow和firstZeroCol来判断第一排和第一列的元素是否需要全部变为0，若为true，则将第一排和第一列的元素置为0

289. 生命游戏

原地算法

如果要做到原地算法，则需要额外的标记符，即用2来记录即将死去，用3来记录即将复活，注意，在遍历时，需要将2看作1，即2也算活的 最后再将2变为0，3变为1

1. 两数之和

哈希表

在ts中，可以直接通过map来实现哈希表，map的key为数组中的元素，value为索引，只要每次遍历每个数，获取其和target的差，判断差是否在map中，若在则返回结果，若不在则将当前数作为key，索引作为value，存入map即可。

128. 最长连续序列

set过滤

本题需要将数组转换成set，然后通过遍历set，找出当前数-1是否存在set中，若不存在，则将当前数作为起始数，通过while循环，不断将当前数+1，直到当前数+1不存在set中，将当前序列长度和max比较

也就是说，需要查找序列的起点，这样就能够保证每个数最多遍历两次

56. 合并区间

区间排序

首先，将数组按照第一个的大小进行升序排序，得到一个排序后的数组，然后通过一个双指针，x,y分别指向首个的start和end，同时遍历排序后的数组，若y>=下一个数组的start，则将y更新为y和下一个数组的end的较大值，若y<下一个数组的start，则将结果数组加入[x,y]，并更新x,y为下一个数组的start,end，注意，最后还要将最后的一个加入结果数组中，防止遗漏

57. 插入区间

条件判断

插入区间要进行判断，若当前区间的end小于插入区间的start，则直接push到ans中，若插入区间的start位于当前区间中，则更新x为当前区间的start，若当前区间的end位于当前区间中，则更新y为当前区间的end，若y小于当前区间的start，则将[x,y]push进ans中，最后将后面的数组全部push进去即可(注意，需要通过一个变量来判断是否插入了[x,y]，这样就可以做到精准调控是否插入当前区间)

71. 简化路径

分割字符串

将字符串按照’/‘进行划分，变为数组，然后遍历数组，若为空字符串,’.‘，则都跳过，若为’..‘，则将ans数组的最后一个元素pop，若其他的，直接push进ans中，最后，将ans拼接为字符串返回即可，还要在转换完的字符串前面添加一个’/’

155. 最小栈

动态记录最小值

创建一个变量min，初始化为正无穷，在push时，若栈为空，则push一个0进去，然后将min赋值为当前元素； 若栈不为空，则push一个当前值-min进去，然后将min更新为当前值和min的较小值

在pop时，若pop的元素小于0，则将min更新为min-top(因为最小值和第二小的值就差一个top) 同样的，在top时，若top的元素小于0，则返回min，否则返回top+min

380. O(1) 时间插入、删除和获取随机元素

数组+map

创建一个数组，创建一个map，map的key为数组中的元素，value为索引，这样，在插入时，将元素插入数组的末尾，并更新map，在删除时，将map中该元素对应的索引的元素与数组末尾的元素进行交换，将数组末尾的元素删除，并更新map，在获取时，随机获取一个索引，并返回该索引对应的元素

224. 基本计算器

符号栈

构建一个type

type signStack = {
    num:number,
    sign:number
}

先构建一个nums，用于存储数字的字符串，再构建一个num，用于存储当前的结果，再构建一个sign，用于存储当前符号，初始化为1 根据该type构建一个数组，然后遍历数组 若遍历到(，则将当前的num和sign入栈 若遍历到+，则是先进行num+=sign*Number(nums)的计算并清空nums，再将sign变为1 若遍历到-，则也是先进行num+=sign*Number(nums)的计算并清空nums，将sign变为-1 若遍历到)，则将栈顶的num和sign弹出，定义为a，将num重新赋值为a.num+a.sign*(num+sign*Number(nums))，最后清空nums即可 否则若字符不为’ ‘，则将其加入到nums中 最后，还需要检测nums是否为空found’，若为true，则进行num+=sign*Number(nums)，最后返回num

141. 环形链表

快慢指针（Floyd 判圈算法）

创建两个指针，一个fast，一个slow，fast每次移动两步，slow每次移动一步，若fast和slow相遇，则说明有环，返回true，若fast为null，则说明无环，返回false 这样最多只需要遍历两遍链表，时间复杂度为O(n)

过河拆桥法

每当遍历一个节点后，直接将该结点的值设置为数据范围之外，如果遍历到数据范围之外，则说明有环，返回true，否则只需等待遍历到null，则说明无环，返回false

2. 两数相加

哑节点

创建一个哑节点dummy，在返回时直接返回dummy.next即可，这样可以在循环时初始化头节点，代码逻辑更清晰

138. 随机链表的复制

哈希表

本题的主要难点在于random存储的是地址，所以无法通过新地址来赋值和计数，所以需要用到hash表以及二次循环

创建一个map，用来存储原链表节点和复制节点的对应关系，并创建一个prenode，用于在第一次循环时进行连接，优化查询

第一次循环，遍历原链表，并创建一个新的节点，将原节点作为键，新节点作为值存入map，并通过prenode进行next连接，并将新节点作为prenode

第二次循环，同样遍历原链表，并获取对应关系，将通过当前节点获取新节点，并通过当前节点的random来获取对应的新节点，进行random连接即可 最后返回根据头节点所获取的新节点

25. K 个一组翻转链表

头插法

头插法需要三个节点，prev指向当前链表起始节点的上一个节点，curr指向当前节点的头结点，newtail指针也指向当前节点的头结点头插法需要将需要处理的链表断开 进行头插法时，需要将curr的下一个节点保存到temp中，并将curr.next=prev.next，这是为了将新插入的节点插入到prev之后并保证链表完整性最后连接prev和curr，将curr赋值为temp

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

快慢指针

设置一个快指针和一个慢指针，且都指向dummy节点，快指针先移动n+1步，这样当快指针指向null时，慢指针指向的刚好就是要删除的节点的前一个节点，只需要注意边界问题即可

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

数学方法

定义一个哑节点，并赋给prev 遍历链表，当head.next && head.val === head.next.val时，将该值设置为curr，然后定义一个新的循环并继续遍历，直到head为null或者head.val !== curr，此时，设置prev.next=head 若不触发上述条件，则prev=prev.next，head=head.next

86. 分隔链表

分割法

直接创建两个链表，一个存放小于x的节点，一个存放大于等于x的节点，最后将两个链表连接起来，返回小于x的链表头即可，注意在连接head节点后，记得将head.next=null，避免链表循环

146. LRU 缓存

双向链表+哈希表

双向链表表示节点之间的顺序，哈希表表示key和节点的关系。

在获取时，先将节点从链表中删除，然后将该节点插入到链表头部，最后返回该节点的值。

在插入时，先判断key是否存在，若存在，则直接修改该节点的值，然后将该结点从链表中删除，然后将该节点插入到链表头部，最后更新key对应的节点的值。若不存在，则判断节点数是否到达最大值，若到达，则将链表尾部节点删除，并删除对应的key，再将该结点插入，若没到达，直接将该结点插入头部即可

104. 二叉树的最大深度

从底向上递归

从叶子递归到根，也就是从根节点开始，依次向下递归leftLength和rightLength (只需要反复调用自身即可)，并返回Math.max(leftLength,rightLength)+1，若为null，则返回0

从顶向下递归

这里的max初始化需要用到函数闭包，在外函数中定义max，在内函数中使用max即可

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

哈希表+递归

递归思路：

1. 找到当前树的根
2. 找到根在中序遍历中的位置，并确定左子树和右子树的长度
3. 找到前序遍历的左子树和右子树
4. 重复执行2，3

哈希表的使用

创建一个哈希表，将中序遍历的节点值作为键，节点的索引作为值，这样在寻找根节点时，可以通过中序遍历的节点值来获取根节点的索引，这样可以减少查找时间 注意：若使用哈希表，则无法拆解数组，因为数组的索引无法保证唯一 提示：可以用三个参数pre表示当前节点的根节点在前序数组中的索引，l表示当前子树的左边界，r表示当前子树的右边界，连接可以直接通过递归调用构造方法创建，即返回new TreeNode(val,fuc(),fuc())这样就可以通过递归的方式直接连接，减少代码冗余

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

bfs

bfs需要用到一个队列，且需要记录当前层数的节点总数 创建一个队列，并额外创建一个prev记录上一个节点，sum和size负责更新层数节点 先将root节点入队，并更新sum和size，然后进行循环，判断队列是否为空，若不为空，则进行一个size次数的循环，将队列中的节点出队，判断prev是否为null，若不为null，则将prev.next指向当前节点，并更新prev为当前节点，同时将该节点的左右子节点入队，并更新sum，当size次数循环结束，将size更新为sum，并将prev置为null，sum重置为0

根据next构建链表

该方法的本质时通过上一层构建的next链表来移动当前层的指针，并构建下一层的链表

需要创建一个cur，初始化为root，一个prev和一个chiidHead，初始化为null

创建一个while循环，判断cur是否为null，若不为null，则进行循环，将cur赋予一个node变量 然后再创建一个while循环，判断node是否为null，若不为null，则先检测node.left，且若prev为null，则将childHead赋值为node.left，若不为null，则将prev.next=node.left，并更新prev=node.left，然后以同样的方法检测node.right，然后node=node.next 跳出第二层循环后，cur=childHead，childHead=null，prev=null

114. 二叉树展开为链表

O(1)空间迭代法

创建一个cur节点，初始化为root，然后开始循环，检测cur.left是否为null，若不为null，则将cur.left作为节点进行右侧节点的搜查，找到最右节点后，将其右指针指向cur.right，然后将cur.right指向cur.left，将cur.left置为null，最后cur=cur.right，重复上述过程，直到cur为null

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

递归

本题需要从下往上递归，经过分析可以发现，一共就两种加法，一种倒v，一种则是取单边

递归思路

1. 计算左子树的单边和leftSum
2. 计算右子树的单边和rightSum
3. 若其中的单边和为负数，则置为0
4. 计算node.val+leftSum+rightSum，若其大于max，则更新max
5. 返回node.val+Math.max(leftSum,rightSum)

222. 完全二叉树的节点个数

优于O(n)的算法

由于树为完全二叉树，所以根据数学原理可以得出，当左边高度大于右边时，右边是完全二叉树，当左边高度等于右边时，左边是完全二叉树 因此，我们可以根据这个构建递归

高度的计算

左边高度的计算为从当前节点的左节点开始，一直向左 右边高度的计算为从当前节点的右节点开始，一直向左

注意：无论是左子树节点的计算还是右子树，都需要额外加上一个1，也就是当前节点

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

递归

本题我们需要用到后序遍历，因为这样最能够体现出节点的父子关系，通过后序遍历加状态记录，从而解决该题

思路

通过检测传入的节点是否为null，若为null，则返回null，若节点和p或q相等，则返回该结点，并在主函数中记录为left和right，当前函数的left和right分别表示当前节点的左右子树是否包含p和q，若left和right同时为true，则返回当前节点，否则返回left和right中不为null的节点

199. 二叉树的右视图

数学思路

层序遍历中每层的最后一个就是该层的右视图

130. 被围绕的区域

反向寻找

若正向寻找被围绕的区域，很难实现，所以我们可以从反方向考虑，不被围绕的区域一定有一个边缘O，这样我们就可以从边缘开始，遍历边缘，进行dfs，一旦遇到O，就将其变为#，注意，这里不能对循环进行优化，即只遇到O才进行dfs，否则在全为O时会有所遗漏

最后再次遍历矩阵，将O变为X，将#变为O

399. 除法求值

图+搜索

本题的主要难点在于若采用其他数据结构，很难去进行反向求值以及传递求值，而采用图的好处是可以通过双向权图来进行记录，并通过搜索来进行传递求值

图的构建

const graph=new Map<string,Map<string,number>>();
for(let i=0;i<equations.length;i++){ 
    const [a,b]=equations[i];
    if(!graph.has(a)) graph.set(a,new Map());
    if(!graph.has(b)) graph.set(b,new Map());
    graph.get(a).set(b,values[i]);
    graph.get(b).set(a,1/values[i]);
}

这样就完成了一个图的构建

深度搜索

需要通过一个set来记录之前搜索过的节点，避免重复搜索

const check=new Set();
const dfs=(node:string,target:string,product:number)=>{
    if(node===target) return product;
    check.add(node);
    const neighbors=graph.get(node);
    if(!neighbors) return -1;
    for(const [key,value] of neighbors){
        if(check.has(key)) continue;
        const result=dfs(key,target,product*value);
        if(result!==-1) return result;
    }
    check.delete(node);
    return -1;
}

在最后求解问题时只需要额外判断一下是否在图中即可，若不在在，则返回-1

207. 课程表

三色法+图

该问题需要通过数据先构建出一个图，然后判定该图中是否存在环，若存在环，则返回false，否则返回true

三色法

将节点分为三个部分，0表示未访问，1表示正在访问，2表示已访问且安全 然后遍历该图中所有节点并进行dfs搜索，只要有一个返回false，则返回false，否则返回true 在dfs中，若节点的颜色为1，则说明存在环，返回false，若为2，则说明该节点已访问过且安全，返回true，若为0，则说明该节点未访问过，若该节点不存在图中，则标记为安全返回true，否则将该节点标记为1，dfs其邻居，若有一个返回false，则返回false，否则返回true并标记为安全

909. 蛇梯棋

bfs+图

本题的核心思路为将棋盘转化成图，再进行bfs搜索，核心思想为，每骰一次骰子，就会出现一个新的结果，也就是连接到下一个节点的边，且每一个边的权为1，只需要对节点值进行约束，若节点值>n^2，则直接剪枝，若节点值<=n^2，则入队

bfs

使用队列，循环以队列长度不为0为条件，并额外添加一个visited数组，用于记录访问过的节点，若节点已访问过，则跳过，否则将节点入队，并标记为已访问 所有准备好后，遍历每层节点，将其依次出队，若节点值===n^2，则直接返回即可，并根据骰子的6个值进行循环，构建下一层的队列，注意，若next>n^2，则直接剪枝，同时，需要将next其转换成对应的二维数组，检测此处是否有传送，若有，则更新next为传送后的值，最后看next是否位于visited数组中，若在则跳过，否则将其入队，并标记为已访问

433. 最小基因变化

bfs+剪枝

一样的，需要用到图的bfs，不过若巧妙运用剪枝，则会大大降低复杂度，正常情况是逐个替换，查看bank是否拥有

剪枝

本题可以优化为考虑当前字符串是否和bank里面的某一个字符串相等或者只相差一个字符串，若满足条件，则直接入栈，并在bank中删除该字符串，避免重复的同时，也减少了搜索范围，但是注意，这里涉及到在循环中操作依赖数组，所以要从后往前遍历，避免出现问题