LeetCode刷题记录

题号 思路 时间
8. String to Integer (atoi) 没想到有限自动机,写的太臃肿,边界条件考虑的也不足,用DFA分析起来就会很舒服 2020.4.3
11. Container With Most Water 看题解,双指针 2020.4.18
20. Valid Parentheses 简单的栈应用题 2020.8.14
21. Merge Two Sorted Lists 简单的归并,题解中有递归 2020.5.1
22. Generate Parentheses 看题解,动态规划:(a)b
"("+generateParenthesis(i/2)+")"+generateParenthesis(n-1-i/2)) i从1到2n-1递增2
或DFS搜索剪枝
2020.4.9
23. Merge k Sorted Lists 仿照归并排序;用优先队列降低复杂度 2020.4.26
28. Implement strStr() KMP实现字符串匹配
小错误:string.length()返回的是size_t无符号整数,在有-1哨兵时比较有问题
参数调用vector若想改变请&引用,时刻要考虑传进来的参是NULL或者""的情况
2020.3.6
32. Longest Valid Parentheses 看的题解,把问题想简单了,对情况的考虑不足,对作废右括号的位置没有记录和思考;动态规划没有想到,对))和()分析不足;也没有想到双指针 2020.7.4
33. Search in Rotated Sorted Array 复杂一点的二分 2020.4.27
42. Trapping Rain Water 用stack AC;题解中双指针:如果右边的某个柱子(最高柱)比左边高,那么该位置的水位由左边决定,反之同理。 2020.4.4
43. Multiply Strings 字符串相乘,模拟大整数过程,第一次想的太简单,写了数字转化,看了题解自己写完了竖式模拟 2020.8.13
44. Wildcard Matching 错了12次,一开始把一个分支的任务分的过细,导致修修补补都不能完成,最后还是要回到最简单的处理方案+边界条件处理;题解中有动态规划状态转移方法,便于理解;题解中的贪心算法跟原本思路类似 2020.7.5
46. Permutations 全排列;复习搜索和字典序 2020.4.25
55. Jump Game 维护最远可达的距离 2020.4.17
56. Merge Intervals 合并线段 2020.4.16
63. Unique Paths II 简单的动态规划题,题解用了滚动数组即用一个数组f[m]直接保存所有信息,当f[j]没计算前,保存的是f[i-1][j],计算式为f[j] = f[j-1] + f[j]; 等价于f[i][j] = f[i][j-1] + f[i-1][j] 2020.7.6
72. Edit Distance 看题解,动态规划,“horse”->"ros"相当于下面三种可能的最小值:
“hors”->“ros”+1(horse删除) 或
“horse”->“ro” + 1 (horse增加) 或
“hors”->“ro” + (word1[4]==word[2])? 0 : 1
2020.4.6
93. Restore IP Addresses 好久没写了,简单的搜索写的不是很顺畅,好好补补题解,这题不能有前导零 2020.8.9
110. Balanced Binary Tree 迷惑了很久为什么是Easy,写的求高,然后BFS判断是否是AVL子树,看题解为从上到下或者从下到上,从下到上是判断该子树是否AVL,如果不是AVL,就传递一个-1树高向上,出口为根节点的高度是否非负 2020.8.17
112. Path Sum 简单题,递归开头还是写复杂了,后来看了题解完善的写法,BFS用的两个队列,简单的搜索 2020.7.7
121. Best Time to Buy and Sell Stock 计算一个序列中后者相对前者的最大差值,标准题解是滑动窗口并在每次滑动时判断是否需要更新 2020.3.9
124. Binary Tree Maximum Path Sum 递归,递归解决单边贡献问题,用ans实时保存最大值 2020.6.21
130. Surrounded Regions 搜索题,写的DFS 2020.8.11
133. Clone Graph DFS , BFS
用Map来记录是否访问
BFS需要用queue来控制过程
2020.3.2
138. Copy List with Random Pointer 类图的拷贝,题解习惯使用原节点和新节点的dic来控制过程 2020.3.5
139. Word Break 原来写了暴力搜索,应该采用动态规划,或者记忆化的搜索,【手绘图解】三种方法及其优化:DFS、BFS、动态规划题解中的memo应该指的是从Start(index)往后的字符串可以匹配成功 2020.6.25
151. Reverse Words in a String 自己写的递归,题解有全部装到双端队列或者栈里,再掏出来 2020.4.10
167. Two Sum II - Input array is sorted Easy题,写的二分,题解中为双指针 2020.7.20
169. Majority Element 众数(个数大于 ? n 2 ? \lfloor \frac{n}{2} \rfloor ?2n??)复习题,算法:1.哈希表记录个数 2.排序 3.随机抽取 4.总众数必然为总体两半其中一半的众数 5.Boyer-Moore 投票算法 2020.3.13
174. Dungeon Game 反向dp,思路很有意思,看了题解 2020.7.12
199. Binary Tree Right Side View BFS提交成功 看了一遍DFS的题解 2020.4.22
200.岛屿数量 并查集,DFS, BFS 2020.1; 2020.4.20(看题解)
202. Happy Number 写的用哈希表查找循环 2020.4.30
209. Minimum Size Subarray Sum 前缀和+双指针滑动窗口,题解中有二分的方法,以后要学会思考这种思路 2020.6.28
215. Kth Largest Element in an Array 快排方法,写法还不够熟悉,要加强练习 2020.6.29
300. Longest Increasing Subsequence 看题解,想不到 O ( n l o g n ) O(nlogn) O(nlogn)
动态规划 O ( n 2 ) O(n^2) O(n2):维护一个dp[i]数组,记录以num[i]结尾的最长子序列的长度,公式 d p [ i ] = m a x ( d [ j ] ) + 1 , 0 ≤ j < i 且 n u m [ i ] > n u m [ j ] dp[i]=max(d[j])+1,0\le j < i且num[i]>num[j] dp[i]=max(d[j])+1,0≤jnum[j]
贪心+二分查找 O ( n l o g n ) O(nlogn) O(nlogn):维护数组d[i]:当前长度为i的单调增子序列末尾最小的值(可能有当前有很多个长度为i的子序列 选择末尾最小的那个子序列)
2020.3.14
312. Burst Balloons 不会做,以为是个贪心,最后是个记忆化搜索,逆向思维的记忆化搜索,看的题解 2020.7.19
315. Count of Smaller Numbers After Self 学习树状数组,logn时间内完成查询和访问,保存的是前缀和,先把原数组离散化排序,降低维度,然后用树状数组维护前缀和,降低复杂度 2020.7.11
322. Coin Change 第一次接触动态规划,把大问题分解为小问题+常数,自顶向下或自底向上求解都可,F(amount)表示amount需要F(amount)个硬币,F(a)=F(a-c)+1; c为币值 2020.3.8
355. Design Twitter 存一列消息,再存一列用户(用户自己管理自己的FOLLOW) 2020.4.13
365. Water and Jug Problem 两个水桶x,yL;能否衡量出zL水。好好学习题解:1.搜索 记录两个水桶的状态DFS看会不会出现zL水(排除重复)2.数学方法:先想出每次操作水总量只会变化x,yL;然后ax+by=kgcd(x,y) 即如果z为gcd的倍数,那么就可以用ax+by描述 2020.3.21
378. Kth Smallest Element in a Sorted Matrix 重写了一遍归并,注意优先队列的自定义用法,没注意到题目中列也排序好了,题解中有二分的方法 2020.7.2
409. Longest Palindrome 水题,第一遍没写对,没有考虑奇数个的数字也能-1变成偶数个使用 2020.3.19
445. Add Two Numbers II 反链表相加两数,用栈 2020.4.14
460. LFU Cache 页面淘汰算法:最不经常使用算法。看题解,哈希储存,平衡二叉树找最不常用。或用两个哈希,一个以频率为key装双向链表,链表头为最近使用,链表尾为最远使用,一个哈希以key为key,存放双向链表内存地址 2020.4.5
466. Count The Repetitions 自己试着写了写,方向不对,题解在于找循环节,即要弄清楚S1的循环情况,S2的循环情况不太重要 2020.4.19
542. 01 Matrix 多源最短路,这里写了动态规划 2020.4.15
543. Diameter of Binary Tree 水题,但有坑,题目要求是求任意两个节点间的最大距离,要同时维护路径最大值和每个节点的(最大)高度 2020.3.10
546. Remove Boxes hard,本来以为是对区间搜索,看了题解发现是动态规划,即对搜索空间没有想清楚,请多复习这题 2020.8.15
572. Subtree of Another Tree 写的递归,没有优化;题解里有哈希有空看看 2020.5.7
695. Max Area of Island DFS,BFS复习题,求最大的岛屿面积 2020.3.15
696. Count Binary Substrings 蛮简单的一道题,写复杂了 2020.8.12
718. Maximum Length of Repeated Subarray Medium的题,第一遍想到动态规划了,没想清怎么写不应该,看了题解重写的。题解中的滑动窗口还需要再想想。研究一下哈希的逻辑,大概看懂了 2020.7.1
733. Flood Fill 搜索题 2020.8.16
820. Short Encoding of Words 暴力法超时,字典树(或者用倒转过来的字典序) 2020.3.28
836. Rectangle Overlap 两个矩形是否重叠问题,给两个矩形的左下右上各两个坐标(共4个),没有精确找到问题本质,也没有找反方向。问题本质:投影到x,y轴上判断边投影是否重叠;反方向:不重叠的时候必然有一条与x或y轴垂直的线分开两个矩形 2020.3.18
876. Middle of the Linked List 快慢指针 2020.3.23
887. Super Egg Drop 题意见李永乐老师视频,动态规划,要优化,相当于两个函数找相交的最低点,二分查找。或者题解中的决策单调性 2020.4.11
892. Surface Area of 3D Shapes 统计表面积,做加法或做减法,在投影的方法的纠结过久,直接关注表面积怎么消失的就好了 2020.3.25
912. Sort an Array 排序练习,写了一个快排,有小细节没有弄好 2020.3.31
914. X of a Kind in a Deck of Cards 计数没有简单方法,要注意这里用的是最大公约数 2020.3.27
945. Minimum Increment to Make Array Unique 暴力没过,优化是还是要牺牲空间,并且优化数学算法,以 [1, 1, 1, 1, 3, 5] 为例,当我们发现有 3 个重复的 1 时,我们先将操作次数减去 1 + 1 + 1。接下来,当我们发现 2,4 和 6 都没有出现过时,我们依次将操作次数增加 2,4 和 6 2020.3.22
999. Available Captures for Rook 水题,然后请学会使用方向数组,写四个while循环也太傻了 2020.3.26
1013. Partition Array Into Three Parts With Equal Sum 求和,拆三部分,i从头,j从尾求和,当两部分都为总和的 1 3 \frac{1}{3} 31?时,true
没有想到优化方法
2020.3.11
1071. Greatest Common Divisor of Strings 看了题解,str1=nX,str2=mX; 即X.len = gcd(str1.len,str2.len),用最大公约数来检验;数学优化方案:如果 str1 和 str2 拼接后等于 str2和 str1 拼接起来的字符串(注意拼接顺序不同),那么一定存在符合条件的字符串 X。必要性易证,充分性考虑gcd长度的字符串在两种拼接方式中发挥的作用和位置 2020.3.12
1103. Distribute Candies to People 简单的等差数列计算问题,在多行时讨论过久浪费时间,需要更关注整体效果 2020.3.5
1111. Maximum Nesting Depth of Two Valid Parentheses Strings 题干讲的太差了,就是有效括号对,分成(可以交叉的)两块,总深度是他们俩的最大值,求深度最小的分类 2020.4.1
1160. Find Words That Can Be Formed by Characters 题目不难,不过要注意过度依赖STL耗时和内存都比较高,提交的题解中设计的哈希表就可以用数组代替 2020.3.17
1162. As Far from Land as Possible 多源最短路,提交写的多源BFS,题解中有动态规划 从左上到右下一次遍历,从右下到左上第二次遍历(在同一个函数数组上) 2020.3.29
1248. Count Number of Nice Subarrays 写的奇数位置记录;考虑了前缀和但是找不到优化方法;题解中用记录频率来优化 2020.4.22
5179. Balance a Binary Search Tree 把任意的二叉搜索树重构为AVL,大佬题解是先中序遍历,然后mid=l+r>>1为根节点,左l,mid-1右mid+1,r重构;一直在思考有没有在原基础上重构的方法(暂没有),消耗了太多时间 2020.3.15
5185. Three Consecutive Odds 简单统计题,签到 2020.8.16
5352. Generate a String With Characters That Have Odd Counts 水题
做题时考虑过多,而且一直在想着二分,奇+奇=偶=偶+偶,在这两种情况里纠缠过久,题目可以显而易见的分为奇=奇+0 偶=奇+1
2020.3.8
5353. Bulb Switcher III 此题在分析时有了较好的思路,因为没有重复的映射即有关灯操作,那么当当前开着的灯中序号(n)最大的前面有n-1个灯开着的时候就会出现一次全蓝,那么问题就变成了统计n之前有多少个灯亮着,如果有比n大的灯被点亮那么更新n并继承之前统计的小序号灯亮的盏数 2020.3.8
5354. Time Needed to Inform All Employees 类似于求最大加权子树高度,自底向上更新节点的最大加权子树高度,可剪枝(放弃已通过之前父子关系访问过的父子关系,若子树根节点高度不增加,则不用向上传递) 2020.3.8
5355. Frog Position After T Seconds 不含环的图,求并记录最短路径,比较路径长和可移动的步数,小心讨论特殊情况 2020.3.8
5356. Lucky Numbers in a Matrix lucky==当前数为这列最大,这行最小;记录每列最大数和每行最小数,看看是不是同一个 2020.3.15
5357. Design a Stack With Increment Operation 设计一个可以增量的stack(从bottom向上k个元素增加val),可以通过数组来实现,优秀题解设计了一个数组inc记录增量位置和增量val,inc[i]=val,当pop到i位置时,输出stack.pop()+inc[i],并让inc[i-1]+=inc[i],保留这个增量能继续为栈内的数据服务 2020.3.15
5359. Maximum Performance of a Team Output=sum(speed)*min(efficiency),先绑定每个engineer的speed和efficiency,然后根据efficiency从大到小排序,从0到n,用优先队列来找出k+1个中的最小值剔除,并维护一个最大的output 2020.3.15
5488. Minimum Operations to Make Array Equal 数学规律题 2020.8.16
5489. Magnetic Force Between Two Balls 二分搜索解空间,这种题目的思路都在于 有一个解空间,然后二分,检查当前的mid是否满足要求,然后继续在left与mid-1和mid+1与right之间寻找 2020.8.16
5490. Minimum Number of Days to Eat N Oranges 递归搜索,map记忆化 2020.8.16
面试题13. 机器人的运动范围 想着可能会有从右从下两个方向,其实好像没有,不可以访问的地方视为障碍物,dp做的 2020.4.8
面试题40. 最小的k个数 k选择问题:1.排序 2.维护k大小的堆 3.快速排序原理 4.这道题数据有范围恰好可以计数排序 2020.3.20
面试题51. 数组中的逆序对 写的归并排序,要注意不是原地排序;建立线段树,记录从后到i有多少个比nums[i]小的数,所以统计起来即可;然后可以离散化数据范围,用排名代替数据 2020.4.24
面试题57 - II. 和为s的连续正数序列 在初步考虑时就在思考求和公式,但过多的想关注因数分解,导致需要讨论的情况过多而且繁杂,最后还是应该更多涉及两个数的乘积,以及需要改变不使用求根公式的习惯 2020.3.6
面试题59 - II. 队列的最大值 做题看了题解,题目要求push,pop,max均为O(1),实现时维护一个跟原队列一致顺序的单调递减双端队列,这两个队列顺序一致,保持共同进退,只是双端队列中比最后一个元素小的元素均已被提前剔除,这样push的平均均摊时间复杂度为O(1),其他的为标准O(1) 2020.3.7
面试题62. 圆圈中最后剩下的数字 约瑟夫问题,(第m个人出列)假设n-1个人从0开始数的赢家为x,那么n问题若想从0数变成n-1问题,先除去标号m-1%n,那么标号m%n(n问题)相当于标号0(n-1问题),那么(n-1问题)赢家x相当于(n问题)赢家(x+m)%n 2020.3.30
面试题 01.06. Compress String LCCI 简单模拟即可,过程中实现一个简单的int转string 2020.3.16
面试题 01.07. Rotate Matrix LCCI 先转置再镜面,或者直接原地交换4个数 2020.4.7
面试题 08.03. Magic Index LCCI 跳跃查找或者二分分治问题 2020.7.31
面试题 08.11. Coin LCCI 写的数学方法 2020.4.23
面试题 17.16. The Masseuse LCCI 简单动态规划,做题时没耐心好好分析,分成当前顾客要不要服务两种情况,就可以从max( i-2 + nums[i] , i -1 ) 算出dp[i] 2020.3.24
剑指 Offer 09. 用两个栈实现队列 Easy题,花的时间有点多,用一个栈实现尾部,另一个栈保存头部即可(当这个头部栈为空的时候,把那边全塞过来) 2020.6.30
1.并查集
1.1 例题
  1. 200.岛屿数量
    200涉及DFS,BFS,并查集
