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

搜索文档…
两整数之和
不使用运算符 + 和 - ，计算两整数 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!
复杂度分析
时间复杂度：O(n)O(n)O(n)
​
对于任意两个数，循环体的代码需要执行 3n3n3n
 次。问题规模属于线性阶，故时间复杂度为 O(n)O(n)O(n)
。
空间复杂度：O(1)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)O(1)
​
对于任意两个数，只需要进行 1 次运算。问题规模属于常数阶，故时间复杂度为 O(1)O(1)O(1)
。
空间复杂度：O(1)O(1)O(1)
​
此算法需要为 2 个常量 a 和 b 分配空间。空间占用属于常数阶，故空间复杂度为 O(1)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)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(n)
​
上述解法中用二分查找将耗费 O(log(n))O(log(n))O(log(n))
 时间，插入时将耗费 O(n)O(n) O(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+的运算符为+、操作数分别为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!
复杂度分析
时间复杂度：O(n)O(n)O(n)
​
需要遍历逆波兰表达式数组，查找操作数及运算符，这将耗费 O(n)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(n)O(n)
 的时间。
空间复杂度：O(1)O(1)O(1)
​
只需 1 个元素存储复用空间的地址索引 pos。