牛客最菜应届生
牛客最菜应届生
全部文章
分类
题解(38)
归档
标签
去牛客网
登录
/
注册
牛客最菜应届生的博客
全部文章
(共38篇)
题解 | #树的子结构#
思路 1、递归2、辅助函数3、先找父节点的值相等的节点,进行IsPart判断;如果结果为false,那么对左右节点分别递归调用函数。4、注意边界条件、递归终止条件 代码 /* struct TreeNode { int val; struct TreeNode *left; ...
二叉树
2021-07-17
0
323
题解 | #合并区间#
思路 1、首先根据起点排序2、一个指针指向要检验的区间,一个对象代表已经合并好的区间,一直合并二者,知道他们不能合并,此时将合并好的区间存放进去,然后更新指针和区间3、注意越界情况和最后一段区间的保存问题 代码 /** * Definition for an interval. * struct...
双指针
2021-07-16
0
328
题解 | #寻找第K大#
思路 快排的思想,partition函数的使用。如果返回的pivot>n-K,那么right = pivot-1如果返回的pivot<n-K,那么left = pivot+1进行新一轮的partition,直到pivot = n-K 代码 class Solution { public:...
快速排序
2021-07-16
0
389
题解 | #删除链表的倒数第n个节点#
思路 双指针,同等速度,但是出发点不一样(fast比slow多走n-1步骤) 注意要考虑到前一个节点,注意要释放节点,拒绝内存泄漏注意要设置一个哑巴节点,使算法具有普适性 代码 /** * struct ListNode { * int val; * struct ListNode...
双指针
链表
2021-07-16
0
377
题解 | #合并区间#
思路 1、根据区间起点的大小,对区间排序2、一个指针,指向当前考虑的区间元素,一个区间元素代表当前合并后的区间,也就是判断两个区间能否合并3、对于能合并的,更新区间,更新指针;对于不能合并的,保存合并好的区间,将当前指针指向的区间设置为新的区间,指针向后移动1位4、当指针越界以后,保存当前合并好的区...
数组
2021-07-15
0
324
题解 | #接雨水问题#
思路 计算某一个位置处的雨水,就是计算该位置处往左最大高度、往右的最大高度的最小值与当前高度的差 所以思路一就是遍历每一个点,然后求和但是因为时间复杂度大,所以超时 思路二是使用动态规划,创建两个dp数组,代表下标为i处的左侧的最大值(或右侧的最大值,包括其本身),递推公式就是:当前最大高度 = m...
数组
动态规划
2021-07-15
0
330
题解 | #合并两个有序的数组#
思路 双指针因为A的空间是足够大的,所以将A数组和B数组中的最大的依次放在A的最后 所以双指针,分别指向A和B的尾部,比较其大小,大的放在A的最后 代码 class Solution { public: void merge(int A[], int m, int B[], int n) {...
双指针
数组
2021-07-15
0
268
题解 | #岛屿数量#
思路 1、广度优先搜索2、pair<int, int> 保存坐标3、遍历每一个点,如果发现是1,那么count++,并将其置为0,然后把这个pos放在队列中(广度优先),当队列不为空的时候做下面的事情:取坐标、判断上下左右是否为1,若为1则加入到队列中并将其置为0(防止重复计数),直至遍...
广度优先
数组
2021-07-14
0
419
题解 | #寻找第K大#
思路 借助快排的Partition函数注意:1、是第K大,因此Partition返回的结果要和n-K比较!!! 代码 class Solution { public: int Partition(vector<int>& arr, int L, int R ){ ...
二分法
快速排序
数组
2021-07-11
0
238
题解 | #数组中出现次数超过一半的数字#
思路 参考《剑指offer》1、一个数字出现次数超过一半,那么排序后的中间位置的元素肯定就是这个要求的数字2、借助Partition函数,返回一个索引index,代表该位置的元素在排序后的数组中下标是index,比arr[index]小的都在左侧,比arr[index]大的都在右侧;3、根据inde...
快速排序
数组
二分法
2021-07-11
0
337
首页
上一页
1
2
3
4
下一页
末页