计算机基础

1.操作系统

1.1 32位系统和64位体统的区别

参考答案：

1、处理数据的能力

32位和64位表示CPU一次能处理的最大位数，理论上来说，64位系统处理的数据效率比32位更高，相当于 单车道和双车道开车似得，双车道单位时间可以有更多的车辆通行。但需要内存跟上，而且程序本身也是64位编译才能发挥64位系统的优势。

2、支持的内存不同（寻址能力不同）

64位处理器的优势还体现在系统对内存的控制上。由于地址使用的是特殊的整数，因此一个ALU（算术逻辑运算器）和寄存器可以处理更大的整数，也就是更大的地址。比如，Windows Vista x64 Edition支持多达128 GB的内存和多达16 TB的虚拟内存，而32位CPU和操作系统最大只可支持4G内存

3、软件兼容性

32位系统无法运行64位软件，64位系统可以安装多数32位软件，以前因为大部分软件都是基于32位架构环境下开发，所以64位系统的兼容性不如32位。但现在64位兼容性也很强了，基本都是可以兼容各类软件了，而且64位的病毒都少了很多。特别是平面设计软件，64位和32位软件在64位系统里区别很大，64位真的快许多。

1.2 线程和进程

参考答案：

进程（Process） 是计算机中的程序关于某数据集合上的一次运行活动，是系统进行资源分配和调度的基本单位，是操作系统结构的基础。 在当代面向线程设计的计算机结构中，进程是线程的容器。程序是指令、数据及其组织形式的描述，进程是程序的实体。是计算机中的程序关于某数据集合上的一次运行活动，是系统进行资源分配和调度的基本单位，是操作系统结构的基础。程序是指令、数据及其组织形式的描述，进程是程序的实体。

线程（thread） 是操作系统能够进行运算调度的最小单位。它被包含在进程之中，是进程中的实际运作单位。一条线程指的是进程中一个单一顺序的控制流，一个进程中可以并发多个线程，每条线程并行执行不同的任务。

总结：

进程：指在系统中正在运行的一个应用程序；程序一旦运行就是进程；进程——资源分配的最小单位。

线程：系统分配处理器时间资源的基本单元，或者说进程之内独立执行的一个单元执行流。线程——程序执行的最小单位。

1.3 进程间通信

参考答案：

进程通信：
每个进程各自有不同的用户地址空间,任何一个进程的全局变量在另一个进程中都看不到，所以进程之间要交换数据必须通过内核,在内核中开辟一块缓冲区,进程A把数据从用户空间拷到内核缓冲区,进程B再从内核缓冲区把数据读走,内核提供的这种机制称为进程间通信。

管道(pipe)

管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。

有名管道 (namedpipe)

有名管道也是半双工的通信方式，但是它允许无亲缘关系进程间的通信。

信号量(semaphore)

信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。

消息队列(messagequeue)

消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。

信号 (sinal)

信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。

1.4 线程间的通信方式

参考答案：

• 使用全局变量
  主要由于多个线程可能更改全局变量，因此全局变量最好声明为volatile

• 使用消息实现通信
  在Windows程序设计中，每一个线程都可以拥有自己的消息队列（UI线程默认自带消息队列和消息循环，工作线程需要手动实现消息循环），因此可以采用消息进行线程间通信sendMessage,postMessage。

  1)定义消息#define WM_THREAD_SENDMSG=WM_USER+20;
  2)添加消息函数声明afx_msg int OnTSendmsg();
  3)添加消息映射ON_MESSAGE(WM_THREAD_SENDMSG,OnTSM)
  4)添加OnTSM()的实现函数；
  5)在线程函数中添加PostMessage消息Post函数

• 使用事件CEvent类实现线程间通信
  Event对象有两种状态：有信号和无信号，线程可以监视处于有信号状态的事件，以便在适当的时候执行对事件的操作。

  1)创建一个CEvent类的对象：CEvent threadStart;它默认处在未通信状态；
  2)threadStart.SetEvent();使其处于通信状态；
  3)调用WaitForSingleObject()来监视CEvent对象

2. 算法

2.1 树 找到某节点的路径

参考答案：

查找某个节点的路径的方法通常有两种，一种是递归算法,另一种是非递归算法

定义树节点

// 树节点定义
class TreeNode{
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

构建树

// 构建树
let root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

递归算法

// 递归中序遍历二叉树
function midOrder(root) { 
    if(!root || !(root instanceof TreeNode)){
        return;
    }
    // 递归访问左子树
    midOrder(root.left);
    console.log(root.value);
    // 递归访问右子树
    midOrder(root.right);
}
midOrder(root);

非递归算法

// 非递归中序遍历二叉树
function midOrderN(root) { 
    let p = root; // p为当前遍历的节点， 初始为根
    let arr = []; // arr作为栈
    while(p || arr.length !== 0){
        if(p){
            // 遍历左子树
            arr.push(p);
            // 每遇到非空二叉树先向做走
            p = p.left;
        }else{
            // p为空，出栈
            let node = arr.pop();
            // 访问该节点
            console.log(node.value);
            // 向右走一次
            p = node.right;
        }
    }
 }
 midOrderN(root)

2.2 洗完牌抽5张判断是否为同花顺

参考答案：

题目：从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2-10为数字本身，A为1，J为11，Q为12，K为13，而大小王可以看成任意数字。

思路一:

我们需要把扑克牌的背景抽象成计算机语言。不难想象，我们可以把5张牌看成由5个数字组成的数组。大小王是特殊的数字，我们不妨把它们都当成0，这样和其他扑克牌代表的数字就不重复了。接下来我们来分析怎样判断5个数字是不是连续的。最直观的是，我们把数组排序。但值得注意的是，由于0可以当成任意数字，我们可以用0去补满数组中的空缺。也就是排序之后的数组不是连续的，即相邻的两个数字相隔若干个数字，但如果我们有足够的0可以补满这两个数字的空缺，这个数组实际上还是连续的。举个例子，数组排序之后为{0，1，3，4，5}。在1和3之间空缺了一个2，刚好我们有一个0，也就是我们可以它当成2去填补这个空缺。于是我们需要做三件事情：把数组排序，统计数组中0的个数，统计排序之后的数组相邻数字之间的空缺总数。如果空缺的总数小于或者等于0的个数，那么这个数组就是连续的；反之则不连续。最后，我们还需要注意的是，如果数组中的非0数字重复出现，则该数组不是连续的。换成扑克牌的描述方式，就是如果一副牌里含有对子，则不可能是顺子。

思路二:

1）确认5张牌中除了0，其余数字没有重复的（可以用表统计的方法）;

2) 满足这样的逻辑：（max，min分别代表5张牌中的除0以外的最大值最小值）

