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

两整数之和

不使用运算符 +- ,计算两整数 ab 之和。

示例 1:

输入: a = 1, b = 2
输出: 3

示例 2:

输入: a = -2, b = 3
输出: 1

方法一 二进制位操作法

思路

既然不能直接使用运算符 +- ,可以考虑使用二进制相关的与、非和异或等位操作符来完成运算。

详解

  • 与运算:二进制中的与运算是均为 1 才 得 1,这样可以得到需要进位的地方,然后将其左移一位得到其进位后的结果。如:

a = 5 = 0101
b = 4 = 0100
a & b 如下:
0 1 0 1
0 1 0 0
-------
0 1 0 0
结果左移一位后如下:
1 0 0 0
  • 异或运算:二进制中的异或运算是无进位加法,也就是两数异或得到所有不需要进位的结果。如:

a = 5 = 0101
b = 4 = 0100
a ^ b 如下:
0 1 0 1
0 1 0 0
-------
0 0 0 1

因此对于任意两个数,我们可以通过与运算后左移一位得到需要进位的结果,两数异或运算得到不需要进位的结果。循环操作,直到需要进位的为 0 ,那么得到的不需要进位的结果就是两数之和。

  • 解题步骤如下:

  • 两整数 ab 之和的问题可以拆分为 a 和 b 的进位结果 + a 和 b 的无进位结果

  • 需要进位的地方进行与操作并将得到的结果左移一位得到 a 和 b 的进位结果

  • 不需要进位的地方进行异或操作得到a 和 b 的无进位结果

  • 一直循环操作第 2 和 3 步,直到需要进位的为0

代码

const getSum = function (a, b) {
while (a !== 0) {
const t = (a & b) << 1; // a & b 将需要进位的地方进行与操作,并左移一位
b = a ^ b; // a ^ b 将不需要进位的地方进行异或操作
a = t; // 每次将需要进位的赋值给 a ,继续执行上述操作,直到不需要进位
}
return b;
};

复杂度分析

  • 时间复杂度:O(n)O(n)

    对于任意两个数,循环体的代码需要执行 3n3n 次。问题规模属于线性阶,故时间复杂度为 O(n)O(n)

  • 空间复杂度:O(1)O(1)

方法二 取对数法

思路

我们可以利用同底数幂的底数不变,指数相加的乘法规则,先取指数再取对数,等到答案。JS 中 Math 对象相关函数如下:

Math.log();
// 用于返回一个数的自然对数
Math.exp();
// 用于返回一个数的指数
Math.round();
// 用于返回一个数四舍五入后最接近的整数

详解

  1. 此方法法主要借用了 JS 内置对象的 Math.log()、Math.exp() 和 Math.round() 三个函数

  2. 先取两个整数的指数的乘积

  3. 再取乘积结果的对数

  4. 最后再对得到的对数四舍五入,得到最终答案

  5. 注:引入了 10 的 10 次方是为了解决精度丢失的问题

参考代码

const getSum = function (a, b) {
return Math.round(Math.log((Math.exp(a / 10e10) * Math.exp(b / 10e10))) * 10e10);
};

复杂度分析

  • 时间复杂度: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() - 返回目前所有元素的中位数。

示例

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3)
findMedian() -> 2

方法一 堆

思路

生成两个堆:small和large。用small堆存放数据中较小的一半元素,large堆存放数据中较大的一半元素

详解

建立两个堆,这两个堆需要满足:

  1. 大顶堆元素都比小顶堆小;

  2. 大顶堆元素不小于小顶堆,且最多比小顶堆多一个元素

然后,我们观察可以发现,如果,数据总数是偶数,那么大顶堆,和小顶堆, 一边占一半元素,而且,还是有序的,很像二分法,这时,中位数为两堆顶平均值 如果数据个数为奇数,则,中位数出现在元素个数多的堆的堆顶中

代码

const MedianFinder = function () {
this.maxHeap = [];
this.minHeap = [];
};
function minHeapify () {
this.minHeap.unshift(null);
const a = this.minHeap;
for (let i = a.length - 1; i >> 1 > 0; i--) {
// 自下往上堆化
if (a[i] < a[i >> 1]) {
// 如果子元素更小,则交换位置
const temp = a[i];
this.minHeap[i] = a[i >> 1];
this.minHeap[i >> 1] = temp;
}
}
this.minHeap.shift(null);
}
function maxHeapify () {
this.maxHeap.unshift(null);
const a = this.maxHeap;
for (let i = a.length - 1; i >> 1 > 0; i--) {
// 自下往上堆化
if (a[i] > a[i >> 1]) {
// 如果子元素更大,则交换位置
const temp = a[i];
this.maxHeap[i] = a[i >> 1];
this.maxHeap[i >> 1] = temp;
}
}
this.maxHeap.shift(null);
}
MedianFinder.prototype.addNum = function (num) {
// 插入
if (num >= (this.minHeap[0] || Number.MIN_VALUE)) {
this.minHeap.push(num);
} else {
this.maxHeap.push(num);
}
// 使得大顶堆的数量最多大于小顶堆一个, 且一定不小于小顶堆数量
if (this.maxHeap.length > this.minHeap.length + 1) {
// 大顶堆的堆顶元素移动到小顶堆
this.minHeap.push(this.maxHeap.shift());
}
if (this.minHeap.length > this.maxHeap.length) {
// 小顶堆的堆顶元素移动到大顶堆
this.maxHeap.push(this.minHeap.shift());
}
// 调整堆顶元素
if (this.maxHeap[0] > this.minHeap[0]) {
const temp = this.maxHeap[0];
this.maxHeap[0] = this.minHeap[0];
this.minHeap[0] = temp;
}
// 堆化
maxHeapify.call(this);
minHeapify.call(this);
};
MedianFinder.prototype.findMedian = function () {
if ((this.maxHeap.length + this.minHeap.length) % 2 === 0) {
return (this.minHeap[0] + this.maxHeap[0]) / 2;
} else {
return this.maxHeap[0];
}
};

