youxiwang

题解

/ 注册

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

题解 | 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 #买卖股票的最好时机(四)# [P0-T2] 来自专栏

就是三的解法loop个k遍。 profit[k,i]: k次买卖都在0～i天内执行，在第i天手上钱的最大值。对于每个k，profit需要分两部计算 (i.e. buy and sell). 例子, k = 3 price: 3 16 6 14 10 19 pass1-buy:...

Java 动态规划

2022-01-31

2 541

题解 | JAVA O(1) 空间 #买卖股票的最好时机(三)# [P2] 来自专栏

参考的leetcode#123。但是感觉leetcode的O(1)的解法思路有点反人类，就稍微转换了一下。先看(四)的解法再看三(因为四不用空间优化, 好理解)。举例 price: 3 16 6 14 10 19 大致可以理解为把#买卖股票的最好时机(一)#走三遍。第一遍和#买...

Java 动态规划

2022-01-31

1 531

题解 | 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

题解 | #不相邻最大子序列和# [P3 - T2] 来自专栏

JAVA - DP Solution, O(n) time, O(1) space 请输出不相邻最大子序列和递归逻辑 f(0) = max(array[0], 0); f(1) = max(array[1], 0); f(2) = max(array[2], 0) + max(f(0)); ...

Java 动态规划

2022-01-16

1 388