牛客最菜应届生

分类

题解(38)

/ 注册

全部文章（共10篇）

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

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

数组

2021-07-24

0 408

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

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

二分法数组

2021-07-17

0 313

题解 | #合并区间#

思路 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

题解 | #最小的K个数#

思路参考剑指offer1、首先使用快排的思想，对一个数组进行分割，大于某个值的在其右侧，小于某个值的在其左侧，该函数(Partition)返回一个索引，代表选择的数字的下标（可能有点绕）。2、然后就是根据这个返回的索引和k-1（需要k个数，下标范围就是0~k-1）比较，若返回的index<k...

快速排序数组

2021-07-11

0 331

题解 | #反转字符串#

丑数思路 1、使用一个数组保存之前的丑数2、更新下一个丑数的时候只需要比较三个值即可3、所以，程序的核心就是维护好三个值（对应的下标）代码 class Solution { public: bool isUgly(int x ){ while(x%2==0){ ...

数组

2021-07-10

0 327