林伟星
林伟星
全部文章
分类
未归档(2)
题解(15)
归档
标签
去牛客网
登录
/
注册
林伟星的博客
全部文章
(共17篇)
动态规划(7)-01背包
题目描述 已知一个背包最多能容纳物体的体积为V现有n个物品第i个物品的体积为v_i,第i个物品的重量为w_iw求当前背包最多能装多大重量的物品 示例1 输入10,2,[[1,3],[10,4]]返回值4说明第一个物品的体积为1,重量为3,第二个物品的体积为10,重量为4。只取第二个物品可以达到最优方...
2021-03-30
0
654
动态规划(6)-最长的括号子串
题目描述 给出一个仅包含字符'('和')'的字符串,计算最长的格式正确的括号子串的长度。对于字符串"(()"来说,最长的格式正确的子串是"()",长度为2.再举一个例子:对于字符串")()())",来说,最长的格式正确的子串是"()()",长度为4. 示例1 输入"(()"返回值2 思路 Q1:d...
2021-03-30
1
487
动态规划(5)-最长公共子序列
题目描述 给定两个字符串str1和str2,输出连个字符串的最长公共子序列。如过最长公共子序列为空,则输出-1。 示例1 输入"1A2C3D4B56","B1D23CA45B6A"返回值"123456"说明"123456"和“12C4B6”都是最长公共子序列,任意输出一个。 思路 Q1:dp数组设...
2021-03-30
0
544
动态规划(4)-求路径
题目描述 一个机器人在m×n大小的地图的左上角(起点)。机器人每次向下或向右移动。机器人要到达地图的右下角(终点)。可以有多少种不同的路径从起点走到终点? 示例 输入2,1返回值1 思路 Q1:dp数组如何设置?二维数组中求一条路径,一般设置dp为二维数组。dp[i][j]表示到达ij位置的结果。...
2021-03-29
0
526
动态规划(3)-最小编辑代价
题目描述 给定两个字符串str1和str2,再给定三个整数ic,dc和rc,分别代表插入、删除和替换一个字符的代价,请输出将str1编辑成str2的最小代价。 示例1 输入"abc","adc",5,3,2返回值2 思路 Q1:dp设置一维还是二维?涉及2个数组的比较,一般设置二维数据dp[i][...
2021-03-29
0
520
动态规划(2)-矩阵的最小路径和
题目描述 给定一个 n * m 的矩阵 a,从左上角开始每次只能向右或者向下走,最后到达右下角的位置,路径上所有的数字累加起来就是路径和,输出所有的路径中最小的路径和。 示例1 输入[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]返回值12 思路 这题的转移方程很...
2021-03-28
0
660
排列组合(1)-字符串的排列
题目描述 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。输入描述:输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。 示例1 输入"ab"返回值...
2021-03-28
0
618
动态规划练习(1)-买卖股票的最好时机
题目描述 假设你有一个数组,其中第\ i i 个元素是股票在第\ i i 天的价格。你有一次买入和卖出的机会。(只有买入了股票以后才能卖出)。请你设计一个算法来计算可以获得的最大收益。 示例1 输入[1,4,2]返回值3 思路 这种有点像双指针的问题,使用以下dp模板:一维数组,i往右遍历,j从i...
2021-03-28
0
468
最长回文子串
题目描述 对于一个字符串,请设计一个高效算法,计算其中最长回文子串的长度。给定字符串A以及它的长度n,请返回最长回文子串的长度。 示例1 输入"abc1234321ab",12返回值7 思路 1.转移方程容易想,但两个指针的移动方向容易出错。2.应该A指针向右走,B指针从A开始向左走,目的是B指针扫...
2021-03-22
0
523
字符串相加
题目 给定两个字符串形式的非负整数 num1 和num2 ,计算它们的和。提示:num1 和num2 的长度都小于 5100num1 和num2 都只包含数字 0-9num1 和num2 都不包含任何前导零你不能使用任何內建 BigInteger 库, 也不能直接将输入的字符串转换为整数形式 cod...
2021-03-18
0
499
首页
上一页
1
2
下一页
末页