Fibonacci

function Fibonacci(n) {
  if (n==1 || n == 2) {return 1
  }
  return Fibonacci(n-1)+Fibonacci(n-2)}console.log(Fibonacci(30))
Copy the code

// Non-recursive methods
function Fibonacci(num){
    var n1 = 1, n2 = 1 , n= 1
    for(var i = 3; i < num; i++){
      n = n1 + n2
      n1 = n2
      n2 = n
 }
 return n
}
Copy the code

0 string

var str = 'hello july'
console.log(str.length)
console.log(str[2])//l
console.log(str[0])//h
console.log(str.charAt(0)) //h
console.log(str.charCodeAt(0))/ / 104 Unicode
console.log(String.fromCharCode(74))//J

console.log(str.concat("hi"))//hello julyhi
console.log(str + "hi~")//hello julyhi~

console.log(str.indexOf('h'))//0 indicates yes, at index=0
console.log(str.indexOf('k'))/ / - 1 said no
console.log(str.indexOf('l'.3))// start index= 3
console.log(str.lastIndexOf('h'))

console.log(str.slice(0.2))/ / he, [0, 2) location
console.log(str.slice(4))//o july
console.log(str.slice(-1))//y
console.log(str.slice(1, -1))//ello jul
console.log(str.substring(0.2))//he [0,2) is similar to slice, but cannot be negative, adjusting the [a, b) position

a = 'asd,ggh,dsf,sas'
b = a.split(', ')/ / split
console.log(b)//[ 'asd', 'ggh', 'dsf', 'sas' ]
c = a.split(' ')// Each character is split
console.log(c)//['a', 's', 'd', ',', 'g', 'g', 'h', ',', 'd', 's', 'f', ',', 's', 'a', 's']
console.log(Array.isArray(b))//true
console.log(b[1])//ggh
console.log(str.toUpperCase())//HELLO JULY
console.log(str.toLowerCase())//hello july
Copy the code

1 array

 var n = [1.23.4.45.345.2.1]
 n.push(11)
 n.push(14.24)
 n.unshift(-2)// Add in the first place
 n.pop()
 n.shift()// Delete from first place
 console.log(n.splice(1.3))
 var n= b.concat(a,c)
 let ncopy = Array.of(... n)let one = Array(6).fill(1)
 console.log(num.reverse())
 console.log(num.sort())
 console.log(n.indexOf(2))
 console.log(n.includes(999))
 console.log(n.toString())
 var b= n.join(The '-')
Copy the code

Gets the number and number of repeats in the array

If the target argument is a string, it can be converted to an array using the split() method

var str="qwertyuiopasdfghjklzxcvbnmqazwsxaswazaaa";
var arr=str.split("");  // Convert to an array
Copy the code


function moreValue() {
  if(! arr)return false;
  if (arr.length === 1) return 1;
  let result = {}
  let maxNum = 0;// The number of occurrences of the element
  let maxValue = null;// The maximum corresponding maxValue value
  // Loop over the maxValue with the largest value
  for(let i = 0; i < arr.length; i++) {let val = arr[i]
    // Loop through the array, passing the element as the key and the number of occurrences of the element as the value into the result object
    // The operation of inserting a loop array into an object is evaluated by a ternary expression and merged into a for loop
    result[val] === undefined ? result[val] = 1 : result[val]++;
    if(result[val] > maxNum) {
      maxNum = result[val];
      maxValue = val
    }
  }
  return maxValue +', '+ maxNum;
}

Copy the code

Array to heavy

function unique(arr) {
  var a = []
  a[0] = arr[0]

  for (let i = 0; i < arr.length; i++) {
    for (let k = 0; k < a.length; k++) {
      if (a[k] == arr[i]) {
        break
      }
      if (k == a.length-1) {
        a.push(arr[i])
      }
    }
  }
  return a
}
Copy the code

An array of pat down

function fn(arr) {
  var arr1 = []
  arr.forEach(val= >{
    if ( val instanceof Array) {
      arr1 = arr1.concat(fn(val))
    } else {
      arr1.push(val)
    }
  })
  return arr1
}

Copy the code

Enter a two-dimensional array and an integer to determine whether the integer is in the two-dimensional array

Const arr = [1, 9, 3 Sherwin, 6,9,19]; function hasNumber(array,target){}

Solution 1: The violent method traverses all the elements in the number group to find whether there is any.

