leetcode究极班百题祭
作者:
目标不检测
,
2022-05-09 17:20:13
,
所有人可见
,
阅读 208
冲冲冲
# 100: 相同的树: 一个递归判断,判断左子树, 判断右子树
# 99: 恢复二叉搜索树: Morris遍历,1,此数没有左子树,就遍历,然后走到右儿子
2,此数有右儿子,找前驱节点p,如果前驱节点的右儿子为空,则指向当前跟节点。,不为空的话,遍历。
#98: 验证二叉搜索树: 用的是一个数组存储,递归遍历。利用一个数组存储子树的最大最小值,并与当前层的根节点进行比较。
#97:交错字符串: 这是一道动态规划, 状态表示是s[i + j] 是由s[i],s[j]交错形成的方案,状态是看最后一个
字符是来自哪个字符串
#96:不同的二叉搜索树,因为二叉搜索树是,左子树小于根节点,右子树大于根节点,并且中序遍历是升序,所以可以哦通过判断升序表达来做二叉搜索树的建立
#95: 不同的二叉搜索树II: 不同的二叉搜索树,需要构建二叉搜索树,因为二叉树有左右子树之分,所以构建出来的肯定不会因为镜像对称而导致重复。
#94: 二叉树的中序遍历: 二叉树的中序遍历,第一种方式就是通过递归来做,每次判断进入的树是否为空,再看能不能进入左子树。第二种方式,是通过非递归来做,要借助栈的原理来,通过栈把路过的节点记下来,直到先找到最左端的节点,如果最左端的节点被遍历再遍历当前节点。
# 93: 复原IP地址: 复原IP地址实际是一个递归暴力搜索题目,直接往下深度搜索,通过变量控制搜索起始位置,搜索到满足条件没有。
# 92: 反转链表II: 反转链表题目核心点就在于 1,判空,2,找到开始节点的前一个节点,再找到结束节点的后继,关于指针移动如何判空问题,是个很重要的问题。
# 91: 解码方法: 关于解码,读取字符串的,大多都是动态规划或者是暴力深搜+回溯.此题更像是一个爬楼梯问题,状态表示是:所有前i个字符可以解码回去的字符串集合。状态计算是:当前的解码可以是从前一个字符而来,也可以通过前两个字符得来。
# 90: 子集II: 关于子集的题,实际也是一场深度搜索题,关键点在于由于集合里面没有顺序,因此我们要人为的安排顺序,而采取的方式方法是我们通过排序后,在同样的数进行选择的时候对此有个计数,再进行深度搜索下去。
# 89:格雷编码: 格雷编码定义是n位编码序列要求相邻两个编码在二进制表示上只有一位不同,如何实现此呢,可以通过对称实现,n = n + 1 时将当前的序列对称复制后,在前半段+0,后半段+1。
# 88: 合并两个有序数组: 合并两个有序数组是归并排序的最核心代码部分。其实和链表的合并是一样的。就是每次比较头部较小者用于存储到新的数组或者当前数组中。
# 87: 扰乱字符串: 扰乱字符串,实则也是一个动态规划问题,遇事不决,动态规划。状态表示:字符串s[i, i + k - 1 转化成字符串t[j, j + k - 1] 的方案的集合; 状态计算:因为s与t要最终相等,说明此部分匹配,另外一部分也要匹配。
# 86: 分隔链表: 分割链表:就是遍历一边
# 85: 最大矩形: 此题实际是最大矩形的进一步,增加了一个求解每个数能到达的最大高度,再通过单调栈找到一个左边能到达最大高度,右边能到达最大高度,再求矩阵面积
# 84: 柱状图中最大得矩形: 通过单调栈判断左边能到达得最大高度,再判断右边能到达得地方,找到宽,求面积。
# 83: 删除排序链表中得重复元素: 链表题一定要注意判空,还要注意此题是怎么删法。
# 82:删除排序链表中的重复元素II: 这里的链表判空,要引入一个哑节点,防止链表被删空;再进行删除的时候注意在纸上实现。
# 81:搜索旋转排序数组II: 旋转数组都是通过二分法来做,二分法模板提,但是此题拥有重复元素,需要在开始的时候做一个首尾去重
# 80: 删除有序数组中的重复项II: 有序数组中的重复项时,要求的是原地删除,而且每个元素最多出现两次,这个时候需要判断我要进行赋值的数是否已经大于等于2,之后才可以使用i-1,i-2
# 79: 单词搜索:此题是一个暴力搜索的题目。需要深度搜索+回溯。还有就是对方位的选择与判断,此时如果做回溯,记录现场和恢复现场。
# 78: 子集: 由于元素互不相同,可以通过状态压缩来做遍历,遍历后再取位。
# 77:组合: k个组合,深度搜索+回溯。注意点是判断起始位置与,满足个数
# 76:最小覆盖子串: 先通过一个先行变量i寻找到最大多存储的子串,再满足的时候,移动左位置。
# 75: 颜色分类: 颜色分类目的是考察三指针,怎么使用利用三个指针,前两个指针正向,最后一个指针反向遍历。
# 74: 搜索二维矩阵: 二维矩阵是一个有序的,这里考察的点就是对于坐标点的定位表示,实际还是一个二分模板;
# 73: 矩阵置零: 原地矩阵置零,的记录住需要被置零的行与列,因为不能够开辟空间,因此我们可以利用第一行,第一列,当然的先记录第一行第一列是否有0;
# 72: 编辑距离: 遇事不决动态规划, 闫式DP分析法,UESTC分教,教员申请出列,状态表示:将A串的1-i 变成B串1-j的所有按顺序操作的方案数集合,属性求最少的方案数。 状态计算: 要么A增,A删,A修.A的变动等同于B的反向动。
# 71: 简化路径: 对于Unix风格的绝对路径,对此进行简化,如何进行简化实则是一个逻辑判断题,逻辑能否理得清晰就能做好此题。判断逻辑,第一首先给最后加一个/,让分每次都能以/结尾一个状态. 利用一个串来装目录名,返回符,原地符。
# 70: 爬楼梯: 爬楼题就是一个斐波拉契数列,而斐波拉契数列可以通过动态规划来做,用记忆化搜索来确定最终值;
# 69:x的平方根: x的平方根,是浮点数二分;
# 68: 文本左右对齐: 首先得判断每行能容纳几个单词, 然后再判断是左右对齐,还是左对齐。左右对齐得方式需要注意的是最后一个单词是加不加间隔,如何来做这个判断,是单独做这个判断还是在添加的时候判断
# 67: 二进制求和: 二进制求和,实际和高精度求和一样,区别在于取模的地方不同。
# 66: 加一: 这是一道很简单的题目,但是得注意出现了情况,还是的按照高精度求法来做这题。
# 65: 有效数字: 有效数字 是怎么构成得,首先是有哪些规则, 得总结出规则,再对字符串进行判断,那么规则是怎么会是呢,遇到规则怎么遍历处理呢,
# 64: 最小路径和: 如何动态规划,就是说你首先的知道你可以从哪里来,到哪里去,找到来源只有两个来源,向下和向右;
# 63:不同路径II : 此题也是怎么表示来源
# 62:不同路劲: 此题知道来源,但是由于此题比较简单,直接可以通过状态计算得到,那我们得状态表示是什么呢,是从起点到i,j点所有路径得集合。
# 61: 旋转链表: 这里有一个取模,在遍历到开头点。
# 60: 排列序列: 排列顺序有两种方法一种是直接利用下一个排列来做,一个是直接手写全部排列的代码。先确定第一个位置,是可以排除出多少个需要遍历的,再确定第二个位置,以此类推,直到最后一个。
# 59: 螺旋矩阵II: 为什么总是有矩阵相关的题目呢, 到底是有啥应用场景吗? 是想考察我们的判断边界条件能力吗?核心点在于制定边界转移集合。
# 58: 最后一个单词的长度,首先将最后的空字符去掉,然后再从后面一直遍历到空字符
# 57: 插入区间: 排序,区间问题,依次遍历,直到遇到第一个右端点大于左端点,再到最后右端点大小于左端点,将其压入答案。
# 56: 合并区间: 排序,合并区间就是每次用一个左右值,来做暂存,如果出现一个左端点,大于右端点则合并,如果没有就压进去。
# 55: 跳跃游戏: 跳跃游戏是一个动态规划问题,也不算是动态规划,只需要满足的是,最远能够到达的下标。
# 54: 螺旋矩阵: 同样的方式制定遍历规则
# 53: 最大子数组和: 每加入一个数,如果这个数前面的子数组是小于0的就不要前面的子数组
# 52: N皇后II : N皇后问题,是怎么放置棋盘,但是放置期盼有一定规则,那么这个规则制定需要的是每个行每列每个对角线,来进行。可以采用的是深度搜索,+回溯, 再注意如何表示主对角线,副对角线。
# 51: N皇后: 同上是一样的,这里需要打印出结果,因此需要存储下矩阵。
# 50: Pow(x,n) 快速幂,快速幂的模板题,注意要将答案用ll,因为如果是最小的负数,那么绝对值过后会爆int
# 49: 字母异位词分组: 抓住都是同一个字符串,只需对字符串进行排序,然后按照ASCII码值相同,放入hash表中,再通过遍历哈希表输出结果
# 48: 旋转图像: 旋转图像,顺时针旋转,首先转置,然后再左右对阵交换:
# 47: 全排列 II: 这个全排列,里面包含重复数,因此首先对数组进行排序,排序完成后再利用我们常用的深度搜索+回溯,这里注意要使不重复,就必须得人为规定顺序,认为规定的顺序,需要找到起始位置,以及以已经完成了多少个。
# 46: 全排列: 全排列,深搜+回溯,如何回溯,这里有个问题如何回溯,这不是N皇后得回溯,也不是其他得需要记录点的回溯,这里是需要的记录下标,下标的回溯是可以通过bool数组来进行的。其实回溯的本质都是一样的,是记录状态
# 45: 跳跃游戏II : 最少能够跳到的位置,可以从每次跳最远只要能够超出的就+1
# 44:通配符匹配: 匹配问题很多都用到动态规划,状态表示:表示这个地方回顾不起来了,需要下来看看。
# 43: 字符串相乘: 字符串相乘,高精度乘法,第一用一个vector来存嘛,用一个t来存储进位。最后反转
# 42: 接雨水: 接雨水可以通过单调栈来做。通过单调栈,将找到一个矩形,进行累加
# 41: 缺失的第一个正数: 其实这提很难,很绕,绕在了我们如何利用下标计算,但是为什么这题那么火,考察智力与下标运算。
# 40: 组合总和II: 已经忘记此题啦!!!!! 看代码是通过深度搜索+ 回溯来做。但是让我想想,这不是像背包问题吗?多重背包问题
# 39: 组合总和: 这题像是完全背包问题,但是y总方法是通过深度搜索来的。 加回溯法来进行的
# 38: 外观数列: 遍历加计数;
# 37: 解数独: 数独需要判别是否放置,是哪个数放置了,怎样放置规则需要制定,首先肯定是深度搜索,深度搜索需要记录状态,记录状态后需要做得一件事情是恢复状态。
# 36: 有效数独,需要判别的是哪些能放,哪些不能放,需要判断是否能够满足行列小方格是否有效。
# 35: 搜索插入位置: 这题实际还会出现一个问题,如果插入位置是最后的一个位置,这个时候需要r为最后一个位置。
# 34: 在排序数组中查找元素的第一个和最后一个位置: 二分模板
# 33: 搜索旋转排序数组: 二分模板
# 32: 最长有效括号: 有效括号的性质,1,左括号数等于右括号数,2,左括号数大于等于右括号数。
# 31: 下一个排列: 寻找下一个排列,首先找到一个降序,通过降序然后找到峰顶的左边的第一个点,再在右边寻找到最小大于此数的数。
# 30: 串联所有单词的子串: 因为单词是固定长度的,所以我们可以将s串进行划分,通过窗口对比,作为hash的key值对比。
# 29: 两数相除: 注意爆int,因此要利用long long 来存。
# 28:实现strStr(): KMP的模板题;
# 27:移除元素: 就是遍历;
# 26: 删除有效数组中的重复项: 移动遍历;
# 25: K个一组翻转链表: 链表翻转需要找到三个一边尾巴,一边头,一个线段,要进行结合;
# 24: 两两交换链表中的节点: 不能修改内部值,这就需要画图;
# 23: 合并K个升序链表: 通过维护一个小根堆,每次寻找一个最小值。传入链表地址。
# 22: 括号生成: 括号匹配理论;
# 21: 合并两个有序链表: 和合并数组一样的做法;
# 20 : 有效的括号: 关于有效括号,我们可以通过栈来判断,利用栈顶与当前字符进行比较,如果ASCII码值能够小于2说明匹配,否则不匹配。
# 19: 删除链表的倒数第N个节点: 删除单数第N个节点就是正数第n-N +1 在下标表示实际就是n -N但是我们的找到前驱
# 18: 四数之和: 需要套3个循环,在最后一个循环做一个二分查找,还有一个剪枝操作。
# 17: 电话号码的字母组合: 首先判断来自哪个键,然后再深度搜索,不用回溯,是因为没有改变path的值。
# 16: 最接近的三数之和: 同四数之和,我们需要套2个外循环,然后再在最后一个循环做双指针查找;
# 15: 三数之和: 此题外加了一个去重要求,因为答案是不能有重复的数
# 14: 最长公共前缀,最长公共前缀实际也是一个遍历过程,如果出现了一个字符串不能提供相同的字符就需要返回结果
# 13: 罗马数字转整数,罗马数字转整数,需要做一个hash然后在遍历的时候注意此时的字符与下一个字符的大小,判断+与-
# 12:整数转罗马数字,整数转罗马数字是通过整数每次减去能表示罗马数字的最大度量,依次加下去,这个罗马数字需要做一个对应,不一定要hash因为这里可以通过遍历来省去hash的空间
# 11: 盛最多水的容器: 这里可以通过单调栈来判断横坐标长度,寻找最大值。
# 10: 正则表达式匹配: 动态规划,状态表示:
状态计算:
# 9: 回文数: 所有负数都不是回文数, 需要做除法,当剩余的数小于现在创建出来的新数的时候就退出,然后再返回。
# 8: 字符串转换整数(atoi): 就是一个遍历码?
# 7 : 整数反转: 先存下符号,然后再反转,关键在的点是反转这个东西,可能爆int,这时需要你先测试的时候打印出最大时多少,然后再排除不行的数返回0;
# 6: Z字形变换: 制定规则,什么规则就是
# 5: 最长回文子串:
# 4: 寻找两个正序数组的中位数, 寻找第k大的数
# 3: 无重复字符的最长子串: 开辟数组来节约时间。遇到大于的时候就往前移动
# 2: 两数相加: 创建新的节点来装,必要的时候再通过增加一个新的节点
# 1: 两数之和: 利用空间换时间,将数存入hash表中,然后每次往回回顾这样的hash是否存在。