未来0116

题解

c++(4) 算法(5) 编译器(1)

/ 注册

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

题解 | #编辑距离(一)#

一.题目简介给定两个字符串str1和str2，可以进行插入、删除、替换，返回将str1编辑成str2的最小操作次数。二.算法一(动态规划) (1)动态规划：dp[i][j]dp[i][j]dp[i][j]表示str1的前i个字符编辑成str2的前j个字符需要的最小操作数 (2)边界处理：从表...

C++ 动态规划状态压缩

2022-01-09

0 391

题解 | #单词拆分(一)#

一.题目简介给出一个字符串集合判断其是否是给定字符串数组的子集，也就是利用所给的字符串集合能否拼接成所给出的字符串，如果可以拼出返回true，否则返回false。二.算法一(哈希表) 我们可以采用哈希表的方法来解决这道题目，先对字符串集合中每一个字符串进行标记，然后遍历字符串，初始化一个空串s...

C++ 哈希表动态规划

2022-01-08

0 440

题解 | #公共子串计算#

HJ75公共子串计算一.题目描述给定两个只包含小写字母的字符串，计算两个字符串的最大公共子串的长度。注：子串的定义指一个字符串删掉其部分前缀和后缀（也可以不删）后形成的字符串。二.算法一(暴力) 由于是字串是个连续的字符串，我们可以暴力循环的方法查找截取出长串的所有字串，判断其是否会在短串...

C++ 动态规划

2021-12-09

15 1389

题解 | #牛妹的招聘#

一.题目描述NC516牛妹的招聘每一个人都有一个聪明值Si(-1000<=Si<=1000)和勤奋值Fi(-1000<=Fi<=1000)。希望选入所有人的Si+Fi的总和最大，并且选中的所个人聪明值与勤奋值的和不能是负数，求出最大的总和。二.算法(单调栈)对于n个人每个人存...

动态规划单调栈

2021-08-16

1 493

题解 | #牛牛恨66#

一.题目描述NC517牛牛恨66求不超过n位十进制数中有多少个数字不含有连续的6（从1开始算的），输入只包含一个正整数n（1<=n<20）二.算法(动态规划)状态定义：dp[i]表示输入为i时，有多少个数字不含有连续的6。状态初始化：当输入为0时，只有1不含66，赋值为1；当输入为1时，...

动态规划搜索

2021-08-04

0 529

题解 | #生产口罩#

一.题目描述NC519生产口罩牛妹是一家口罩厂家的老板，由于现在疫情严重，牛妹想重新分配每条生产线上的人数来使得能生产的口罩最多。牛妹所在的公司一共有m名员工，n条生产线(0,1,...,n-1)，每条生产线有strategy[i].size种人数安排策略。例如：3个人在a生产线上，a生产线每天生产...

动态规划

2021-08-03

1 512

题解 | #最长公共子串#

一.题目描述给定两个字符串str1和str2,输出两个字符串的最长公共子串，题目保证str1和str2的最长公共子串存在且唯一。二.算法(java实现动态规划)dp[i][j]表示字符串1的以i结尾的字符串，字符串2的以j结尾的公共子串当str1[i]==str2[j],dp[i][j]等于dp[i...

动态规划

2021-07-28

1 590

题解 | #换钱的最少货币数#

一.题目描述给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。如果无解，请返回-1。arr=[5，2，3]，aim=20。 4张5元可以组成20元，其他的找钱方案都要使用更多张的货币...

动态规划

2021-07-27

1 1158

题解 | #最小编辑代价#

一.题目描述NC35最小编辑代价题目链接：https://www.nowcoder.com/practice/05fed41805ae4394ab6607d0d745c8e4tpId=196&&tqId=37134&rp=1&ru=/activity/oj&q...

动态规划

2021-07-10

2 760

题解 | #NC34 求路径#

一.题目描述：NC34求路径题目链接：https://blog.nowcoder.net/detail/0?qurl=/practice/166eaff8439d4cd898e3ba933fbc6358一个机器人在m×n大小的地图的左上角（起点），机器人每次向下或者向右移动，机器人要到达地图的右下角...

动态规划

2021-07-10

4 1182