牛客313925129号 level
获赞
169
粉丝
3
关注
4
看过 TA
35
复旦大学
2021
C++
IP属地：上海
暂未填写个人简介
私信
关注
发布(51) 评论 刷题
2022-03-07 16:48
复旦大学 C++
0 点赞 评论 收藏
分享
2022-03-07 16:18
复旦大学 C++
题解 | #字符串的全部子序列#
题意理解 输出一个字符串的所有子串。注意重复出现的子串只保留一个。 方法一 深度优先搜索 每一个字符都有2种情况，选择或者不选择。我们遍历字符串s中的所有字符，每个字符用递归尝试两种调用（选或者不选）。递归的边界条件是遍历到最后一个字符，将得到的子串加入到答案中，然后再回退并进行另一条支路上的递归。 深度优先搜索的示意图如下，字符串为"ab"，边上"0"表示不选，"1"表示选： 最后对包含了所有答案的数组进行排序并去重。 具体代码如下： class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 ...
0 点赞 评论 收藏
分享
2022-03-07 15:07
复旦大学 C++
题解 | #给单链表加一#
题意理解 用链表表示一个数字，把该数字加1，再用链表的格式输出。 方法一 递归 因为这里是单向链表，且最低位在链表的尾端。如果指针遍历到链表尾端做加法后，处理进位时无法向前传递。所以考虑使用递归的方法，cal()函数返回这一位上产生的进位。 在该函数中，我们先通过递归调用获得前一位产生的进位，然后计算本位上会产生的进位，最后计算本位在加法计算后的值。注意这里的顺序不能改变。最低位需要加1，我们单独处理。同时，如果最高位产生了进位，我们还需要在链表的头前面再加上一个节点。 递归调用的示意图如下： 具体代码如下： /** * struct ListNode { * int val; * s...
0 点赞 评论 收藏
分享
2022-03-06 17:35
复旦大学 C++
题解 | #二进制求和#
题意理解 把两个字符串格式的二进制数字相加，求和的结果也用字符串的二进制数表示。 方法一 高精度加法 把字符串二进制数字转换成数组格式，每一位对应于数组中的一个整型元素。两个数组a，b从位置0开始表示二进制数的最低位（即倒序），在每一个位置上做加法操作，并计算是否要进位。当较短的数字的每一位都加完后，单独处理另外一个数组剩下的位。 示意图如下： 具体代码如下： class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param A string字符串...
0 点赞 评论 收藏
分享
2022-03-05 16:58
复旦大学 C++
0 点赞 评论 收藏
分享
2022-03-04 18:34
复旦大学 C++
题解 | #岛屿的最大面积#
题意理解 地图是一个矩阵，每个格子里面是0或者1。格子的上下左右视为相邻，即连在一起。要求最大的岛屿面积就是求连在一起的1的个数最多是多少。 方法一 深度优先搜索 对于每一个格子，我们有上下左右四个方向，如果相邻的格子是1，那么就可以向这个方向移动，面积加1。 我们使用pass数组记录每个格子是否遍历过，没有遍历过且值为1的格子才可以走上去，否则都不行。注意这里不是在寻找路径，所以在递归后pass不回退，否则会导致面积计算错误。 在主程序中，我们遍历矩阵grid，遇到格子值为1就进行一次dfs，得到一个连在一起的1的个数，更新一次最大值。 演示过程如下，红点表示当前所在位置： 具体代码如下：...
0 点赞 评论 收藏
分享
2022-03-16 08:15
已编辑
复旦大学 C++
题解 | #判断是不是二叉搜索树#
题意理解 二叉搜索树的要求，每个节点大于其左子树中所有节点，且小于其右子树中所有节点。 方法一 前序遍历 对于每一个结点，我们判断它是否满足搜索树的条件，再依次判断其左孩子和右孩子是否满足。在判断节点是否满足条件时，分两种情况讨论： 1）该节点为左孩子，那么它要小于其父节点，且大于其父节点需要大于的值。 2）该节点为右孩子，那么它要大于其父节点，且小于其父节点需要小于的值。 换句话说，当父节点小于x时，以其为根的子树均小于x；当父节点大于y时，以其为根的子树均大于y。 下图展示了1、2对应的情形： 具体代码如下： /** * struct TreeNode { * int val; *...
0 点赞 评论 收藏
分享
2022-03-02 16:30
复旦大学 C++
题解 | #单词拆分(二)#
题意理解 把一个字符串s拆分为若干个子串，要求每个子串都是数组dic中的某个元素。拆分的方***有多种，要求输出所有的方法，每一种拆分方法用空格将子串隔开从而形成一个字符串。 方法一 深度优先搜索 看到题目要求的数据较小，考虑使用深度优先搜索枚举所有的可能性。如果s可以被正确拆分，说明其头部的一段子串是dic中的元素。 每次搜索时，遍历dic数组。对于其中的每个元素，判断它和s的头部等长的子串是否相同。 1、如果相同：把s头部对应的子串剔除，拆分剩余的部分remain，进入递归； 2、如果不同，判断dic中下一个元素。 边界条件：s为空，说明s被拆分完毕。 由于dic中可能出现重复的元素，会导...
0 点赞 评论 收藏
分享
2022-03-01 23:44
复旦大学 C++
题解 | #给数组加一#
题意理解 用数组从前往后每个元素分别表示数字的从高到低的每一位，现在对表示的数字进行加1操作，要求得到的结果仍要用数组表示。 方法一 模拟 数组元素的个数（表示数字的位数）可能有500个，因此不考虑将数字还原成整型。我们使用列竖式计算的方法，将1和数组的最后一个元素对齐并相加，如果产生进位则继续把前一个元素加1。需要判断数字的最高位是否还要向前进位。最后要将得到的结果翻转。整个过程可以参考高精度加法。 示意图如下： 具体代码如下： class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 ...
0 点赞 评论 收藏
分享
2022-03-01 16:53
复旦大学 C++
0 点赞 评论 收藏
分享
2022-02-28 14:56
复旦大学 C++
题解 | #打家劫舍(三)#
题意理解 相比于前面两题，这里把房子的布局设置为二叉树的形式。现在要求选择数字的时候，父结点和孩子结点不能同时选。 方法一 深度优先搜索 对于某个结点，可以选择或者不选，我们通过深度优先搜索遍历出每种可能的情况，并计算出对应结点数字的总和。如果选择当前结点，那么以它为根结点的数字总和为它本身加上以其左右孩子为根（且不选择其左右孩子）的数字总和；如果不选择当前结点，那么以它为根结点（不选择）的数字总和为以其左右孩子为根的数字总和。这样就形成了一个递归过程。 我们使用map类型num来表示每个结点在选或者不选的时候，对应的数字总和的最大值；其中索引为由结点和布尔型构成的pairpairpair。 ...
0 点赞 评论 收藏
分享
2022-02-25 23:08
复旦大学 C++
题解 | #打家劫舍(二)#
题意理解 同样的，也是从一个数组中不相邻地取出若干的数，使其之和最大，这里把第0个数和最后一个数视为相邻的。 方法一 动态规划 和题目176一样，我们使用value数组表示从前往后到第i个数字，且选择第i个数字的时候，选到的数之和的最大值。因为最后的结果中肯定有某个数是最后一个被选到的数字，所以我们只要遍历一遍value，找到其最大值即可。 不同的是，由于第0个数和最后一个数相邻，我们要分两种情况讨论，一是选第0个数，不选最后一个数；另一种是正好相反。最后比较这两种情况下的最大值谁更大。 至于value[i]怎么求。我们假设已经知道之前每个位置上的value，value[i]则为nums[i]...
0 点赞 评论 收藏
分享
2022-02-25 17:16
复旦大学 C++
题解 | #打家劫舍(一)#
题意理解 对于一个非负数组nums，我们从中选取若干个数，要求被选到的数不能相邻。问选到的数之和最大为多少。 方法一 动态规划 由于相邻的数字不能同时选，那么不确定的因素太多了，我们先要确定一个下来。使用value数组表示从前往后到第i个数字，且选择第i个数字的时候，选到的数之和的最大值。因为最后的结果中肯定有某个数是最后一个被选到的数字，所以我们只要遍历一遍value，找到其最大值即可。 至于value[i]怎么求。我们假设已经知道之前每个位置上的value，value[i]则为nums[i]加上value[0]~value[i-2]之间的最大值，nums[i-1]是不能被选的。这样状态转移...
0 点赞 评论 收藏
分享
2022-02-24 23:20
复旦大学 C++
0 点赞 评论 收藏
分享
关注他的用户也关注了：
牛客网
牛客企业服务