刷题林

分类

/ 注册

全部文章（共13篇）

题解 | #明明的随机数#

方法一去重、排序？这不是直接可以用集合中的TreeSet不就行了就是直接把输入的值放入TreeSet再输出就行，代码略。方法二被去重的值在1-500之间，个数在1-1000之间，那么这个信息告诉我们不就是说明可以用空间换时间吗？那么可以声明一个长度为501的数组，用数组的下标代表数字的值，数组下标对...

2023-09-02

1 411

题解 | #购物单#动态规划

1、思路分析如果这题把附件去掉，只考虑主件是不是跟01背包问题完全一样？。所以我也是想着怎么把附件给忽略掉。最终的想法就是把主件和附件合在一起，它就是一个物品，只是这个物品会有不同的价格与满意度。这个物品可能存在以下四个状态： 1、只有主件 2、主件+附件1 ...

Java 动态规划哈希表

2022-12-11

1 658

题解 | #计算字符串的编辑距离#动态规划

动态规划题型和提示都很明显的指向动态规划算法，难点在于动态转移方程。1、状态定义定义一个二维数组：[i][j]，表示的含义是字符串A的前i个字符，与字符串B的前j个字符的最短编辑距离。 //状态定义 int[][] f = new int[a.length()+1][b.length()+1]; 2...

2022-12-11

2 582

题解 | #合唱队#动态规划#二分查找

一、动态规划题目分析：这题就是求一个序列，先升序后降序的序列，这个序列最长是多少？就是找一个点，这个点左边的升序队列最长是多少？右边的降序队列最长是多少？就是先求当前这个人左边的升序队列最长多少？然后同样的方法求右边的降序队列最长多少？求左边最长升序思路：这个问题就是给一个乱序的序列，找一个最长的升...

2022-12-07

2 415

题解 | #称砝码#动态规划

题目分析：可以直接看成：给n个砝码，求能称出的不同的重量数。暂不考虑质量相同的砝码怎么办，一视同仁方法一：Set直接去重假设有3个砝码，质量分别为：1、1、2。1个砝码都没可以称出的结果：0。加第1个砝码可以称出的结果：0 、1。加第2个砝码可以称出的结果：0 、1、2。加第2个砝码可以称出的结果：...

2022-12-06

1 669

题解 | #字符串通配符#动态规划

一、正则匹配我一开始想到的是使用正则匹配的方式去做。* 按题意用正则表示则是[0-9a-z]*。？按题意用正则表示则是[0-9a-z]。另外特殊字符.，需要前面加上\\进行转移，这样把匹配串转化成了一个正则匹配串，就可以之间用String的方法直接获取结果。import java.util.Scan...

2022-12-04

0 407

题解 | #将真分数分解为埃及分数#

贪心这题一开始，我是在找组成这个真分数的埃及分数的规律，其实完全没必要，因为不管什么样的真分数，它都是可以用埃及分数组成的。并且结果可能有多个。这两个关键信息一定要get到1、任何的真分数，都可以用多个埃及分数进行分解 2、结果可能有多个所以可以把大问题化成小问题，大的真分数化成小的真分数。例题目...

2022-11-27

1 644

题解 | #Redraiment的走法# 动态规划详解

动态规划解法就按题目中的示例来讲吧，首先我们肯定把复杂问题向简单问题靠拢，只有找到简单和复杂之间的转换规律 2 5 1 5 4 5 一开始我的思路是想，第一步踩 2 这个数，第二步又分情况，可以踩三个5中的任意一个，或踩4 ，第三步再踩5（前提是第二步踩得是4）。但是这个解法似乎只能暴力...

2022-11-21

0 417

题解 | #24点游戏算法#

注意坑！这题注意一下有括号对运算优先级的影响，我看之前就已经有大佬发现，排行里的部分提交代码是通过不了（9 5 7 1）的，但实际9-5=4，7-1=6，4*6 = 24。这是可以组成24的，所以一般的dfs是有bug的。解题思路：我就是直接模拟人工计算的方式，穷举暴力破解，我觉得是最容易理解的方式...

2022-11-20

1 429

题解 | #查找两个字符串a,b中的最长公共子串#

题目：提取两个字符串中最大的公共子串，并输入（先考虑求出最大子串）动态规划思路：1、先简单后复杂都是解题的常规思路，首先想到两个字符串都很小的情况，比如字符串长度为1，然后考虑复杂的情况。如果两个字符串都在变，思考起来肯定很乱，那我们先固定一个，比如x串的长度固定为1，y串长度未知，可能为1到n。/...

2022-11-19

2 715