​ 如果没有0，则max-min=4，则为顺子，否则不是

​ 如果有一个0，则max-min=4或者3，则为顺子，否则不是

​ 如果有两个0，则max-min=4或者3或者2，则为顺子，否则不是最大值和最小值在1）中就可以获得，这样就 不用排序了

2.3 爬楼梯 编代码

参考答案：

题目描述：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

方法分析：

这道题主要是要明白该爬楼梯的规律其实就是符合斐波那契数列（Fibonacci Sequence） 规律的，问题就迎刃而解了。为什么说它是斐波那契数列呢？我们可以这样来思考：当我们从第 n-1 阶楼梯爬到第 n 阶楼梯时，需要1步；当我们从第 n-2 阶楼梯爬到第 n 阶楼梯时，需要2步.也就是说 到达第 n 阶楼梯的方法数等于到达第 n-1 阶楼梯的方法数加上到达第 n-2 阶楼梯的方法数，其正好符合斐波那契通项。

代码实现：

1. 采用递归实现

var climbStairs = function(n) {
    if(n == 1) return 1;
    if(n == 2) return 2;
    return climbStairs(n-1) + climbStairs(n-2);
};

递归是求解斐波那契数列最经典和最直接的方式，其简洁易懂；但是递归特别费时，在该题中使用会出现[超出时间限制]的错误提示。

2. 数组方式

var climbStairs = function(n) {
    let result = [1,2];
    for (let i = 2; i < n; i++) {
        result.push(result[i-1] + result[i-2]);
    }
    return result[n-1];
};

数组方式大大的减少了运行时间，我们先预设好前两项，再得到结果，返回数组最后一项即可。

3. ES6的方式

var climbStairs = function(n) {
    let a = b = 1;
    for (let i = 0; i < n; i++) {
        [a, b] = [b, a + b];
    }
    return a;
};

其中 [a, b] = [b, a + b] 表示解构赋值，其等价于

temp = a;
a = b;
b = temp + b;

2.4 怎么识别100枚硬币中的假币

参考答案：

问题描述：
在n枚外观相同的硬币中，有一枚是假币，并且已知假币与真币的重量不同，但不知道假币与真币相比较轻还是较重。可以通过一架天平来任意比较两组硬币，设计一个高效的算法来检测这枚假币(以下提供两种方法)。
解题思路1 (本例为真币重量大于假币)：
使用减治法的解题思路，将硬币分为3堆，则每堆的硬币数量为 n/3 ，但是这是在 n%3==0 的情况下才能成立，所以我们将 n 枚硬币分为 3 堆加 1 堆 余数堆(余数堆可能为0)，则可分为如下(n-n%3)/3, (n-n%3)/3, (n-n%3)/3, n%3。
如下分组：
a堆： (n-n%3)/3
b堆： (n-n%3)/3
c堆： (n-n%3)/3
d(余数堆): n%3
逻辑流程：

1. 判断n中的硬币数量，如果n>2则执行2，否则执行5.
2. 将n分为上图的四堆，拿 a 和 b 比较，如果 a == b ,则 假币在 c 或 d 中。否则假币在 a 或 b 中。
3. 如果 a == b，则拿 a 和 c 比较。如果 a == c,则假币在d(余数堆)中。将 d 再次 执行流程1，并且n=n%3。如果不等，则假币在 c 中，将 c 再次 执行流程1，并且n=(n-n%3)/3。
4. 如果 a != b，则拿 a 和 c 比较。如果 a == c,则假币在b中，将 b 再次 执行流程1，并且n=(n-n%3)/3。如果不等，则假币在 a 中，将 a 再次 执行流程 1，并且n=(n-n%3)/3。
5. 如果n==2，则将两枚硬币进行比较找出假币。
6. 如果n==1，则该硬币就是假币，输出结果结束。

解题思路2（以12枚硬币为例，且假币未知轻重）：

1. 将硬币编号：1，2，3，4，5，6，7，8，9，10，11，12。三次称重如下安排：
2. 称重：
   第一次称重：左盘：1，2，3，4 右盘：5，6，7，8 其他：9，10，11，12
   第二次称重：左盘：1，6，7，8 右盘：5，10，11，12 其他：9，2，3，4
   第三次称重：左盘：5，6，10，2 右盘：9，7，11，3 其他：1，8，12，4
   称重结果：平衡取0，左倾取1，右倾取-1。
   3次称重安排可表示成矩阵形式：

其中，矩阵第一行是硬币序号，下面每一行都是一次称重结果，1表示该硬币放左盘，-1表示放右盘，0表示不放。矩阵每一列为检测结果，检测结果对应的硬币序号为假币。如果结果与上边的符合，则对应重量为重，如果结果不包含在上述表中，则进行1 -1互换，得到的重量为轻。例如：若称重结果是110，则1号为假币，且重量较重：若称重结果为1-10，1与-1进行交换后为-110，则8号为假币，且重量较轻。

2.5 手撕快排算法

参考答案：

思想：

1. 在数据集之中，选择一个元素作为"基准"（pivot）。
2. 所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。
3. 对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

实现：

var quickSort = function(arr) {
　　if (arr.length <= 1) { return arr; }
　　var pivotIndex = Math.floor(arr.length / 2);
　　var pivot = arr.splice(pivotIndex, 1)[0];
　　var left = [];
　　var right = [];
　　for (var i = 0; i < arr.length; i++){
　　　　if (arr[i] < pivot) {
　　　　　　left.push(arr[i]);
　　　　} else {
　　　　　　right.push(arr[i]);
　　　　}
　　}
　　return quickSort(left).concat([pivot], quickSort(right));
};

2.6 常见的排序算法和它们的时间复杂度是多少？

参考答案：

2.7 说一下归并排序思想怎么实现的

参考答案：

“归并”的意思是将两个或两个以上的有序表组合成一个新的有序表。假如初始序列含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到[n/2]（向上取整）个长度为2或1的有序子序列；再两两归并，……，如此重复，直到得到一个长度为n的有序序列为止，这种排序方法称为2-路归并排序。

步骤解析：

1、把长度为n的输入序列分成两个长度为n/2的子序列；

2、对这两个子序列继续分为m/2的子序列，一直分下去，直为1个元素；

3、将两个排序好的子序列合并成一个最终的排序序列。

特点：

速度仅次于快速排序，为稳定排序算法，一般用于总体无序，但是各子项相对有序的数列，属于分治思想，递归归并。

动图演示：

JavsScript代码实现：