Time is O(N^2), space is O(1).

function Find(target, array) {
    const rowNum = array.length;
    if(! rowNum) {return false;
    }
    const colNum = array[0].length;
    for (let i = 0; i < rowNum; i++) {
        for (let j = 0; j < colNum; j++) {
            if (array[i][j] === target) return true; }}return false;
}

Copy the code

Solution 2: Observe the array pattern

Each row is sorted in ascending order from left to right, and each column is sorted in ascending order from top to bottom. Consider the following array:

1 2 3

4 5 6

7 8 9

Look for the presence of 5. The process is as follows:

The current element is smaller than the target element (3 < 5). According to the characteristics of the array, the maximum element in the current row is also smaller than the target element, so enter the next row. The current element is larger than the target element (6 > 5)

Time is O(M+N), space is O(1). Where M and N represent the number of rows and columns respectively.

function Find(target, array) {
    const rowNum = array.length;
    if(! rowNum) {return false;
    }
    const colNum = array[0].length;
    if(! colNum) {return false;
    }

    let row = 0,
        col = colNum - 1;
    while (row < rowNum && col >= 0) {
        if (array[row][col] === target) {
            return true;
        } else if (array[row][col] > target) {
            --col;
        } else{ ++row; }}return false;
}
Copy the code

The intersection and union of two arrays

Extend Array

// Array function extension
// Array iterating function
Array.prototype.each = function(fn){
 fn = fn || Function.K;
 var a = [];
 var args = Array.prototype.slice.call(arguments.1);
 for(var i = 0; i < this.length; i++){
 var res = fn.apply(this[this[i],i].concat(args));
 if(res ! =null) a.push(res);
 }
 return a;
};
// Whether the array contains the specified element
Array.prototype.contains = function(suArr){
 for(var i = 0; i < this.length; i ++){
 	if(this[i] == suArr){
	 	return true; }}return false;
}
// An array of non-repeating elements
Array.prototype.uniquelize = function(){
 var ra = new Array(a);for(var i = 0; i < this.length; i ++){
	 if(! ra.contains(this[i])){
	 	ra.push(this[i]); }}return ra;
};
// The intersection of two arrays
Array.intersect = function(a, b){
 return a.uniquelize().each(function(o){return b.contains(o) ? o : null});
};
// The difference between two arrays
Array.minus = function(a, b){
 return a.uniquelize().each(function(o){return b.contains(o) ? null : o});
};
// A complement of two arrays
Array.complement = function(a, b){
 return Array.minus(Array.union(a, b),Array.intersect(a, b));
};
// Combine two arrays
Array.union = function(a, b){
 return a.concat(b).uniquelize();
};
Copy the code

2 filter Filters out certain elements of an Array and returns the remaining elements.

Like map(), filter() of Array receives a function. Unlike map(), filter() applies the passed function to each element in turn, and then decides whether to keep or discard the element depending on whether the value returned is true or false.

The callback function

Filter () receives a callback function that can take multiple arguments. Usually we just use the first parameter, which represents an element of the Array. The callback can also take two additional arguments that represent the position of the element and the array itself:

var a = [1.2.3.4.5]
var b = [2.4.6.8.10]
/ / intersection
var intersect = a.filter(function(v){ return b.indexOf(v) > -1 })
/ / difference set
var minus = a.filter(function(v){ return b.indexOf(v) == -1 })
/ / complement
var complement = a.filter(function(v){ return! (b.indexOf(v) > -1) })
  .concat(b.filter(function(v){ return! (a.indexOf(v) > -1)}))
/ / and set
var unionSet = a.concat(b.filter(function(v){ return! (a.indexOf(v) > -1)}));

console.log("Intersection of A and B:", intersect);
console.log("Difference set of A and B:", minus);
console.log("Complement of A and B:", complement);
console.log("Union of A and B:", unionSet);

Copy the code

Merge two arrays and sort

Merge two arrays and sort

