jsデータ構造とアルゴリズム

一、javascript基礎1.javascriptのデータタイプは、数字、文字列、関数、オブジェクト、undefined、nullと配列、日付、正規表現です.2.変数のスコープ:ローカル変数とグローバル変数.一つの関数では、変数はvarキーワードを使用しないと、グローバル変数を説明または引用します.3.ブール値を偽の値に変換した有|undefined𞓜-null-124124;＋0、-0、NaN 124;;空の文字列4.作成対象の2つの方式:コンストラクションと字面量方式で5.配列を作成します.

1次元配列

追加:ラスト:push  ;開始:unshift
削除:末尾:pop  ;最初の要素を削除します.shift()任意の位置で要素splice numbers.splice(5,3):配列インデックス5から3つの要素numbers.splice(5,0,2,3,4):インデックス5から0つの要素を削除します.その後3つのパラメータは配列に追加する値です.

 二次元と多次元配列 

行列ネストで行列または多次元配列を実現します.

配列のコア方法

メソッド名
説明
every
配列の各項目に指定された関数を実行します.各項目に対してtrueを返すと、trueを返します.
filter
配列の各項目に対して指定された関数を実行します.この関数を返します.trueの項目からなる行列を返します.
forEach
配列の各項目に指定された関数を実行します.この方法は戻り値がありません.
indexOf
与えられたパラメータに等しい最初の配列要素のインデックスを返します.
map
配列の各項目に対して与えられた関数を実行し、各関数が呼び出した結果からなる行列を返します.
slice
入力されたインデックス値は、行列内の対応するインデックス範囲内の要素を新しい配列として返します.
splice
配列の任意のインデックス位置に追加と削除ができます.
行列全体を反復する必要がある場合は、forEachを使用します.
新しい配列のエルゴード方法を返します.
map  戻る配列には、入力されたmapメソッドの関数の実行結果(戻り値)が含まれています.
filterが返した新しい数は、関数をtrueに戻す要素から構成されています.
reduceはパラメータとして関数を受信します.この関数は4つのパラメータがあります.previous Value、current Value、index、array.はアキュムレータに重畳される値を返します.reduce方法は実行を停止したらこのアキュムレータに戻ります.
二、スタック:後進先出
スタックを実現し、配列でスタックの要素を保存します.

function Stack(){
  var items=[];
  this.push=function(el){  //  
    items.push(el);
    }
  this.pop=function(el){    //  
    items.push(el);
    }
  this.peek=function(el){    //      
    return items[items.length-1];
    }
  this.isEmpty=function(el){   //       
    return items.length==0;
    }
   this.clear=function(){
       items=[];
   }
}

使用:

var stack=new Stack();
stack.push(5);
stack.push(8);
stack.pop();  //  8
stack.peek();  //       5

三、隊列:先入先出

function Queue(){
  var items=[];
  this.enqueue=function(el){  //         
      items.push(el);
    }
  this.dequeue=function(){   //        ，         
      items.shift();
    }
  this.front=function(){  //         
     return items[0];
    }
  }

使用:

var queue=new Queue();
queue.enqueue("Jhon")
queue.enqueue("lisa")
queue.dequeue()   //  lisa

優先キュー:要素の追加と削除は優先順位に基づいています.

