一、什么是单点登录？

单点登录（Single Sign On），简称为 SSO，是比较流行的企业业务整合的解决方案之一。SSO的定义是在多个应用系统中，用户只需要登录一次就可以访问所有相互信任的应用系统。

二、背景 & 前言

在 B/S 系统中，登录功能通常都是基于 Cookie 来实现的。一般有两种形式。第一种：当用户登录成功后，一般会将登录状态记录到 Session 中。第二种是：给用户签发一个 Token。然而这两种形式，均需要在客户端保存一些信息（Session ID 或 Token ），并要求客户端在之后的每次请求中携带它们。

在这样的场景下，使用 Cookie 无疑是最方便的，因此我们一般都会将 Session 的 ID 或 Token 保存到 Cookie 中，当服务端收到请求后，通过验证 Cookie 中的信息来判断用户是否登录 。

单点登录是指在同一帐号平台下的多个应用系统中，用户只需登录一次，即可访问所有相互信任的应用系统。

举例来说，百度贴吧和百度地图是百度公司旗下的两个不同的应用系统，如果用户在百度贴吧登录过之后，当他访问百度地图时无需再次登录，那么就说明百度贴吧和百度地图之间实现了单点登录。

单点登录的本质就是在多个应用系统中共享登录状态。如果用户的登录状态是记录在 Session 中的，要实现共享登录状态，就要先共享 Session，比如可以将 Session 序列化到 Redis 中，让多个应用系统共享同一个 Redis，直接读取 Redis 来获取 Session。

当然仅此是不够的，因为不同的应用系统有着不同的域名，尽管 Session 共享了，但是由于 Session ID 是往往保存在浏览器 Cookie 中的，因此存在作用域的限制，无法跨域名传递，也就是说当用户在 app1.com 中登录后，Session ID 仅在浏览器访问 app1.com 时才会自动在请求头中携带，而当浏览器访问 app2.com 时，Session ID 是不会被带过去的。实现单点登录的关键在于，如何让 Session ID（或 Token）在多个域中共享。

三、实现单点登录（SSO）的方式

实现单点登录的方式有三种：

1. 父域Cookie

如上所举例，保持cookie放置在一级域名之中，二级域名会自动继承来自父域（一级域名）的Cookie，因此就会实现一次登录，多个业务模块共享登录状态。此种方式实现比较简单，但是具有局限性，不可跨主域。

2. 认证中心

认证中心，是一个专门负责处理登录，鉴权，状态检查的专用模块，一般用于大型企业之内的各级部门协同工作，能较好实现一次登录，多个部门，多个不同主域的登录状态共享。目前我司内部就是采用这种认证中心，涉及到要校验用户权限时，就会跳转到一个专有的页面进行帐号登录去确认状态。 一般用的是Apereo CAS，它是一个企业级单点登录系统。稍后我会去针对这些进行详细的补充。。。。

3. LocalStorage跨域

目前来说，浏览器的安全策略是越来越严格，特别是浏览器新的版本更是控制了Cookie的Same Site属性，无意Cookie受限条件更多，可应用场景变的不再那么广泛。我们可以针对SSO这一块，考虑使用LocalStorage进行单点登录的实现。

在前后端分离的情况下，完全可以不使用 Cookie，我们可以选择将 Session ID （或 Token ）保存到浏览器的 LocalStorage 中，让前端在每次向后端发送请求时，主动将 LocalStorage 的数据传递给服务端。这些都是由前端来控制的，后端需要做的仅仅是在用户登录成功后，将 Session ID （或 Token ）放在响应体中传递给前端。 在这样的场景下，单点登录完全可以在前端实现。前端拿到 Session ID （或 Token ）后，除了将它写入自己的 LocalStorage 中之外，还可以通过特殊手段将它写入多个其他域下的 LocalStorage 中。

代码实现：

// 获取 token
var token = result.data.token;

