牛客687146177号

分类

题解(7)

/ 注册

全部文章（共12篇）

题解 | #加分二叉树#

这道题最开始该考虑的是数组用n+1的大小还是n的大小，因为二叉树的节点是从1开始的，所以用n+1作为数组大小最好。具体讲解见：https://www.acwing.com/video/495/ 反复看几遍就懂了： import java.util.*; publ...

Java 动态规划

2022-08-16

1 440

题解 | #括号区间匹配#

括号区间匹配给定一个由 ‘[’ ，‘]’，‘(’，‘)’ 组成的字符串，请问最少插入多少个括号就能使这个字符串的所有括号左右配对。例如当前串是 “([[])”，那么插入一个’]‘即可满足。数据范围：字符串长度满足 1≤n≤100 输入描述：仅一行，输入一个字符串，字符串仅由 ...

Java 动态规划

2022-08-14

6 1683

题解 | #分割等和子集#

利用01背包问题的变形： 1.首先求和后确定是否奇数，是则返回false； 2.我们要求这道题可以变形成求一个背包能否被装满，而背包容量为bag=sum/2； 3.如果背包能被装满则剩下的值之和也是sum/2，所以要求背包能否被装满利用01背包问题，建dp[bag+1]，我...

Java 动态规划

2022-08-07

0 286

题解 | #最少的完全平方数#

借鉴左神的思路：采用方法一：根据四平方和定理： 1.一个数最多可以被4个平方和累加得到。 2.任何数消掉4的因子结论不变。 3.如果一个数模8等于7，则这个数一定被4个平方数累加得到 import java.util.*; public&nbs...

Java

2022-08-06

0 320

题解 | #跳跃游戏(三)#

贪心算法：每次用cur表示当前走的最远距离，遍历数组，用next表示最大位置，当随着i走的时候next也会跟着要么不变要么变大。如果变大了在cur<i的时候又跑到了最远的位置。直到跑到最终位置： public class Main{ public static int proces...

Java

2022-05-26

0 334

题解 | #跳跃游戏2#

跳跃游戏二：有没有人感觉牛客网的题解都是只上代码，不给思路的。只上代码总觉得是在直接抄答案。这道题我先找了leetcode发现没有这道题。于是我想到了leetcode的跳跃游戏一的视频题解。上面说到了方法2用倒推的方式。我们在这道题上用倒推变形。首先最后一个数组元素一定是包含在最大分数中的。然...

Java

2022-05-25

14 483

题解 | #打家劫舍(二)#

在一的基础上改进，做两个dp分别是代表arr[0 ~ n-2],arr[1 ~ (n-1)]. import java.util.*; public class Main{ public static int process(int[] arr,int n){ int[]dp1=new in...

Java

2022-05-23

0 389

题解 | #不相邻取数#

类似打家劫舍一：就是dp[i]表示以i-1结尾的数组的最大值： import java.util.*; public class Main{ public static int process(int[] arr,int n){ int[]dp=new int[n+1]; dp[1...

Java

2022-05-23

0 342

题解 | #正则表达式匹配#

public class Main{ public static boolean process(String str,String pattern){ if (str == null || pattern == null) { return fal...

Java

2022-05-12

1 401

题解 | #最大子矩阵#

动态规划：利用题题目DP5（连续自数字最大和）的思路，首先将矩阵分为第一列，第二列... 用字母表示：m0,m1,m2...m(n-1)，得到n个数组，然后：先求第一个数组的最大子数组值a1。求第一个数组+第二个数组得到的数组的最大子数组值a2。 m0+m1+m2的最大子数组值a3 m0+....

Java

2022-04-28

3 715