复杂度分析

  • 时间复杂度:O(n)O(n)

  • 空间复杂度:O(n)O(n)

方法二 二分查找插入法

思路

JS中操作数组非常方便,我们可以使用Array.splice这样的方法向数组的中间进行数据添加和删除。因此在JS中,二分法则成为了一个不错的选择

详解

难点在于每次插入后,保证数列按顺序排列,每次插入时可用二分法找出插入位置 1. 使用二分查找发找出插入位置 2. 维护一个数组永远保持有序

代码

var MedianFinder = function() {
this.num = []
};
function binarySearch(a, target) {
target += 1;
var start = 0
var end = a.length - 1;
while(start <= end) {
var mid = ~~((start + end) >> 1);
if (a[mid] >= target)
end = mid - 1;
else
start = mid + 1;
}
return start;
}
MedianFinder.prototype.addNum = function(num) {
var index = binarySearch(this.num, num);
this.num.splice(index, 0, num);
};
MedianFinder.prototype.findMedian = function() {
var len = this.num.length;
if (len & 1)
return this.num[~~(len / 2)];
else return (this.num[len / 2] + this.num[len / 2 - 1]) / 2;
};

复杂度分析

  • 时间复杂度: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:

输入: ["2", "1", "+", "3", "*"]
输出: 9
解释: ((2 + 1) * 3) = 9

示例 2:

输入: ["4", "13", "5", "/", "+"]
输出: 6
解释: (4 + (13 / 5)) = 6

示例 3:

输入: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
输出: 22
解释:
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

方法一 入栈出栈法

思路

根据示例中的逆波兰表达式转中序表达式的过程可知,+, -, *, /运算符的两个操作数正好是运算符前两位,即逆波兰表达式 ab+的运算符为+、操作数分别为ab,转中序表达式就是a + b;根据这个规则,顺序遍历表达式中各项值,遇到操作数时,操作数入栈,遇到运算符时,栈顶两个操作数分别出栈,并应用运算符完成两个操作数的计算;

详解

  1. 定义 *, +, -, / 四个运算符与对应操作的映射关系ACTIONS。

  2. 定义stack数组,用于数据出栈入栈。

  3. 遍历tokens数组,如遇到运算符时,依次弹出栈顶两个元素,并作为参数调用运算符对应的操作,将操作结果入栈。

  4. 如遇上非运算符,则解析成Int类型压栈。

  5. 返回stack数组栈顶元素作为逆波兰表达式结果。

代码

/**
* @param {string[]} tokens
* @return {number}
*/
const ACTIONS = {
'*': (a, b) => b * a,
'+': (a, b) => b + a,
'-': (a, b) => b - a,
'/': (a, b) => parseInt(b / a)
};
const evalRPN = function (tokens) {
const stack = [];
tokens.forEach(token => {
const action = ACTIONS[token];
if (action) {
stack.push(action(stack.pop(), stack.pop()));
} else {
stack.push(parseInt(token));
}
});
return stack.shift();
};

复杂度分析

  • 时间复杂度:O(n)O(n)

    需要遍历逆波兰表达式数组,查找操作数及运算符,这将耗费 O(n)O(n) 的时间。

  • 空间复杂度:O(n)O(n)

    遍历逆波兰表达式数组时遇到操作数时,将操作数入栈,这将耗费 O(n)O(n) 的栈空间。

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

思路

方法一是新开辟栈空间,在遍历时存储操作数,根据逆波兰表达式计算规则,运算符前两个地址空间分别为两个操作数,计算之后,两个操作数与运算符三个地址空间是可以复用存储计算结果的;

详解

  1. 定义 *, +, -, / 四个运算符与对应操作的映射关系ACTIONS。

  2. 定义pos变量,用于保存指示当前操作数索引。

  3. 遍历tokens数组,如遇到运算符时,依次取出索引位置为pos-1及pos-2两个元素,并作为参数调用运算符对应的操作。

  4. 将操作结果存入数组pos-2索引空间,并且pos 减1,表示左移到上一个数组索引。

  5. 如遇上非运算符,则解析成Int类型存入数组pos索引空间,并且pos加1,表示右移到下一个索引。

  6. 返回tokens数组0索引位置元素作为逆波兰表达式结果。

代码

/**
* @param {string[]} tokens
* @return {number}
*/
const ACTIONS = {
'*': (a, b) => b * a,
'+': (a, b) => b + a,
'-': (a, b) => b - a,
'/': (a, b) => parseInt(b / a)
};
const evalRPN = function (tokens) {
let pos = 0;
tokens.forEach((token, index) => {
const action = ACTIONS[token];
if (action) {
tokens[pos - 2] = action(
parseInt(tokens[pos - 1]),
parseInt(tokens[pos - 2])
);
pos = pos - 1;
} else {
if (pos !== index) {
tokens[pos] = tokens[index];
}
pos++;
}
});
return tokens[0];
};

复杂度分析:

  • 时间复杂度:O(n)O(n)

    需要遍历逆波兰表达式数组,查找操作数及运算符,这将耗费 O(n)O(n) 的时间。

  • 空间复杂度:O(1)O(1)

    只需 1 个元素存储复用空间的地址索引 pos。