空中转体一周半

分类

未归档(1) 题解(80)

/ 注册

全部文章（共93篇）

题解 | #二叉树中的最大路径和#

思路：最大路径和的产生：左子树的单路径、右子树的单路径、左右子树的单路径和根节点值这三者之一。因此，先用两个变量存储左右子树的单路径（单路径就是只有从下到上的一条路径，没有左右）的最大和，分别取最大值即可。需要注意的是，取某条单路径的最大和的时候，如果某子树单路径之和加上根节点的值比根节点小，那么该...

2022-09-16

0 377

题解 | #三个数的最大乘积#

C++：顺便回顾一下快速排序。最大乘积：负负得正再乘以最大，或者三个最大的数相乘。最大的数可能是这两者的一个。那么就好办了，排序一上就完成了。 class Solution { public: /** * 最大乘积 * @param A int整型一维数组 *...

C++ 数学数组

2022-08-12

0 520

题解 | #二叉树的最大宽度#

思路：本题乍一看可以用层序遍历？但是涉及到空节点的问题，层序遍历存在诸多麻烦，因此可以利用二叉树的特性：左叶子节点的序号为根节点的两倍，右叶子节点的序号为根节点的2倍加1.利用这个性质，我们把每一层的最左节点的序号加入一个map中（这个动作只进行一次即可），以后每次遍历到该层的时候，刷新该层的最大节...

Java

2022-05-24

5 543

题解 | #岛屿的最大面积#

思路：dfs。每次遇到岛屿就把岛屿清零，用size记住清除的次数即可。 public class Solution { int maxSize; int size; public int maxAreaIsland (int[][] grid) { for(i...

Java

2022-05-24

4 857

题解 | #懂二进制#

思路：二进制不同位，直接采用异或，然后采用循环右移计算1的个数即可。 Java: public class Solution { public int countBitDiff (int m, int n) { int c = m^n; int count =...

Java

2022-05-23

3 585

题解 | #最长重复子串#

既然题目要求时间复杂度为O(n^2),那么直接套用双重循环：外层循环i为假定起始重复子串的初始位置，内层循环的j为假定重复子串的结束位置。注意，如果j-i为奇数，那么不可能是重复子串，因此，每次把j的下标增加2。由于我们是假定从i到j的子串为重复子串，因此我们需要去验证，验证很简单，就是从中间截断，...

Java

2022-05-23

5 791

题解 | #插入区间#

这个题看起来可以使用“合并区间”的解法，但题目已经告知了输入的数组是已经按start字段升序，那么我们仅需要找到插入点，然后向后合并即可。时间复杂度O(n)，空间复杂度O(n)(采用了list)。 public class Solution { public Interval[] inser...

Java

2022-05-22

1 388

题解 | #从中序与后序遍历序列构造二叉树#

这个题的思路是和根据中前遍历重建二叉树类似的。因为后续遍历的最后一个元素总是根节点，那么只需要先找到后序遍历中的根节点，再把数组分为左右两个区间就能找到左子树与右子树。 public class Solution { public TreeNode buildTree (int[] inor...

Java

2022-05-22

8 589

题解 | #重复的DNA序列#

分割子串，放入set.如果set中已经存在该子串，那么加入返回列表。再遍历set，找到最先出现的串即可。 public class Solution { Set<String> set =new LinkedHashSet<>(); public String...

Java

2022-05-22

2 474

题解 | #设计LFU缓存结构#

使用LinkedHashMap,每次调用之后，删除再加入这个K-V，就能保证是最新操作的在前面了。需要注意的是，每次操作put操作需要分成三个类别：1、k已存在；2、k不存在且未达到最大容量；3、k不存在且已经达到最大容量。其中第三种需要找出最少使用且最久的Bolck（笔者在这里没有使用O(lgn)...

2022-05-15

1 482