1.2 并查集参考资料
  1. 超有爱的并查集
  2. 并查集的C++实现及优化
线段树
初步理解 用一颗树记录一段区间的和,叶节点为每个点的值,父节点为两个子节点线段区间和的和
参考资料 1.线段树从零开始
2.线段树详解
排序算法
参考资料 1.十大经典排序算法(动图演示)
众数 LeetCode刷题记录
文章图片

最短路
Floyd算法 d p [ k ] [ i ] [ j ] dp[k][i][j] dp[k][i][j]表示从 i → j i\rightarrow j i→j路径上有 1 , 2 , . . , k 1,2,..,k 1,2,..,k节点的最短路
∴ d p [ k ] [ i ] [ j ] = m i n ( d p [ k ? 1 ] [ i ] [ j ] , d p [ k ? 1 ] [ i ] [ k ] + d p [ k ? 1 ] [ k ] [ j ] ) \therefore dp[k][i][j]=min(dp[k-1][i][j],dp[k-1][i][k]+dp[k-1][k][j]) ∴dp[k][i][j]=min(dp[k?1][i][j],dp[k?1][i][k]+dp[k?1][k][j])
简化为
d p [ i ] [ j ] = m i n ( d p [ i ] [ j ] , d p [ i ] [ k ] + d p [ k ] [ j ] ) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])k k k从 0 → n 0 \rightarrow n 0→n
BFS(注意消除重复状态),DFS Dijkstra算法 不能处理带负权的边,因为该算法把顶点分为两类,A类是已找到最短路的,B类是未找到最短路的,用贪心的方法把B类点移到A类时,不会在后续的分析中考虑有边回来A类中的点的情况。
松弛 指 d i s [ 0 ] [ i ] > d i s [ 0 ] [ k ] + e d g e [ k ] [ i ] dis[0][i] \gt dis[0][k]+edge[k][i] dis[0][i]>dis[0][k]+edge[k][i]时
用 d i s [ 0 ] [ k ] + e d g e [ k ] [ i ] dis[0][k]+edge[k][i] dis[0][k]+edge[k][i]代替 d i s [ 0 ] [ i ] dis[0][i] dis[0][i]的过程(即从起点(节点0)到节点i的路径要添加上节点k)
用边 e d g e [ k ] [ i ] edge[k][i] edge[k][i]松弛
Bellman-Ford算法 简单地对所有边进行松弛操作,共 |V|-1次,其中 |V|是图的点的数量。在重复地计算中,已计算得到正确的距离的边的数量不断增加,直到所有边都计算得到了正确的路径。
可解决负权边的最短路问题,也可以检查有没有负权环
SPFA算法 SPFA(Shortest Path Faster Algorithm)算法在Bellman-ford算法的基础上加上一个队列优化
UESTCACM 每周算法讲堂 SPFA与迪杰斯特拉算法 的写法看起来像从起点开始进行的BFS
然后我也看不懂为什么知乎上写的 如何看待 SPFA 算法已死这种说法?
据他们说SPFA会卡时间要用Dijkstra算法
动态规划
01背包 问题:
给定一个体积为n袋子和一堆货物(体积为s[m];价值为v[m])
问怎么装袋子中总价值最高
假设我们已经处理好了前m-1个货物(可选择装或者不装),此时总价值最大
对于第m个货物是否要装
分为
1.装,那么前m-1个货物只能分配到n-s[m]的体积
2.不装,那么前m-1个货物可分到n的体积
比较这两种情况的价值大小来进行选择
参考资料:动态规划解决01背包问题
AC 自动机
字典树+fail指针 参考资料 【LeetCode刷题记录】AC 自动机

    推荐阅读