题号 | 思路 | 时间 |
---|---|---|
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 例题
- 200.岛屿数量
200涉及DFS,BFS,并查集
- 超有爱的并查集
- 并查集的C++实现及优化
初步理解 用一颗树记录一段区间的和,叶节点为每个点的值,父节点为两个子节点线段区间和的和
参考资料 1.线段树从零开始
2.线段树详解
排序算法
参考资料 1.十大经典排序算法(动图演示)
众数
文章图片
最短路
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 自动机