- 博客(233)
- 收藏
- 关注
原创 力扣爆刷第107天之CodeTop100五连刷21-25
思路:本题要求每层先从左往右遍历,下一层从右往左,再往下一层又变成了从左往右遍历,就是这种交替遍历,其实层序遍历的方式我们不需要改变,只需要改变记录的方式,对于每层出队节点收集时,如果该层是要求正序,那么把元素从尾部添加进新队列,如果该层要求逆序,那就从头部添加进队列,因为尾插法是正序,头插法是逆序,遍历后,然后再把收集到的数据添加进总集合中即可。题目链接:https://leetcode.cn/problems/intersection-of-two-linked-lists/description/
2024-03-28 22:58:26 178
原创 力扣爆刷第106天之CodeTop100五连刷16-20
题目链接:https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/题目链接:https://leetcode.cn/problems/merge-sorted-array/description/题目链接:https://leetcode.cn/problems/linked-list-cycle/description/思路:遇到左括号,添加右括号,如果是右括号,栈为空报错,栈非空看栈顶,不同报错。
2024-03-28 00:11:57 274
原创 力扣爆刷第105天之CodeTop100五连刷11-15
对于不持有可以是之前就不持有了,也可以是今天才持有的。那么本题就可以不停的二分,然后进入其中的顺序区间,看看target是否在这段顺序区间内(通过两端数值即可判断),在的话就往其内移动指针,不在就往反方向移动指针,即可。题目链接:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/思路:求最长回文子串,要以单点为中心或以双点为中心,向左右进行扩散,然后遍历字符串,在每一个点位上向两边进行扩散,然后记录即可。
2024-03-27 00:06:18 556
原创 力扣爆刷第104天之CodeTop100五连刷6-10
动态规划,定义dp[i]表示在区间nums[0, i]中,以nums[i]为结尾的最大子数组的和,那么对于每一个dp[i]来说,它都可以选择把nums[i]是否追加到子数组的结尾,这个就是状态与选择,选择的条件是最大子数组的和,这一句话就把动态规划讲透了。题目链接:https://leetcode.cn/problems/merge-two-sorted-lists/description/题目链接:https://leetcode.cn/problems/two-sum/description/
2024-03-25 23:00:12 469
原创 力扣爆刷第103天之CodeTop100五连刷1-5
题目链接:https://leetcode.cn/problems/kth-largest-element-in-an-array/description/思路:非常经典的题目,最近最少使用,我们需要构建一个双向链表和哈希表,其中双向链表应该有虚拟的头结点和尾结点,方便进行添加删除操作,其他的是常规操作。题目链接:https://leetcode.cn/problems/reverse-nodes-in-k-group/description/
2024-03-23 23:32:39 518
原创 力扣爆刷第102天之hot100五连刷96-100
思路:求下一个排列,是求下一个最小的大于它的值,基本原理从下图的5, 7, 6, 4处进行寻找,寻找最小的一个大于它的数,自然要从右边开始找,找第一个凹陷处,nums[i] < nums[i+1],此时i= 5,然后再从右边找第一个大于5 的数,为6,也就是nums[j]>nums[i],此刻这个6就是最小的一个大于它的数,然后交换,交换后[i, end]为单调递减,然后翻转即可。题目链接:https://leetcode.cn/problems/single-number/description/?
2024-03-21 22:35:48 602
原创 力扣爆刷第101天之hot100五连刷91-95
思路:求最长公共子序列,如text1 = “abcde”, text2 = “ace” ,定义dp[i][j]表示区间[0, i] 和区间[0, j]中以text1[i]和text2[j]字符为结尾,如果二者相等则 dp[i+1][j+1] = dp[i][j] + 1;,如果不等,可以考虑从左边,上边,左上角。思路:求不同路径,任意一个位置都可以从它的上方和左方推出,也就是dp[i][j] = dp[i][j-1] + dp[i-1][j],压缩数组为dp[j] = dp[j] + dp[j-1];
2024-03-20 23:14:08 636
原创 力扣爆刷第100天之hot100五连刷86-90
每一个dp[i]由三种装填推出。思路:定义dp[i]表示字符串s[0, i]可以被拼接出,那么如果要推导出当前s[0,i]可以被拼出,只需要,s[0, i-word.length]可以被拼出,且s[i-word.length] == w,即可推出,此即为递推公式。思路:定义dp[i]表示区间[0, i]以nums[i]为结尾的最长递增子序列的长度,那么如果nums[i] > nums[j],故 dp[i] = Math.max(dp[i], dp[j]+1);思路:使用动态规划做时间超了,可以使用栈做。
2024-03-19 23:59:17 477
原创 力扣爆刷第99天之hot100五连刷81-85
思路:定义dp[i]表示正数i所需的最少完全平方数为dp[i],那么对于每一个dp[i],我们从i值向后找,减去一个完全平方数看看是否存在,存在就在上一个位置加1,如dp[12]=dp[8]+1, dp[8]=dp[4]+1,dp[4] =dp[0]+1,dp[0]=0。思路:典型的动态规划,当前的状态依赖于当前与前一个位置,newDp[i]=dp[i]+dp[i-1],之后再交换newDp与dp避免数据覆盖。偷:需要间隔一间,dp[i] = dp[i-2] + nums[i]。
2024-03-18 23:24:00 404
原创 力扣爆刷第98天之hot100五连刷76-80
思路:求数据流的中位数,构造数组需要考虑排序,使用优先级队列可以保证排序,可以将整个有序序列从中间划分,分为大顶堆和小顶堆,我们只需要维护大顶堆和小顶堆的size相差不超过一,那么多出一个元素的即为中位数,相等加和除二也是中位数,另外就是要维护好大顶堆里的数都小于小顶堆里的数,所以要保证这个,就要如果想往大顶堆里加数,就得先把数加入小顶堆,然后再把小顶堆的栈顶元素添加到大顶堆中,这样就可以保证有序性。
2024-03-17 16:53:39 722
原创 力扣爆刷第97天之hot100五连刷71-75
题目链接:https://leetcode.cn/problems/kth-largest-element-in-an-array/description/?题目链接:https://leetcode.cn/problems/largest-rectangle-in-histogram/description/?题目链接:https://leetcode.cn/problems/top-k-frequent-elements/description/?
2024-03-16 21:42:03 391
原创 力扣爆刷第96天之hot100五连刷66-70
思路:仔细看会发现不管旋转多少次,旋转之后都是下面的这种情况,即左边整体高于右边,那么要寻找最小值,只需要二分逐段缩小区间,至于如何缩小,请注意nums[right]一定小于nums[left],求出中值后,如果nums[right]>nums[mid]就说明中值靠左,右边不要了,更新right=mid,如果nums[right]<=nums[mid]说明中值靠右,只有nums[mid]小于nums[right]才可能出现最小值,所以更新left=mid+1.
2024-03-15 21:09:43 763
原创 力扣爆刷第95天之hot100五连刷61-65
题目链接:https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/?思路:分别搜索左边界和右边界}else {left : -1;
2024-03-14 18:47:49 496
原创 力扣爆刷第94天之hot100五连刷56-60
题目链接:https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/?题目链接:https://leetcode.cn/problems/word-search/description/?思路:集合元素无重,要求元素可复用,那么需要索引位置,又因为可复用,无需加1,然后掌握一点早停的策略。思路:子集问题,本题集合元素无重,要求搜集所有子集,很简单,递归有起始索引,然后搜集所有节点。
2024-03-13 15:55:37 441
原创 力扣爆刷第93天之hot100五连刷51-55
题目链接:https://leetcode.cn/problems/implement-trie-prefix-tree/description/?题目链接:https://leetcode.cn/problems/number-of-islands/description/?思路:根据题目要求需要构建邻接表,然后我们要判断邻接表是否成环,visited数组使用来记录访问过的节点,避免重复访问,flags数组是用来记录从任意一个节点出发是否成环,如果成环则无法完成课程表。
2024-03-12 17:30:55 311
原创 力扣爆刷第92天之hot100五连刷46-50
题目链接:https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/?题目链接:https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/?题目链接:https://leetcode.cn/problems/path-sum-iii/description/?
2024-03-11 16:27:02 552
原创 力扣爆刷第91天之hot100五连刷41-45
题目链接:https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/description/?题目链接:https://leetcode.cn/problems/kth-smallest-element-in-a-bst/description/?题目链接:https://leetcode.cn/problems/binary-tree-right-side-view/description/?
2024-03-10 18:31:55 402
原创 力扣爆刷第90天之hot100五连刷36-40
题目链接:https://leetcode.cn/problems/binary-tree-inorder-traversal/description/?题目链接:https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/?题目链接:https://leetcode.cn/problems/diameter-of-binary-tree/description/?思路:前序遍历,然后逐个交换节点左右子树即可。
2024-03-09 17:12:04 564
原创 力扣爆刷第89天之hot100五连刷31-35
思路:最近最少使用,get或put都会是得该元素优先级最高,容量满了就要把最久未使用的给去掉,那么可以利用LinkedHashMap的特性,底层采用哈希表和双向链表,put方法加入的元素永远在链表的最后,最先添加进来的在头结点,所以可以使用Integer first = map.keySet().iterator().next();题目链接:https://leetcode.cn/problems/copy-list-with-random-pointer/description/?
2024-03-08 16:56:52 414
原创 力扣爆刷第88天之hot100五连刷26-30
思路:本题让求环形链表的入口,根据一个数学推论,使用快慢指针,慢指针每次走一步,快指针每次走二步,相遇便说明有环,此时从头结点到达环入口节点的距离是等于从相遇节点到入口节点的距离的,然后让其中一个指针指向头结点,另一个指针从相遇节点出发,再次相遇便是入口。题目链接:https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/?
2024-03-07 15:33:08 290
原创 力扣爆刷第87天之hot100五连刷21-25
思路:从横向递增纵向递增的矩阵中搜索target,利用顺序的特性,从矩阵的右上角进行搜索,如果相等就返回,如果大于向下进行搜索,如果小于向左进行搜索,存在的话自然可以找到,不存在的话会一直搜索到边界才会停止,也就是当前算法还有改进的空间,可以采取早停措施。题目链接:https://leetcode.cn/problems/intersection-of-two-linked-lists/description/?
2024-03-06 15:50:34 430 1
原创 力扣爆刷第86天之hot100五连刷16-20
思路:求缺失的第一个正整数,可以利用数组的索引,构造成哈希表,数组长度为N,如果nums中的数值都在[1, N]之中,那么缺失的第一个正数为N+1,如果不是,那么我们把所有的负数都给处理为N+1,让其不参与后续步骤,然后检查所有数值的绝对值,绝对值只要小于等于N+1,就将对应索引位置的数值改为负数,作为出现的标记,之后,只需要从头往后遍历,第一个大于零的即为缺失的第一个正整数。题目链接:https://leetcode.cn/problems/set-matrix-zeroes/description/?
2024-03-05 16:55:26 482
原创 力扣爆刷第85天之hot100五连刷11-15
思路:求滑动窗口内的最大值,自然要维护一个滑动窗口,这里我们使用一个队列来表示滑动窗口,既然要记录最大值,那么我们在添加元素时,自然要如果队尾元素小于当前元素,队尾元素就应该出队,直到没有小于当前元素的存在,然后把当前元素入队,这样队头位置就是滑动窗口内的最大值。题目链接:https://leetcode.cn/problems/sliding-window-maximum/description/?
2024-03-04 16:50:31 1789
原创 力扣爆刷第84天之hot100五连刷6-10
思路:一看是异位词基本上就得使用set或map来处理,字符串的长度又巨长,10的4次方,常规遍历自然超时,需要使用双指针去掉一层循环,即使用滑动窗口,维护好字符串窗口,开始时扩大窗口,顺便记录标记值,当窗口达到p字符串长度时,进行判断,看看标记值是否符合,然后缩减窗口,这样一次循环结束。题目链接:https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/?杜绝相同的nums[i]。
2024-03-02 22:03:23 653
原创 力扣爆刷第83天之hot100五连刷1-5
思路:本题是乱序的数组,求最长的连续序列,如{4, 3, 100, 1, 2}最长连续序列长度是4,即为1,2,3,4,这种和动态规划中求最长递增子序列,最长重复子序列还不同,明显是无需的序列,还需要把无需给理顺了,题目要求O(n),自然不能排序,数值范围10的9次方,自然不能用数组遍历,这种情况下就应该考虑hashset了,把所有元素添加set之后遍历,只有当前元素是序列的起始元素才会向下求长度,只要不是起始元素,就不进入while,正好所有元素只遍历一遍,时间复杂度为O(n)。
2024-03-01 17:08:56 610
原创 力扣爆刷第82天--单调栈一网打尽
思路:本题刚好和上一题相反,本题需构造凸型,当元素小于栈顶时出栈,即可使得 stack顶下一个元素,stack元素,当前元素,构成凸型,初始状态只计算栈顶这一列,当有元素再出栈时,宽度就会随i - stack.peek() - 1;思路:利用单调栈栈内单调的特性结合大于栈顶的元素构造出凹槽,即 stack栈顶下第一个元素,stack栈顶,大于栈顶的元素,3者构成一个可以接雨水的凹槽。题目链接:https://leetcode.cn/problems/next-greater-element-i/
2024-02-27 19:54:49 313
原创 力扣爆刷第81天--动态规划一网打尽字符串删除和回文子串
思路:求两个字符串经过最少的删除操作,使得两个字符串相等,初始化要格外注意,定义dp[i][j]表示区间word1[0,i]和区间word2[0,j]相等所需要的最少的删除操作,那么如果word1[i]==word2[j]说明不需要删除,直接延续上一个位置,即dp[i][j]=dp[i-1][j-1],如果word1[i]!举一个替换的例子,dp[1][1]时,h和r不等,可以考虑替换,从dp[0][0]+1可达到。输入:word1 = “horse”, word2 = “ros”
2024-02-26 23:12:15 625
原创 力扣爆刷第80天--动态规划一网打尽子序列一维二维连续不连续变体
今天也是子序列的一天,但和上一期不同的是都是变体,也分为一维、二维、连续、非连续四种题型。另外就是做子序列相关的题目一定要考虑好定义以后就使用实例自己推导一下,把结果展现出来,然后再看看能否推导出递推公式或者看看递推公式是否匹配。
2024-02-25 16:47:35 848
原创 力扣爆刷第79天--动态规划一网打尽子序列一维二维连续不连续问题
今天的专题是子序列问题,有一维的,也有二维的,有求连续的,也有求不连续的,组合是四种类型,且看一网打尽。
2024-02-24 21:23:30 1198 1
原创 力扣爆刷第78天--动态规划买卖股票一网打尽
但凡是买卖股票相关的题目,定义dp[i]时,每天都有两种状态,持有股票和不持有股票,然后对这两种状态进行处理即可得到答案,所谓的持有股票,可以是之前就持有,也可以是今天才持有;所谓的不持有股票,可以是之前就不持有,也可以是今天才持有。把握住这个思想,所有的买卖股票题目迎刃而解。
2024-02-23 14:59:42 377
原创 力扣爆刷第77天--动态规划一网打尽打家劫舍问题
思路:本题和上一题不同之处是房间首尾相连,那么也很简单,直接从两个范围求,第一个范围[0, len-1], 第二个范围[1, len],分别从这两个范围,一个只含头,一个只含尾,其他的和上一题一样。思路:二叉树形态的打家劫舍,其实也很简单,每个节点有两种状态分别是抢不与抢,后序遍历返回dp数组,有了左右子树的dp数组即可计算当前节点的dp数组,计算后返回,以此递归即可解题。题目链接:https://leetcode.cn/problems/house-robber-iii/description/
2024-02-22 11:36:51 281
原创 力扣爆刷第76天--动态规划完全背包和多重背包
思路:本题让使用单词拼接成字符串,单词可以重复使用,问能否拼接出来,要看出题目的本质,拼单词的过程类似于往背包中装东西,只不过要求顺序,和爬楼梯一样,需要顺序,故本题是一个典型的完全背包求排序,明白了这点,本题非常好做,定义dp[i]表示[0, i]可以被单词拼接,那么只要dp[i-word.length()]=true,且s.substring(i-w.length(), i) == word,即可推出dp[i]=true,从而递推公式也有了。
2024-02-21 15:08:41 353
原创 力扣爆刷第75天--动态规划完全背包组合数与排列数5题
思路:本题是完全背包,求组合数,不过求的是放入物品数量最少的组合数,定义dp[j]表示,填满容量为j的背包所需最少物品的数量为dp[j],递推公式为dp[j] = Math.min(dp[j], dp[j-coins[i]] + 1);思路:本题是每次可以爬k个台阶,1<=k<=m,问有多少种爬到楼顶N的方法,1,2和2,1自然不同,本题是一个完全背包求排列数,很简单背包在外,物品在内,不过题是卡码网上的,需要自己写输入输出,可以练习一下。完全背包遍历顺序:物品背包没有先后顺序,物品背包都是正序。
2024-02-20 11:42:53 882
原创 力扣爆刷第74天--动态规划01背包
思路:求目标和的组合数,把物品里的元素分为左右两堆,left+right=sum,left-right=target,两式相加可以得到left = (sum + target)/2,那么题目就转变成了,从物品中挑选元素把容量为left的背包填满有多少种元素组合,这求的是组合数,定义dp[j]表示,把容量为j的背包填满有dp[j]种方法。题目链接:https://leetcode.cn/problems/ones-and-zeroes/description/
2024-02-19 11:29:25 216
原创 力扣爆刷第73天--动态规划
题目链接:https://leetcode.cn/problems/last-stone-weight-ii/description/思路:本题说石头之间两两抵消,求最后余数,其实就是把石头划分为两堆,然后计算差值,差值即为最后一块石头的重量,那么求一半和的背包问题,即可。
2024-02-18 11:15:39 273
原创 力扣labuladong一刷day72天动态规划
那么定义dp[i]表示整数i拆分得到的最大和,由此我们可以知道,从2开始都可以被拆分为两数之和,三数之和,等等,对于任意一个i,(i-j)*j是两数之和,dp[i-j]*j就最起码是三数之和了(dp[i-j]的定义就是拆分最大乘积和最起码是拆成两个数),由此可以确定递推公式dp[i]=max( (i-j)*j, dp[i-j]*j )。题目链接:https://leetcode.cn/problems/unique-binary-search-trees/description/
2024-02-03 17:32:19 253 1
原创 力扣labuladong一刷day71天动态规划5题
思路:定义dp[i]表示爬到第i个楼梯,有dp[i]种方法,因为一次只能爬1或者2个台阶,那么要想抵达dp[i]就要么从dp[i-1]要么从dp[i-2]出发,从dp[i-1]只需要一次走一个台阶即可,从dp[i-2]只需要一次走2个台阶即可,dp[i-2]不能连续走两个1这样会和dp[i-1]重复,故递推公式为dp[i]=dp[i-1]+dp[i-2]。题目链接:https://leetcode.cn/problems/min-cost-climbing-stairs/description/
2024-01-30 11:30:00 360
原创 力扣labuladong一刷day70天回溯大集合
题目链接:https://leetcode.cn/problems/sudoku-solver/description/思路:n皇后问题,利用回溯来搜索正确答案,每次向下递归都是新的一层,进入递归之前都会做是否可以作为皇后的判断。思路:思路和n皇后类似,不过为了避免结尾搜集元素要copy数组,可以使用带返回值的回溯,搜索到答案后返回。题目链接:https://leetcode.cn/problems/n-queens/
2024-01-29 23:30:49 214
原创 力扣labuladong一刷day69天回溯大集合
思路:本质上还是回溯题,依然是带有排序的性质,for循环不需要起始位置,先把数组按照字典序排序,然后第一次找到行程后直接早停,即可完成该题,不过目前使用递归超时了,只能用优先级队列了。题目链接:https://leetcode.cn/problems/reconstruct-itinerary/description/采用优先级队列和深度优先。
2024-01-27 15:56:48 125
原创 力扣labuladong一刷day68天回溯大集合
这个去重策略只能是排序后,让重复元素都挨着才能用。思路:排列问题,和组合问题还不一样,排列问题不需要indexStart,也就是for循环是固定的0到结束,但是纵向需要去重,避免使用重复元素,这时可以使用used数组,标记为true即跳过,只有向下递归才会遇到重复元素跳过,横向是没有重复元素的。思路:nums = [1,1,2]本题包含重复元素,又是排序,所以,不光要纵向去重,也需要横向去重,纵向去重使用used数组,横向去重需要排序,而且used[i-1]为false,即可起到去重的效果。
2024-01-26 15:46:32 238
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人