逝去的曾经
逝去的曾经
全部文章
分类
题解(22)
归档
标签
去牛客网
登录
/
注册
逝去的曾经的博客
全部文章
(共22篇)
题解 | #扑克牌顺子#
第一次思路: 对于每个元素x: 如果x == 0,则忽略; 如果x已经出现过,则false; 否则取其合理空间[x - 4, x + 4](遇到边界截取) 对每个元素的合理区间取交集,如果所有元素都在交集里,则合法,否则不能成为顺子 class Solution { public: bo...
C++
2021-12-17
0
236
题解 | #不用加减乘除做加法#
首先看十进制是如何做的: 5+7=12,三步走 第一步:相加各位的值,不算进位,得到2。 第二步:计算进位值,得到10. 如果这一步的进位值为0,那么第一步得到的值就是最终结果。 第三步:重复上述两步,只是相加的值变成上述两步的得到的结果2和10,得到12。 同样我们可以用三步走的方式计算二进制值相...
C++
2021-12-16
0
251
题解 | #数据流中的中位数#
堆的做法: 中位数是指:有序数组中中间的那个数。则根据中位数可以把数组分为如下三段: [0 ... median - 1], [median], [median ... arr.size() - 1],即[中位数的左边,中位数,中位数的右边] 那么,如果我有个数据结构保留[0...median-1]...
C++
2021-12-16
0
277
题解 | #正则表达式匹配#
动态规划: 首先我们定义一个f[i][j]的状态转移方程,其中i 表示str中的第i个字符;j表示pattern中的第j个字符,然后判断是否匹配。我们需要判断两种情况: 第一种是当i、j指向的字符是同一个字母/点号(".")的时候,我们只需要判断对应位置的字符是否相同,相同则转移状态去判断子问题f...
C++
2021-12-13
0
312
题解 | #连续子数组的最大和(二)#
动态规划的思路,但要注意:每次考虑的元素是包含当前元素的子数组 1. 如果当前子数组和为负数,即便加上当前元素,和也不会变大,因此从当前元素开始开辟新数组; 2. 否则当前子数组加上当前元素合并成新的子数组; 3. 过程中始终维护最大子数组的和及开始与结束的下标 class Solution { ...
C++
2021-12-11
0
258
题解 | #序列化二叉树#
通过前序遍历或层次遍历(递归 或 非递归)去建树 注意char* 的使用 /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : ...
C++
2021-12-09
0
226
题解 | #在二叉树中找到两个节点的最近公共祖先#
递归: 如果当前root是o1或o2,则当前root为要找的公共祖先; 否则: 如果o1和o2都在左(右)子树,则递归去子树中寻找; 如果o1和o2分散在左右子树中,则当前root为要找的公共祖先 /** * struct TreeNode { * int val; * struct...
C++
2021-12-07
0
233
题解 | 二叉树中和为某一值的路径(三)
这题首先需要遍历一遍树,把当前遍历的节点作为根节点出发,再去求符合条件的路径的个数。 第一次遍历可以用简单的层次遍历,利用队列实现;第二次遍历可以用dfs 方法一:非递归的dfs /** * struct TreeNode { * int val; * struct TreeNode *lef...
C++
2021-12-07
1
332
题解 | #矩阵中的路径#
数学方式解决 在做这题之前我们先来看这样一个问题: 一个整数先把他分成两部分,x+y=n(假设x>=y并且x-y<=1,也就是说x和y非常接近)那么乘积是xy。 然后我们再把这两部分的差放大(x+1)+(y-1)=n(假设x>=y);他们的乘积是(x+1)(y-1)=xy-(x-y...
C++
2021-12-06
1
274
题解 | #旋转数组的最小数字#
时间复杂度要求O(lgn),考虑二分法: 如果当前数组 v[l] < v[j],则当前数组是有序的,返回最小值v[l]; 否则取数组中间mid: 如果v[l] < v[mid],则最小值在mid + 1 ~ r 中; 如果v[l] > v[mid],则最小值在l ~ mid 中...
C++
2021-12-05
0
260
首页
上一页
1
2
3
下一页
末页