var a =[2.5.8.9];
var b=[7.9.7.9]
var c = a.concat(b).sort(function(a,b){return a-b }/ / ascending
// The value returned in the callback function is: parameter 1- parameter 2; Ascending order.

Copy the code

Two ordered arrays, merge after reordering JS implementation

Use the condition that the two arrays are sorted to set two Pointers, one to each array

When one is less than the other, the smaller number is pushed into the new array, moving the pointer back

Equal to each other pushes all of the Pointers back into the new array

Until one pointer reaches the end of the array, add another array directly to the new array

let sortArr = (arr1, arr2) = > {
  let [i,j] = [0.0];
  let newArr = [];
 
  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] < arr2[j]) {
      newArr.push(arr1[i]);
      i++;
    } else if (arr1[i] > arr2[j]) {
      newArr.push(arr2[j]);
      j++;
    } else if(arr1[i] === arr2[j]) { newArr.push(arr1[i]); newArr.push(arr2[j]); i++, j++; }}// Take out the part of the pointer that is not moved to the end of the new array
  if (i < arr1.length) {
    return newArr.concat(arr1.splice(i));
  } else if (j < arr2.length) {
    return newArr.concat(arr2.splice(j));
  } else {
    returnnewArr; }};let arr1 = [1.2.3.4.6.9.11];
let arr2 = [2.4.6.8.12.19.33.45];
console.log(sortArr(arr1, arr2));
Copy the code

Array inversion

// Invert the array
function reverse(arr) {
  for (let i = 0; i < arr.length/2; i++) {
    [arr[i],arr[arr.length-1-i]]=[arr[arr.length-1-i],arr[i]]
  }
  return arr
}
Copy the code

The iterator functions filter() forEach()some() every() map()

filter()

// Runs the callback function on each item in the array, which returns a new array of items that result in true
// The new array consists of elements from the old array whose return is true;Ex. :var arr = [111.222.333.444.555];
    var newArr = arr.filter(function (element, index, array) {
        // If it is odd, it is an array. (Identify elements in array)
        if(element%2= = =0) {return true;
        }else{
            return false; }})console.log(newArr); / / [222, 444]
Copy the code

forEach()

// Same as for loop; No return value;Ex. :var arr = [111.222.333.444.555];
    var sum = 0;
    var aaa = arr.forEach(function (element,index,array) {
        console.log(element); // Prints each element in the array
        console.log(index); // The index of the array element
        console.log(array); // Array itself [111, 222, 333, 444, 555]
        sum += element; // Sum the elements in the array;
    });
    console.log(sum); // The sum of the array elements
    console.log(aaa);/ / undefined; There is no return value so undefined is returned

Copy the code

Some with every

Some iterates through every element in the array until the function returns true and every iterates through every element in the array until the function returns false

var isEven = function(x){return (x%2= =0)}

var isEven =(x) = > (console.log( x%2= =0))
var numbers = [2.4.6.3]
numbers.some(isEven)
numbers.every(isEven)
Copy the code

map()


// Run the callback function on each item in the array to return a new array of the results of that function
// return whatever is in the new array; Return undefined; Reprocess an arrayEx. :var arr = [111.222.333.444.555];
    var newArr = arr.map(function (element, index, array) {
        if(index == 2) {return element; // this returns 333
        }
        return element*100; // Return the element values multiplied by 100
    })
    console.log(newArr); // [11100, 22200, 333, 44400, 55500]
Copy the code

Implement the sum function (closure) :

Sum (1)(2)() output 3; Sum (1)(2)(3)(4)()

It refers to changing a function that takes multiple arguments into a fixed form that takes one argument and returns one function, so that it is easy to call again. For example, add(1)(2)(3)(4)=10; , the add (1) (1, 2, 3) and (2) = 9;

function sum() {
  const _args = [...arguments];
  function fn() { _args.push(... arguments);return fn;
  }
  fn.toString = function() {
    return _args.reduce((sum, cur) = > sum + cur);
  }
  return fn;
}

Copy the code

Parsing URL parameters


function GetRequest(url) {
  if (typeof url == "undefined") {
    var urla = decodeURI(location.search)// Get the "?" in the url The string after the character
  } else {
    var urla  = "?" + url.split("?") [1]}var request = new Object(a)if (urla.indexOf("?") != -1) {var str = urla.substr(1)
    strs = str.split("&")
    for (let i = 0; i < strs.length; i++) {
      request[strs[i].split("=") [0]] = decodeURI(strs[i].split("=") [1])}}return request
}

var parms_2 = GetRequest('http://htmlJsTest/getrequest.html? Uid = admin&rid = 1 & fid = 2 & name = xiao Ming ');
console.log(parms_2); / / {" uid ":" admin ", "rid" : "1", "fid" : "2", "name" : "xiao Ming"}

Copy the code

