用户工具

站点工具


算法题型分类

1 算法思想

双指针

leetcode序号 题目 思路要点
167 有序数组的 Two Sum 对撞
633 两数平方和 对撞
345 反转字符串中的元音字符 对撞
680回文字符串对撞。子函数
88归并两个有序数组从后往前
141判断链表是否存在环快慢指针重合
524最长子序列子序列的判断方法(双指针,从左到右扫一遍)

排序

leetcode序号 题目 思路要点
215 Kth Element 小顶堆
桶排序
347出现频率最多的 k 个元素算出频率、插入桶中、从后往前遍历桶。List<Integer>[] buckets = new ArrayList[nums.length + 1]
451按照字符出现次数对字符串排序同上
荷兰国旗问题
75按颜色进行排序三路快排

贪心思想

leetcode序号 题目 思路要点
455 分配饼干 胃口升序、饼干升序、双指针
435不重叠的区间个数根据结尾排序;若 start < 上次的 end,则判定为重合,跳过
452投飞镖刺破气球同上。对于边界情况,使用 Integer.compare 做比较
406根据身高和序号重组队列根据身高倒序、序号正序排序;以序号为索引位置,插入List<int[]>中;toArray(new int[n][2])
121买卖股票最大收益一次遍历。Math.max(max, price[i]-soFarMin)
122买卖股票最大收益2所有连续上升序列的差值之和
605种植花朵尽量靠前种花;每种一棵,计数&更新状态
392判断是否为子序列双指针
665修改一个数成为非递减数组只允许变一次(可以用count或flag);发现异常时,尽量变前一个数,不行再变后一个数
53子数组最大的和只扫一遍;记录当前和与最大和,如果上次的当前和<0,则丢弃,取0
763分隔字符串使同种字符出现在一起记录每个字符最后一次出现的索引(int[26]);双指针

二分查找

边界问题非常多! 二分查找解析:https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/er-fen-cha-zhao-suan-fa-xi-jie-xiang-jie-by-labula/

leetcode序号 题目 思路要点
69 求开方 用除法防止越界;l⇐r;return r
744大于给定元素的最小元素二分法变种
540有序数组的 Single Element异或;对偶数位进行搜索
278第一个错误的版本 左边界
153旋转数组的最小数字如果nums[m] < nums[r],那么最小值一定在前半部分;反之则反
34查找区间注意数组越界问题

分治

leetcode序号 题目 思路要点
241 给表达式加括号 遍历,找到每个操作符,一分为二;如果没找到操作符,则Integer.parseInt
95 不同的二叉搜索树 遍历,以每个节点作为root,一分为二

搜索

leetcode序号 题目 思路要点
BFS
1091 计算在网格中从原点到特定点的最短路径长度 batchSize = queue.size();打标记;DIRECTIONS
279组成整数的最小平方数数量生成平方数序列,视为边;从n开始,到达0返回
127最短单词路径先构造一张图,然后寻找起点到终点的最短路径(效率较慢,以后再研究)
DFS
695查找最大的连通面积遍历棋盘,一旦找到一个点位,就dfs求岛屿面积
200矩阵中的连通分量数目遍历棋盘,找到点位就+1,然后dfs清空连通区域
547好友关系的连通分量数目跟上面连通的方式不一样
130填充封闭区域对边界上的O进行dfs,打上不可变标记,再遍历一遍
417能到达的太平洋和大西洋的区域各用一个二维数组标记太平洋、大西洋连通点;从边界出发,逆流dfs
Backtracing
17数字键盘组合sb.deleteCharAt(pos)
93IP 地址划分转换为树形问题,剪枝
79在矩阵中寻找字符串终止条件用 word.length() == 1
257输出二叉树中所有从根到叶子的路径add和remove成对出现;if (root == null) return;
46排列提前声明一个 visited 数组
47含有相同元素求排列先排序,然后在添加一个元素时,判断这个元素是否等于前一个元素,如果等于,并且前一个元素还未访问,那么就跳过这个元素
77组合
39组合求和
40含有相同元素的组合求和
2161-9数字的组合求和
78子集
90含有相同元素求子集
131分割字符串使得每个部分都是回文数
37数独seeNext
51N皇后

动态规划

leetcode序号 题目 思路要点
斐波那契数列
70 爬楼梯
198强盗抢劫
213强盗在环形街区抢劫
信件错排
母牛生产
矩阵路径
64矩阵的最小路径和
62矩阵的总路径数
数组区间
303数组区间和
413数组中等差递增子区间的个数
分割整数
343分割整数的最大乘积
279按平方数来分割整数
91分割整数构成字母字符串
最长递增子序列
300最长递增子序列
646一组整数对能够构成的最长链
376最长摆动子序列
最长公共子序列
1143最长公共子序列
0-1背包
416划分数组为和相等的两部分
494改变一组数的正负号使得它们的和为一给定数
47401 字符构成最多的字符串
322找零钱的最少硬币数
518找零钱的硬币数组合
139字符串按单词列表分割
377组合总和
股票交易
309需要冷却期的股票交易
714需要交易费用的股票交易
123只能进行两次的股票交易
188只能进行 k 次的股票交易
字符串编辑
583删除两个字符串的字符使它们相等
72编辑距离
650复制粘贴字符

