CroMarmot
CroMarmot
全部文章
分类
未归档(12) 题解(138) 题解总结(4)
归档
标签
去牛客网
全部文章 （共43篇）

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

题意 给定一个数组，每个值表示当前位置能向后移动的最远距离，同时也表示得分。 求从数组开始跳到数组结束的最大得分 限制： 数组长度不大于10000 方法 枚举遍历 使用一个辅助数组，记录每个位置能得到的最大得分。 遍历原数组，对于每个可行位置，更新这个位置之后的最大得分的值。 最终输出重终点的值即可...
C++ 数组 数学
2022-01-04
0 403

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

题意 给一个数组,每个位置表示当前能到之后的数组的最远距离,求从最开始到最后一个的位置跳转的最小次数 限制: 数组长度不大于1000 方法 遍历枚举 直接模拟题目,增加一个辅助数组记录每个位置的最小跳次数. 从头开始遍历,对每个可以到达的位置,更新它和它之后的位置的最小跳跃次数 如果有位置能直接到终...
C++ 数组 数学
2022-01-03
1 446

题解 | #螺旋矩阵(二)#

题意 输出边长为n的从外到内顺时针螺旋矩阵 限制: 边长不大于20 方法 模拟实现 考虑从1开始写,那么如果考虑书写的方向,则有4个方向, 右下左上. 注意到当一个方向不可再书写时,切换到下一个方向即可 以题目中样例数据 n=3为例 值 i j 方向 操作 1 0 0 右 右侧还可以写...
C++ 数组
2022-01-03
0 465

题解 | #长度最小的连续子数组#

题意 正值数组中,求最短的连续区间,使其区间上值的和大于等于给定值. 限制: 数组长度不大于10510^5105 数组中值不大于10410^4104 方法 二分法 首先,因为数组元素全为正,那么长度为i的所有区间的和的最大值,一定小于长度为i+1的区间和的最大值. 因此,随着区间长度上升,其区间和最...
C++ 数组 二分查找
2022-01-03
0 491

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

题意 字符串A最少需要多少次, 插入/删除/修改 能变成字符串B 限制,两个字符串长度均不超过500500500 方法 递推+状态 设计状态 dp[i][j] 表示,地一个字符串的前i个最少操作dp[i][j]次能变成第二个字符串前j 那么有状态转移 A[i]=B[j]时,对应位置字符相等,直接匹配...
C++ 数组 动态规划
2022-01-03
1 831

题解 | #压缩字符串(二)#

题意 给定字符串,和最多可以先删除的字符数量,再对它进行连续字符的压缩,求压缩后字符串的最短长度 限制: 原字符串长度不大于100 方法 dfs(TLE) 题目拆解为两部分 字符串删除 压缩字符串 对于字符串删除字符的部分,采用深度搜索的方式, 每层记录,当前遍历的字符串位置,还可以删除的字符串...
C++ 字符串 动态规划 数组
2022-01-03
0 784

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

题意 给定字符串能否由给定字典中的单词拼接而成. 限制: 字符串长度不大于500 字典单词数不大于1000,每个单词长度不大于20 方法 dfs 通过递归,每次匹配字典里所有单词,一旦匹配成功, 从匹配成功的下标递归搜索下一个位置,如果完全匹配了则返回匹配成功. 代码 class Solution ...
C++ 字符串 数组 动态规划
2022-01-03
0 443

题解 | #记票统计#

题意 n个人参与被投票，统计每人被投次数，与无效票数量 限制：参与人不大于100，投票总数不大于100 方法 基于STL实现 把题目要求文字内容直接翻译成代码 为了保持输出顺序，所以使用vector来记录输入顺序 为了判断是否出现过，使用set来记录参与人 为了统计每人被投次数，使用map来记录人...
C++ 数组
2021-12-09
0 355

题解 | #数组分组#

题意 一个数组分成两组 5的倍数在一组 是3的倍数 且 不是5的倍数 在另一组 剩余数字自由分组 是否能让分成的两组数字的和相等 限制：数组长度不大于50，数值绝对值不大于500 方法 动态规划 先不考虑限制，分成两组和相等，也就是两组数字和的差为0,即是第一组的和 - 第二组的和 = 0 再看...
C++ 动态规划 数组
2021-12-08
0 424

题解 | #走方格的方案数#

题意 沿n 乘 m的棋盘边界从左上角，只能向右或向下走到右下角的方案数 限制：n和m均不超过8 方法 递推 既然只能向右或者向下走，反过来说明一个位置要么从上方来，要么从左方来。切因为上一个点不同，所以这两个方向来的各不相同 定义dp[i][j]dp[i][j]dp[i][j] 表示从左上角走到第i...
C++ 数学 数组
2021-12-08
0 353
牛客博客，记录你的成长
关于博客 意见反馈 免责声明 博文推荐 牛客网首页
公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层
联系方式：010-60728802(电话)
admin@nowcoder.com
京ICP备14055008号-1
京公网安备 11010502036488号