dzye / js-algorithms

js-algorithms's Issues

链表

链表

链表是一组非连续非顺序的存储结构，元素通过指针相连
常用的链表包含单链表，双向量表，循环链表，
循环链表是一种特殊的单链表，结尾的指针指向头节点，
双向量表在开发中更为常用，虽然每个节点都占用更多空间存储了前置指针，但是实际开发中如果要获取某节点前驱节点，在单链表中只能从头进行遍历，双向链表则可以直接获取，这样可以降低时间复杂度，即空间换时间

基于Object的实现单链表

const a = { val: 'a' };
const b = { val: 'b' };
const c = { val: 'c' };
const d = { val: 'd' };
a.next = b;
b.next = c;
c.next = d;
d.next = null;
// 遍历链表
let p = a;
while (p) {
 console.log(p.val);
 p = p.next;
}
// 插入e到c d 之间
const e = { val: 'e' };
const mut = c.next;
c.next = e;
e.next = mut;
// 删除e
c.next = d

链表的基础题目

1. 删除单链表中的节点
   leetcode(237) 删除节点 将next节点赋值给当前节点，然后将当前节点的next指向下下个节点即可实现删除当前节点

var deleteNode = function(node) {
 node.val = node.next.val
 node.next = node.next.next
};

2. 反转链表
   leetcode(206)
   反转两个节点：将n+1的next指向n
   反转多个节点：双指针遍历链表，重复反转两个节点的操作

var reverseList = function(head) {
 let cur = head
 let pre = null
 while(cur){
	 const tmp = cur.next;
	 cur.next = pre
	 pre = cur
	 cur = tmp
 }
 return pre
};

3. 两数之和
   leetcode(2)

var addTwoNumbers = function (l1, l2) {
 const l3 = new ListNode(0);
 let p1 = l1;
 let p2 = l2;
 let p3 = l3;
 let a = 0;
 while (p1 || p2) {
	 const v1 = p1 ? p1.val : 0;
	 const v2 = p2 ? p2.val : 0;
	 const sum = v1 + v2 + a;
	 a = Math.floor(sum / 10)
	 p3.next = new ListNode(sum % 10)
	 if (p1) {
		 p1 = p1.next;
	 }
	 if (p2) {
		 p2 = p2.next;
	 }
	 p3 = p3.next
 }
 if (a) {
	 p3.next = new ListNode(a)
 }
 return l3.next
};

4. 删除排序链表中的重复元素
   leetcode(83)
   排序链表重复元素必定相邻，循环链表，比较当前链表和下个元素是否相同，相同就删除下个元素，即可

var deleteDuplicates = function (head) { 
	let p = head; 
	while (p) { 
		if (!!p.next && p.val === p.next.val) { 
			if (!!p.next.next) { 
				p.next = p.next.next 
			} else { 
				p.next = null 
			} 
		}else{ 
			p = p.next 
		} 
	} 
	return head 
};

5.环形链表
leetcode(141)
快慢指针循环 如果有环 会出现快指针等于慢指针的情况

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中的链表

1. 原型链
   实现instanceof 循环原型链

const instanaceOf = (a, b) => {
 let p = a;
 while (p) {
	 if (p === b.prototype) {
		 return true;
	 }
	 p = p.__proto__;
 }
 return false;
};

2. 链表指针获取json节点值

const json = {
 a: { b: { c: 1 } },
 d: { e: 2 },
};
const path = ['a', 'b', 'c'];
let p = json;
path.forEach((item) => {
 p = p[item];
});
return p;

字典

字典

字典也是存储唯一的数据结构，以键值对的形式存储，即es6中的Map

字典的常用操作

增 删 改 查

const m = new Map();
m.set('a','aaa');
m.set('b','bbb');
m.delete('a');
//m.clear();
m.set('a','aa');
m.get('a')

leetcode常见题目

1. 两个数组的交集（349）

var intersection = function(nums1, nums2) {
    let m1 = new Map()
    let m2 = new Map()
    nums1.forEach(item=>{
        m1.set(item,true)
    })
    nums2.forEach(item=>{
        m2.set(item,true)
    })
    let list =[]
    for(var item of m1.keys()){
        if(m2.get(item)){
            list.push(item)
        }
    }
    return list
};

