逝去的曾经

题解

/ 注册

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

题解 | #扑克牌顺子#

第一次思路：对于每个元素x：如果x == 0，则忽略；如果x已经出现过，则false；否则取其合理空间[x - 4, x + 4](遇到边界截取) 对每个元素的合理区间取交集，如果所有元素都在交集里，则合法，否则不能成为顺子 class Solution { public: bo...

C++

2021-12-17

0 373

题解 | #不用加减乘除做加法#

首先看十进制是如何做的： 5+7=12，三步走第一步：相加各位的值，不算进位，得到2。第二步：计算进位值，得到10. 如果这一步的进位值为0，那么第一步得到的值就是最终结果。第三步：重复上述两步，只是相加的值变成上述两步的得到的结果2和10，得到12。同样我们可以用三步走的方式计算二进制值相...

C++

2021-12-16

0 348

题解 | #数据流中的中位数#

堆的做法：中位数是指：有序数组中中间的那个数。则根据中位数可以把数组分为如下三段: [0 ... median - 1], [median], [median ... arr.size() - 1]，即[中位数的左边，中位数，中位数的右边] 那么，如果我有个数据结构保留[0...median-1]...

C++

2021-12-16

0 409

题解 | #正则表达式匹配#

动态规划：首先我们定义一个f[i][j]的状态转移方程，其中i 表示str中的第i个字符；j表示pattern中的第j个字符，然后判断是否匹配。我们需要判断两种情况：第一种是当i、j指向的字符是同一个字母/点号（"."）的时候，我们只需要判断对应位置的字符是否相同，相同则转移状态去判断子问题f...

C++

2021-12-13

0 407

题解 | #连续子数组的最大和(二)#

动态规划的思路，但要注意：每次考虑的元素是包含当前元素的子数组 1. 如果当前子数组和为负数，即便加上当前元素，和也不会变大，因此从当前元素开始开辟新数组； 2. 否则当前子数组加上当前元素合并成新的子数组； 3. 过程中始终维护最大子数组的和及开始与结束的下标 class Solution { ...

C++

2021-12-11

0 364

题解 | #序列化二叉树#

通过前序遍历或层次遍历（递归或非递归）去建树注意char* 的使用 /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : ...

C++

2021-12-09

0 314

题解 | #在二叉树中找到两个节点的最近公共祖先#

递归：如果当前root是o1或o2，则当前root为要找的公共祖先；否则：如果o1和o2都在左（右）子树，则递归去子树中寻找；如果o1和o2分散在左右子树中，则当前root为要找的公共祖先 /** * struct TreeNode { * int val; * struct...

C++

2021-12-07

0 330

题解 | 二叉树中和为某一值的路径(三)

这题首先需要遍历一遍树，把当前遍历的节点作为根节点出发，再去求符合条件的路径的个数。第一次遍历可以用简单的层次遍历，利用队列实现；第二次遍历可以用dfs 方法一：非递归的dfs /** * struct TreeNode { * int val; * struct TreeNode *lef...

C++

2021-12-07

1 465

题解 | #矩阵中的路径#

数学方式解决在做这题之前我们先来看这样一个问题: 一个整数先把他分成两部分，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

2 363

题解 | #旋转数组的最小数字#

时间复杂度要求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 348