The longest public prefix in a string array


function longestCommonPrefix(string) {
  if(! string.length){return ' '
  }
  if (string.length === 1) {
    return string[0]
  }
  string.sort()
  let first = string[0]
  let end = string[string.length -1]
  let result = ' '
  for (let i = 0; i < first.length; i++) {
    if (first[i] === end[i]) {
      result += first[i]
    } else {
      break}}return result
}

var a = ["abca"."abc"."abca"."abc"."abcc"]
console.log(longestCommonPrefix(a))

Copy the code

5 ways to find the maximum

var arr = [23.5.6.2.1]
// ES6
var a = Math.max(... arr)// ES5
var a = Math.max.apply(null,arr)

//sort
a= arr.sort((num1,num2) = >{
  return num1 - num2 >0
})
 arr[0]

//reduce
a = arr.reduce((num1,num2 ) = >{
  return num1>num2 ? num1:num2
})

// for
let max= arr[0]
for (let i = 0; i < arr.length -1; i++) {
  max = max > arr[i+1]? max:arr[i+1]}console.log(a)
Copy the code

2 stack (lifO)

es5


function Stack() {
  let items = []
  this.push = function (element) {
    items.push(element)
  }
  this.pop = function () {
    return items.pop()
  }
  this.peek =function () {
    return items[items.length-1]}this.isEmpty =function () {
    return items.length == 0
  }
  this.size = function () {
    return items.length
  }
  this.clear = function () {
    items = []
  }
  this.print = function () {
    console.log(items.toString())
  }
}
Copy the code

es6

class Stack {
  constructor() {
    this.item = []
  }
  push(element){
    this.item.push(element)
  }
  pop(){
    this.item.pop()
  }
  peek(){
    return this.item[this.item.length-1]}isEmpty(){
    return this.item.length==0
  }
  size(){
    return this.item.length
  }
}
Copy the code

let stack = new Stack()
console.log(stack.isEmpty())
stack.push(1)
stack.push(4)
stack.push(32)
console.log(stack.peek())
stack.push(99)
console.log(stack.size())
console.log(stack.isEmpty())
stack.pop()
stack.pop()
console.log(stack.size())
stack.print()
Copy the code

3 Queue (first in, first out)

es5

function Queue() {
  let items = []
  this.enqueue = function(element){
    items.push(element)
  }
  this.dequeue = function () {
    items.shift()
  }
  this.front = function () {
    return items[0]}this.isEmpty =function () {
    return items.length == 0
  }
  this.size = function () {
    return items.length
  }
  this.print = function () {
    console.log(items.toString())
      }
}
Copy the code

es6


let Queue = (function () {
  const items = new WeakMap(a)class Queue2 {
    constructor() {
      items.set(this[])},enqueue(element){
      let q = items.get(this)
      q.push(element)
    }
    dequeue(){
      let q = items.get(this)
      let r = q.shift()
      return r
    }
    size(){
      let q = items.get(this)
      return q.length
    }
    isEmpty(){
      let  q = items.get(this)
      return q.length == 0
    }
    front(){
      let q = items.get(this)
      return q[0]}print(){
      let q = items.get(this)
      console.log(items.toString())
    }
  }
  return Queue2
})();

Copy the code

let queue = new Queue()
console.log( queue.isEmpty())
queue.enqueue('ll')
queue.enqueue('ss')
queue.enqueue('qq')
queue.print()
console.log(queue.size())
console.log(queue.isEmpty())
queue.dequeue()
queue.dequeue()
queue.print()
Copy the code

Priority queue


function PriorityQueue() {
  let items = []
  function QueueElememt(element,priority) {
    this.elements = element
    this.priority = priority
  }

  this.enqueue = function (element,priorty) {
    let queueElememt = new QueueElememt(element,priorty)
    let added = false
    for (let i = 0; i < items.length; i++){
      if (queueElememt.priority < items[i].priority) {
        items.splice(i,0,queueElememt)
        added = true
        break}}if(! added){ items.push(queueElememt) } }this.print =function () {
    for (let i = 0; i < items.length; i++) {
      console.log(`${items[i].elements}-${items[i].priority}`)}}}let pq = new PriorityQueue()
pq.enqueue('jack'.3)
pq.enqueue('sam'.2)
pq.enqueue('lucy'.2)
pq.enqueue('tim'.1)
pq.print()
Copy the code

Circular queue – Drum pass flowers