数学

leetcode序号 题目 思路要点
最大公约数最小公倍数
204生成素数序列
最大公约数
使用位操作和减法求解最大公约数
进制转换
5047进制
40516进制
16826进制
阶乘
172统计阶乘尾部有多少个0
字符串加法减法
67二进制加法
415字符串加法
相遇问题
462改变数组元素使所有的数组元素都相等
多数投票问题
169数组中出现次数多于 n / 2 的元素
其他
367平方数
3263 的 n 次方
238乘积数组
628找出数组中的乘积最大的三个数

2 数据结构相关

链表

leetcode序号 题目 思路要点
160找出两个链表的交点如果不存在交点,l1 和 l2 会同时为 null,从而退出循环。
206链表反转pre,cur,next;pre = null
21归并两个有序的链表归并排序
83从有序链表中删除重复节点
19删除链表的倒数第n个节点双指针
24交换链表中的相邻节点pre,cur,next; pre = dummyHead
445链表求和用栈倒序
234回文链表快慢指针切成两半,把后面的反转
725分隔链表如果链表有N 个结点,则分隔的链表中每个部分中都有n/k 个结点,且前N%k 部分有一个额外的结点。
328链表元素按奇偶聚集分割奇偶链;找到奇数链的尾部;连接两条链

leetcode序号 题目 思路要点
递归
104树的高度Math.max(leftDepth, rightDepth) + 1
110平衡树还是求最大深度,多了一次比较和状态记录
543两节点的最长路径等于两子树的最大深度之和
226反转树反转左右子树;交换位置
617归并两棵树
112判断路径和是否等于一个数
437统计路径和等于一个数的路径数量pathSumStartsWithRoot(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum)
572子树
isSubtreeStartsWithRoot(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t)

注意子树的定义

101树的对称isMirror(root.left, root.right)
111最小路径当 root 节点左右孩子有一个为空时,返回不为空的孩子节点的深度;当 root 节点左右孩子都不为空时,返回左右孩子较小深度的节点值
404统计左叶子节点的和
687相同节点值的最大路径长度
337间隔遍历
671找出二叉树中第二小的节点
层次遍历
637一棵树每层节点的平均数
513得到左下角的节点
前中后序遍历
144非递归实现二叉树的前序遍历
145非递归实现二叉树的后序遍历
94非递归实现二叉树的中序遍历
BST
669修剪二叉查找树
230寻找二叉查找树的第 k 个元素
把二叉查找树每个节点的值都加上比它大的节点的值
235二叉查找树的最近公共祖先
236二叉树的最近公共祖先
108从有序数组中构造二叉查找树
109根据有序链表构造平衡的二叉查找树
653在二叉查找树中寻找两个节点,使它们的和为一个给定值
530在二叉查找树中查找两个节点之差的最小绝对值
501寻找二叉查找树中出现次数最多的值
Trie
208实现一个 Trie
677实现一个 Trie,用来求前缀和

栈和队列

leetcode序号 题目 思路要点
232用栈实现队列当 sOut 空的时候,一次性把 sIn 加到 sOut 上
225用队列实现栈两个队列;push 的时候,把元素插入临时队列的前面,然后把主队列一一插过去;交换两个队列的名字
155最小值栈多使用一个minStack,同步更新
20用栈实现括号匹配左括号入栈,右括号出栈
739数组中元素与下一个比它大的元素之间的距离一次遍历。用栈记录已经遇到的索引,一旦遇到更大的值,就持续出栈,计算结果
503循环数组中比当前元素大的下一个元素int i = 0; i < n * 2; i++。只在 i<n 时入栈

哈希表

leetcode序号 题目 思路要点
1数组中两个数的和为给定值<needNum:currentIndex>
217判断数组是否含有重复元素多种算法,略
594最长和谐序列构造freqMap,遍历此map
128最长连续序列<num, length>;forward 递归计算从每个num出发的length

字符串

leetcode序号 题目 思路要点
字符串循环移位包含
字符串循环移位
字符串中单词的翻转
242两个字符串包含的字符是否完全相同
409计算一组字符集合可以组成的回文字符串的最大长度
205字符串同构
647回文子字符串个数
9判断一个整数是否是回文数
696统计二进制字符串中连续 1 和连续 0 数量相同的子字符串个数

数组与矩阵

leetcode序号 题目 思路要点
283把数组中的 0 移到末尾
566改变矩阵维度
485找出数组中最长的连续 1
240有序矩阵查找
378有序矩阵的 Kth Element
645一个数组元素在 [1, n] 之间,其中一个数被替换为另一个数,找出重复的数和丢失的数
287找出数组中重复的数,数组值在 [1, n] 之间
667数组相邻差值的个数
697数组的度
766对角元素相等的矩阵
565嵌套数组
769分隔数组

leetcode序号 题目 思路要点
二分图
785判断是否为二分图
拓扑排序
207课程安排的合法性
210课程安排的顺序
并查集
684冗余连接

位运算

leetcode序号 题目 思路要点
461统计两个数的二进制表示有多少位不同
136数组中唯一一个不重复的元素
算法题型分类.txt · 最后更改: 2020/11/05 18:29 由 plough