// 动态创建一个不可见的iframe，在iframe中加载一个跨域HTML
var iframe = document.createElement("iframe");
iframe.src = "http://app1.com/localstorage.html";
document.body.append(iframe);
// 使用postMessage()方法将token传递给iframe
setTimeout(function () {
    iframe.contentWindow.postMessage(token, "http://app1.com");
}, 4000);
setTimeout(function () {
    iframe.remove();
}, 6000);

// 在这个iframe所加载的HTML中绑定一个事件监听器，当事件被触发时，把接收到的token数据写入localStorage
window.addEventListener('message', function (event) {
    localStorage.setItem('token', event.data)
}, false);

链表是什么？

• 多个元素组成的列表
• 元素存储不连续，用next指针连在一起

数组 VS 链表

• 数组：增删非首尾元素时往往需要移动元素
• 链表：增删非首尾元素，不需要移动元素，只需要更改next指向即可

JS中的链表

• JavaScript中没有链表
• 可以用Object模拟链表

Coding Part

LeetCode #237 删除链表中的节点

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点 。

现有一个链表 -- head = [4,5,1,9]，它可以表示为: 示例 1：

• 输入：head = [4,5,1,9], node = 5
• 输出：[4,1,9]
• 解释：给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

示例 2：

• 输入：head = [4,5,1,9], node = 1
• 输出：[4,5,9]
• 解释：给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.  

提示：

• 链表至少包含两个节点。
• 链表中所有节点的值都是唯一的。
• 给定的节点为非末尾节点并且一定是链表中的一个有效节点。
• 不要从你的函数中返回任何结果。

解题思路：

1. 无法直接获取被删除节点的上个节点
2. 将被删除节点转移到下个节点 即：如果要删除1节点 则需要先把9节点的值赋值给1节点，即4-5-9-9，然后删除最后一个节点 即 4-5-9

解题步骤：

• 将被删除的节点的值改为下个节点的值
• 删除下个节点

复杂度：

• 时间复杂度O（1）
• 空间复杂度O（1）

/*
 * @param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */
var deleteNode = function(node) {
    node.val = node.next.val;
    node.next = node.next.next;
    // 删除一个节点即 将本来要删除的节点的指针 指向下个节点的下个节点。
};

LeetCode #206 反转链表

反转一个单链表。

示例:

• 输入: 1->2->3->4->5->NULL
• 输出: 5->4->3->2->1->NULL

解题思路

1. 假如：反转两个节点：将n+1的next指向n
2. 假如：反转多个节点：双指针遍历链表，重复上述操作

解题步骤：

1. 双指针一前一后遍历链表
2. 遍历过程中不断反转双指针

复杂度：

• 时间复杂度 O（n）
• 空间复杂度 O（1）

  /**
  * @param {ListNode} head
  * @return {ListNode}
  */
  var reverseList = function(head) {
  let p1 = head;
  let p2 = null;
  while(p1){
      const temp = p1.next;
      p1.next = p2;
      p2 = p1;
      p1 = temp;
  }
  return p2;
  };

LeetCode #83 删除排序链表中的重复元素

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 :

• 输入: 1->1->2

• 输出: 1->2

• 输入: 1->1->2->3->3
• 输出: 1->2->3

解题思路：

1. 因为 链表是有序的，所以重复元素一定相邻
2. 遍历链表，如果发现当前元素和下个元素值相同，就删除下个元素值

解题步骤：

1. 遍历链表，如果发现当前元素和下个元素值相同，就删除下个元素值
2. 遍历结束以后，返回原链表的头部

复杂度：

1. 时间复杂度：O（n）
2. 空间复杂度：O（1）

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
    let p = head;
    while(p && p.next){
        if(p.val === p.next.val){
            p.next = p.next.next;
        }else{
            p = p.next;
        }
    }
    return head;
};

LeetCode # 141 环形链表

给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。 否则，返回 false

示例一：

• 输入：head = [3,2,0,-4], pos = 1
• 输出：true
• 解释：链表中有一个环，其尾部连接到第二个节点

示例二：

• 输入：head = [1,2], pos = 0
• 输出：true
• 解释：链表中有一个环，其尾部连接到第一个节点。

示例三：

• 输入：head = 1, pos = -1
• 输出：false
• 解释：链表中没有环。