//归并排序
function mergeSort(arr){
  var len = arr.length;
  if(len < 2){
    return arr;
  }

  //首先将无序数组划分为两个数组
  var mid = Math.floor(len / 2);
  var left = arr.slice(0,mid);
  var right = arr.slice(mid,len);
  return merge(mergeSort(left),mergeSort(right));//递归分别对左右两部分数组进行排序合并
}
//合并
function merge(left,right){
  var result = [];
  while(left.length>0 && right.length>0){
    if(left[0]<=right[0]){
      //如果左边的数据小于右边的数据，将左边数据取出，放在新数组中
      result.push(left.shift());
    }else{
       result.push(right.shift());
     }
  }

  while(left.length){
     result.push(left.shift());
  }
  while(right.length){
     result.push(right.shift());
  }
  return result;
}
var arr = [3,44,38,5,47,15,36,26];
console.log(mergeSort(arr));//3,5,15,26,36,38,44,47

2.8 算法：3数之和

参考答案：

题目描述：

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，*使得 *a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

//例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
//满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]
var threeSum = function(nums) {
    nums=nums.sort(function(a,b){return a-b});//先排序
    var i=0;
    var arr=[];
    while(i<nums.length-1){
        var a=nums[i],j=i+1,k=nums.length-1;
        while(j<k){
            var b=nums[j],c=nums[k];
            var sum=a+b+c;
            if(sum==0)arr.push([a,b,c]);//存起来
            if(sum<=0)
                while(nums[j]==b&&j<k)j++;//第2个
            if(sum>=0)
                while(nums[k]==c&&j<k)k--//最后一个数
        }
        while(nums[i]==a&&i<nums.length-1)i++;//第一个
    }
    return arr
};

2.9 算法：连续最大乘积

参考答案：

题目描述

给一个浮点数序列，取最大乘积连续子串的值，例如 -2.5，4，0，3，0.5，8，-1，则取出的最大乘积连续子串为3，0.5，8。也就是说，上述数组中，3 0.5 8这3个数的乘积30.58=12是最大的，而且是连续的。

分析与解法

此最大乘积连续子串与最大乘积子序列不同，请勿混淆，前者子串要求连续，后者子序列不要求连续。也就是说，最长公共子串（Longest CommonSubstring）和最长公共子序列（LongestCommon Subsequence，LCS）是：

• 子串（Substring）是串的一个连续的部分，
• 子序列（Subsequence）则是从不改变序列的顺序，而从序列中去掉任意的元素而获得的新序列；

更简略地说，前者（子串）的字符的位置必须连续，后者（子序列LCS）则不必。比如字符串“ acdfg ”同“ akdfc ”的最长公共子串为“ df ”，而它们的最长公共子序列LCS是“ adf ”，LCS可以使用动态规划法解决。

解法一

或许，读者初看此题，可能立马会想到用最简单粗暴的方式：两个for循环直接轮询。

double maxProductSubstring(double *a, int length)
{
    double maxResult = a[0];
    for (int i = 0; i < length; i++)
    {
        double x = 1;
        for (int j = i; j < length; j++)
        {
            x *= a[j];
            if (x > maxResult)
            {
                maxResult = x;
            }
        }
    }
    return maxResult;
}

但这种蛮力的方法的时间复杂度为O(n^2)，能否想办法降低时间复杂度呢？

解法二

考虑到乘积子序列中有正有负也还可能有0，我们可以把问题简化成这样：数组中找一个子序列，使得它的乘积最大；同时找一个子序列，使得它的乘积最小（负数的情况）。因为虽然我们只要一个最大积，但由于负数的存在，我们同时找这两个乘积做起来反而方便。也就是说，不但记录最大乘积，也要记录最小乘积。

假设数组为a[]，直接利用动态规划来求解，考虑到可能存在负数的情况，我们用maxend来表示以a[i]结尾的最大连续子串的乘积值，用minend表示以a[i]结尾的最小的子串的乘积值，那么状态转移方程为：

  maxend = max(max(maxend * a[i], minend * a[i]), a[i]);
  minend = min(min(maxend * a[i], minend * a[i]), a[i]);

初始状态为maxend = minend = a[0]。

参考代码如下：

double MaxProductSubstring(double *a, int length)
{
    double maxEnd = a[0];
    double minEnd = a[0];
    double maxResult = a[0];
    for (int i = 1; i < length; ++i)
    {
        double end1 = maxEnd * a[i], end2 = minEnd * a[i];
        maxEnd = max(max(end1, end2), a[i]);
        minEnd = min(min(end1, end2), a[i]);
        maxResult = max(maxResult, maxEnd);
    }
    return maxResult;
}

动态规划求解的方法一个for循环搞定，所以时间复杂度为O(n)。

2.10 第K大的数

参考答案：

三种方案：

• 排序，取第 k 个
• 构造前 k 个最大元素小顶堆，取堆顶
• 计数排序或桶排序，但它们都要求输入的数据必须是有确定范围的整数，所以本题不可用

那么除了这两种方案还有没有其它的方式可解决本题喃？其实还有两种：

• 快速选择（quickselect）算法
• 中位数的中位数（bfprt）算法

解法一：数组排序，取第 k 个数

最简单

代码实现：

let findKthLargest = function(nums, k) {
    nums.sort((a, b) => b - a);
    return nums[k-1]
};

复杂度分析：

• 时间复杂度：O(nlogn)
• 空间复杂度：O(logn)

解法二：构造前 k 个最大元素小顶堆，取堆顶

我们也可以通过构造一个前 k 个最大元素小顶堆来解决，小顶堆上的任意节点值都必须小于等于其左右子节点值，即堆顶是最小值。

所以我们可以从数组中取出 k 个元素构造一个小顶堆，然后将其余元素与小顶堆对比，如果大于堆顶则替换堆顶，然后堆化，所有元素遍历完成后，堆中的堆顶即为第 k 个最大值

具体步骤如下：

• 从数组中取前 k 个数（ 0 到 k-1 位），构造一个小顶堆
• 从 k 位开始遍历数组，每一个数据都和小顶堆的堆顶元素进行比较，如果小于堆顶元素，则不做任何处理，继续遍历下一元素；如果大于堆顶元素，则将这个元素替换掉堆顶元素，然后再堆化成一个小顶堆。
• 遍历完成后，堆顶的数据就是第 K 大的数据

代码实现：

let findKthLargest = function(nums, k) {
    // 从 nums 中取出前 k 个数，构建一个小顶堆
    let heap = [,], i = 0
    while(i < k) {
       heap.push(nums[i++]) 
    }
    buildHeap(heap, k)

    // 从 k 位开始遍历数组
    for(let i = k; i < nums.length; i++) {
        if(heap[1] < nums[i]) {
            // 替换并堆化
            heap[1] = nums[i]
            heapify(heap, k, 1)
        }
    }

    // 返回堆顶元素
    return heap[1]
};

