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

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

题意 字符串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 417

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

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

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

题意 给定字符串,和最多可以先删除的字符数量,再对它进行连续字符的压缩,求压缩后字符串的最短长度 限制: 原字符串长度不大于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

题解 | #在字符串中找出连续最长的数字串#

题意 找字符串中最大长度的所有数字串，输出它们和最大长度 限制：字符串长度不大于200 方法 遍历 对字符串进行一次遍历，同时记录字符串起始位置，和最大长度。 以样例数据abcd12345ed125ss123058789为例 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14...
C++ 数学 字符串
2021-12-08
0 431

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

题意 沿n 乘 m的棋盘边界从左上角，只能向右或向下走到右下角的方案数 限制：n和m均不超过8 方法 递推 既然只能向右或者向下走，反过来说明一个位置要么从上方来，要么从左方来。切因为上一个点不同，所以这两个方向来的各不相同 定义dp[i][j]dp[i][j]dp[i][j] 表示从左上角走到第i...
C++ 数学 数组
2021-12-08
0 353

题解 | #合法IP#

题意 判断给定ip是否合法 方法 内置库 对于这种大量场景地方都会用到的函数，如果是在面向用户生产代码中，尽可能的不要自己实现，而是使用很多人用过有保障的库函数 inet_pton这个函数在成功时返回1，失败时返回0，所以我们直接调用它即可 代码 #include<bits/stdc++.h&...
C++ 数学
2021-12-08
9 821
牛客博客，记录你的成长
关于博客 意见反馈 免责声明 博文推荐 牛客网首页
公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层
联系方式：010-60728802(电话)
admin@nowcoder.com
京ICP备14055008号-1
京公网安备 11010502036488号