提示：

• 链表中节点的数目范围是 [0, 104]
• -105 <= Node.val <= 105
• pos 为 -1 或者链表中的一个 有效索引 。

解题思路:

1. 两个人在圆形操场上的起点同时起跑，速度快的人一定会超过速度慢的人一圈。
2. 用一快一慢两个指针遍历链表，如果指针能够相逢，那么链表就有圈

解题步骤:

1. 用一快一慢两个指针遍历链表，如果指针能够相逢，就返回true
2. 遍历结束后，还没有相逢就返回false

复杂度:

1. 时间复杂度 O（n）
2. 空间复杂度 O（1）

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    let p1 = head; // 慢指针
    let p2 = head; // 快指针
    while(p1 && p2 && p2.next){
        p1 = p1.next;
        p2 = p2.next.next;
        if(p1 === p2){ //两个指针相逢
            return true;
        }
    }
    return false;
};

前端与链表：JS中的原型链

原型链介绍

• 原型链的本质是链表
• 原型链上的节点是各种原型对象，比如Function.prototype、Object.prototype
• 原型链通过_proto_属性连接各种原型对象

  原型链长啥样？

• obj -> Object.prototype -> null
• func -> Function.prototype -> Object.prototype -> null
• arr -> Array.prototype -> Object.prototype -> null

Coding Part

原型链知识点

• 如果A沿着原型链能找到B.prototype，那么A instanceof B 为true
• 如果在A对象上没有找到x属性，那么会沿着原型链找x属性

面试题一

简述instanceof的原理，并实现

• 知识点： 如果A沿着原型链能找到B.prototype，那么A instanceof B 为true
• 解法：遍历A的原型链，如果找到B.prototype，返回true，否则返回false

// 和遍历链表思路一样
const instanceOf = (A, B) => {
  let p = A;
  while(p){
    if(p === B.prototype){
      return true;
    }
    p = p.__proto__;
  }
  return false;
}

面试题二

var foo = {}, F = function(){};
Object.prototype.a = 'value a';
Function.prototype.b = 'value b';
console.log(foo.a);
console.log(foo.b);
console.log(F.a);
console.log(F.b);

分析：

• 知识点：如果在A对象上没有找到x属性，那么会沿着原型链找x属性
• 解法：明确foo和F变量的原型链，沿着原型链找a属性和b属性。

  console.log(foo.a); // 'value a'
  console.log(foo.b); // 'undefined'
  console.log(F.a); // 'value a'
  console.log(F.b); // 'value b'

前端与链表： 使用链表指针获取JSON的节点值

const json = {
  a: { b: {c: 1} },
  d: { e: 2 }
}

const path = ['d', 'e']; // 路径
// 和遍历链表异曲同工之妙
let p = json;
path.forEach(k =>{
  p = p[k];
})
// 路径：2

链表--总结

• 链表里的元素存储不是连续的，之间通过next链接
• JavaScript中没有链表，但可以用Object模拟链接
• 链表常用操作：修改next，遍历链表
• JS中的原型链也是一个链表。沿着proto属性
• 使用链表指针可以获取JSON的节点值

阶段思考题：

1. 编写一个 instanceOf 方法，可以判断一个变量是否是另一个变量的实例。
2. 判断一个链表是否为回文链表。题目链接：https://leetcode-cn.com/problems/palindrome-linked-list/

队列是什么？

• 一个先进先出的数据结构
• Javascript中没有队列，但可以用Array实现队列的所有功能

Coding Part

什么场景用队列？

• 需要先进先出的场景
• 比如：电影院排队进场，JS异步中的任务队列，计算最近请求次数

场景一、电影院排队进场

• 先进先出，保证有序

场景二、JS异步中的任务队列

• JS是单线程，无法同时处理异步中的并发任务
• 使用任务队列先后处理异步任务

场景三、 计算最近请求次数

输入一个数组，代表请求发起的时刻

inputS = [[],[1],[100],[3001],[3002]]
[null,1,2,3,3]

• 有新请求就入队。3000ms前发出的请求出队
• 队列的长度就是最近请求的次数

