youxiwang

题解

/ 注册

全部文章 / 题解（共91篇）

题解 | #多叉树的直径# [P2-T1]

核心就是树的最大直径(globalMax)一定是以某一个node为root最长的两个path-to-leaf. 就是普通dfs的同时算路径长度。时间: O(n), DFS一次空间: O(n) import java.util.*; /** * public class Interval ...

Java

2022-04-14

0 506

题解 | #数组中的最长连续子序列# [P4-T1]

先排序，再从有序数组中找连续 import java.util.*; public class Solution { public int MLS (int[] arr) { Arrays.sort(arr); int curLen = 0; ...

Java

2022-04-14

0 280

题解 | #最长的括号子串# [P0-T1]

栈上存目前未能pair的括号的下标每遍历一个字符(下标i)，check是否能和栈顶下标对应的字符pair，能pair就pop栈顶。 pop完后i与栈顶的差就是截止到i的valid子串长度。 i.e. 此时栈顶下表对应再往前一个未能pair的字符举例 0 1 2 3 4 5 6 7 (...

Java

2022-04-14

0 332

题解 | #城市群数量# [P0-T1]

最普通的DFS DFS了几遍就有几个城市群。 import java.util.*; public class Solution { boolean[] visited; int ans = 0; public int citys (ArrayList<ArrayLis...

Java

2022-04-11

2 477

题解 | #二叉搜索树的第k个节点# [P2-T0]

in-order traversal 时间: O(h) 空间: O(h) import java.util.*; public class Solution { int visited = 0; int ans = -1; public int KthNode (TreeNo...

Java

2022-04-05

0 275

题解 | JAVA #最长不含重复字符的子字符串# [P1-T2] 来自专栏

遍历每个字符，记录每个字符最近一次出现的位置。 dp[i]: length of longest substring without duplicates ending at i dp[i] = { dp[i-1] + 1 // if dp[i-1] does not contiain ch...

Java 哈希函数动态规划

2022-04-04

0 472

题解 | JAVA 前缀和#和为K的连续子数组# [P0-T2] 来自专栏

连续子数组和的问题 -> 前缀和 import java.util.*; public class Solution { public int maxlenEqualK (int[] arr, int k) { // prefixSumMap: 前缀和 -> 前缀和为su...

Java

2022-04-04

2 550

题解 | JAVA #加起来和为目标值的组合(二)# [P0-T2]

正常暴力枚举(递归+回溯) 时间: O(n!) 空间: O(n) import java.util.*; public class Solution { final ArrayList<ArrayList<Integer>> ans = new ArrayList<...

Java

2022-04-03

0 384

题解 | JAVA #矩阵元素查找# [P3]

首先，两点可以确定一个矩形(i.e. 左上+右下) 设左上+右下两点囊括的矩形为M (M初始为整个mat) 不停的去通过比较x与M的右上和左下角的数值的大小，来缩小M的大小。 x > M右上角, topLeft.row++ x < M右上角, botRight.col-- x &...

Java

2022-04-03

0 366

题解 | #链表中的节点每k个一组翻转# [P3]

两个指针分别指向： sentinal: 当前需要反转的k个点的前一个node end: 当前需要反转的k个点的随后一个node e.g.: ans-1-2-3-4-5-6-7-null s e ans-3-2-1-4-5-6-7-null s e ...

Java

2022-04-03

0 382