// 原地建堆，从后往前，自上而下式建小顶堆
let buildHeap = (arr, k) => {
    if(k === 1) return
    // 从最后一个非叶子节点开始，自上而下式堆化
    for(let i = Math.floor(k/2); i>=1 ; i--) {
        heapify(arr, k, i)
    }
}

// 堆化
let heapify = (arr, k, i) => {
    // 自上而下式堆化
    while(true) {
        let minIndex = i
        if(2*i <= k && arr[2*i] < arr[i]) {
            minIndex = 2*i
        }
        if(2*i+1 <= k && arr[2*i+1] < arr[minIndex]) {
            minIndex = 2*i+1
        }
        if(minIndex !== i) {
            swap(arr, i, minIndex)
            i = minIndex
        } else {
            break
        }
    }
}

// 交换
let swap = (arr, i , j) => {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

复杂度分析：

• 时间复杂度：遍历数组需要 O(n) 的时间复杂度，一次堆化需要 O(logk) 时间复杂度，所以利用堆求 Top k 问题的时间复杂度为 O(nlogk)
• 空间复杂度：O(k)

解法三：快速选择（quickselect）算法

无论是排序算法还是构造堆求解 Top k问题，我们都经过的一定量的不必要操作：

• 如果使用排序算法，我们仅仅想要的是第 k 个最大值，但对其余不需要的数也进行了排序
• 如果使用堆排序，需要维护一个大小为 k 的堆(大顶堆，小顶堆)，时间复杂度也为 O(nlogk)

快速选择（quickselect）算法与快排思路上相似，我们先看看快排是如何实现的？

快排

快排使用了分治策略的思想，所谓分治，顾名思义，就是分而治之，将一个复杂的问题，分成两个或多个相似的子问题，在把子问题分成更小的子问题，直到更小的子问题可以简单求解，求解子问题，则原问题的解则为子问题解的合并。

快排的过程简单的说只有三步：

• 首先从序列中选取一个数作为基准数
• 将比这个数大的数全部放到它的右边，把小于或者等于它的数全部放到它的左边 （一次快排 partition）
• 然后分别对基准的左右两边重复以上的操作，直到数组完全排序

具体按以下步骤实现：

• 创建两个指针分别指向数组的最左端以及最右端
• 在数组中任意取出一个元素作为基准
• 左指针开始向右移动，遇到比基准大的停止
• 右指针开始向左移动，遇到比基准小的元素停止，交换左右指针所指向的元素
• 重复3，4，直到左指针超过右指针，此时，比基准小的值就都会放在基准的左边，比基准大的值会出现在基准的右边
• 然后分别对基准的左右两边重复以上的操作，直到数组完全排序

注意这里的基准该如何选择喃？最简单的一种做法是每次都是选择最左边的元素作为基准，但这对几乎已经有序的序列来说，并不是最好的选择，它将会导致算法的最坏表现。还有一种做法，就是选择中间的数或通过 Math.random() 来随机选取一个数作为基准，下面的代码实现就是以随机数作为基准。

代码实现

let quickSort = (arr) => {
  quick(arr, 0 , arr.length - 1)
}

let quick = (arr, left, right) => {
  let index
  if(left < right) {
    // 划分数组
    index = partition(arr, left, right)
    if(left < index - 1) {
      quick(arr, left, index - 1)
    }
    if(index < right) {
      quick(arr, index, right)
    }
  }
}

// 一次快排
let partition = (arr, left, right) => {
  // 取中间项为基准
  var datum = arr[Math.floor(Math.random() * (right - left + 1)) + left],
      i = left,
      j = right
  // 开始调整
  while(i <= j) {

    // 左指针右移
    while(arr[i] < datum) {
      i++
    }

    // 右指针左移
    while(arr[j] > datum) {
      j--
    }

    // 交换
    if(i <= j) {
      swap(arr, i, j)
      i += 1
      j -= 1
    }
  }
  return i
}

// 交换
let swap = (arr, i , j) => {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

// 测试
let arr = [1, 3, 2, 5, 4]
quickSort(arr)
console.log(arr) // [1, 2, 3, 4, 5]
// 第 2 个最大值
console.log(arr[arr.length - 2])  // 4

快排是从小到大排序，所以第 k 个最大值在 n-k 位置上

复杂度分析

• 时间复杂度：O(nlog2n)
• 空间复杂度：O(nlog2n)

快速选择（quickselect）算法

上面我们实现了快速排序来取第 k 个最大值，其实没必要那么麻烦，我们仅仅需要在每执行一次快排的时候，比较基准值位置是否在 n-k 位置上，如果小于 n-k ，则第 k 个最大值在基准值的右边，我们只需递归快排基准值右边的子序列即可；如果大于 n-k ，则第 k 个最大值在基准值的做边，我们只需递归快排基准值左边的子序列即可；如果等于 n-k ，则第 k 个最大值就是基准值

代码实现：

let findKthLargest = function(nums, k) {
    return quickSelect(nums, nums.length - k)
};

let quickSelect = (arr, k) => {
  return quick(arr, 0 , arr.length - 1, k)
}

let quick = (arr, left, right, k) => {
  let index
  if(left < right) {
    // 划分数组
    index = partition(arr, left, right)
    // Top k
    if(k === index) {
        return arr[index]
    } else if(k < index) {
        // Top k 在左边
        return quick(arr, left, index-1, k)
    } else {
        // Top k 在右边
        return quick(arr, index+1, right, k)
    }
  }
  return arr[left]
}

let partition = (arr, left, right) => {
  // 取中间项为基准
  var datum = arr[Math.floor(Math.random() * (right - left + 1)) + left],
      i = left,
      j = right
  // 开始调整
  while(i < j) {

    // 左指针右移
    while(arr[i] < datum) {
      i++
    }

    // 右指针左移
    while(arr[j] > datum) {
      j--
    }

    // 交换
    if(i < j) swap(arr, i, j)

    // 当数组中存在重复数据时，即都为datum，但位置不同
    // 继续递增i，防止死循环
    if(arr[i] === arr[j] && i !== j) {
        i++
    }
  }
  return i
}

// 交换
let swap = (arr, i , j) => {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

复杂度分析：

• 时间复杂度：平均时间复杂度O(n)，最坏情况时间复杂度为O(n2)
• 空间复杂度：O(1)

解法四：中位数的中位数（BFPRT）算法

又称为中位数的中位数算法，它的最坏时间复杂度为 O(n) ，它是由Blum、Floyd、Pratt、Rivest、Tarjan提出。该算法的思想是修改快速选择算法的主元选取方法，提高算法在最坏情况下的时间复杂度。

在BFPTR算法中，仅仅是改变了快速选择（quickselect）算法中 Partion 中的基准值的选取，在快速选择（quickselect）算法中，我们可以选择第一个元素或者最后一个元素作为基准元，优化的可以选择随机一个元素作为基准元，而在 BFPTR 算法中，每次选择五分中位数的中位数作为基准元（也称为主元pivot），这样做的目的就是使得划分比较合理，从而避免了最坏情况的发生。

BFPRT 算法步骤如下：

• 选取主元
  • 将 n 个元素按顺序分为 n/5 个组，每组 5 个元素，若有剩余，舍去
  • 对于这 n/5 个组中的每一组使用插入排序找到它们各自的中位数
  • 对于上一步中找到的所有中位数，调用 BFPRT 算法求出它们的中位数，作为主元；
• 以主元为分界点，把小于主元的放在左边，大于主元的放在右边；
• 判断主元的位置与 k 的大小，有选择的对左边或右边递归

代码实现：

let findKthLargest = function(nums, k) {
    return nums[bfprt(nums, 0, nums.length - 1, nums.length - k)]
}

let bfprt = (arr, left , right, k) => {
  let index
  if(left < right) {
    // 划分数组
    index = partition(arr, left, right)
    // Top k
    if(k === index) {
        return index
    } else if(k < index) {
        // Top k 在左边
        return bfprt(arr, left, index-1, k)
    } else {
        // Top k 在右边
        return bfprt(arr, index+1, right, k)
    }
  }
  return left
}

let partition = (arr, left, right) => {
  // 基准
  var datum = arr[findMid(arr, left, right)],
      i = left,
      j = right
  // 开始调整
  while(i < j) {
    // 左指针右移
    while(arr[i] < datum) {
      i++
    }

    // 右指针左移
    while(arr[j] > datum) {
      j--
    }

    // 交换
    if(i < j) swap(arr, i, j)

    // 当数组中存在重复数据时，即都为datum，但位置不同
    // 继续递增i，防止死循环
    if(arr[i] === arr[j] && i !== j) {
        i++
    }
  }
  return i
}

/**
 * 数组 arr[left, right] 每五个元素作为一组，并计算每组的中位数，
 * 最后返回这些中位数的中位数下标（即主元下标）。
 *
 * @attention 末尾返回语句最后一个参数多加一个 1 的作用其实就是向上取整的意思，
 * 这样可以始终保持 k 大于 0。
 */
let findMid = (arr, left, right) => {
    if (right - left < 5)
        return insertSort(arr, left, right);

    let n = left - 1;

    // 每五个作为一组，求出中位数，并把这些中位数全部依次移动到数组左边
    for (let i = left; i + 4 <= right; i += 5)
    {
        let index = insertSort(arr, i, i + 4);
        swap(arr[++n], arr[index]);
    }

    // 利用 bfprt 得到这些中位数的中位数下标（即主元下标）
    return findMid(arr, left, n);
}

/**
 * 对数组 arr[left, right] 进行插入排序，并返回 [left, right]
 * 的中位数。
 */
let insertSort = (arr, left, right) => {
    let temp, j
    for (let i = left + 1; i <= right; i++) {
        temp = arr[i];
        j = i - 1;
        while (j >= left && arr[j] > temp)
        {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
    return ((right - left) >> 1) + left;
}

// 交换
let swap = (arr, i , j) => {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

复杂度分析：

为什么是5？

在BFPRT算法中，为什么是选5个作为分组？

首先，偶数排除，因为对于奇数来说，中位数更容易计算。

如果选用3，有 ，其操作元素个数还是 n 。

如果选取7，9或者更大，在插入排序时耗时增加，常数 c 会很大，有些得不偿失。

总结

所以，这里我们总结一下，求topk问题其实并不难，主要有以下几个思路：

• 整体排序：O(nlogn)
• 局部排序：只冒泡排序前k个最大值，O(nk)
• 堆：O(nlogk)
• 计数或桶排序：计数排序用于前k个最值，时间复杂度为O(n + m)，其中 m 表示数据范围；桶排序用于最高频k个，时间复杂度为O(n)； 但这两者都要求输入数据必须是有确定范围的整数
• 快速选择（quickselect）算法：平均O(n)，最坏O(n2)
• 中位数的中位数（bfprt）算法：最坏O(n)

2.11 算法题目，验证有效的括号

参考答案：

题目：

给定一个只包括 '('，')'，'{'，'}'，'['，']'的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。

解题思路：

第一种：用repace方法，闭合才有效，也就是最里边的也要闭合，那就把最里边的括号取代为空

var isValid = function(s) {
    while(s.length){
        let temp =s;
        s = s.replace('()','');
        s = s.replace('[]','');
        s = s.replace('{}','');
        if(s==temp)return false
    }
    return true
};

第二种：栈思想 括号都是要闭合的，也就是说遇到第一个右括号时，必定左边就是对应的左括号，也就是说把遇到的左括号都放进栈里，然后遇到右括号时取出栈顶的元素匹配 如"{[()]}"遇到{[(放入栈内，然后遇到）与栈顶匹配，栈顶也就是最后一个进栈的元素（，然后把栈的最后一个元素删掉

var isValid = function(s) {
    let a = [];
    let res=0;
    for(let i=0;i<s.length;i++){
        if(s[i]=='('||s[i]=='{'||s[i]=='['){
            a.push(s[i]);
            res++;
        }
        else if(s[i]==')'){
            if(a[a.length-1]=='('){
               a.pop();
                res--;
            }
            else return false
        }
        else if(s[i]=='}'){
            if(a[a.length-1]=='{'){
               a.pop();
                res--;
            }else return false
        }
        else if(s[i]==']'){
            if(a[a.length-1]=='['){
               a.pop();
                res--;
            }else return false
        }
    }
    return res==0
};

比起第一个方法快了不少但是还是慢

第三种：使用map数据结构

var isValid = function(s) {
    let map = {
        "{":"}",
        "[":"]",
        "(":")",
    }
    let leftArr = [];
    for(let ch of s){
        if(ch in map){
            leftArr.push(ch)
        }else{
            if(ch!=map[leftArr.pop()]){
                return false
            }
        }
    }
     return !leftArr.length
};
复制代码

循环s字符串，ch in map 的意思是循环map的键值，也就是遇到左括号时，放进数组，当开始遇到右括号时，用pop（）弹出栈顶的元素与与之比对，若是不相等，就ruturn false （leftArr.pop()为左括号，map[key]=value,也就是右括号），当程序走完时，left的length长度应该为0，若不为0则没闭合(当length=0 时，!leftArr.length为turn，当length>0 时，!leftArr.length为false)

2.12 算法题，反转单链表

参考答案：

解法一：迭代法
解题思路： 将单链表中的每个节点的后继指针指向它的前驱节点即可

画图实现： 画图帮助理解一下

确定边界条件： 当链表为 null 或链表中仅有一个节点时，不需要反转

代码实现：

var reverseList = function(head) {
    if(!head || !head.next) return head
    var prev = null, curr = head
    while(curr) {
        // 用于临时存储 curr 后继节点
        var next = curr.next
        // 反转 curr 的后继指针
        curr.next = prev
        // 变更prev、curr 
        // 待反转节点指向下一个节点 
        prev = curr
        curr = next
    }
    head = prev
    return head
};

时间复杂度：O(n)

空间复杂度：O(1)

解法二：尾递归法
解题思路： 从头节点开始，递归反转它的每一个节点，直到 null ，思路和解法一类似

代码实现：

var reverseList = function(head) {
    if(!head || !head.next) return head
    head = reverse(null, head)
    return head
};

var reverse = function(prev, curr) {
    if(!curr) return prev
    var next = curr.next
    curr.next = prev
    return reverse(curr, next)
};

时间复杂度：O(n)

空间复杂度：O(n)

解法三：递归法
解题思路： 不断递归反转当前节点 head 的后继节点 next

画图实现： 画图帮助理解一下

代码实现：

var reverseList = function(head) {
    if(!head || !head.next) return head
    var next = head.next
    // 递归反转
    var reverseHead = reverseList(next)
    // 变更指针
    next.next = head
    head.next = null
    return reverseHead
};

时间复杂度：O(n)

空间复杂度：O(n)

2.13 索引是怎么实现的，倒排索引

参考答案：

倒排索引是目前搜索引擎公司对搜索引擎最常用的存储方式，也是搜索引擎的核心内容，在搜索引擎的实际应用中，有时需要按照关键字的某些值查找记录，所以是按照关键字建立索引，这个索引就被称为倒排索引。

首先你要明确，索引这东西，一般是用于提高查询效率的。举个最简单的例子，已知有5个文本文件，需要我们去查某个单词位于哪个文本文件中，最直观的做法就是挨个加载每个文本文件中的单词到内存中，然后用for循环遍历一遍数组，直到找到这个单词。这种做法就是正向索引的思路。

举一个例子，有两段文本

D1：Hello, conan!

D2：Hello, hattori!

第一步，找到所有的单词

Hello、conan、hattori

第二步，找到包含这些单词的文本位置

Hello（D1，D2）

conan（D1）

hattori（D2）

我们将单词作为Hash表的Key，将所在的文本位置作为Hash表的Value保存起来。

当我们要查询某个单词的所在位置时，只需要根据这张Hash表就可以迅速的找到目标文档。

结合之前的说的正向索引，不难发现。正向索引是通过文档去查找单词，反向索引则是通过单词去查找文档。

倒排索引的优点还包括在处理复杂的多关键字查询时，可在倒排表中先完成查询的并、交等逻辑运算，得到结果后再对记录进行存取，这样把对文档的查询转换为地址集合的运算，从而提高查找速度。

2.14 二叉树的实际应用场景

参考答案：

1. 哈夫曼编码，来源于哈夫曼树（给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为赫夫曼树(Huffman tree)。即带权路径长度最短的树），在数据压缩上有重要应用，提高了传输的有效性，详见《信息论与编码》。
2. 海量数据并发查询，二叉树复杂度是O(K+LgN)。二叉排序树就既有链表的好处，也有数组的好处， 在处理大批量的动态的数据是比较有用。
3. C++ STL中的set/multiset、map，以及Linux虚拟内存的管理，都是通过红黑树去实现的。查找最大（最小）的k个数，红黑树，红黑树中查找/删除/插入，都只需要O(logk)。
4. B-Tree，B+-Tree在文件系统中的目录应用。
5. 路由器中的路由搜索引擎。

2.15 数组和链表的优缺点

参考答案：

数组:存放内存地址必须连续的.
查找的时候很方便,可以通过数组下标获取数据;
添加删除很不方便,如果插入一个元素,必须这个元素后面的元素都往后移一个内存地址
删除,所有后面元素都往前移动一个内存地址

链表:存放内存地址可以不连续,存放方式是通过元素中的指针,来寻找下一个元素.
这种结构添加删除元素很容易,只要修改指针指向下下个元素,就能删除,而添加则是
一个元素的指针指向后面的插入位置后面的元素,插入位置的指针指向插入元素就行

比较

数组
优点:查询速度快,可随机访问
缺点:

1. 删除插入效率低,
2. 内存必须连续
3. 有浪费内存的可能
4. 数组大小固定,不能动态拓展

链表
优点:插入删除速度快,内存不需要连续,大小可以不固定
缺点:查询效率低,每次通过第一个开始遍历,只能顺序访问,不支持随机访问

2.16 1000w条数据如何排序，取前一百个

参考答案：

1. 根据快速排序划分的思想
   (1) 递归对所有数据分成[a,b）b（b,d]两个区间，(b,d]区间内的数都是大于[a,b)区间内的数
   (2) 对(b,d]重复(1)操作，直到最右边的区间个数小于100个。注意[a,b)区间不用划分
   (3) 返回上一个区间，并返回此区间的数字数目。接着方法仍然是对上一区间的左边进行划分，分为[a2,b2）b2（b2,d2]两个区间，取（b2,d2]区间。如果个数不够，继续(3)操作，如果个数超过100的就重复1操作，直到最后右边只有100个数为止。

2. 先取出前100个数，维护一个100个数的最小堆，遍历一遍剩余的元素，在此过程中维护堆就可以了。具体步骤如下：
   step1：取前m个元素（例如m=100），建立一个小顶堆。保持一个小顶堆得性质的步骤，运行时间为O（lgm);建立一个小顶堆运行时间为mO（lgm）=O(m lgm);
   step2:顺序读取后续元素，直到结束。每次读取一个元素，如果该元素比堆顶元素小，直接丢弃
   如果大于堆顶元素，则用该元素替换堆顶元素，然后保持最小堆性质。最坏情况是每次都需要替换掉堆顶的最小元素，因此需要维护堆的代价为(N-m)O(lgm);
   最后这个堆中的元素就是前最大的10W个。时间复杂度为O(N lgm）。
   补充：这个方法的说法也可以更简化一些：
   假设数组arr保存100个数字，首先取前100个数字放入数组arr，对于第101个数字k，如果k大于arr中的最小数，则用k替换最小数，对剩下的数字都进行这种处理。

3. 分块查找

   先把100w个数分成100份，每份1w个数。先分别找出每1w个数里面的最大的数，然后比较。找出100个最大的数中的最大的数和最小的数，取最大数的这组的第二大的数，与最小的数比较

2.17 AST 抽象语法树

参考答案：

抽象语法树（abstract syntax code，AST）是源代码的抽象语法结构的树状表示，树上的每个节点都表示源代码中的一种结构，这所以说是抽象的，是因为抽象语法树并不会表示出真实语法出现的每一个细节，比如说，嵌套括号被隐含在树的结构中，并没有以节点的形式呈现。抽象语法树并不依赖于源语言的语法，也就是说语法分析阶段所采用的上下文无文文法，因为在写文法时，经常会对文法进行等价的转换（消除左递归，回溯，二义性等），这样会给文法分析引入一些多余的成分，对后续阶段造成不利影响，甚至会使合个阶段变得混乱。因些，很多编译器经常要独立地构造语法分析树，为前端，后端建立一个清晰的接口。

抽象语法树在很多领域有广泛的应用，比如浏览器，智能编辑器，编译器。

2.18 算法：一个小偷要偷一排顺序的房子，每个房子有固定的价值，但小偷不能偷连续的房子，问小偷能偷到的最大价值

参考答案：

示例 1:

输入: [1,2,3,1] 输出: 4 解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。

示例 2:

输入: [2,7,9,3,1] 输出: 12 解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。

• 问题求解 题意简单说来就是不能偷相邻的两个房屋, 而且要尽量偷得多. 这是典型的动态规划问题, 思路如下, 由于后面房间能偷到的最大钱数取决于前面房间能偷到的最大钱数, 所以可以从第一间房子向后看. 建立一个数组dp, 数组中的第n个元素保存前n间房屋总共能偷到的最大钱数:

1. 若只有一间房子, 则只能偷这间, 则前1间房屋能偷到的最大金额一已知, 保存下来;
2. 若有两间, 则偷其中最多的, 则前两间房屋能偷到的最大金额已知, 保存下来;
3. 若有3间, 则分为两种情况, 1)偷房屋 1和3; 2) 只偷房屋2. 比较这两种哪种获益大. 这可以抽象成两个子问题, 决定这两个子问题的关键是第三间房子偷与否. 分别把偷(子问题1)和不偷(子问题2) 的结果计算出来, 选出最大就是了. 现在, 前三间能偷到的最大金额已知, 保存下来, 以供偷第4、5...N 间房子时参考.
4. 若有4间, 则又是两种情况: 1)偷4不偷3; 2)不偷4. 这两种情况只和前三间房屋偷到的金额(dp[3])和前两间房屋偷到的金额(dp[2])的结果有关,把这两种情况下的金额计算出来, 选择最大的就可以了, 即 max(房屋4的钱+dp[2], dp[3]);
5. 由此可得, 第n间房屋偷还是不偷只要考虑 dp 数组中的dp[n-1]和dp[n-2]+当前可得的金额这两个因素就可以了.

所以状态方程为:max(dp[n-2] + thisValue, dp[n-1]), 代码为:

var rob = function(nums) {
    // 判断异常
    if(!nums || nums.length === 0){ 
        return 0;
    }
    // 边界条件
    if(nums.length < 3){
        return Math.max(...nums);
    }
    // 状态方程 dp(i) = max( dp(i-1) , dp(2) + arr[i])
    let dp = [];
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0],nums[1]);
    for(let i = 2; i < nums.length; i++){
        dp[i] = Math.max(dp[i-2] + nums[i], dp[i-1]);
    }
    return dp[dp.length-1];
};

2.19 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

参考答案：

var maxProfit = function(prices) {
        var max = 0;
        var len = prices.length;
        for (var i=0; i<len-1; i++){
            if (prices[i+1]>prices[i]){
                max += prices[i+1]-prices[i];
            }
        }
        return max;
    };

2.20 二维数组中的查找

参考答案：

题目：

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的
一个二维数组和一个整数，判断数组中是否含有该整数。、

思路：

（1）第一种方式是使用两层循环依次遍历，判断是否含有该整数。这一种方式最坏情况下的时间复杂度为 O(n^2)。

（2）第二种方式是利用递增序列的特点，我们可以从二维数组的右上角开始遍历。如果当前数值比所求的数要小，则将位置向下移动
，再进行判断。如果当前数值比所求的数要大，则将位置向左移动，再进行判断。这一种方式最坏情况下的时间复杂度为 O(n)。

2.21 重建二叉树

参考答案：

题目：

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输
入前序遍历序列 {1,2,4,7,3,5,6,8} 和中序遍历序列 {4,7,2,1,5,3,8,6}，则重建二叉树并返回。

思路：

利用递归的思想来求解，首先先序序列中的第一个元素一定是根元素。然后我们去中序遍历中寻找到该元素的位置，找到后该元素的左
边部分就是根节点的左子树，右边部分就是根节点的右子树。因此我们可以分别截取对应的部分进行子树的递归构建。使用这种方式的
时间复杂度为 O(n)，空间复杂度为 O(logn)

2.22 用两个栈实现队列

参考答案：

题目：

用两个栈来实现一个队列，完成队列的 Push 和 Pop 操作。

思路：

队列的一个基本特点是，元素先进先出。通过两个栈来模拟时，首先我们将两个栈分为栈 1 和栈 2。当执行队列的 push 操作时，直接
将元素 push 进栈 1 中。当队列执行 pop 操作时，首先判断栈 2 是否为空，如果不为空则直接 pop 元素。如果栈 2 为空，则将栈 1 中
的所有元素 pop 然后 push 到栈 2 中，然后再执行栈 2 的 pop 操作。

扩展：

当使用两个长度不同的栈来模拟队列时，队列的最大长度为较短栈的长度的两倍。

2.23 复杂链表的复制

参考答案：

题目：

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为
复制后复杂链表的 head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

思路：

（1）第一种方式，首先对原有链表每个节点进行复制，通过 next 连接起来。然后当链表复制完成之后，再来设置每个节点的 ra
ndom 指针，这个时候每个节点的 random 的设置都需要从头结点开始遍历，因此时间的复杂度为 O(n^2)。

（2）第二种方式，首先对原有链表每个节点进行复制，并且使用 Map 以键值对的方式将原有节点和复制节点保存下来。当链表复
制完成之后，再来设置每个节点的 random 指针，这个时候我们通过 Map 中的键值关系就可以获取到对应的复制节点，因此
不必再从头结点遍历，将时间的复杂度降低为了 O(n)，但是空间复杂度变为了 O(n)。这是一种以空间换时间的做法。

（3）第三种方式，首先对原有链表的每个节点进行复制，并将复制后的节点加入到原有节点的后面。当链表复制完成之后，再进行
random 指针的设置，由于每个节点后面都跟着自己的复制节点，因此我们可以很容易的获取到 random 指向对应的复制节点
。最后再将链表分离，通过这种方法我们也能够将时间复杂度降低为 O(n)。

2.24 数组中出现次数超过一半的数字

参考答案：

题目：

数组中有一个数字出现的次数超过数组长度的一半。请找出这个数字。例如输入一个长度为 9 的数组{1,2,3,2,2,2,5,4,2}。由于数
字 2 在数组中出现了 5 次，超过数组长度的一半，因此输出 2。如果不存在则输出 0。

思路：

（1）对数组进行排序，排序后的中位数就是所求数字。这种方法的时间复杂度取决于我们采用的排序方法的时间复杂度，因此最快为
O(nlogn)。

（2）由于所求数字的数量超过了数组长度的一半，因此排序后的中位数就是所求数字。因此我们可以将问题简化为求一个数组的中
位数问题。其实数组并不需要全排序，只需要部分排序。我们通过利用快排中的 partition 函数来实现，我们现在数组中随
机选取一个数字，而后通过 partition 函数返回该数字在数组中的索引 index，如果 index 刚好等于 n/2，则这个数字
便是数组的中位数，也即是要求的数，如果 index 大于 n/2，则中位数肯定在 index 的左边，在左边继续寻找即可，反之
在右边寻找。这样可以只在 index 的一边寻找，而不用两边都排序，减少了一半排序时间，这种方法的时间复杂度为 O(n)。

（3）由于该数字的出现次数比所有其他数字出现次数的和还要多，因此可以考虑在遍历数组时保存两个值：一个是数组中的一个数
字，一个是次数。当遍历到下一个数字时，如果下一个数字与之前保存的数字相同，则次数加 1，如果不同，则次数减 1，如果
次数为 0，则需要保存下一个数字，并把次数设定为 1。由于我们要找的数字出现的次数比其他所有数字的出现次数之和还要大，
则要找的数字肯定是最后一次把次数设为 1 时对应的数字。该方法的时间复杂度为 O(n)，空间复杂度为 O(1)。

2.25 两个链表的第一个公共结点

参考答案：

题目：

输入两个链表，找出它们的第一个公共结点。

思路：

（1）第一种方法是在第一个链表上顺序遍历每个结点，每遍历到一个结点的时候，在第二个链表上顺序遍历每个结点。如果在第二
个链表上有一个结点和第一个链表上的结点一样，说明两个链表在这个结点上重合，于是就找到了它们的公共结点。如果第一
个链表的长度为 m，第二个链表的长度为 n。这一种方法的时间复杂度是 O(mn）。

（2）第二种方式是利用栈的方式，通过观察我们可以发现两个链表的公共节点，都位于链表的尾部，以此我们可以分别使用两个栈
，依次将链表元素入栈。然后在两个栈同时将元素出栈，比较出栈的节点，最后一个相同的节点就是我们要找的公共节点。这
一种方法的时间复杂度为 O(m+n)，空间复杂度为 O(m+n)。

（3）第三种方式是，首先分别遍历两个链表，得到两个链表的长度。然后得到较长的链表与较短的链表长度的差值。我们使用两个
指针来分别对两个链表进行遍历，首先将较长链表的指针移动 n 步，n 为两个链表长度的差值，然后两个指针再同时移动，
判断所指向节点是否为同一节点。这一种方法的时间复杂度为 O(m+n)，相同对于上一种方法不需要额外的空间

3. 设计模式

3.1 观察者模式

参考答案：

观察者模式（Observer）

通常又被称为 发布-订阅者模式 或 消息机制，它定义了对象间的一种一对多的依赖关系，只要当一个对象的状态发生改变时，所有依赖于它的对象都得到通知并被自动更新，解决了主体对象与观察者之间功能的耦合，即一个对象状态改变给其他对象通知的问题

观察者模式JS实现

let observer_ids=0;
let observed_ids=0;
//观察者类
class Observer {
   constructor() {
      this.id = observer_ids++;
   }
   //观测到变化后的处理
   update(ob){
      console.log("观察者" + this.id + `-检测到被观察者${ob.id}变化`);
   }
}
//被观察者列
class Observed {
   constructor() {
      this.observers = [];
      this.id=observed_ids++;
   }
   //添加观察者
   addObserver(observer) {
      this.observers.push(observer);
   }
   //删除观察者
   removeObserver(observer) {
      this.observers = this.observers.filter(o => {
         return o.id != observer.id;
      });
   }
   //通知所有的观察者
   notify(ob) {
      this.observers.forEach(observer => {
         observer.update(ob);
      });
   }
}

let mObserved=new Observed();
let mObserver1=new Observer();
let mObserver2=new Observer();

mObserved.addObserver(mObserver1);
mObserved.addObserver(mObserver2);

mObserved.notify();

3.2 设计模式有哪些

参考答案：

设计模式（Design pattern）是一套被反复使用、多数人知晓的、经过分类编目的、代码设计经验的总结。

常用的设计模式

• 单体模式：单体是一个用来划分命名空间并将一批相关的属性和方法组织在一起的对象，如果他可以被实例化，那么他只能被实例化一次。
• 工厂模式:提供创建对象的接口，意思就是根据领导（调用者）的指示（参数），生产相应的产品（对象）
• 单例模式：单例模式定义了一个对象的创建过程，此对象只有一个单独的实例，并提供一个访问它的全局访问点。也可以说单例就是保证一个类只有一个实例，实现的方法一般是先判断实例存在与否，如果存在直接返回，如果不存在就创建了再返回，这就确保了一个类只有一个实例对象。
• 观察者模式（发布订阅模式）： 定义对象间的一种一对多的依赖关系，以便当一个对象的状态发生改变时，所有依赖于它的对象都得到通知并自动刷新，也被称为是发布订阅模式。
• 策略模式：策略模式指的是定义一些列的算法，把他们一个个封装起来，目的就是将算法的使用与算法的实现分离开来。说白了就是以前要很多判断的写法，现在把判断里面的内容抽离开来，变成一个个小的个体
• 模板模式：定义了一个操作中的算法的骨架，而将一些步骤延迟到子类中。模板方法使得子类可以不改变一个算法的结构即可重定义该算法的某些特定步骤。 通俗的讲，就是将一些公共方法封装到父类，子类可以继承这个父类，并且可以在子类中重写父类的方法，从而实现自己的业务逻辑
• 代理模式：代理模式的中文含义就是帮别人做事，javascript的解释为：把对一个对象的访问, 交给另一个代理对象来操作.
• 外观模式： 外观模式是很常见。其实它就是通过编写一个单独的函数，来简化对一个或多个更大型的，可能更为复杂的函数的访问。也就是说可以视外观模式为一种简化某些内容的手段