function Queue() {
  let items = []
  this.enqueue = function(element){
    items.push(element)
  }
  this.dequeue = function () {
    items.shift()
  }
  this.size = function () {
    return items.length
  }
}

function f(nameList ,num) {
  let queue =new Queue()

  for (let i = 0; i < nameList.length; i++) {
    queue.enqueue(nameList[i])
  }
  let eliminated = ' '
  while (queue.size ()>1) {for (let i = 0; i <num; i++) {
      queue.enqueue(queue.dequeue())
    }
    eliminated = queue.dequeue()
    console.log(eliminated ,'quit')}return queue.dequeue()

}

let names = ['a'.'v'.'d'.'s'.'q'.'e'.'t'.'u']
let winner = f(names,7)
console.log(winner)
Copy the code

4 list


function LinkedList() {
  let Node =function (element) {
    this.element =element
    this.next = null
  }
  let length = 0
  let head = null

  this.append = function (element) {
    let node = new Node(element),
      current
    if (head === null){
      head = node
    }else {
      current=head
      while(current.next){
        current = current.next
      }
      current.next = node
    }
    length++
  }
  this.insert = function (position,element) {
    if (position >= 0 && position <= length) {
      let node = new Node(element),
      current = head,
      previous,
      index = 0
      if (position === 0) {
        node.next = current
        head = node
      } else {
        while(index++ <position){ previous = current; current = current.next } node.next = current previous.next = node } length++ return true } else { return false } } this.removeAt = function (position) { if (position >= 0 && position <length){ let current = head, previous, index = 0 if (position === 0) { head = current.next }else { while (index++ <position){ previous = current current = current.next } previous.next= current.next } length-- return current.element }else { return null } } this.indexOf = function (element) { let current = head, index = -1 while (current){ if (element = current.element) { return index } index++ current = current.next } return -1 }  this.remove = function (element) { let index = this.indexOf(element) return this.removeAt(index) } this.isEmpty = function () { return length === 0 } this.size =function () { return length } this.getHead = function () { return head } this.toString = function () { let current = head,str = '' while (current){ str +=current.element +(current.next ? 'n':'') current = current.next } return str } this.print = function () { console.log(Node.toString()) } } let list = new  LinkedList(); List.append (15) list.append(20) console.log(list.indexof (20)) console.log(list.insert(2,99)) console.log(list.isempty ())  console.log(list.removeAt(3)) console.log(list.toString())Copy the code

List inversion (using recursion)

Node.next === null; node.next! == null When a last node is encountered, return the last node, the previous node receives the last node, and sets the next of the last node as itself, return the last node, continue to consider special cases: undefined and NULL


function reverseList(head){
  / / closures
  if (head === undefined || head === null) return null
  var reverHead
  var origHead = head

  var re = function (head) {
    if (head.next === null) {
      reverHead = head
      return head
    } else {
      var node = reverse(head.next)
      node.next = head
      if (origHead === head) {
        head.next = null
        return reverHead
      } else {
        return head
      }
    }
  }
  return re(head)
}

Copy the code

Two-way linked list


function DoubleList() {
  let Node = function (element) {
    this.element = element
    this.prev = null
    this.next = null
  }
  let length = 0
  let head = null
  let tail = null
  this.insert = function (position, element) {
    if (position >= 0 && position <= length) {
      let node = new Node(element),
        current = head,
        previous,
        index = 0
      if (position === 0) {
        if(! head) { head = node tail = node }else {
          node.next = current
          current.prev = node
          head = node
        }
      } else if (position === length) {
        current = tail
        current.next = node
        node.prev = current
        tail = node
      } else {
        while(index++ < position) { previous = current current = current.next } node.next = current previous.next = node current.prev  = node node.prev = previous } length++return true
    } else {
      return false}}this.removeAt = function (position) {
    if (position >= 0 && position < length) {
      let current = head,
        previous,
        index = 0
      if (length === 1) {
        tail = null
      } else {
        head.prev = null}}else if (position === length - 1) {
      current = tail
      tail = current.prev
      tail.next = null
    } else {
      while (index++ < position) {
        previous = current
        current = current.next
      }
      previous.next = current.next
      current.next.prev = previous
    }
    length--
    return current.element
  }
}
Copy the code

5 Set Set ES6

