两整数之和、数据流的中位数和逆波兰表达式

两整数之和

不使用运算符 +- ,计算两整数 ab 之和。
示例 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 ,那么得到的不需要进位的结果就是两数之和。
    解题步骤如下:
    两整数 ab 之和的问题可以拆分为 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!
复杂度分析
    时间复杂度:
    O(n)O(n)
    对于任意两个数,循环体的代码需要执行
    3n3n
    次。问题规模属于线性阶,故时间复杂度为
    O(n)O(n)
    空间复杂度:
    O(1)O(1)

方法二 取对数法

思路
我们可以利用同底数幂的底数不变,指数相加的乘法规则,先取指数再取对数,等到答案。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!
复杂度分析
    时间复杂度:
    O(1)O(1)
    对于任意两个数,只需要进行 1 次运算。问题规模属于常数阶,故时间复杂度为
    O(1)O(1)
    空间复杂度:
    O(1)O(1)
    此算法需要为 2 个常量 a 和 b 分配空间。空间占用属于常数阶,故空间复杂度为
    O(1)O(1)

数据流的中位数

中位数是有序列表中间的数。如果列表长度是偶数,中位数则是中间两个数的平均值。
例如,
[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!
复杂度分析
    时间复杂度:
    O(n)O(n)
    空间复杂度:
    O(n)O(n)

方法二 二分查找插入法

思路
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!
复杂度分析
    时间复杂度:
    O(n)O(n)
    上述解法中用二分查找将耗费
    O(log(n))O(log(n))
    时间,插入时将耗费
    O(n)O(n)
    的时间,所以时间复杂度为
    O(n)O(n)
    空间复杂度:
    O(n)O(n)

逆波兰表达式求值

根据[逆波兰表示法](https://baike.baidu.com/item/%E9%80%86%E6%B3%A2%E5%85%B0%E5%BC%8F/128437),求表达式的值。
有效的运算符包括 +, -, *, /。每个运算对象可以是整数,也可以是另一个逆波兰表达式。
说明:
整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 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+的运算符为+、操作数分别为ab,转中序表达式就是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!
复杂度分析
    时间复杂度:
    O(n)O(n)
    需要遍历逆波兰表达式数组,查找操作数及运算符,这将耗费
    O(n)O(n)
    的时间。
    空间复杂度:
    O(n)O(n)
    遍历逆波兰表达式数组时遇到操作数时,将操作数入栈,这将耗费
    O(n)O(n)
    的栈空间。

方法二 复用逆波兰表达式数组

思路
方法一是新开辟栈空间,在遍历时存储操作数,根据逆波兰表达式计算规则,运算符前两个地址空间分别为两个操作数,计算之后,两个操作数与运算符三个地址空间是可以复用存储计算结果的;
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!
复杂度分析:
    时间复杂度:
    O(n)O(n)
    需要遍历逆波兰表达式数组,查找操作数及运算符,这将耗费
    O(n)O(n)
    的时间。
    空间复杂度:
    O(1)O(1)
    只需 1 个元素存储复用空间的地址索引 pos。
最近更新 1yr ago