牛客最菜应届生

题解

/ 注册

全部文章 / 题解（共38篇）

题解 | #输出二叉树的右视图#

思路 1、根据前序+中序遍历重建二叉树2、层序遍历输出二叉树的每一层的最右边的元素代码 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 求二叉树的右视图 * @para...

二叉树递归广度优先

2021-07-28

0 438

题解 | #二叉树根节点到叶子节点的所有路径和#

思路 1、深度优先，先序遍历2、和剑指offer34(和为某一值的二叉树路径)思路一样代码 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }...

二叉树深度优先

2021-07-28

0 426

题解 | #字符串出现次数的TopK问题#

思路 1、使用优先级队列，构建大根堆或者小根堆2、使用map<string, int>记录每一个string出现的次数代码 class Solution { public: /** * return topK string * @param strings ...

哈希 topK

2021-07-25

0 363

题解 | #换钱的最少货币数#

思路 1、动态规划2、计算使用每一种零钱时候的硬币数量（外层是零钱，内层是价值），dp[i]代表i所需的零钱数量，dp[i] = min(dp[i], dp[i-coin]+1)3、注意最后的返回条件代码 class Solution { public: /** * 最少货币数 ...

动态规划

2021-07-24

0 450

题解 | #顺时针旋转矩阵#

思路 1、首先按照左上到右下的连线做对称2、然后根据y轴做对称（下面是另外一种对称方式，道理是一样的）代码 class Solution { public: vector<vector<int> > rotateMatrix(vector<vector&l...

数组

2021-07-24

0 408

题解 | # 子数组的最大累加和问题 #

思路 1、动态规划 2、dp[i] = dp[i-1]+arr[i]或者dp[i] = arr[i] 代码 class Solution { public: /** * max sum of the subarray * @param arr int整型vector t...

动态规划

2021-07-24

0 297

题解 | #最长无重复子数组#

思路 1、哈希map，存放元素-索引2、一个指针表示最长无重复区间的开始，一个指针代表最长无重复区间的结束；当遇到不同元素时，将其加入到map中，第二个指针++，获取长度；当遇到重复的元素时，更新长度，更新i指针为之前重复元素的索引+1，重置map，j=i+1 代码 class Solution {...

双指针哈希

2021-07-24

0 301

题解 | #最长回文子串#

## 思路 1、辅助函数：计算从mid1和mid2开始往两边发散的最长的长度（为了考虑奇偶的情况，设置了两个形参） 2、计算每一个点的最长回文的长度 3、注意边界条件 ## 代码 ```cpp class Solution { public: &n...

字符串

2021-07-22

0 287

题解 | #最小编辑代价#

思路 1、动态规划问题，dp[i][j]代表前i个转化到前j个的代价（第i个代表下标为i-1的字符）2、初始化第0行、第0列（边界条件）3、递推公式：当str1[i-1] == str2[j-1]时，dp[i][j] == dp[i-1][j-1]; 当不想等时，取三个情况的最小值4、返回dp[m]...

动态规划字符串

2021-07-19

0 347

题解 | #在旋转过的有序数组中寻找目标值#

思路 1、二分法2、得到mid后先判断单调区间。分两种讨论，得到单调区间以后再判断target和当前单调区间的关系，对应地更新端点3、注意边界条件（输入为1的时候等）代码 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改...

二分法数组

2021-07-17

0 313