const obj = new Set(a)/ / add
obj.add(1)
obj.add(2)
obj.add(['aa'.'bbb'])
obj.add(2)
obj.add(5)
console.log(obj)

// Check whether there is
console.log(obj.has(5))
obj.has(6)

/ / delete
obj.delete(5)
console.log( obj.delete(6))
console.log(obj)

/ / traverse
obj.forEach(n= > console.log(n))
/ / the total number of
console.log(obj.size)
// Clear all elements
console.log(obj.clear())
Copy the code

let set = new Set()
set.add(1)
set.add(3)
set.add(5)
set.add(7)
console.log(set)
console.log(set.values())
console.log(set.size)
console.log(set.has(1))
set.delete(1)

let setA = new Set()
setA.add(1)
setA.add(2)
setA.add(3)

let setB = new  Set()
setB.add(4)
setB.add(5)
setB.add(6)
/ / and set
let unionAb = new Set(a)for (let x of setA) unionAb.add(x)
for (let x of setB) unionAb.add(x)
console.log(unionAb)
/ / intersection
let intersection = function (setA,setB) {
  let intersectionSet = new Set(a)for (let x of setA) {
    if (setB.has(x)) {
      intersectionSet.add(x)
    }
  }
  return intersectionSet
}
let interAB = intersection(setA,setB)
/ / difference set
let diff = function (setA, setB) {
  let diffSet = new Set(a)for (let x of setA) {
    if(! setB.has(x)){ diffSet.add(x) } }return diffSet
}
let diffAb = diff(setA,setB)
Copy the code

5.5 the Map ES6

const obj2 = new Map(a)/ / add
obj2.set('one'.'abc')
console.log(obj2)//Map(1) { 'one' => 'abc' }
obj2.set('two'.221)
console.log(obj2)//Map(2) { 'two' => '221', 'abc' => 221 }

/ / value
console.log(obj2.get('one'))//abc
console.log(obj2.get('two'))/ / 221
console.log(obj2.get('three'))//undefined

/ / delete
console.log(obj2.delete('one'))//true

/ / the number of
console.log(obj2.size)/ / 1

// Clear all elements
console.log(obj2.clear())//undefined

console.log(map.has('lida'))
console.log(map.keys())
console.log(map.values())

Copy the code


var weekmap = new WeakMap(a)var ob1 = {name:'gad'}
var ob2 = {name: 'san'}
var ob3 = {name:'ll'}

weekmap.set(ob1,'[email protected]')
weekmap.set(ob2,'[email protected]')
weekmap.set(ob3,'[email protected]')

console.log(weekmap.has(ob1))
console.log(weekmap.get(ob3))
weekmap.delete(ob2)
Copy the code

6 Dictionary and hash table

The dictionary

function Dictionary() {
  var items = {}
  this.has = function (key) {
    return key in items
  }
  this.set = function (key,value) {
    items[key] = value
  }
  this.delete = function (key) {
    if (this.has(key)){
      delete items[key]
      return true
    }
    return false
  }
  this.get = function (key) {
    return this.has(key) ? items[key]:undefined
  }
  this.values = function () {
    var values = []
    for (let k in items) {
      if (this.has(k)) {
        values.push(items[k])
      } 
    }
    return values
  }
  this.keys = function () {
    return Object.keys(items)
  }
  this.getItems = function () {
    return items
  }
}
Copy the code

var dict = new Dictionary()
dict.set('tony'.'[email protected]')
dict.set('som'.'[email protected]')
dict.set('jack'.'[email protected]')
dict.set('lily'.'[email protected]')
console.log(dict.has('som'))
console.log(dict.keys())
console.log(dict.values())
console.log(dict.get('lily'))
dict.delete('som')
Copy the code

HashMap (HashTable HashTable)


function HashTable() {
  var table = []
  // Hash function, which is private
  var loseCode = function (key) {
    var hash = 0
    for (let i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i)
    }
    return hash%37
  }

  this.put = function (key,value) {
    var position = loseCode(key)
    console.log(position,The '-',key)
    table[position] =value
  }
  this.get = function (key) {
    return table[loseCode(key)]
  }
  this.remove = function (key) {
    table[loseCode(key)] = undefined}}var hash = new HashTable()
hash.put('lida'.'[email protected]')
hash.put('yould'.'[email protected]')
hash.put('miky'.'[email protected]')
console.log(hash.get('lida'))
console.log(hash.get('llll'))
hash.remove('yould')
Copy the code

