两整数之和、数据流的中位数和逆波兰表达式
两整数之和
不使用运算符
+ 和 - ，计算两整数 a 、b 之和。示例 1：
1
输入: a = 1, b = 2
2
输出: 3
Copied!
示例 2：
1
输入: a = -2, b = 3
2
输出: 1
Copied!
方法一 二进制位操作法
思路
既然不能直接使用运算符
+ 和 - ，可以考虑使用二进制相关的与、非和异或等位操作符来完成运算。详解
- 与运算：二进制中的与运算是均为 1 才 得 1，这样可以得到需要进位的地方，然后将其左移一位得到其进位后的结果。如：
1
a = 5 = 0101
2
b = 4 = 0100
3
4
a & b 如下：
5
6
0 1 0 1
7
0 1 0 0
8
-------
9
0 1 0 0
10
11
结果左移一位后如下：
12
1 0 0 0
Copied!
- 异或运算：二进制中的异或运算是无进位加法，也就是两数异或得到所有不需要进位的结果。如：
1
a = 5 = 0101
2
b = 4 = 0100
3
4
a ^ b 如下：
5
6
0 1 0 1
7
0 1 0 0
8
-------
9
0 0 0 1
Copied!
因此对于任意两个数，我们可以通过与运算后左移一位得到需要进位的结果，两数异或运算得到不需要进位的结果。循环操作，直到需要进位的为 0 ，那么得到的不需要进位的结果就是两数之和。
- 解题步骤如下：
- 两整数
a、b之和的问题可以拆分为a 和 b 的进位结果+a 和 b 的无进位结果 - 需要进位的地方进行与操作并将得到的结果左移一位得到
a 和 b 的进位结果 - 不需要进位的地方进行异或操作得到
a 和 b 的无进位结果 - 一直循环操作第 2 和 3 步，直到需要进位的为0
代码
1
const getSum = function (a, b) {
2
while (a !== 0) {
3
const t = (a & b) << 1; // a & b 将需要进位的地方进行与操作，并左移一位
4
b = a ^ b; // a ^ b 将不需要进位的地方进行异或操作
5
a = t; // 每次将需要进位的赋值给 a ，继续执行上述操作，直到不需要进位
6
}
7
return b;
8
};
Copied!
复杂度分析
- 时间复杂度：对于任意两个数，循环体的代码需要执行次。问题规模属于线性阶，故时间复杂度为。
- 空间复杂度：
方法二 取对数法
思路
我们可以利用同底数幂的底数不变，指数相加的乘法规则，先取指数再取对数，等到答案。JS 中 Math 对象相关函数如下：
1
Math.log();
2
// 用于返回一个数的自然对数
3
Math.exp();
4
// 用于返回一个数的指数
5
Math.round();
6
// 用于返回一个数四舍五入后最接近的整数
Copied!
详解
- 1.此方法法主要借用了 JS 内置对象的 Math.log()、Math.exp() 和 Math.round() 三个函数
- 2.先取两个整数的指数的乘积
- 3.再取乘积结果的对数
- 4.最后再对得到的对数四舍五入，得到最终答案
- 5.注：引入了 10 的 10 次方是为了解决精度丢失的问题
参考代码
1
const getSum = function (a, b) {
2
return Math.round(Math.log((Math.exp(a / 10e10) * Math.exp(b / 10e10))) * 10e10);
3
};
Copied!
复杂度分析
- 时间复杂度：对于任意两个数，只需要进行 1 次运算。问题规模属于常数阶，故时间复杂度为。
- 空间复杂度：此算法需要为 2 个常量 a 和 b 分配空间。空间占用属于常数阶，故空间复杂度为。
数据流的中位数
中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
- void addNum(int num) - 从数据流中添加一个整数到数据结构中。
- double findMedian() - 返回目前所有元素的中位数。
示例
1
addNum(1)
2
addNum(2)
3
findMedian() -> 1.5
4
addNum(3)
5
findMedian() -> 2
Copied!
方法一 堆
思路
生成两个堆：small和large。用small堆存放数据中较小的一半元素，large堆存放数据中较大的一半元素
详解
建立两个堆，这两个堆需要满足:
- 1.大顶堆元素都比小顶堆小；
- 2.大顶堆元素不小于小顶堆，且最多比小顶堆多一个元素
然后，我们观察可以发现，如果，数据总数是偶数，那么大顶堆，和小顶堆， 一边占一半元素，而且，还是有序的，很像二分法，这时，中位数为两堆顶平均值 如果数据个数为奇数，则，中位数出现在元素个数多的堆的堆顶中
代码
1
const MedianFinder = function () {
2
this.maxHeap = [];
3
this.minHeap = [];
4
};
5
function minHeapify () {
6
this.minHeap.unshift(null);
7
const a = this.minHeap;
8
for (let i = a.length - 1; i >> 1 > 0; i--) {
9
// 自下往上堆化
10
if (a[i] < a[i >> 1]) {
11
// 如果子元素更小，则交换位置
12
const temp = a[i];
13
this.minHeap[i] = a[i >> 1];
14
this.minHeap[i >> 1] = temp;
15
}
16
}
17
this.minHeap.shift(null);
18
}
19
20
function maxHeapify () {
21
this.maxHeap.unshift(null);
22
const a = this.maxHeap;
23
for (let i = a.length - 1; i >> 1 > 0; i--) {
24
// 自下往上堆化
25
if (a[i] > a[i >> 1]) {
26
// 如果子元素更大，则交换位置
27
const temp = a[i];
28
this.maxHeap[i] = a[i >> 1];
29
this.maxHeap[i >> 1] = temp;
30
}
31
}
32
this.maxHeap.shift(null);
33
}
34
35
MedianFinder.prototype.addNum = function (num) {
36
// 插入
37
if (num >= (this.minHeap[0] || Number.MIN_VALUE)) {
38
this.minHeap.push(num);
39
} else {
40
this.maxHeap.push(num);
41
}
42
// 使得大顶堆的数量最多大于小顶堆一个， 且一定不小于小顶堆数量
43
if (this.maxHeap.length > this.minHeap.length + 1) {
44
// 大顶堆的堆顶元素移动到小顶堆
45
this.minHeap.push(this.maxHeap.shift());
46
}
47
48
if (this.minHeap.length > this.maxHeap.length) {
49
// 小顶堆的堆顶元素移动到大顶堆
50
this.maxHeap.push(this.minHeap.shift());
51
}
52
53
// 调整堆顶元素
54
if (this.maxHeap[0] > this.minHeap[0]) {
55
const temp = this.maxHeap[0];
56
this.maxHeap[0] = this.minHeap[0];
57
this.minHeap[0] = temp;
58
}
59
60
// 堆化
61
maxHeapify.call(this);
62
minHeapify.call(this);
63
};
64
65
MedianFinder.prototype.findMedian = function () {
66
if ((this.maxHeap.length + this.minHeap.length) % 2 === 0) {
67
return (this.minHeap[0] + this.maxHeap[0]) / 2;
68
} else {
69
return this.maxHeap[0];
70
}
71
};
Copied!
复杂度分析
- 时间复杂度：
- 空间复杂度：
方法二 二分查找插入法
思路
JS中操作数组非常方便，我们可以使用Array.splice这样的方法向数组的中间进行数据添加和删除。因此在JS中，二分法则成为了一个不错的选择
详解
难点在于每次插入后，保证数列按顺序排列，每次插入时可用二分法找出插入位置 1. 使用二分查找发找出插入位置 2. 维护一个数组永远保持有序
代码
1
var MedianFinder = function() {
2
this.num = []
3
};
4
5
function binarySearch(a, target) {
6
target += 1;
7
var start = 0
8
var end = a.length - 1;
9
10
while(start <= end) {
11
var mid = ~~((start + end) >> 1);
12
if (a[mid] >= target)
13
end = mid - 1;
14
else
15
start = mid + 1;
16
}
17
18
return start;
19
}
20
21
MedianFinder.prototype.addNum = function(num) {
22
var index = binarySearch(this.num, num);
23
this.num.splice(index, 0, num);
24
};
25
26
27
MedianFinder.prototype.findMedian = function() {
28
var len = this.num.length;
29
if (len & 1)
30
return this.num[~~(len / 2)];
31
else return (this.num[len / 2] + this.num[len / 2 - 1]) / 2;
32
};
Copied!
复杂度分析
- 时间复杂度：上述解法中用二分查找将耗费时间，插入时将耗费的时间，所以时间复杂度为
- 空间复杂度：
逆波兰表达式求值
有效的运算符包括
+, -, *, /。每个运算对象可以是整数，也可以是另一个逆波兰表达式。说明：
整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：
1
输入: ["2", "1", "+", "3", "*"]
2
输出: 9
3
解释: ((2 + 1) * 3) = 9
Copied!
示例 2：
1
输入: ["4", "13", "5", "/", "+"]
2
输出: 6
3
解释: (4 + (13 / 5)) = 6
Copied!
示例 3：
1
输入: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
2
输出: 22
3
解释:
4
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
5
= ((10 * (6 / (12 * -11))) + 17) + 5
6
= ((10 * (6 / -132)) + 17) + 5
7
= ((10 * 0) + 17) + 5
8
= (0 + 17) + 5
9
= 17 + 5
10
= 22
Copied!
方法一 入栈出栈法
思路
根据示例中的逆波兰表达式转中序表达式的过程可知，
+, -, *, /运算符的两个操作数正好是运算符前两位，即逆波兰表达式 ab+的运算符为+、操作数分别为a和b，转中序表达式就是a + b；根据这个规则，顺序遍历表达式中各项值，遇到操作数时，操作数入栈，遇到运算符时，栈顶两个操作数分别出栈，并应用运算符完成两个操作数的计算；详解
- 1.定义
*, +, -, /四个运算符与对应操作的映射关系ACTIONS。 - 2.定义stack数组，用于数据出栈入栈。
- 3.遍历tokens数组，如遇到运算符时，依次弹出栈顶两个元素，并作为参数调用运算符对应的操作，将操作结果入栈。
- 4.如遇上非运算符，则解析成Int类型压栈。
- 5.返回stack数组栈顶元素作为逆波兰表达式结果。
代码
1
/**
2
* @param {string[]} tokens
3
* @return {number}
4
*/
5
const ACTIONS = {
6
'*': (a, b) => b * a,
7
'+': (a, b) => b + a,
8
'-': (a, b) => b - a,
9
'/': (a, b) => parseInt(b / a)
10
};
11
12
const evalRPN = function (tokens) {
13
const stack = [];
14
tokens.forEach(token => {
15
const action = ACTIONS[token];
16
if (action) {
17
stack.push(action(stack.pop(), stack.pop()));
18
} else {
19
stack.push(parseInt(token));
20
}
21
});
22
return stack.shift();
23
};
Copied!
复杂度分析
- 时间复杂度：需要遍历逆波兰表达式数组，查找操作数及运算符，这将耗费的时间。
- 空间复杂度：遍历逆波兰表达式数组时遇到操作数时，将操作数入栈，这将耗费的栈空间。
方法二 复用逆波兰表达式数组
思路
方法一是新开辟栈空间，在遍历时存储操作数，根据逆波兰表达式计算规则，运算符前两个地址空间分别为两个操作数，计算之后，两个操作数与运算符三个地址空间是可以复用存储计算结果的；
Could not load image
详解
- 1.定义
*, +, -, /四个运算符与对应操作的映射关系ACTIONS。 - 2.定义pos变量，用于保存指示当前操作数索引。
- 3.遍历tokens数组，如遇到运算符时，依次取出索引位置为pos-1及pos-2两个元素，并作为参数调用运算符对应的操作。
- 4.将操作结果存入数组pos-2索引空间，并且pos 减1，表示左移到上一个数组索引。
- 5.如遇上非运算符，则解析成Int类型存入数组pos索引空间，并且pos加1，表示右移到下一个索引。
- 6.返回tokens数组0索引位置元素作为逆波兰表达式结果。
代码
1
/**
2
* @param {string[]} tokens
3
* @return {number}
4
*/
5
const ACTIONS = {
6
'*': (a, b) => b * a,
7
'+': (a, b) => b + a,
8
'-': (a, b) => b - a,
9
'/': (a, b) => parseInt(b / a)
10
};
11
12
const evalRPN = function (tokens) {
13
let pos = 0;
14
tokens.forEach((token, index) => {
15
const action = ACTIONS[token];
16
if (action) {
17
tokens[pos - 2] = action(
18
parseInt(tokens[pos - 1]),
19
parseInt(tokens[pos - 2])
20
);
21
pos = pos - 1;
22
} else {
23
if (pos !== index) {
24
tokens[pos] = tokens[index];
25
}
26
pos++;
27
}
28
});
29
return tokens[0];
30
};
Copied!
复杂度分析：
- 时间复杂度：需要遍历逆波兰表达式数组，查找操作数及运算符，这将耗费的时间。
- 空间复杂度：只需 1 个元素存储复用空间的地址索引 pos。
最近更新 1yr ago