youxiwang
youxiwang
全部文章
题解
归档
标签
去牛客网
登录
/
注册
youxiwang的博客
全部文章
/ 题解
(共91篇)
题解 | #跳跃游戏(一)# [P0]
来自专栏
假DP 从前往后遍历每一个点,更新目前能跳到的最远的点 import java.util.*; public class Solution { public boolean canJump (int[] nums) { int reach = 0; // 目前最远能跳到的点 ...
Java
2022-02-06
5
559
题解 | JAVA #分割等和子集# [P2]
来自专栏
题目明显可以转化为“是否存在和为sum/2的子数组” 所以就先求和,除以2,得出target sum 定义dp[i][s] 如果dp[i][s]=true, 表示nums[0, i]中存在一个subset的和为s 那么对于第i个数,能凑出s有两种情况: 1. 之前i-1个数已经能凑出s ...
Java
2022-02-06
1
513
题解 | JAVA #打家劫舍(二)# [P2]
来自专栏
跟(一)同样的解法,dp定义也完全不用变。跑两遍而已 环形只影响最后一个房子的选择: - 如果偷了第0个房子,那最后一个房子就偷不了。 - 如果不偷第0个房子,那最后一个房子可以选择偷或着不偷 那岂不是把两个情况都跑一遍 挑个更好的就行了。。。 偷了第0个房子: 在第1个房子时, g(1...
Java
2022-02-06
2
992
题解 | JAVA #打家劫舍(一)# [P0]
来自专栏
import java.util.*; // F(i): max profit at nums[i], and rob nums[i] // = G(i-1) + nums[i] // G(i): max profit at nums[i], and do not rob nums[i] //...
Java
2022-02-06
0
400
题解 | #目标和# [P3]
来自专栏
时间: O(maxSum*N) 空间: O(maxSum) DP 定义: DP(i, j): # of ways num[0, i] can sum to j. DP(i, j) = DP(i-1, j + num[i]) + DP(i-1, j - num[i]) import jav...
Java
2022-02-02
0
338
题解 | #三角形最小路径和# [P0]
来自专栏
从下往上dp f(i,j) = Min{f(i+1,j), f(i+1,j+1)} + v(i,j) O(n^2), O(n^2) TODO: 第二个for-loop倒着走可以空间优化至O(n) import java.util.*; public class Solution { p...
Java
2022-02-01
2
617
题解 | 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 DP #买卖股票的最好时机(一)# [P0]
介绍两种时间O(n), 空间O(1)的解法 第一种(更符合DP思维): 定义F[i]: 在第i天持有股票的最大浮盈 情况1: 第i-1天已经持有股票,那么第i天继续持有的浮盈就是i-1天的浮盈加上i和i-1的价差: F[i-1]+(P[i]-P[i-1]) 情况2: 第i-1天未持有,第i...
Java
2022-01-31
1
343
题解 | JAVA O(1)空间 #最长严格上升子数组(一)# [P2]
首先比较容易会想到需要在dp时每一位考虑用了wildcard和没用wildcard的情况 没用wildcare的情况比较简单(见F(i)定义) 用了wildcare的情况为什么要考虑 G(i) 和 H(i),请看以下案例: 10, 3, 10, 5, 6 G(2)的最优解是[1, 3, 10],...
Java
2022-01-30
0
473
首页
上一页
1
2
3
4
5
6
7
8
9
10
下一页
末页