LeetCode #933题

最近的请求次数

写一个 RecentCounter 类来计算特定时间范围内最近的请求。

请你实现 RecentCounter 类：

RecentCounter() 初始化计数器，请求数为 0 。

int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。

保证每次对 ping 的调用都使用比之前更大的 t 值。

输入：
["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]
输出：
[null, 1, 2, 3, 3]

解释：
RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1);     // requests = [1]，范围是 [-2999,1]，返回 1
recentCounter.ping(100);   // requests = [<u>1</u>, <u>100</u>]，范围是 [-2900,100]，返回 2
recentCounter.ping(3001);  // requests = [<u>1</u>, <u>100</u>, <u>3001</u>]，范围是 [1,3001]，返回 3
recentCounter.ping(3002);  // requests = [1, <u>100</u>, <u>3001</u>, <u>3002</u>]，范围是 [2,3002]，返回 3

提示：
1 <= t <= 104
保证每次对 ping 的调用都使用比之前更大的 t 值
至多调用 ping 方法 104 次

解题思路：

1. 越早发出的请求越早不在最近3000ms内的请求里
2. 满足先进先出，考虑用队列

解题步骤：

1. 有新请求就入队，3000ms前发出的请求出队
2. 队列的长度就是最新请求的次数

时间复杂度 O（n） 空间复杂度 O（n）

var RecentCounter = function() {
    this.queue = [];
};

/** 
 * @param {number} t
 * @return {number}
 */
RecentCounter.prototype.ping = function(t) {
    this.queue.push(t);
    while(this.queue[0] < t-3000){
        this.queue.shift();
    }
    return this.queue.length;
};

队列-总结

• 队列是一个先进先出的数据结构
• JavaScript中没有队列，但是可以用Array实现队列的所有功能
• 队列常用操作push、 shift、 queue[0]

栈是什么？

• 一个后进先出的数据结构

• JavaScript中没有栈，但可以用Array实现栈的所有功能

  

栈的应用场景

• 需要后进先出的场景
• 比如： 十进制转二进制，判断字符串的括号是否有效、函数的调用栈

场景一、 十进制转二进制

• 后出来的余数要先出来

• 把余数依次入栈，然后再出栈，就可以实现余数倒序输出

  

场景二、 有效的括号

• 越靠后的左括号，对应的右括号越靠前
• 左括号入栈，右括号出栈，最后栈空了就是合法的。

场景三、 函数调用堆栈

• 最后调用的函数，最先执行完成
• JS解释器使用栈来控制函数的调用顺序

LeetCode #20题

20 有效的括号

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

有效字符串需满足：

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

解题思路：

1. 对于没有闭合的左括号而言，越靠后的左括号，对应的右括号越靠前。
2. 满足后进先出，考虑用栈的思路

步骤：

1. 新建一个栈
2. 扫描字符串。遇到左括号入栈，遇到和栈顶括号类型匹配的右括号出栈，类型不匹配直接判定为不合法
3. 最后栈控了合法，不空就不合法

时间复杂度 O(n)

空间复杂度 O(n)

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    if(s.length %2 === 1) { return false }
    const stack = [];
    for(let i = 0; i<s.length; i+=1){
        const c = s[i];
        if(c === '(' || c === '{' || c === '['){
            stack.push(c);
        }else{
            const top = stack[stack.length-1];
            if(
                (top === '(' && c === ')') ||
                (top === '{' && c === '}') ||
                (top === '[' && c === ']')
            ){
                stack.pop();
            }else{
                return false;
            }
        }
    }
    return stack.length === 0;
};

总结

• 栈是一个后进先出的数据结构
• JavaScript中没有栈，但是可以用array实现栈的所有功能
• 栈的常用操作： push、pop、stack[length-1]

用ES6的class，封装一个stack类，包括push、pop、peek方法

```JavaScript
// 使用es6的class来封装一个stack类
class farkStack{ // 定义一个名字为Stack的类
  constructor(){
    this.dataStore = []
  }
  push(item){
    this.dataStore.push(item);
  }
  pop(){
    return this.dataStore.pop();
  }
  peek(){ // 探出
    return this.dataStore[this.dataStore.length - 1];
  }
  size(){
    return this.dataStore.length;
  }
  clear(){
    this.dataStroe = []
  }
}
```

