youxiwang

分类

题解(90)

/ 注册

TA的专栏 28篇文章 2人订阅

28篇文章 992人学习

全部文章（共91篇）

题解 | Java O(1)空间 #连续子数组的最大和(二)# [P2-T2] 来自专栏

假dp 思路和连续子数组的最大和一模一样的只需要多记录当前最优解的长度和endingIndex(为了在Sum相同的情况下比较长度，和之后还原SubArray). 这里把global和local的GSS的参数存成两个int[3]。具体逻辑看comment。时间：O(n), 每个数visit一次 ...

Java

2022-01-30

1 376

题解 | #最长上升子序列(三)# [P2] 来自专栏

就是(一)的衍生需要多一个mem2记录每个数在以它结尾的LIS中的index。看懂了(一)的O(nlogn)解这个基本也就懂了。 import java.util.*; public class Solution { public int[] LIS (int[] arr) { ...

Java

2022-01-30

0 422

题解 | JAVA #最长上升子序列(二)# [P0] 来自专栏

就是(一)的O(nlogn)解 https://blog.nowcoder.net/n/dae14ef8bd484b01b541da73a155d9a2 import java.util.*; public class Solution { public int LIS (int[] a)...

Java

2022-01-30

0 381

题解 | JAVA #二分查找 #最长上升子序列(一)# [P0-T2] 来自专栏

经典的LIS问题的最简形态(求LIS长度) 核心逻辑是: mem[n]: 长度为n+1的LIS的最后一个数的最优值(i.e. 最小). 有O(n^2)和O(nlogn)时间两种解。 import java.util.*; // time O(nlogn) solution // 视频讲...

Java

2022-01-30

0 641

题解 | JAVA #最大正方形# [P0-T2]

mem[i][j]: 右下角坐标为(i,j)分正方形最大边长 if matrix[i][j] = 1: mem[i][j] = 1+ MIN{ mem[i-1][j], mem[i-1][j-1], mem[i][j-1] } import java....

Java

2022-01-26

0 311

题解 | JAVA #几步可以从头跳到尾# [P0-T2] 来自专栏

import java.util.*; public class Solution { public int Jump (int n, int[] A) { // 0作为起始点，n-1作为终点 int step = 0; // 跨了X步 int dis...

Java 动态规划

2022-01-26

0 385

题解 | JAVA DP#最长公共子序列(一)# [P0-T2] 来自专栏

空间: O(Max(m, n))，时间: O(mn) 定义LCS(i, j)为s1.substring(0, i+1)和s2.substring(0, j+1)的最长公共序列。对于每一对i, j，以下两种情况：如果s1[i] = s2[j], LCS(i, j) = LCS(i-1, j-1...

Java 动态规划

2022-01-26

0 336

题解 | JAVA DP#子数组最大乘积# [P1-T2] 来自专栏

dp, 定义: min(i)为arr[0,i]包含arr[i]的最小子数乘积 max(i)为arr[0,i]包含arr[i]的最大子数乘积注意min,max都是可正可负很明显 min(i+1)只有三种可能： 1. = min(i) * arr[i+1] // 比如min(i) = -1, ...

Java 动态规划

2022-01-26

0 369

题解 | #汉诺塔问题# [P1-H] 来自专栏

自知表达能力不行肯定讲不清楚，干脆找了个讲的清楚的视频链接 https://www.youtube.com/watch?v=rf6uf3jNjbo 这里我直接recursion了没去记忆了。时间O(n^2), 每次recursion会分两支新的recursion 空间O(n), 递归n层，所以栈...

Java

2022-01-25

0 440

题解 | JAVA 数学 #求路径# [P3] 来自专栏

DP解 import java.util.*; public class Solution { public int uniquePaths (int m, int n) { int[][] mem = new int[m][n]; // fill first ro...

Java

2022-01-24

0 342