云海翻腾

题解

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

/ 注册

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

题解 | #把数组排成最小的数#

将数组进行排序，排序的原则是对于数字a和b，如果ab<ba，则a在b前。将数组中的元素连起来即可。注意计算ab和ba过程中的性能优化，避免重复计算，包括指数运算和求位数，也可以选择性能高的排序算法。 int g_tenPow[] = { 0, 10, ...

C++

2021-10-16

0 409

题解 | #整数中1出现的次数（从1到n整数中1出现的次数）#

统计1到N的所有数中1出现的次数，只需要计算1出现在每一位上的次数分析：N有n位，将n位数记作(x1)...(xi-1)(xi)(xi+1)...(xn), 前i-1位组成的数记作X前, 后n-i位组成的数记作X后。一般地，求第i位为1时的数字个数，分三种情况 N的第i位为0：X前要小于(x...

C++ 数学

2021-10-16

0 438

题解 | #链表中环的入口结点#

快慢指针法快指针速度是慢指针速度的2倍。如图所示，设快慢指针相遇在C点，相遇时快指针走过2S，则慢指针走过S。慢指针走了S=a+b 快指针走了2S=a+b+n(b+c) 可得a=(n-1)(b+c)+c 也就是说a等于若干圆周加上c。那让两个指针同时在A点和C点出发，必然相遇在B点（入口） ...

C++ 双指针数学

2021-10-16

0 356

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

用二分法分别找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 418

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

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

C++ 回溯递归

2021-10-16

0 348

题解 | #矩形覆盖#

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 267

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

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

C++ 排序树二叉树递归

2021-10-16

0 421

题解 | #扑克牌顺子#

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

C++ 数组

2021-10-13

0 435

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

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

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

2021-10-13

0 335

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

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

C++ 数组计数

2021-10-13

0 319