【重拾算法】01-STL

2023-04-22 16:27:41 浏览数 (2)

为什么会突然想起要重拾算法呢？

上次认真的学习、复习算法已经是3年以前了，那时候是为了校招，在这之后算法似乎变的不太重要。我只是矜矜业业地做好前端开发该做的工作，但在业务开发越来越熟练的时候，我发现自己的视野也会变的越来越窄。

做程序开发，广度和深度是同样重要的，也许现在的工作中不会直接用上，但是算法、设计模式等等这些底层的知识时候熟练掌握，是我们能不能走得更远的前提，我觉得是时候，再重拾起已经快遗忘的算法，为自己的下一个三年，储备更多的基础知识。

作为前端开发，本系列的算法代码实现，将全部用TypeScript实现，同时也会贴一些力扣的题目方便上手实践。

STL简介

Standard Template Library，即“标准模板库”，是一套C 编译器默认支持的标准组件。

这是我入门算法和数据结构最开始学的东西，也是算法比赛中最常用的库，不过这次复习，我们主要是学习常用的数据结构，不会认真介绍STL的用法。同时也探究一个网上经常被问到的问题：JavaScript中有没有类似STL这样的库？

容器

定义：与数据类型无关的数据结构

容器的类型

顺序容器

  • vector：向量
  • list：双端列表
  • stack：栈
  • queue：队列

关联容器

map：映射

set：有序集

顺序容器

vector、list、queue看起来很容易混淆，其在C 中的区别，主要是在内存中的存储方式和支持的操作不同。

  1. vector和C 数组的区别在与，vector不需要程序员自己去分配内存空间。
  2. vector和queue是连续存储，list是非连续存储（双链表）。
  3. queue支持在队头队尾插入元素，vector只支持在队尾插入元素。
  4. list支持高效的插入删除，但是随机访问的效率低下。
  5. 堆(heap 优先队列)和栈(stack)的区别是，先进先出(FIFO)和先进后出(FILO)。

这些顺序容器，在JavaScript中是Array这个内置对象（js是基于对象的语言）。

其支持的方法看这个文档

https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Array

下面来简单总结一下：

JavaScript数组对象

forEach：遍历
代码语言：javascript复制
array.forEach(function(item, index, array) {
  console.log(item, index)
})
push：添加元素到数组的末尾
代码语言：javascript复制
let newLength = array.push('Orange')
pop：删除数组末尾的元素
代码语言：javascript复制
let last = array.pop()
shift：删除数组头部元素
代码语言：javascript复制
let first = array.shift()
unshift：添加元素到数组的头部
代码语言：javascript复制
let newLength = array.unshift('Strawberry')
indexOf/lastIndexOf：找出某个元素在数组中的索引
代码语言：javascript复制
let pos = fruits.indexOf('Banana')
//lastIndexOf ：最后一个的索引
let pos = fruits.lastIndexOf('Banana')
splice：通过索引删除某个元素
代码语言：javascript复制
let removedItem = array.splice(pos, 1)
//从一个索引位置删除多个元素
let removedItem = array.splice(pos, n)
//复制一个数组
let shallowCopy = fruits.slice() //begin和end的默认值是0和结尾
concat：合并数组
代码语言：javascript复制
const array3 = array1.concat(array2);
find/findIndex：查找符合条件的元素
代码语言：javascript复制
const found = array1.find(element => element > 10);
//findIndex返回索引
const isLargeNumberIndex = array1.findIndex(element => element > 13);
flat：拍扁数组
代码语言：javascript复制
const arr1 = [0, 1, 2, [3, 4]];

console.log(arr1.flat());
// expected output: [0, 1, 2, 3, 4]

const arr2 = [0, 1, 2, [[[3, 4]]]];

console.log(arr2.flat(2));
// expected output: [0, 1, 2, [3, 4]]
map：映射/flatMap：映射并拍平数组
代码语言：javascript复制
let arr1 = ["it's Sunny in", "", "California"];

arr1.map(x => x.split(" "));
// [["it's","Sunny","in"],[""],["California"]]

arr1.flatMap(x => x.split(" "));
// ["it's","Sunny","in", "", "California"]
//相当于map和flat(1)一起用，但效率高一些
arr1.map(x => x.split(" ")).flat(1);
// ["it's","Sunny","in", "", "California"]
includes：是否包含某个值
代码语言：javascript复制
array.includes('cat')
join：连接成字符串
代码语言：javascript复制
const elements = ['Fire', 'Air', 'Water'];

console.log(elements.join('-'));
// expected output: "Fire-Air-Water"
reduce： 递推对元素执行函数，并返回值/reduceRight：从右开始执行
代码语言：javascript复制
const array1 = [1, 2, 3, 4];
const reducer = (previousValue, currentValue) => previousValue   currentValue;

// 1   2   3   4
console.log(array1.reduce(reducer));
// expected output: 10

// 5   1   2   3   4
console.log(array1.reduce(reducer, 5));
// expected output: 15
reverse：返回倒序数组，原数组也会改变
代码语言：javascript复制
const reversed = array1.reverse();
some：判断是否存在符合条件的元素
代码语言：javascript复制
array.some(element => element % 2 === 0)

关联容器

js中，Map和Set是ES6标准新增的数据类型，参考廖雪峰老师的教程

https://www.liaoxuefeng.com/wiki/1022910821149312/1023024181109440

JavaScript中的Map

代码语言：javascript复制
var m = new Map([['Michael', 95], ['Bob', 75], ['Tracy', 85]]);
m.get('Michael'); // 95
代码语言：javascript复制
var m = new Map(); // 空Map
m.set('Adam', 67); // 添加新的key-value
m.set('Bob', 59);
m.has('Adam'); // 是否存在key 'Adam': true
m.get('Adam'); // 67
m.delete('Adam'); // 删除key 'Adam'
m.get('Adam'); // undefined

JavaScript中的Set

代码语言：javascript复制
var s1 = new Set(); // 空Set
var s2 = new Set([1, 2, 3]); // 含1, 2, 3
s.add(4);
s; // Set {1, 2, 3, 4}
s.delete(3);
s; // Set {1, 2, 4}
s.has(1); //true
s.clear(); //清空set

相关题目

题目：《有效的括号》：栈的使用 问题：https://leetcode-cn.com/problems/valid-parentheses/ 题解：https://leetcode-cn.com/problems/valid-parentheses/solution/typescript-you-xiao-de-gua-hao-zhan-de-y-lnv8/

题目：《接雨水》：栈的使用 问题：https://leetcode-cn.com/problems/trapping-rain-water/

题目：《任务调度器》：队列 问题：https://leetcode-cn.com/problems/task-scheduler/

题目：《接雨水ii》：堆 问题：https://leetcode-cn.com/problems/trapping-rain-water-ii/

容器 stl 队列 数组 算法

0 人点赞