两整数之和、数据流的中位数和逆波兰表达式
不使用运算符 + 和 - ，计算两整数 a 、b 之和。
示例 1：
输入: a = 1, b = 2输出: 3
示例 2：
输入: a = -2, b = 3输出: 1
思路
既然不能直接使用运算符 + 和 - ，可以考虑使用二进制相关的与、非和异或等位操作符来完成运算。
详解
与运算：二进制中的与运算是均为 1 才 得 1，这样可以得到需要进位的地方，然后将其左移一位得到其进位后的结果。如：
a = 5 = 0101b = 4 = 0100a & b 如下：0 1 0 10 1 0 0-------0 1 0 0结果左移一位后如下：1 0 0 0
异或运算：二进制中的异或运算是无进位加法，也就是两数异或得到所有不需要进位的结果。如：
a = 5 = 0101b = 4 = 0100a ^ b 如下：0 1 0 10 1 0 0-------0 0 0 1
因此对于任意两个数，我们可以通过与运算后左移一位得到需要进位的结果，两数异或运算得到不需要进位的结果。循环操作，直到需要进位的为 0 ，那么得到的不需要进位的结果就是两数之和。
解题步骤如下：
两整数
a、b之和的问题可以拆分为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;};
复杂度分析
时间复杂度：
对于任意两个数，循环体的代码需要执行 次。问题规模属于线性阶，故时间复杂度为 。
空间复杂度：
思路
我们可以利用同底数幂的底数不变，指数相加的乘法规则，先取指数再取对数，等到答案。JS 中 Math 对象相关函数如下：
Math.log();// 用于返回一个数的自然对数Math.exp();// 用于返回一个数的指数Math.round();// 用于返回一个数四舍五入后最接近的整数
详解
此方法法主要借用了 JS 内置对象的 Math.log()、Math.exp() 和 Math.round() 三个函数
先取两个整数的指数的乘积
再取乘积结果的对数
最后再对得到的对数四舍五入，得到最终答案
注：引入了 10 的 10 次方是为了解决精度丢失的问题
参考代码
const getSum = function (a, b) {return Math.round(Math.log((Math.exp(a / 10e10) * Math.exp(b / 10e10))) * 10e10);};
复杂度分析
时间复杂度：
对于任意两个数，只需要进行 1 次运算。问题规模属于常数阶，故时间复杂度为 。
空间复杂度：
此算法需要为 2 个常量 a 和 b 分配空间。空间占用属于常数阶，故空间复杂度为 。
中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
示例
addNum(1)addNum(2)findMedian() -> 1.5addNum(3)findMedian() -> 2
思路
生成两个堆：small和large。用small堆存放数据中较小的一半元素，large堆存放数据中较大的一半元素
详解
建立两个堆，这两个堆需要满足:
大顶堆元素都比小顶堆小；
大顶堆元素不小于小顶堆，且最多比小顶堆多一个元素
然后，我们观察可以发现，如果，数据总数是偶数，那么大顶堆，和小顶堆， 一边占一半元素，而且，还是有序的，很像二分法，这时，中位数为两堆顶平均值 如果数据个数为奇数，则，中位数出现在元素个数多的堆的堆顶中
代码
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];}};
复杂度分析
时间复杂度：
空间复杂度：
思路
JS中操作数组非常方便，我们可以使用Array.splice这样的方法向数组的中间进行数据添加和删除。因此在JS中，二分法则成为了一个不错的选择
详解
难点在于每次插入后，保证数列按顺序排列，每次插入时可用二分法找出插入位置 1. 使用二分查找发找出插入位置 2. 维护一个数组永远保持有序
代码
var MedianFinder = function() {this.num = []};function binarySearch(a, target) {target += 1;var start = 0var end = a.length - 1;while(start <= end) {var mid = ~~((start + end) >> 1);if (a[mid] >= target)end = mid - 1;elsestart = 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;};
复杂度分析
时间复杂度：
上述解法中用二分查找将耗费 时间，插入时将耗费 的时间，所以时间复杂度为
空间复杂度：
根据[逆波兰表示法](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+的运算符为+、操作数分别为a和b，转中序表达式就是a + b；根据这个规则，顺序遍历表达式中各项值，遇到操作数时，操作数入栈，遇到运算符时，栈顶两个操作数分别出栈，并应用运算符完成两个操作数的计算；
详解
定义
*, +, -, /四个运算符与对应操作的映射关系ACTIONS。定义stack数组，用于数据出栈入栈。
遍历tokens数组，如遇到运算符时，依次弹出栈顶两个元素，并作为参数调用运算符对应的操作，将操作结果入栈。
如遇上非运算符，则解析成Int类型压栈。
返回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();};
复杂度分析
时间复杂度：
需要遍历逆波兰表达式数组，查找操作数及运算符，这将耗费 的时间。
空间复杂度：
遍历逆波兰表达式数组时遇到操作数时，将操作数入栈，这将耗费 的栈空间。
思路
方法一是新开辟栈空间，在遍历时存储操作数，根据逆波兰表达式计算规则，运算符前两个地址空间分别为两个操作数，计算之后，两个操作数与运算符三个地址空间是可以复用存储计算结果的；
详解
定义
*, +, -, /四个运算符与对应操作的映射关系ACTIONS。定义pos变量，用于保存指示当前操作数索引。
遍历tokens数组，如遇到运算符时，依次取出索引位置为pos-1及pos-2两个元素，并作为参数调用运算符对应的操作。
将操作结果存入数组pos-2索引空间，并且pos 减1，表示左移到上一个数组索引。
如遇上非运算符，则解析成Int类型存入数组pos索引空间，并且pos加1，表示右移到下一个索引。
返回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];};
复杂度分析：
时间复杂度：
需要遍历逆波兰表达式数组，查找操作数及运算符，这将耗费 的时间。
空间复杂度：
只需 1 个元素存储复用空间的地址索引 pos。
