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

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

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

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

题意 输出边长为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

题解 | #字符串解码#

题意 把压缩过的字符串还原, 压缩过的通过次数[字符串]来表示 范围: 输出长度不会超过50 方法 每次枚举展开 按照题意,我们可以从内到外进行解码. 那第一个出现的右侧括号所包含的内容,就是最内层的. 这样每次解码一块内容更新整个字符串.直到字符串被完全解码为止,就是要求的答案 代码 class ...
C++ 字符串
2022-01-03
0 413

题解 | #计算器(一)#

题意 给定一个包含加减括号的表达式，计算表达式的值 限制： 表达式长度不大于100000，计算过程保证在int内，只包含 数字 加减乘除 和 括号，保证表达式正确 方法 递归同时计算 考虑表达式，其实是由数值 运算符 数值 运算符 数值 运算符构成的 其中第一个数值可能是负号开始，可以通过判断起始字...
C++ 数学 字符串
2022-01-03
0 531

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

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

题解 | #下一个排列#

题意 求数组的所有排列中,恰好在当前数组排列的下一个的数组 限制: 数组长度不大于1000 方法 性质分析 如果一个数组恰好是另一个数组排列的下一个,那么首先两个数组不等,其次它们有公共前缀,在公共前缀后新数组比原数组大, 新数组剩余部分从小到大排列 正确性证明: 因为是下一个,所以不相等.存在一位...
C++ 数学
2022-01-03
1 416

题解 | #二叉树的后序遍历#

题意 给定一个二叉树，返回他的后序遍历的序列。 范围: 节点数不大于100 方法 递归遍历树 按题意所说,通过递归遍历树来获得其后续遍历 每次先遍历左子树,再右子树,最后根 以题目样例为例 递归层级 左子树 根 右子树 数组 0 null 1 {2,3} {} 1 {3} 2 nu...
C++ 二叉树
2022-01-03
0 404

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

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

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

题意 给定字符串能否由给定字典中的单词拼接而成. 限制: 字符串长度不大于500 字典单词数不大于1000,每个单词长度不大于20 方法 dfs 通过递归,每次匹配字典里所有单词,一旦匹配成功, 从匹配成功的下标递归搜索下一个位置,如果完全匹配了则返回匹配成功. 代码 class Solution ...
C++ 字符串 数组 动态规划
2022-01-03
0 442
牛客博客，记录你的成长
关于博客 意见反馈 免责声明 博文推荐 牛客网首页
公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层
联系方式：010-60728802(电话)
admin@nowcoder.com
京ICP备14055008号-1
京公网安备 11010502036488号