function PriorityQueue(){
   var items=[];
   function QueueElement(Value,Priority){
      this.value=Value;
      this.proiority=Priority
   }
   this.enqueue=function(el,priority) { //       ，        ，       ，      
   var queueElement=new QueueElement(el,priority)  //  QueueElement    
   if(this.isEmpty()){  //      ，     
        items.push(queueElement)
     }else{   //    ，        ，                  
        var flag=false;
       for(var i=0;i

四、集合:対象で実現する
集合は無秩序で唯一の項目で構成されている(重複しない).

function Set(){
    var items={};
    this.has=function(value){
        return items.hasOwnProperty(value);
    };
    this.add=function(value){
      if(!this.has(value)){
        items[value]=value;
        return ture;
      }
      return false;
    };
   this.remove=function(value){
      if(this.has(value)){
        delete items[value];
        return ture;
      }
      return false;
    };
   this.values=function(){
     return Object.keys(items);
    }
}

Object.keys 与えられたobjectから直接列挙できる属性からの要素を含むすべての要素の配列を返します.これらの属性の順序は、オブジェクトの属性を手動で巡回したときと一致します.
五、木
二叉サーチツリーBST:親ノードよりも左側のノードに小さな値を格納するだけで、右側のノードに親ノードよりも大きい値または等しい値を格納することができます.

function BinarySearchTree(){
  var Node=function(key){
     this.key=key;
     this.left=null;
     this.right=null;
   };
  var root=null;
  this.insert()=function(key){  //        
     var newNode=new Node(key);
     if(root===null){
       root=newNode;
     }else{
         insertNode(root,newNode)
      }
   }
 var insertNode=function(node,newNode){
       if(newNode.key

木の遍歴
1、中順巡回

this.inOrderTraverse=function(callback){
   inOrderTraverseNode(root,callback);
}
var inOrderTraverseNode=function(node,callback){
  if(node!==null){
    inOrderTraverseNode(node.left,callback);
    callback(node.key);
    inOrderTraverseNode(node.right,callback);
  }
}

2、まずは巡回

this.preOrderTraverse=function(callback){
   preOrderTraverseNode(root,callback);
}
var preOrderTraverseNode=function(node,callback){
  if(node!==null){
    callback(node.key);
    preOrderTraverseNode(node.left,callback);
    preOrderTraverseNode(node.right,callback);
  }
}

3、後から順に巡回します

this.postOrderTraverse=function(callback){
   preOrderTraverseNode(root,callback);
}
var postOrderTraverseNode=function(node,callback){
  if(node!==null){
    callback(node.key);
    postOrderTraverseNode(node.left,callback);
    postOrderTraverseNode(node.right,callback);
  }
}

六、並べ替えと検索アルゴリズム
1、泡の並べ替え

//      
function bubbleSort(arr){
	for(var i=0; iarr[j+1]){
				var temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
			}
		}
	}
	return arr;
}

改善する

function bubbleSort(arr){
	for(var i=0; iarr[j+1]){
				var temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
			}
		}
	}
	return arr;
}

2、並べ替えを選択する
データ構造の中の最小値を見つけて第一位に置き、第二小の値を第二位に置く.

function selection(ary){
     var min;
    for (var i=0;iary[j]) {
          ary[min]=ary[j]
        }
      }
      if( ary[min]!==ary[i]){
        var temp=ary[i];
        ary[i]=ary[min];
        ary[min]=temp;
      }
    }
  }

3、挿入順序:第一項が順序付けされていると仮定し、第二項が第一項の前に挿入されるべきかそれともその場にあるべきかを判断する.

function insert(ary){
   var j,temp;
   for(var i=0;i0&&ary[j-1]>temp){
          ary[j]=ary[j-1];
          j--;
      }
      ary[j]=temp;
    }
}

4、規格化された並べ替え:元の配列を小さい配列に切り分け、各小さい配列が一つの位置になるまで、続いて小さい配列をまとめて大きな配列にします.

var mergeSort=function(ary){
  var len=ary.length;
  if(len===1){return ary}
  var mid=Math.floor(length/2);
  left=ary.slice(0,mid);
  right=ary.slice(mid,len);
  return merge(mergeSort(left),mergeSort(right));
}
var merge=function(left,right){
  var result=[],il=0,ir=0;
  while(il

5、快速並べ替え

    //      
	function quickSort(arr){
		if(arr.length <= 1){
			return arr;
		}
		var left = [];
		var right =[];
		var pivotkey = arr[0];
		for(var i=1; i

二分割検索

this.binarySearch = function(item){
  var low=0,high=ary.length-1,mid,ele;
  while(low<=high){
    mid=Math.floor((low+high)/2);
    ele=ary[mid];
    if(eleitem){
        high=mid-1;
      }else{
        return mid;
      }
  }
   return -1;
}

八:欲張りアルゴリズム
最小硬貨のお釣り問題d 1=1、d 2=5、d 3=10、d 4=25;
私の実現

function minCoinChange(coins){
    var count=0;//        
    var result=[];
    var digui=function(coins)
    {
      if (Math.floor(coins / 25)) {  //  25  
        var num=Math.floor(coins / 25);
        count += num;
        coins = coins - 25*num;
        console.log(coins)
        for(var i=0;i

多くの重複コードがあり、再帰的に再帰的に呼び出され、4回実行されるコード思想は同じであることが見られます.
改善:

function MinCoinChange0(coins){
    var coins=coins;
    this.makeChange=function(amount){
      var change=[];
      var total=0;
      for(var i=coins.length;i>=0;i--){
        var coin=coins[i];
        while(total+coin<=amount){
          change.push(coin);
          total+=coin
        }
      }
      return (change)
    }
  }
 var minCoinChange0=new MinCoinChange0([1,5,10,25])
 console.log(minCoinChange0.makeChange(36))

小銭の基数を自由に指定できます.コアコードも少ないです.ここで注意したいのはifではなくwhileです.Ifは一回だけ入ります.例えば、お釣りは20です.じゃ、0+10<20;結果配列を10に押し、forサイクルを続けます.coins[2]は5になり、さらに5を押して、最後に1を押します.結果は【10,5,1】です.
だから、whileを使わなければなりません.初めて0+10<20,total=10で、10+10<=20.もう一度このサイクルに入り、10を押して、結果は【10,10】です.