2. 有效的括号（20）
   //todo
3. 两数之和（1）

var twoSum = function (nums, target) {
    let m = new Map();
    for (let i = 0; i < nums.length; i++) {
        let item = nums[i];
        if (m.has(target - item)) {
            return [m.get(target - item), i]
        } else {
            m.set(item, i)
        }
    }
};

3. 无重复字符的最长字串（3）

var lengthOfLongestSubstring = function (s) {
    let l = 0;
    let m = new Map();
    let max = 0;
    for (let r = 0; r < s.length; r++) {
        if (m.has(s[r]) && m.get(s[r]) >= l) {
            l = m.get(s[r])+1;
        }
        max = Math.max(max, r - l + 1)
        m.set(s[r], r)
    }
    return max
};

4. 最小覆盖子串（4）

var minWindow = function (s, t) {
 let l = 0;
 let r = 0;
 let need = new Map();
 for (let i = 0; i < t.length; i++) {
	 if (need.has(t[i])) {
		 need.set(t[i], need.get(t[i]) + 1)
	 } else {
		 need.set(t[i], 1)
	 }
 }
 let needType = need.size
 let res = ''
 while (r < s.length) {
	 if (need.has(s[r])) {
		 need.set(s[r], need.get(s[r]) - 1)
		 if (need.get(s[r]) === 0) {
			 needType--;
		 }
		 }
		 while (needType === 0) {
		 const newRes = s.substring(l, r + 1);
		 if (!res || newRes.length < res.length) {
			 res = newRes
		 }
		 if (need.has(s[l])) {
			 need.set(s[l], need.get(s[l]) + 1)
			 if (need.get(s[l]) === 1) {
				 needType++;
			 }
		 }
		 l++;
	 }
	 r++;
 }
 return res
};

队列

队列

一个先进先出的数据结构

基于数组的实现

const queue = [];
queue.push(1);
queue.push(2);
const item1 = queue.shift();
const item2 = queue.shift()

队列的应用实例

对于资源有限的场景，没有空闲资源时，都可以通过数据结构来实现请求排队

1. js中的异步队列
   涉及js中eventloop相关，js是单线程，执行中，所有的同步任务都在主线程执行，形成执行栈，异步任务会将其回调存入任务队列等待，在主线程执行结束后，读取任务队列，获取相应任务的回调放入执行栈执行
2. 计算最近请求次数
   leetcode(933) 越早发出请求，越早不在最近范围，符合先进先出使用队列

var RecentCounter = function () {
 this.q = [];
};
RecentCounter.prototype.ping = function (t) {
 this.q.push(t);
 while (this.q[0] + 3000 < t) {
 this.q.shift()
 }
 return this.q.length
};

javascript中常用的栈操作

入队：push,出队shift,获取队头元素：queue[0]

树

树

一种分层数据的抽象模型
js中没有树的数据结构，可以用Object和Array构建

树的常用操作

1. 深度优先遍历
   尽可能深的搜索树的分支
   a. 访问根节点
   b. 循环深度遍历子节点

const dfs = (root) => {
 root.children.forEach(dfs);
};
dfs(tree);

2. 广度优先遍历
   先访问离根节点最近的节点
   a. 新建一个队列，根节点入队
   b. 队头出队并访问
   c. 队头的children挨个入队
   d. 重复第二三步，直到队列为空

const bfs = (root) => {
 const q = [root];
 while (q.length > 0) {
	 let out = q.shift();
	 out.children.forEach((item) => {
		 q.push(item);
	 });
 }
};
bfs(tree);

二叉树

树中每个节点最多有两个子节点

1. 二叉树的先序遍历

