柴崎越

Leetcode

代码总结(4) 毕业设计(18)

/ 注册

全部文章 / Leetcode （共12篇）

Leetcode 221 最大正方形来自专栏

解法通过暴力法，一点一点的尝试。动态规划，一个位置的能构成的最大正方形，是依赖三个位置的。代码暴力法 public int maximalSquare(char[][] matrix) { int max=Integer.MIN_VALUE; for(int i...

动态规划 Leetcode

2020-04-19

0 522

Leetcode 474 一和零来自专栏

分析背包问题，但是这里的target有两个，所以最开始的是三维，降为二维的情况下，原本的二三维都需要逆序代码 class Solution { /*public int findMaxForm(String[] strs, int m, int n) { int[][]...

动态规划 Leetcode

2020-04-16

0 594

Leetcode 140 单词拆分II 来自专栏

解法回溯，记忆化，动态规划，动态规划的话，仍然会时间超时，对于一长串aaaa的情况代码回溯 //我的解法 public static List<String> wordBreak(String s, List<String> wordDict) { ...

回溯算法记忆动态规划 Leetcode

2020-04-15

0 507

Leetcode 139 单词拆分来自专栏

解法 boolean类型的状态转移方程，一维就可以，没有必要使用二维代码 import java.util.*; import java.util.List; class Solution { public boolean wordBreak(String s, List<Strin...

背包问题动态规划 Leetcode

2020-04-14

0 519

Leetcode 416 分割等和子集来自专栏

解法背包问题的true和false，两个等和的子集，实际上就是何为总和的一半的子集，dp[i][j]的状态转移方程就可以解决了。压缩空间的问题，对于target这一列，要倒着走，因为正着走会覆盖代码 class Solution { public boolean canPartitio...

背包问题动态规划 Leetcode

2020-04-14

0 751

Leetcode 377，494，518 背包问题总结1 来自专栏

Leetcode 377 组合求和四 public int combinationSum4(int[] nums, int target) { int[] dp=new int[target+1]; dp[0]=1; for(int i=1;i&l...

背包问题动态规划 Leetcode

2020-04-13

0 613

Leetcode 198，213 ,337 打家劫舍套题

Leetcode 198 最初的就是考虑一维的dp，代码实现如下 class Solution { public static int rob(int[] nums) { if(nums==null||nums.length==0) return 0; if(nu...

递归回溯算法记忆数组动态规划 Leetcode

2020-03-11

0 484

Leetcode 174 地下城游戏

代码分析典型的动态规划，走的顺序就是从下到上从右到左，举出几个例子，就可以确定状态转移方程代码实现 int[][] dp=new int[dungeon.length][dungeon[0].length]; //init //dp[dungeon.length-...

动态规划 Leetcode

2020-03-03

0 418

Leetcode 4 寻找两个有序数组的中位数(还有一种解法没有学习)

题目代码分析要达到有log的时间复杂度，可以想到一定和二分有关系，我们的普通做法就是每次都从两个数组的头出去一个，当出去总量的一半之后，就完成了。这里我们每次都出一半，具体的，如果两个数组的总量是14，我们要找了就是第7小和第8小的数字，对于第7小的，我们首先要找第7/2=3小的数字，这就是这道...

二分查找动态规划 Leetcode

2020-02-06

0 479

Leetcode 152 乘积最大子序列

题目分析考虑到有负数的参与，会使现有的最大的变成最小的，最小的变成最大的，实际上也可以看做是一种动态规划，imax和imin分别记录的是以当前位置为结尾的，最大和最小的子序列乘积的大小。代码 public static int maxProduct(int[] nums){ ...

动态规划 Leetcode

2020-02-06

0 397