youxiwang

题解

/ 注册

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

题解 | #斐波那契数列# [P0] 来自专栏

public class Solution { public int Fibonacci(int n) { if (n <= 2) return 1; int f_a = 1; int f_b = 1; for (int i...

Java

2022-04-03

0 306

题解 | JAVA #检测循环依赖# [P0-T2]

拓扑排序三个数据存储的内容： infosMap: 还没安排的课(以及该门课的上下游依赖关系) inEdge: 还没上的上游课程的数量 inEdge==0表示这门课不依赖其他课，或者依赖的课已经上过了(i.e. 加入ans了) neis: 下游的课号 ...

Java

2022-04-03

0 526

题解 | JAVA Prim/Kruskal #最小生成树# [P3-T1]

Prim和Kruskal两种方法 // Prim // Time: O(MlogM), each edge is inserted to minHeap once. // Spcae: O(n) import java.util.*; public class Solution { pu...

Java

2022-04-01

2 461

题解 | JAVA Dijkstra#单源最短路# [P2-T2]

就标准Dijkstra import java.util.*; public class Solution { // shortest path from 1 to n. public int findShortestPath (int n, int m, int[][] gra...

Java

2022-04-01

1 350

题解 | JAVA 递归+回溯 #字符串的排列# [P1]

Permutation大部分都能用递归+回溯解决先build一个charCount把字符串中每个字母的count记下来 recurse的时候从a-z依次选count>0的字母append到输出字符串。时间: O(n!) 空间: O(n) 栈高 import java.util.*; ...

Java

2022-03-28

0 320

题解 | JAVA 递归回溯#加起来和为目标值的组合(三)# K-sum [P1]

K-sum 跟这道题一样的思路，递归回溯的暴力枚举。唯一不同的就是basecase(i.e. 已经用了k个数时)检查下和是否为n. 时间: O(n^k) 空间: O(k) 栈最高为k。因为用了回溯,栈上每层都是const space. import java.util.*; public cl...

Java 回溯递归

2022-03-28

0 420

题解 | 递归回溯 #组合# [P1]

就是递归去暴力枚举. 后选的数必须比之前选的大(之前选的数用last记录, last初始为0), 以保证不会有重复(i.e. 不会出现同时输出[1,2]和[2,1])。用回溯去避免不必要的array copy. i.e 回溯是basecase输出的时候才copy 不回溯是每一次re...

Java 递归回溯

2022-03-28

0 444

题解 | #至少有 K 个重复字符的最长子串# [P1-T2]

分治递归每次递归：统计每个字符的出现次数存入freq[] 遍历每一个字符，遇到freq < k的就把字符串拆分成左右两边分别求解，取max 比如 aaabbbcdddefff 对于c拆分 -> aaabbb, dddefff aaabbb会直接return 6， dddefff...

Java 分治

2022-03-24

0 334

题解 | #最短无序连续子数组# [P3]

对于i，如果满足i左侧所有数都小于i，并且i右侧所有数都大于i，那么i的位置不用变两个条件中任意一个条件不满足，那么i就要挪位置 (充分必要)。那不就是找出需要挪位置的最小和最大下标，求个差就行了从左向右走一遍判断是不是i左侧所有数都小于i 从右向左走一遍判断是不是i右侧所有数都大于i ...

Java

2022-03-22

0 396

题解 | JAVA 单调栈 #直方图内最大矩形# [P0 - T2]

熟悉的味道, 跟这道题一摸一样的解法。对于每个i: 找i左右两侧离i最近的比i低的柱子j和k, j<i<k, h[j]<h[i]>h[k] 以height[i]为高的矩形的最大宽度为(k-j-1) 时间: O(n) 空间: O(n) import java.ut...

Java 单调栈

2022-03-22

0 472