const bt = require('./bt');
// function preorder(root) {
//   if (!root) return;
//   console.log(root.val);
//   preorder(root.left);
//   preorder(root.right);
// }
// 通过使用堆栈的先进后出特性，先获取根节点，然后将右左压入栈中，以此输出左右 循环执行
function preorder(root) {
 if (!root) return;
 const stack = [root];
 while (stack.length != 0) {
	 const item = stack.pop();
	 console.log(item.val);
	 if (item.right) {
		 stack.push(item.right);
	 }
	 if (item.left) {
		 stack.push(item.left);
	 }
 }
}

preorder(bt);

2. 二叉树的中序遍历

const bt = require('./bt');
// function inorder(root) {
//   if (!root) return;
//   inorder(root.left);
//   console.log(root.val);
//   inorder(root.right);
// }
// 通过使用堆栈的先进后出特性，1，先将从根节点开始的所有左节点依次压入栈中，从最后一个左节点开始输出自身，2.然后获取它的右节点作为根节点开始重复1步骤
function inorder(root) {
 if (!root) return;
 const stack = [];
 let p = root;
 while (stack.length || p) {
	 while (p) {
		 stack.push(p);
		 p = p.left;
	 }
	 const n = stack.pop();
	 console.log(n.val);
	 p = n.right;
 }
}
inorder(bt);

3. 二叉树的后序遍历

const bt = require('./bt');
// function postorder(root) {
//   if (!root) return;
//   postorder(root.left);
//   postorder(root.right);
//   console.log(root.val);
// }
//通过先序遍历的方法 ，将访问节点的操作改为节点压入栈，获取一个后序输出的栈，遍历此栈输出即后续遍历
function postorder(root) {
 if (!root) return;
 const stack = [root];
 const outStack = [];
 while (stack.length) {
	 const item = stack.pop();
	 if (item.left) {
		 stack.push(item.left);
	 }
	 if (item.right) {
		 stack.push(item.right);
	 }
	 outStack.push(item);
 }
 console.log(outStack);
 while (outStack.length) {
	 const n = outStack.pop();
	 console.log(n.val);
 }
}

postorder(bt);

leetcode

1. 二叉树的最大深度（104）
   使用树的深度优先遍历，记录每一层级的级数，获取最大的

var maxDepth = function (root) {
 let max = 0;
 const dfs = (n, l) => {
	 if (!n) return
	 if (!n.left && !n.right) {
		 max = Math.max(max, l)
	 }
	 dfs(n.left, l + 1)
	 dfs(n.right, l + 1)
 }
 dfs(root, 1)
 return max
};

2. 二叉树的最小深度（111）
   使用树的广度优先遍历，记录层级，遇到第一个叶子节点直接返回层级即最小深度

var minDepth = function (root) {
 if (!root) return 0
 let q = [[root, 1]];
 while (q.length > 0) {
	 let [n, l] = q.shift();
	 if (!n.left && !n.right) {
		 return l
	 }
	 if (n.left) q.push([n.left, l + 1]);
	 if (n.right) q.push([n.right, l + 1]);
 }
};

3. 二叉树的层序遍历（102）
   a. 使用树的广度优先遍历，记录层级，以层级为新数组的索引向数组内添加节点元素

var levelOrder = function (root) {
 if (!root) return [];
 let q = [[root, 0]];
 let list = [];
 while (q.length) {
	 const [n, i] = q.shift();
	 list[i] = list[i] || [];
	 list[i].push(n.val);
	 if (n.left) q.push([n.left, i + 1])
	 if (n.right) q.push([n.right, i + 1])
 }
 return list
};

b. 使用树的广度优先遍历，确保循环中每一层全部压入当前索引再继续遍历下一层

var levelOrder = function (root) {
 if (!root) return [];
 let q = [root];
 let list = [];
 while (q.length) {
	 let len = q.length
	 list.push([]);
	 while (len--) {
		 let n = q.shift()
		 list[list.length - 1].push(n.val)
		 if (n.left) q.push(n.left)
		 if (n.right) q.push(n.right)
	 }
 }
 return list
};

4. 二叉树的中序遍历（94）

var inorderTraversal = function (root) {
 if (!root) return [];
 let list = [];
 const stack = [];
 let p = root;
 while (stack.length || p) {
	 while (p) {
		 stack.push(p);
		 p = p.left
	 }
	 const n = stack.pop();
	 list.push(n.val)
	 p = n.right
 }
 return list
};

