1.时间复杂度与空间复杂度
时间复杂度：一个用来描述算法运行时间的函数。
空间复杂度：算法在运行过程中临时占用存储空间大小的量度。
常见时间复杂度耗时排序：O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)
2.链表
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表的常见算法有：单链表的插入与删除、反转链表、循环链表（环形链表）、双向链表。
单链表的数据结构在JavaScript中可以表示为：
//链表中单个节点的构造函数
function ListNode(val){
this.val = val;
this.next = null;
}
//单向链表的构造函数
function SingleLink(){
this.head = null;
this.length = 0;
}
//向链表末尾添加一个元素的append方法
SingleLink.prototype.append= function(ele){
var node = new ListNode(ele);
if(this.head == null){
this.head = node;
}else{
var n = this.head;
//找到最后一个节点，其next为null
while(n.next){
n = n.next;
}
n.next = node;
}
this.length++;
return this.head;
}
//向链表任意位置添加一个元素的insert方法
SingleLink.prototype.insert = function (ele, index) {
var node = new ListNode(ele);
if (index > this.length) {
return false;
} else if (this.head == null) {
this.head = node;
} else if (index == 0) {
node.next = this.head;
this.head = node;
} else {
let n = this.head;
let i = 0;
//找到要插入位置的前一个节点
while (i < index - 1) {
n = n.next;
i++;
}
node.next = n.next;
n.next = node;
}
this.length++;
return this.head;
}
//删除指定位置的节点的delete方法
SingleLink.prototype.delete = function (index) {
if (index >= this.length) {
return false;
} else if (index == 0) {
this.head = this.head.next;
} else {
let i = 0;
let n = this.head;
//找到要删除位置的前一个节点
while (i < index - 1) {
n = n.next;
i++;
}
n.next = n.next.next;
}
this.length--;
return this.head;
}
//获取指定位置的节点的getIndexOf方法
SingleLink.prototype.getIndexOf = function (index) {
let node;
if (index >= this.length) {
return false;
} else if (index == 0) {
node = this.head;
} else {
let i = 0;
let n = this.head;
while (i < index) {
n = n.next;
i++;
}
node = n;;
}
return node;
}此外还应该有获取链表长度的length方法和判断链表是否为空的isEmpty方法，这两个方法根据链表的length属性可以非常容易实现，这里不再赘述。
(1)删除链表的倒数第N个节点
//给定一个链表，删除链表的倒数第n个结点，并返回头结点
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} n
* @return {ListNode}
*/
var removeNthFromEnd = function (head, n) {
let temp = [];
//将链表转换为数组进行存储，方便获取链表长度
while (head) {
temp.push(head);
head = head.next;
}
//获取要删除的节点位置
let index = temp.length - n;
//长度为1时，直接返回null
if (temp.length === 1) {
return null;
//删除的节点不是最后一个
} else if (index + 1 < temp.length) {
//删除当前节点，返回头节点
temp[index].val = temp[index + 1].val;
temp[index].next = temp[index + 1].next;
return temp[0];
//删除的节点是最后一个
} else {
//删除最后一个节点，并将前一个节点置空
temp[index - 1].next = null;
return temp[0];
}
}（2）反转链表
//反转一个单链表
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function (head) {
//直接修改node的next属性会改变原链表，造成死循环，借助数组或者new一个node来深度赋值
if (head) {
let result = new ListNode(head.val);
//通过while循环，不断将后边的节点作为头节点，直到head.next为空
while (head.next) {
//借助一个new的节点来保存之前的节点数据
let preNode = new ListNode(result.val);
preNode.next = result.next;
result.val = head.next.val;
result.next = preNode;
head = head.next;
}
return result;
} else {
return head;
}
}可以将while循环的内容改为递归调用的函数，也可以采用将链表保存成一个数组，再倒序生成链表的方式。
（3）回文链表
//判断一个链表是否为回文链表。(空间复杂度为常数阶O(1),时间复杂度为O(n))
//空间复杂度为O(1)可以先遍历得到链表长度，再反转前半部分，再与后半部分比较
/**
* @param {ListNode} head
* @return {boolean}
*/
var isPalindrome = function (head) {
let length = 0;
let i = 0;
//获取链表的长度length
for (let cur = head; cur != null; cur = cur.next) {
length++;
}
//链表为空或长度为1，为回文链表
if (length <= 1) {
return true;
//链表长度为2
} else if (length == 2) {
return head.val == head.next.val;
} else {
//将链表划分为left,right两部分
let left = new ListNode(head.val);
//将左半部分链表反转
while (i < Math.floor(length / 2) - 1) {
let preNode = new ListNode(left.val);
preNode.next = left.next;
left.val = head.next.val;
left.next = preNode;
head = head.next;
i++;
}
//若链表长度为偶数，则right的头节点为head.next,否则跳过一个节点为head.next.next
let right = parseInt(length / 2) === length / 2 ? head.next : head.next.next;
//比较left和right链表
while (left && right) {
if (left.val != right.val) {
return false;
} else {
left = left.next;
right = right.next;
}
}
return true;
}
}空间复杂度为O(n)可以先遍历得到链表数组，再遍历数组从数据头尾两个方向比较。
（4）环形链表
//给定一个链表，判断链表中是否有环。
/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = function (head) {
//链表中经常使用双指针法
//若链表中不存在环，slow和fase步调不同，永不指向同一个对象
//反之，若存在环，则终有指向同一个对象之时
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}
//////////////////////////////////////////////////////
var hasCycle = function (head) {
//将链表存储为数组，若新push进的对象与之前存储的对象相同，则存在环
//若不存在环，则链表终会遍历完，不会造成死循环
let arr = [];
while (head) {
arr.push(head);
for (let i = 0; i < arr.length; i++) {
if (head.next == arr[i]) {
return true;
}
}
head = head.next;
}
return false;
};链表种使用双指针法有效降低了空间复杂度，为O(1)，时间复杂度为O(n)。而使用数组的解法，空间复杂度为O(n)，时间复杂度为O(n2)。
3.栈
栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，把另一端称为栈底。栈的应用包括：递归、四则运算表达式求值、进制数转换等。
栈的数据结构在JavaScript中可以表示为：
//栈中单个元素的构造函数function StackNode(val) {
this.val = val;
this.next = null;
}
//栈的构造函数
function Stack() {
this.top = null;
this.length = 0;
}
//入栈方法
pushStack.prototype.push = function (ele) {
var node = new StackNode(ele);
if (this.top == null) {
this.top = node;
} else {
node.next = this.top;
this.top = node;
}
this.length++;
return this;
}
//出栈方法
popStack.prototype.pop = function () {
if (this.length == 0) {
return false;
} else {
var temp = this.top.next;
this.top = temp;
}
this.length--;
return this;
}以上代码实现了栈的链式结构存储。与链表类似，top是栈的栈顶元素，相当于链表的头节点。每次push都会在栈顶加入一个元素，即在链表的头节点前再加一个节点。pop即删除头节点，栈顶元素变为头节点的下一个节点。
JavaScript中栈的实现常用数组Array，Array自带push\pop\length等方法，在此不再实现。
此外还应有栈的length方法和clear方法，不再赘述。
（1）最小栈
/*设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) -- 将元素 x 推入栈中。
pop() -- 删除栈顶的元素。
top() -- 获取栈顶元素。
getMin() -- 检索栈中的最小元素。*/
/**
* initialize your data structure here.
*/
var MinStack = function () {
this.items = [];
this.min = [];
this.p = null;
};
/**
* @param {number} x
* @return {void}
*/
MinStack.prototype.push = function (x) {
this.items.push(x);
this.p = x;
if (this.min.length == 0) {
this.min.push(x);
} else {
//min中存储直到栈中push进x为止，最小的元素，加等号，相同的最小元素
let l = this.min.length;
this.min[l - 1] >= x ? this.min.push(x) : '';
}
};
/**
* @return {void}
*/
MinStack.prototype.pop = function () {
let len = this.items.length;
let minLen = this.min.length;
//当最小的元素被pop出去时，min也pop出最小元素，
//则min中最后一个为截止到剩下的元素为止,它们中的最小值
if (this.items[len - 1] == this.min[minLen - 1]) {
this.min.pop();
}
this.items.pop();
this.p = this.items[len - 2];
};
/**
* @return {number}
*/
MinStack.prototype.top = function () {
return this.p;
};
/**
* @return {number}
*/
MinStack.prototype.getMin = function () {
let minLen = this.min.length;
return this.min[minLen - 1];
};最小栈的难点在于如何在常数时间内找到最小值，如果之前未对push进栈中的元素进行相关记录的话，则找到最小值最少也需要O(n)的时间复杂度。
声明一个数组，第一项为栈底元素（默认最小值），在每次push一个新数进栈时，与数组的最后一项比较，如果比这一项小，则push进该数组，表示到该元素进栈为止，最小值是数组最后一项，数组长度+1。如果不比这一项小，则表示到该元素进栈为止，最小的仍然是数组最后一项，数组长度不变。在元素出栈pop时，如果刚好pop出的是最小值，则将数组的最后一项也pop出，代表到栈中元素pop之后时，最小值发生了改变。
/*根据逆波兰表示法，求表达式的值。
有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。*/
/**
* @param {string[]} tokens
* @return {number}
*/
//JavaScript数组实现栈结构
function Stack() {
this.items = [];
this.top = null;
this.length = 0;
}
Stack.prototype.push = function (ele) {
this.items.push(ele);
this.top = ele;
this.length++;
}
Stack.prototype.pop = function () {
let len = this.items.length;
this.items.pop();
this.top = this.items[len - 2];
this.length--;
}
//逆波兰式求值
var evalRPN = function (tokens) {
var sta = new Stack();
for (let i = 0; i < tokens.length; i++) {
if (isNaN(tokens[i])) {
let num1 = parseInt(sta.top);
sta.pop();
let num2 = parseInt(sta.top);
sta.pop();
let t;
switch (tokens[i]) {
case "+":
t = num2 + num1;
break;
case "-":
t = num2 - num1;
break;
case "*":
t = num2 * num1;
break;
case "/":
t = parseInt(num2 / num1);
break;
}
sta.push(t);
} else {
sta.push(tokens[i]);
}
}
return sta.top;
};将后缀表达式利用栈的先进后出计算得出结果，规则是从左至右遍历后缀表达式，如果是数字就直接进栈，如果是符号则将栈顶两个元素出栈，进行计算，再将计算结果入栈。
将常见的中缀表达式转为后缀表达式也是利用栈的先进后出。规则是从左至右遍历中缀表达式，如果式数字就直接输出，如果符号就比较与栈顶符号的优先级，是右括号或优先级低于栈顶符号，则栈顶元素依次输出并出栈，并将当前符号进栈，一直到最后输出后缀表达式。
（3）递归-斐波那契数列
/*斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。
该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。
给定 N，计算 F(N)。*/
/**
* @param {number} N
* @return {number}
*/
var fib = function(N) {
if(N<=1) return N;
return fib(N-1)+fib(N-2)
}（4）递归-爬楼梯
/*假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？*/
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
if(n<=2) return n;
return climbStairs(n-1)+climbStairs(n-2);
///////////使用动态规划思路////////////////
var result = new Array();
result = [0,1,2];
for(var i=3;i<=n;i++){
result[i] = result[i-1]+result[i-2];
}
return result[n];
}爬楼梯问题适合从上向下的解决问题，当爬上最后一阶时有两种可能，一是最后一步爬一阶，二是最后一步爬两阶。同理，当爬到倒数第二阶时，也有两种可能。故可以得出f(n)=f(n-1)+f(n-2)[n>2]。
爬楼梯问题更符合动态规划类问题的解题思路，之后再续。