// The community's preferred hash function
var djb2HashCode = function (key) {
  var hash = 5381
  for (let i = 0; i < key.length; i++) {
    hash = hash *33 + key.charCodeAt(i)
  }
  return hash % 1013
}
Copy the code

7 tree

BST


// Declare the structure
function BinarySeacheTree() {
  var Node = function (key) {
    this.key = key
    this.left = null
    this.right = null
  }
  var root = null
  this.inset = function (key) {
    var newNode = new Node(key)
    if (root === null) {
      root = newNode
    } else {
      insertNode(root, newNode)
    }
  }
  var insertNode = function (node,newNode) {
    if (newNode.key <node.key) {
      if (node.left === null) {
        node.left = newNode
      } else {
        insertNode(node.left,newNode)
      }
    } else {
      if (node.right === null) {
        node.right = newNode
      } else {
        insertNode(node.right,newNode)
      }
    }
  }
  // middle order traversal
  this.inOrderTraverse = function (callback) {
    var inOrderNode =function (node,callback) {
      if(node ! = =null){
        inOrderNode(node.left,callback)
        callback(node.key)
        inOrderNode(node.right,callback)
      }
    }
  }
  
  // find the smallest node
  this.min = function () {
    return minNode(root)
  }
  var minNode = function (node) {
    if (node){
      while(node && node.left ! = =null){
        node = node.left
      }
      return node.key
    }
    return null
  }
  // find the smallest node
  this.max = function () {
    return maxNode(root)
  }
  var maxNode = function (node) {
    if (node){
      while(node && node.right ! = =null){
        node = node.right
      }
      return node.key
    }
    return null
  }
  // Search for a specific value
  this.search = function (key) {
    return searchNode(root,key)
  }
  var searchNode = function (node,key) {
    if(node === null) {return false
    }
    if (key < node.key) {
      return searchNode(node.left,key)
    }else if (key > node.key) {
      return searchNode(node.right,key)
    } else {
      return true}}// Remove a node
  this.remove = function (key) {
    root = removeNode(root,key)
  }
  var removeNode = function (node,key) {
    if (node === null) {
      return null
    }
    if (key < node.key) {
      node.left = removeNode(node.left,key)
      return node
    } else {/ / key = node. The key
      // A leaf node
      if (node.left === null&& node.right === null) {
        node = null
        return node
      }
      // Case 2: a node with only one child node
      if (node.left === null) {
        node = node.right
        return node
      } else if(node.right === null){
        node = node.left
        return node
      }
      // Case 3: a node with two children
      var aux = findMinNode(node.right)
      node.key = aux.key
      node.right = removeNode(node.right,aux.key)
      return node

      var findMinNode = function (node) {
        while(node && node.left ! = =null){
          node = node.left
        }
        return node
      }
    }
  }
  // preorder traversal
  this.preOrderTraverse = function (callback) {
    var preOrderNode =function (node,callback) {
      if(node ! = =null){
        callback(node.key)
        preOrderNode(node.left,callback)
        preOrderNode(node.right,callback)
      }
    }
  }
  // after the sequence traversal
  this.postOrderTraverse = function (callback) {
    var postOrderNode =function (node,callback) {
      if(node ! = =null){
        postOrderNode(node.left,callback)
        postOrderNode(node.right,callback)
        callback(node.key)
      }
    }
  }

}

Copy the code


var tree = new BinarySeacheTree()
tree.inset(11)

 tree.inset(15)
  tree.inset(5)
tree.inset(1)
tree.inset(2)
tree.inset(13)
tree.inset(16)
tree.inset(15)
tree.inset(19)
tree.inset(10)

function printNode(value) {
  console.log(value)
}
tree.inOrderTraverse(printNode)
Copy the code

Sorting and search algorithms

Bubble sort O (n2)

function bubbleSort(array) {
  for (let i = 0; i < array.length; i++) {
    for (let j = 0; j < array.length -1; j++) {
      if (array[j] > array[j +1]) {
        [array[j],array[j+1]] = [array[j+1],array[j]]
      }
    }
  }
  return array
}

// Improved bubbling
function modifyBubbleSort(array) {
  var n=array.length
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n-1-i; j++) {
      if (array[j] > array[j+1]) {
        [array[j],array[j+1]] = [array[j+1],array[j]]
      }
    }
  }return array
}

var arr = [3.1.5.6.2]
console.log(bubbleSort(arr))