5. 路径总和（112）

var hasPathSum = function (root, targetSum) {
 if (!root) return false
 let flag = false
 const dfs = (m, s) => {
	 if (!m.left && !m.right) {
		 if (s === targetSum) {
			 flag = true
		 }
	 }
	 if (m.left) dfs(m.left, s + m.left.val)
	 if (m.right) dfs(m.right, s + m.right.val)
 }
 dfs(root, root.val)
 return flag
};

图

图

一组由边连接的节点

图的表示

1. 邻接矩阵
2. 邻接表

图的常用操作

邻接表表示一个图

const graph = {
 0: [1, 2],
 1: [2],
 2: [0, 3],
 3: [3],
};

图的深度优先遍历

1. 访问根节点
2. 对根节点没访问过的相邻节点挨个深度遍历

const visited = new Set();
const dfs = (n) => {
 console.log(n);
 visited.add(n);
 graph[n].forEach((item) => {
	 if (!visited.has(item)) {
		 dfs(item);
	 }
 });
};
dfs(2);

图的广度优先遍历

1. 新建一个队列，根节点入队
2. 把队头出队并访问
3. 把队头没有访问过的相邻节点入队
4. 重复二三步 直到队列为空

const visited = new Set();
const queue = [];
const bfs = (n) => {
 visited.add(n);
 queue.push(n);
 while (queue.length) {
	 const n = queue.shift();
	 console.log(n);
	 graph[n].forEach((item) => {
		 if (!visited.has(item)) {
			 queue.push(item);
			 visited.add(item);
		 }
	 });
 }
};

bfs(2);

leetcode相关题目

1. 65有效数字

var isNumber = function (s) {
 const graph = {
	 0: { 'blank': 0, 'sign': 1, '.': 2, 'digit': 6 },
	 1: { 'digit': 6, '.': 2 },
	 2: { 'digit': 3 },
	 3: { 'digit': 3, 'e': 4 },
	 4: { 'digit': 5, 'sign': 7 },
	 5: { 'digit': 5, },
	 6: { 'digit': 6, '.': 3, 'e': 4 },
	 7: { 'digit': 5 },
 }
 let state = 0
 for (c of s.trim()) {
	 if (c >= 0 && c <= 9) {
		 c = 'digit'
	 } else if (c === ' ') {
		 c = 'blank'
	 } else if (c === '+' || c === "-") {
		 c = 'sign'
	 } else if (c === 'E') {
		 c = 'e'
	 }
	 state = graph[state][c]
	 if (!state) {
		 return false
	 }
 }
 if (state === 3 || state === 5 || state === 6) {
	 return true
 }
 return false
};

栈

栈

一个后进先出的数据结构

基于数组的实现

const stack = [];
stack.push(1);
stack.push(2);
const item1 = stack.pop();
const item2 = stack.pop();

栈的应用示例

1. 十进制转换二进制
   计算方式为数值循环除2取余，倒序输出即2进制，即符合后进先出的数据结构

function fn(num){
	if(!num){
		return 0
	}
	let stack = [];
	let number = num;
	let rem;
	let binaryString = '';
	while(number){
		rem = Math.floor(number % 2);
		stack.push(rem);
		number = Math.floor(number / 2);
	}
	while(stack.length!=0){
		binaryString += stack.pop().toString()
	}
	return binaryString
}

2. 有效的括号
   leetcode(20) 使用栈的数据结构，将左括号压入栈，碰到右括号判断时候和最后的左括号是否对应，对应出栈，不对应则非有效的括号，最终栈为空即有效的括号，符合后进先出的数据结构

function isValid(s){
	let dict = {')':'(','}':'{',']':'['};
	let leftList = ['(','{','['];
	let stack = [];
	let flag = true
	for(let i=0;i<s.length;i++){
		let item = s[i];
		if(dict[item]){
			if(stack[stack.length-1] === dict[item]){
				stack.pop();
			}else{
				flag = false
				break;
			}
		}else{
		 stack.push(item)
		}
	}
	if(stack.length){
		flag = false
	}
	return flag
}

