云海翻腾

分类

C++(5) 程序/算法设计(2) 题解(29)

/ 注册

全部文章（共36篇）

题解 | #数字在升序数组中出现的次数#

用二分法分别找k-0.5和k+0.5应该插入的位置，位置距离即k的个数 class Solution { public: int bSearch(const vector<int> &vec, double k) { int beg = 0; int end...

C++ 二分查找

2021-10-16

4 421

题解 | #机器人的运动范围#

从[0,0]开始向右或向下进行探索，直到不满足threshold就停止。停止理由是如果当前坐标都不满足threshold，那么右下方就不可能有满足的坐标。 class Solution { public: char ** newMaxtrix(int rows, int cols) { ...

C++ 回溯递归

2021-10-16

0 350

题解 | #矩形覆盖#

f(n)表示2*n（横为n，竖为2）时的结果。当最后一列选择竖放时，即为f(n - 1) 当最后一列选择横放时，即为f(n - 2) 所以f(n) = f(n - 1) + f(n - 2)，类斐波那契数列，递归式如下： f(n)={f(n−1)+f(n−2),n>21,n=12,n=2f(...

C++ 动态规划递归

2021-10-16

0 271

题解 | #二叉搜索树的后序遍历序列#

BST的特点是对任意结点，左子树小于该结点，右子树大于该结点。后序遍历产生的序列为左子树-右子树-结点。所以可知后序遍历序列的最后一个元素即为BST的根，再根据大小规律，可以找到左右子树对应的序列。递归处理这两个序列即可。找左右子树序列时可采用二分查找法，虽然左右子树序列不是完全有...

C++ 排序树二叉树递归

2021-10-16

0 425

题解 | #扑克牌顺子#

首先对数字进行排序，排序过程中同时判断除0外是否有重复的数字，有重复则不能组成顺子。对排好序的非0序列arr[start:end]进行计算，看要组成顺子还差几张牌，差的牌数小于等于0的个数，则能组成，否则不能组成如2,4,7序列，则还差(4-2+1) + (7-4+1)=3张，这时只有两个0是不...

C++ 数组

2021-10-13

0 441

题解 | #二叉搜索树与双向链表#

递归分析：递归左子树，递归返回时左子树自然成双向链表，如图，4的左子树将变成1-2-3，当然4的左孩子还是2，这时只要顺着2向链表的右边找到最后一个结点3将是4在链表中的直接前驱。右子树操作与左子树对称 class Solution { public: TreeNode *searc...

C++ 二叉搜索树深度优先搜索双向链表

2021-10-13

0 338

题解 | #数组中出现次数超过一半的数字#

分析一个数字出现的次数超过数组长度的一半<=>这个数字出现的次数可以抵消所有其它数字出现的次数首先对elem=a[0]进行计数cnt=1, 当后面a[i]为elem时，就cnt++，否则cnt--，当cnt减为0时，从elem=a[i]重复前面的动作。这样最终所求数字只可能是ele...

C++ 数组计数

2021-10-13

0 323

题解 | #丑数#

一、维护两个序列，分别叫uglys和factors uglys表示生成的丑数序列，每时刻该序列都是正确的，无需调整，初始化值只有1 factors与uglys对应，每个元素表示对应丑数当前应该乘的因子（只可能是2、3、5和-1），初始值2 二、丑数生成过程，循环执行下面的步骤从factors中找...

C++ 数组数学

2021-10-12

0 318

题解 | #最小的K个数#

方法一基于堆排序构建小顶堆arr[0:n-1]后，重复k次：将堆顶交换到堆末，即swap(arr[0], arr[n-1])，调整arr[0:n-2]，使其为小顶堆。 arr[n-1:n-k]即为所求方法二基于快排对于arr[beg:end]每次递归调整后，基准元素arr[j]不小于前面...

C++

2021-10-12

0 397

题解 | #矩阵的最小路径和#

这是一个典型的动态规划问题。从最左上结点a[0][0]到当前结点a[i][j]的最短路径dp[i][j]只取决于dp[i - 1][j], dp[i][j - 1]和a[i][j]。当然要特殊考虑一下i或j为0的情况。递推式为：dp[i][j] = min(dp[i - 1][j], dp[...

C++ 动态规划

2021-10-11

0 384