Algorithms and data structures

Pseudocode and flowcharts

logic

Structured programming theory

You only need three statements to represent logic.

Sequential execution statement

Statement 1 statement 2Copy the code

Conditional execution statement

if ... then ... else ...
if ... else if ... else
Copy the code

Looping statements

while ... do ...
for i from 1 to n ...
Copy the code

Flowchart, pseudocode benefits

Exercise the brain

You have to draw it yourself, you can’t run it on a computer.

To compose

The idea is disorderly, then the diagram is disorderly. Pseudocode is bad, code is worse.

Use the flow chart to find the largest number of N numbers

The data structure

Data structure is the relationship and structure between data.

Data structure = data form + operation

Different forms of data expose different operations

How do I represent two pieces of data

If the order makes sense

[x,y] means the first one is x and the second one is y

[y,x] means the first one is y and the second one is x

For example, coordinates are data like this

Provide first and last operations

If the order is meaningless

(x,y) is the same as (y,x)

For example, blood pressure (120,80) and (80,120) are the same

There is no need to provide first and last operations

How do I represent N numbers

If the order makes sense

Array representation [A1, A2,… aN]

To provide the index operation get(I)

Provide add/indexOf/DELETE operations

If the order doesn’t make sense

The set represents {a1,a2… ,aN}

Provide add/delete/HAS operations

How do I represent N versus N data

Such as student id

Let’s say it’s a hash table

Hash = {1001 => ‘small square ‘,1002 =>’ small red ‘}

Note that unlike JS, the arguments to JS can only be strings, which can be numbers, strings, objects, and so on.

Interview questions:

Please tell me the number of times each character appears.

For example, Hi,I’m River, output v appears once, R appears once, R appears once…
str = `Hi,I'm River` hash = {} for i from 0 to str.length-1 key = str.get(i) value = hash.get(key,0) + 1 Hash. Set (key,value) for key,value from hash print '${key} ${value} times'Copy the code

The role of data structures

Keep some structures in mind in advance

These are common structures that help you to clear your mind quickly and are often asked in interviews

Practice abstraction

A single data structure can solve many of these problems, and if you choose the wrong data structure, you can’t think of anything

Sorting algorithm

Selection sort

selection sort

For the minimum

Find the smallest of the two numbers

code

let minOf2 = (numbers) => {
	if(numbers[0] < numbers[1]){
		return numbers[0]
	}else{
		return numbers[1]
	}
}
Copy the code

Optimize the code

let minOf2 = numbers =>
	numbers[0] < numbers[1]
		? numbers[0] : numbers[1]
Copy the code

Reoptimize code

let minOf2 = ([a,b]) => a < b ? a : b
Copy the code

This writing is called destructor assignment

call

MinOf2 ([1, 2]) / / small white minOf2 call method. The call (null, [1, 2]) master / / call the methodCopy the code

Existing API

JS built in`Math.min`

Math. Min (1, 2) / / 1 Math. Min. The call (null, 1, 2) Math. Min. Apply (null, [1, 2])Copy the code

about`Math`

Math looks like a constructor like Object, but actually Math is just an ordinary Object.

Capitalizing is the only special case of the constructor.

Find the smallest of the three numbers

code

let minOf3 = ([a,b,c]) => {
	return minOf2([minOf2([a,b]),c])
}
Copy the code

let minOf3 = ([a,b,c]) => {
	return minOf2([a,minOf2([b,c])])
}
Copy the code

Find the smallest of the four numbers

code

let minOf4 = ([a,b,c,d]) => {
	return minOf2([a,minOf3([b,c,d])])
}
Copy the code

MinOf2 can be used to minimize arrays of any length

Minimizes an arbitrary length array

code