Copy the code

Selection sort O (n2)

function selectSort(array) {
  var indexMin,temp, n=array.length
  for (let i = 0; i < n-1; i++) {
    indexMin = i
    for (let j = i+1; j < n; j++) {
      if (array[indexMin] > array[j]) {
        indexMin = j
      }
    }
    temp = array[i]
    array[i]= array[indexMin]
    array[indexMin]=temp
  }
  return array
}
Copy the code

Insertion sort O(n2)

function insertSort(array) {
  var n =array.length,j,temp
  for (let i = 0; i < n; i++) {
    j = i
    temp = array[i]
    while (j > 0 && array[j -1]>temp){
      array[j]=array[j-1]
      j--
    }
    array[j] = temp
  }
  return array
}
Copy the code

Merge sort O nlogn


function mergeSort(arr) {
  const length = arr.length;
  if (length === 1) { // Stop condition of the recursive algorithm, i.e. check whether the array length is 1
    return arr;
  }
  const mid = Math.floor(length / 2);

  const left = arr.slice(0,  mid);
  const right = arr.slice(mid, length);

  return merge(mergeSort(left), mergeSort(right)); // Split the original array until there is only one element before merging
}

function merge(left, right) {
  const result = [];
  let il = 0;
  let ir = 0;

  // Left and right are sorted from smallest to largest
  while( il < left.length && ir < right.length) {
    if (left[il] < right[ir]) {
      result.push(left[il]);
      il++;
    } else{ result.push(right[ir]); ir++; }}// There can be no left and right items at the same time. Either left or right items have left items
  while (il < left.length) {
    result.push(left[il]);
    il++;
  }
  while(ir < right.length) {
    result.push(right[ir]);
    ir++;
  }
  return result;
}
console.log(mergeSort([2.9.1.8.3,]))
Copy the code

Quick sort O(nlogn) Worst case O(n2)

// select A random number from the array (A).
// 2. Compare other numbers with this number, and place those smaller numbers to its left and those larger numbers to its right.
// 3, after A cycle, the left side of A is less than A, the right side is greater than A;
// 4, then the left and right numbers recurse to the above process.

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr
  }
  let pivotIndex = Math.floor(arr.length / 2)
  let pivot = arr.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])
    }
  }
  / / recursion
  return quickSort(left).concat([pivot], quickSort(right))
}

console.log(quickSort([1.4.5.6.2]))
Copy the code

Sequential search O(n2) and binary search O(logn) (sorted in advance)

// Sequential search
function search(array,item) {
  for (let i = 0; i < array.length; i++) {
    if (item === array[i]){
      return i
    }
  }
  return -1
}
var arr = [3.1.5.6.2]
console.log(search(arr,2))
Copy the code


// Binary search
function binarySearch(array,item) {
  var low = 0,
    high = array.length -1,
    mid,element

  while (low <= high){
    mid = Math.floor((low+high)/2)
    element = array[mid]
    if (element <item) {
      low = mid+1
    } else if (element >item) {
      high = mid -1
    } else {
      return mid
    }
  }
  return -1
}

var arr = [1.2.3.4.5]
console.log(binarySearch(arr,2))
Copy the code

Depth-first algorithm & breadth-first algorithm

const data = [
    {
        name: 'a'.children: [{name: 'b'.children: [{ name: 'e'}]}, {name: 'c'.children: [{ name: 'f'}]}, {name: 'd'.children: [{ name: 'g'}]},],}, {name: 'a2'.children: [{name: 'b2'.children: [{ name: 'e2'}]}, {name: 'c2'.children: [{ name: 'f2'}]}, {name: 'd2'.children: [{ name: 'g2'}]},],}]// Deep traversal, using recursion
function getName(data) {
    const result = [];
    data.forEach(item= > {
        const map = data= > {
            result.push(data.name);
            data.children && data.children.forEach(child= > map(child));
        }
        map(item);
    })
    return result.join(', ');
}

// breadth traversal creates an execution queue and terminates when the queue is empty
function getName2(data) {
    let result = [];
    let queue = data;
    while (queue.length > 0) {
        [...queue].forEach(child= >{ queue.shift(); result.push(child.name); child.children && (queue.push(... child.children)); }); }return result.join(', ');
}

console.log(getName(data))
console.log(getName2(data))
Copy the code

JavaScript data structures and algorithms