Why do you suddenly think of the algorithm to retrieve?

The last time I seriously studied and reviewed the algorithm was three years ago. At that time, it was for school recruitment. After that, the algorithm seems to become less important. I just do a good job in front-end development, but when I become more and more skilled in business development, I find my vision will become narrower and narrower.

The breadth and depth of program development are equally important. Maybe it will not be used directly in our current work, but mastering the underlying knowledge such as algorithms and design patterns is the premise for us to go further. I think it's time to pick up the forgotten algorithms and reserve more basic knowledge for our next three years.

As a front-end development, the algorithm code implementation of this series will be implemented by TypeScript. At the same time, some problems will be posted to facilitate hands-on practice.

Introduction to STL

Standard Template Library, or "Standard Template Library", is a set of standard components supported by C + + compiler by default.

This is the first thing I learned about algorithms and data structures. It is also the most commonly used library in algorithm competitions. However, this review is mainly to learn common data structures and will not seriously introduce the usage of STL. At the same time, it also explores a question often asked on the Internet: is there a library like STL in JavaScript?

container

Definition: data structure independent of data type

Type of container

Sequential container

• Vector: vector
• List: double ended list
• Stack: stack
• Queue: queue

Associated container

map: mapping

Set: ordered set

Sequential container

vector, list and queue are easy to be confused. The main differences in C + + are the storage mode in memory and the supported operations.

1. The difference between vector and C + + array is that vector does not require programmers to allocate memory space themselves.
2. vector and queue are continuous storage, and list is discontinuous storage (double linked list).
3. Queue supports inserting elements at the head and end of the queue, while vector only supports inserting elements at the end of the queue.
4. list supports efficient insertion and deletion, but random access is inefficient.
5. The difference between heap priority queue and stack is first in first out (FIFO) and first in last out (FILO).

These sequential containers are the built-in object Array in JavaScript (js is an object-based language).

The supported methods are shown in this document

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

Here is a brief summary:

JavaScript array object

forEach: traversal

array.forEach(function(item, index, array) {
  console.log(item, index)
})

push: adds an element to the end of the array

let newLength = array.push('Orange')

pop: deletes the element at the end of the array

let last = array.pop()

shift: delete array header elements

let first = array.shift()

unshift: adds an element to the header of the array

let newLength = array.unshift('Strawberry')

indexOf/lastIndexOf: find the index of an element in the array

let pos = fruits.indexOf('Banana')
//lastIndexOf: index of the last
let pos = fruits.lastIndexOf('Banana')

splice: deletes an element through the index

let removedItem = array.splice(pos, 1)
//Delete multiple elements from an index location
let removedItem = array.splice(pos, n)
//Copy an array
let shallowCopy = fruits.slice() //The default values for begin and end are 0 and end

concat: merge arrays

const array3 = array1.concat(array2);

find/findIndex: find qualified elements

const found = array1.find(element => element > 10);
//findIndex returns the index
const isLargeNumberIndex = array1.findIndex(element => element > 13);

Flat: flat array

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: map / flatMap: map and flatten the array

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"]
//It is equivalent to using map and flat(1) together, but it is more efficient
arr1.map(x => x.split(" ")).flat(1);
// ["it's","Sunny","in", "", "California"]

includes: whether to include a value

array.includes('cat')

join: concatenate into a string

const elements = ['Fire', 'Air', 'Water'];

console.log(elements.join('-'));
// expected output: "Fire-Air-Water"

reduce: recursively execute the function on the element and return the value / reducereight: execute from the right

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: returns the inverted array, and the original array will also be changed

const reversed = array1.reverse();

some: judge whether there are qualified elements

array.some(element => element % 2 === 0)

Associated container

js, Map and Set are new data types in ES6 standard. Please refer to teacher Liao Xuefeng's tutorial

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

Map in JavaScript

var m = new Map([['Michael', 95], ['Bob', 75], ['Tracy', 85]]);
m.get('Michael'); // 95

var m = new Map(); // Empty Map
m.set('Adam', 67); // Add new key value
m.set('Bob', 59);
m.has('Adam'); // Whether key 'Adam' exists: true
m.get('Adam'); // 67
m.delete('Adam'); // Delete key 'Adam'
m.get('Adam'); // undefined

Set in JavaScript

var s1 = new Set(); // Empty Set
var s2 = new Set([1, 2, 3]); // Including 1, 2 and 3
s.add(4);
s; // Set {1, 2, 3, 4}
s.delete(3);
s; // Set {1, 2, 4}
s.has(1); //true
s.clear(); //Clear set

Related topics

Title: "valid parentheses": use of stack

Question: https://leetcode-cn.com/problems/valid-parentheses/

Solution: https://leetcode-cn.com/problems/valid-parentheses/solution/typescript-you-xiao-de-gua-hao-zhan-de-y-lnv8/

Title: use of rainwater collection stack

Question: https://leetcode-cn.com/problems/trapping-rain-water/

Title: task scheduler: queue

Question: https://leetcode-cn.com/problems/task-scheduler/

Title: rainwater ii pile

Question: https://leetcode-cn.com/problems/trapping-rain-water-ii/