云海翻腾

题解

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

/ 注册

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

题解 | #表达式求值#

表达式求值是经典问题。将表达式由中辍转为后辍如将(3+2)*30*(4-1)转为3,2,+30,*4,1,-*。转换方法为，用一个栈stk保存运算符号。对表达式进行遍历，当访问到数字时，添加到后辍式。当访问到'('时，入栈，当访问到')'时，出栈到后辍式，直到遇到'('，当访问到'+...

C++ 栈

2021-11-23

1 422

题解 | #最长无重复子数组#

最朴素的想法，用i做下标遍历数组，对于当前i，用j从i + 1开始遍历数组，当a[i:j-1]子数组中包含a[j]（设下标为k)时，说明a[i:j-1]不能更长，此时更新i为k+1。这样我们可以找到所有子数组和其长，自然可以找到最长子数组。优化点：判断a[i:j-1]中是否包含a[j]，以及如果...

C++ 数组哈希表

2021-11-22

0 354

题解 | #两数之和#

找满足和为target的两数下标，最主要是要能快速根据数找到下标。可以先建立数与下标的映射map。然后用i遍历数组，根据target与当前数计算出另一个数，然后在map中找，能找到，则很快能得到两数下标。 class Solution { public: vector<int>...

C++ 哈希表

2021-10-23

0 340

题解 | #包含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