3. 函数调用堆栈
   js函数嵌套调用，后调用的先执行结束
4. 表达式求值
   通过一个数字栈，一个运算符栈来解析表达式，从表达式取出运算符时，与运算符栈顶元素进行优先级对比。优先级低则取出运算符栈顶元素进行计算，优先级高则进栈等待计算
5. 浏览器的前进后退
   使用两个栈，新页面压入栈a中,后退页面从a栈顶取出压入栈b中，前进从b栈顶取出压入栈a

javascript中常用的栈操作

入栈：push,出栈pop,获取栈顶元素：stack[stack.length-1]

集合

集合

一个无序且唯一的数据结构，es6中的set即集合

集合的常用操作

1. 去重

const set = new Set([1,2,3,4,4,3]);
console.log([...set],Array.from(set))

2. 判断元素是否在集合中

const set = new Set([1,2,3,4])
set.has(1);

3. 求交集

const set1 = new Set([1,2,3])
const set2 = new Set([2,3,4])
[...set1].filter(item=>set2.has(item))

leetCode常见题目

两个数组的交集 349

var intersection = function(nums1, nums2) { 
	const l1 = new Set(nums1); 
	const l2 = new Set(nums2); 
	return [...l1].filter(item =>{ return l2.has(item) }) 
};

ES6中的set操作

1. add
   自动去重，对象会根据内存地址判断去重

let mySet = new Set();
mySet.add(1); //set{1}
mySet.add(5); //set{1,5}
mySet.add(5); //set{1,5}
mySet.add('string'); //set{1,5,string}
let o = { a: 1, b: 2 }; 
mySet.add(o); //set{1,5,string,{ a: 1, b: 2 }}
mySet.add(o); //set{1,5,string,{ a: 1, b: 2 }}
mySet.add({ a: 1, b: 2 }) //set{1,5,string,{ a: 1, b: 2 },{ a: 1, b: 2 }}

2. has
   对象会根据内存地址判断

mySet.has(1) //true
mySet.has('string') //true
mySet.has(o) //true
mySet.has({ a: 1, b: 2 }) //false

3. delete

mySet.size //5
mySet.delete(5) //set{1,string,{ a: 1, b: 2 },{ a: 1, b: 2 }}
mySet.size //4

4. 迭代
   set的keys和values获取的值是一样的

for(let item of mySet) console.log(item)
for(let item of mySet.keys()) console.log(item)
for(let item of mySet.values()) console.log(item)
for(let [key,value] of mySet.entries()) console.log(key,value)

5. set <=> array

const myArr = [...mySet])
myArr = Array.from(mySet);

const mySet2 = new Set([1,2,3,4])

6. 交集和差集

//交集见常用操作
//差集
[...mySet].filter(item=>!mySet2.has(item)) //set{string,{ a: 1, b: 2 },{ a: 1, b: 2 }}

时间复杂度与空间复杂度

时间复杂度

即渐进时间复杂度，用于表示代码执行时间随数据规模增长的变化趋势

如何表示一段代码时间复杂度

1. 只关注循环执行次数最多的一段代码
2. 总时间复杂度等于量级最大的那段代码的时间复杂度
3. 嵌套循环的代码时间复杂度等于嵌套代码的乘积

时间复杂度的常见实例

1. O(1)

let i = 1;
i+ = 1

2. O(n)

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

3. O(logn)

let i = 1;
while(i < n){
	console.log(i);
	i *= 2;
}

4. O(n²)

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

空间复杂度

即渐进空间复杂度，用于表示算法的存储空间与数据规模之间的增长关系

如何表示一段代码空间复杂度

1. 如果存在一维数组存储，数组的长度就是代码的空间复杂度即0(n),如果是二维数组(矩阵)，则O(n²)
2. 如果存在递归的话，那么递归的最深处即空间复杂度的最大值

空间复杂度的常见实例

1. O(1)

let i = 1;
i+ = 1

2. O(n)

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

3. O(n²)

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