云海翻腾

分类

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

/ 注册

全部文章（共36篇）

题解 | #包含min函数的栈#

以入栈3 2 1 5 1为例，维护两个栈，分别是正常栈stk和栈顶时刻为最小元素的栈minstk，观察入栈过程中两个栈的变化。栈顶在右边。入栈原则: 比较入栈元素和minstk栈顶元素，小的入minstk。初始状态: stk: minstk: 入栈3： stk: 3 minstk: 3 ...

C++ 栈

2021-10-22

0 327

题解 | #两数相除#

用减法来实现除法，a/b就是看a可以最多减去多少个b。优化，可以对b进行左移n位得到c，只要c比a小。这样a可以一次减去c，也即一次减去了2的n次方个b。 class Solution { public: int divide(int dividend, int divisor) { ...

C++ 数学

2021-10-21

0 521

题解 | #栈的压入、弹出序列#

遍历压栈序列，压入初始为空的栈stk中。在此过程中，每压入一个元素时判断stk栈顶元素是否和出栈序列首元素相等如果相等，删除栈顶元素，同时删除出栈序列首元素（实际实现时不用删除，用下标++访问即可）循环这两步操作，直到不满足相等条件。遍历完压栈序列时，stk为空，说明满足。 class...

C++ 栈

2021-10-21

0 369

题解 | #数值的整数次方#

快速幂。思路就是增大底数减少循环次数。下面用^表示指数运算，讨论a^b非负指数情况。当b为偶数时，a^b=(a^2)^(b/2) 当b为奇数时，a^b=a(a^2)^(b/2) 程序实现时，奇偶判断可以用位与运算，除2可以用位移运算，负指数转化成正指数。如果用递归实现看起来会更直观，下面用循环实...

C++ 数学

2021-10-21

0 345

题解 | #求1+2+3+...+n#

递增数列加法转乘法,除2转位移结合二进制位运算用加法来实现两数相乘（与十进制乘法转加法类似） class Solution { public: int multi(int a, int b) { int ret = 0; (a & 1) && (ret +=...

C++ 数学

2021-10-20

0 267

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

sum=a^b为不考虑进位的情况下进行了加法运算 carry=(a&b)<<1求出了每一位的进位，如果进位不为0,加到sum上，重新求得sum和carry。如此循环直到进位为0 class Solution { public: int Add(int num1, int...

C++ 数学

2021-10-20

0 361

题解 | #二进制中1的个数#

其实第1种情况是第2种情况的特例，只用第2种情况的证明，不管i是否为1逻辑上也是OK的。 class Solution { public: int NumberOf1(int n) { unsigned int v1 = n; int cnt = 0; wh...

C++ 数学

2021-10-18

0 301

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

将数组进行排序，排序的原则是对于数字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