用栈这个数据结构，将100这个十进制数字转为2进制

```JavaScript
function  switchBinary(decNum){
  let stack = new farkStack();
  while(decNum > 0){
    stack.push(decNum % 2);
    decNum = Math.floor(decNum/2)
  }
  let binaryStr = ''
  while(stack.size() !== 0) {
    binaryStr += stack.pop()
  }
  return binaryStr;
}

switchBinary(125)
```

时间复杂度是什么？

• 一个函数，用大O表示，比如O（1）、O（n）、 O（logN）...
• 定性描述该算法的运算时间

• 需要关注的 O(1) < O（log₂n）< O（n）< O（n²）

  

主要的时间复杂度有：

• 常数阶 O（1）：无论代码执行了多行，只要没有循环等复杂结构，那这个代码的复杂度就是 O(1)

• 对数阶 O（logN）：在while循环里面，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了。我们试着求解一下，假设循环x次之后，i 就大于 2 了，此时这个循环就退出了，也就是说 2 的 x 次方等于 n，那么 x = log2(n) 也就是说当循环 log2(n) 次以后，这个代码就结束了。因此这个代码的时间复杂度趋势为：O(logn)

• 线性阶 O(n)： 在 单层 循环体内，代码会随着每次循环执行，它消耗的时间是随着n的变化而变化的，因此这是一个线性相关趋势，时间复杂度为 O(n)。

• 线性对数阶 O(nlogN)：线性对数阶O(nlogN) 其实非常容易理解，将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN)。

  for (let i = 0; i < n; i++) {
  let m = 1;
  while(m < n) {
      i = i * 2;
  }
  }

• 平方阶 O(n^2)： 将 O(n) 的代码再循环嵌套一遍，它的时间复杂度就是 O(n^2)。

  for (let i = 0; i < n; i++) {
  for (let j = 0; i < n; i++) {
      console.log(i, j)
  }
  }

  如果将其中一层循环的n改成m，即：

  for (let i = 0; i < m; i++) {
  for (let j = 0; i < n; i++) {
      console.log(i, j)
  }
  }

  那么它的时间复杂度就变成了 O(m*n)

• 立方阶 O(n^3)： O(n³)相当于三层n循环，其它的类似

• K次方阶 O(n^k)

• 指数阶 O(2^n)

空间复杂度是什么？

• 一个函数，用大O表示，比如O（1）、O（n）、O（n²）
• 算法在运行过程中临时占用存储空间大小的量度

常见空间复杂度：

• 空间复杂度 O(1)，如果算法执行所需要的临时空间不随着某个变量 n 的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1);

• 空间复杂度 O(n)

  const list = []
  for(let i = 0; i < n; i +=1 ){
    list.push(i);
  }

• 空间复杂度 O(n^2)

  const matrix = []
  for (let i = 0; i < n; i++) {
      matrix.push([]);
      for (let j = 0; i < n; j++) {
        matrix[i].push(j);
      }
  }

  开始定义了一个数组，而后使用 for 循环再次定义了一个数组，相当于创建了一个二维数组(矩阵)，这个数组中的每一项都是一个空间度量为 n 的数组，因此它的空间复杂度为 O(n^2)

阶段思考题：

1. 如果一段代码中有3个循环，它们的循环次数都是n，那么这段代码的时间复杂度是O（3n）还是O（n）？
   • 如果是 3 个并列循环的代码，那么总的时间复杂度趋势为 O(n)
   • 如果是 3 个循环嵌套，那么总的时间复杂度趋势为 O(n^3)
2. 假设每天睡觉前，你都会数2的次方，1、2、4、8...,每次你都数到n才能睡着，那么你数了几个数？时间复杂度是多少？
   • 数了：2^x = n ==> x = log2(n) ; x 从 0 算起 所以数了 log2(n) + 1 个数
   • 时间复杂度的趋势为 O(logN)