Let min = (numbers) => {return min([numbers[0],min(numbers. Slice (1))])Copy the code

let min = (numbers) => { if(numbers.length > 2){ return min( [numbers[0],min(numbers.slice(1))] ) }else{ return Math.min.apply(null,numbers)}} // This is recursionCopy the code

Do it recursively

recursive

The characteristics of

The function keeps calling itself, with slightly different arguments each time

When a simple condition is met, a simple call is implemented

And then we get the answer

understand

You can use substitution to quickly understand recursion

Call stacks can be used to quickly understand recursion

Sort an array of length 2

code

Let sort2 = ((a, b)) = > {the if (a < b) {return [a, b] / / the [a, b] and the [a, b] are two different array} else {return [b, a]}}Copy the code

Optimize the code

let sort2 = ([a,b]) =>
	a < b ? [a,b] : [a,b]
Copy the code

Sort an array of length 3

code

Let sort3 = ((a, b, c)) = > {return [min ((a, b, c)), sort2 ([?])]} / / to the minimum to delete from the arrayCopy the code

Improve your code

let sort3 = (numbers) => { let index = minIndex(numbers) let min = numbers[index] numbers.splice(index,1) Return [min]. Concat (sort2(numbers))}Copy the code

The realization of the minIndex

Let minIndex = (numbers) => numbers. IndexOf (min(numbers)) // Let minIndex = (numbers) => numbersCopy the code

Sort an array of length 4

code

let sort4 = (numbers) => {
	let index = minIndex(numbers)
	let min = numbers[index]
	numbers.splice(index,1)
	return [min].concat(sort3(numbers))
}
Copy the code

Sort an array of length N

code

let sort = (numbers) => {
	if(numbers.length > 2){
		let index = minIndex(numbers)
		let min = numbers[index]
		numbers.splice(index,1)
		return [min].concat(sort(numbers))
	}else{
		return numbers[0] < numbers[1] ? numbers : numbers.reverse()
	}
}
Copy the code

Implement with a loop

minIndex

There are always two ways to write it: recursion and loop.

Rewrite minIndex

Current minIndex:

let minIndex = (numbers) => {
	numbers.indexOf(min(numbers))
}
let min = (numbers) => {
	return min(
		[numbers[0],min(numbers.slice(1))]
	)
}
Copy the code

Rewrite minIndex:

let minIndex = (numbers) => {
	let index = 0
	for(let i = 1; i < numbers.length; i++){
		if(numbers[i] < numbers[index]){
			index = i
		}
	}
	return index
}
Copy the code

Rewrite the sort

The current sort:

let sort = (numbers) => {
	if(numbers.length > 2){
		let index = minIndex(numbers)
		let min = numbers[index]
		numbers.splice(index,1)
		return [min].concat(sort(numbers))
	}else{
		return numbers[0] < numbers[1] ? numbers : numbers.reverse()
	}
}
Copy the code

Rewrite the sort:

let sort = (numbers) => { for(let i = 0; i < ??? ; I ++){let index = minIndex(numbers, index, I)} // Let index = minIndex(numbers, index, I)}Copy the code

Realize the swap

Let swap = (array, I,j) => {let temp = array[I] array[I] = array[j] array[j] = temp} swap(numbers,1,2)Copy the code

Implement swap incorrectly:

let swap = (a,b) => {
	let temp = a
	a = b
	b = temp
}
swap(numbers[1],numbers[2])
Copy the code

Numbers [1] and numbers[2] remain the same. This is because a and B are simple types that copy values when passing arguments. Numbers is the object, pass the copy address.

then`?????`What is it?

If I =2, I =2, I =2, I =2, I =2, I =2, I =2 Supplement for Numbers. Length – 1

There is a problem with the minIndex search scope

Let index = minIndex(numbers) let index = minIndex(numbers) let index = minIndex(numbers)

let index = minIndex(numbers.slice(i)) + i

Plus I, because if you don’t add it, index always starts at 0, splice subtracts I, and you need to add I, so that index corresponds to the correct minIndex

The final code

let sort = (numbers) => { for(let i = 0; i < numbers.length - 1; i++){ console.log(`----`) console.log(`i: ${i}`) let index = minIndex(numbers.slice(i)) + i console.log(`index: ${index}`) console.log(`min: ${numbers[index]}`) if(index ! == i){ swap(numbers, index, i) console.log(`swap ${index}: ${i}`) console.log(numbers) } } return numbers }Copy the code

Add function

let swap = (array, i ,j) => { let temp = array[i] array[i] = array[j] array[j] = temp } let minIndex = (numbers) => { let index = 0 for(let  i = 1; i < numbers.length; i++){ if(numbers[i] < numbers[index]){ index = i } } return index }Copy the code

Quick sort

quick sort

Recursive thinking

The small ones go to the front and the big ones go to the back

Just repeat the phrase, and you can sort it

Fast row source

let quickSort = arr => { if(arr.length <= 1){return arr; } let pivotIndex = Math.floor(arr.length / 2); Pivot pivot = pivot. Splice (pivotIndex,1)[0]; let left = []; let right = []; for(let i = 0; i < arr.length; i++){ if(arr[i] < pivot){ left.push(arr[i]) }else{ right.push(arr[i]) } } return quickSort(left).concat([pivot],quickSort(right)) }Copy the code

Merge sort

merge sort

Recursive thinking

The left half is sorted and the right half is sorted

Then merge the left and right sides

Merge sort source code

let mergeSort = arr => {
	let k = arr.length
	if(k === 1){return arr}
	let left = arr.slice(0,Math.floor(k/2))
	let right = arr.slice(Math.floor(k/2))
	return merge(mergeSort(left),mergeSort(right))
}
let merge = (a,b) => {
	if(a.length === 0) return b
	if(b.length === 0) return a
	return a[0] > b[0]
	? [b[0]].concat(merge(a,b.slice(1)))
	: [a[0]].concat(merge(a.slice(1),b))
}
Copy the code

Count sorting

counting sort

Recursive thinking

Use a hash table for the record

If you find the number N, write it as N: 1. If you find it again, add 1

Finally, print all the keys in the hash table. Suppose N: m, then N needs to be printed m times

While recording the array, a Max is also recorded, which will be printed out from smallest to largest after traversing.

Counting sort source code

let countSort = arr => { let hashTable ={}, max = 0, result = [] for(let i = 0; i < arr.length; I++){// iterate over the group if(! (arr[i] in hashTable)){ hashTable[arr[i]] = 1 }else{ hashTable[arr[i]] += 1 } if(arr[i] > max){max = arr[i]} } for(let j = 0; j <= max; If (j in hashTable){for(let I = 0; i < hashTable[j]; i++){ result.push(j) } } } return result }Copy the code

Counting sort features

Different data structures

Additional Hashtables were used

Only iterate over groups of numbers once (but also over sequential hashtables)

This is “Space for time.”

Time complexity comparison

Selection sort O(n^2)

Quick sort O(n log2 n)

Merge sort O(n log2 n)

Count sort O(n + Max), least

Other sort

Bubble sort

Insertion sort

Click on the INS

Hill sorting

Select the Shell Sort

Radix sort

Click on the RAD

7.3 Data Structure

Queue & stack

Queue Queue

FIFO array

The title

Please realize a restaurant calling number web page. Click the “Call number” button to generate a number. Click the “call number” button to display “Please have dinner on X date”.

code

Queue. A push for the team

Queue. Shift for the team

Stack Stack

LIFO array

For example,

The JS function call stack is a stack

Suppose F1 calls F2, which in turn calls F3

So when F3 ends it should go back to F2, and when F2 ends it should go back to F1

code

function f1(){let a = 1; return a + f2()}
function f2(){let b = 2; return b + f3()}
function f3(){let c = 3; return c}
f1()
Copy the code

List Linked List

queue-demo-1

One chain at a time

The actual use

Let array = [1,2,3] array.__proto__ === array.prototype array.proto__ === object.prototypeCopy the code

From this perspective, objects are linked lists

code

list = create(value)
node = get(index)
append(node,value)
remove(node)
travel(list,fn)
Copy the code

Deformation of linked lists

Two-way linked list

Each node has a previous pointing to the previous node

Circular linked list

The next of the last node points to the head node

Key-value pairs for hash table

scenario

Suppose there are 10,000 pairs of key-values in the hash table, such as name: ‘River’, age: 18, P1: ‘property’…

How to read hash[‘ XXX ‘] fastest

The solution

No optimization, hash[‘ XXX ‘] traverses all keys, O(n)

Sort key, using binary search, O(log2 n)

Index the string with the corresponding ASCII number, O(1)

Divide the index and get the remainder, O(1).

Tree Tree

The actual use

China’s provinces and cities can be seen as a tree

The corporate hierarchy can be viewed as a tree

A node in a web page can be viewed as a tree

code

let tree = createTree(value)
let node = createNode(value)
addChild(tree,node)
removeChild(node1,node2)
travel(tree)
Copy the code

Pseudocode and flowcharts

logic

Structured programming theory

Sequential execution statement

Conditional execution statement

Looping statements

Flowchart, pseudocode benefits

Exercise the brain

To compose

The data structure

How do I represent two pieces of data

If the order makes sense

If the order is meaningless

How do I represent N numbers

If the order makes sense

If the order doesn’t make sense

How do I represent N versus N data

Such as student id

The role of data structures

Keep some structures in mind in advance

Practice abstraction

Sorting algorithm

Selection sort

For the minimum

Find the smallest of the two numbers

code

Optimize the code

Reoptimize code

call

Existing API

JS built inMath.min

aboutMath

Find the smallest of the three numbers

code

Find the smallest of the four numbers

code

Minimizes an arbitrary length array

code

Do it recursively

recursive

The characteristics of

understand

Sort an array of length 2

code

Optimize the code

Sort an array of length 3

code

Improve your code

The realization of the minIndex

Sort an array of length 4

code

Sort an array of length N

code

Implement with a loop

minIndex

Rewrite minIndex

Rewrite the sort

then?????What is it?

There is a problem with the minIndex search scope

Quick sort

Recursive thinking

Fast row source

Merge sort

Recursive thinking

Merge sort source code

Count sorting

Recursive thinking

Counting sort source code

Counting sort features

Different data structures

Time complexity comparison

Other sort

Bubble sort

Insertion sort

Hill sorting

Radix sort

7.3 Data Structure

Queue & stack

Queue Queue

JS built in`Math.min`

about`Math`

then`?????`What is it?