Implementierungscode für den allgemeinen JS-Algorithmus-js-Tutorial-php.cn

Implementierungscode für den allgemeinen JS-Algorithmus

高洛峰

Freigeben： 2016-12-07 09:57:32

Original

791 Leute haben es durchsucht

Der Hauptzweck dieses Artikels besteht darin, jedem zu helfen, sich mit der Implementierung mehrerer häufig verwendeter Algorithmen mithilfe von JS vertraut zu machen. Der spezifische Inhalt lautet wie folgt:

(1) Array-Deduplizierung

Prinzip : Definieren Sie ein Objekt obj. Verwenden Sie dann das Array-Element als Attributnamen von obj und verwenden Sie, ob der Attributname wiederholt wird, um das Gewicht zu bestimmen

var unique = function(arr){
  let obj = {};
  let newArr = [];
  arr.forEach(function(x){
    if(!obj[x]){ //如果对象中没有该元素对应的属性
      obj[x] = true;
      newArr.push(x);
    }
  });
  return newArr;
}

Nach dem Login kopieren

(2) Verwenden Sie den Schnellsortierungsalgorithmus für die Array-Sortierung

Dies beinhaltet zwei Effekte: Der eine besteht darin, die Eigenschaften der Schnellsortierung zu nutzen, um eine schnelle Sortierung ohne Deduplizierung zu erreichen, und der andere ist die schnelle Sortierung ohne Deduplizierung .

Prinzip: Erhalten Sie das Zielarray, wählen Sie ein Element als Flag aus, durchlaufen Sie die verbleibenden Elemente, platzieren Sie die Elemente rechts größer als das Flag und links kleiner als das Flag.

Besonderer Hinweis: Es gibt Elemente, die dem Flag-Bit entsprechen, wenn Sie gleiche Elemente speichern. Wenn Sie sie speichern, werden sie nicht dedupliziert.

var quickSort = function(arr){
   
  if(arr.length <= 1){
    return arr;
  }
   
  //定义一个左数组，定义一个右数组
  let leftArr = [];
  let rightArr = [];
  //选定一个参照值
  let tag = arr[0];
   
  /*
   * 使用如下方式判断，会把重复元素去掉，就实现了快排的同时去重
   */
  for(let i = 0; i < arr.length; i++){
    if(arr[i] < tag){ //将比tag小的元素放在左数组中
      leftArr.push(arr[i]);
    }
    if(arr[i] > tag){ //将比tag大的元素放在右数组中
      rightArr.push(arr[i]);
    }
  }
   
  /*
   * 使用如下方式就是使用快排进行排序，不去重
   */
  for(let i = 1; i < arr.length; i++){
    if(arr[i] < tag){ //将比tag小的元素放在左数组中
      leftArr.push(arr[i]);
    }else{ //将比tag大的元素放在右数组中
      rightArr.push(arr[i]);
    }
  }
   
  //递归调用
  return [].concat(quickSort(leftArr),[tag],quickSort(rightArr));
}

Nach dem Login kopieren

(3) Zählen Sie die Zeichen, die am häufigsten in der Zeichenfolge vorkommen

Prinzip: Dies ähnelt einem Array Bei der Deduplizierung wird auch ein Objektobjekt verwendet, um das Array-Element als Attributnamen des Objekts zu verwenden. Wenn der Attributname nicht vorhanden ist, wird der Wert 1 zugewiesen. Wenn er vorhanden ist, wird der Wert um 1 erhöht.

var maxShowTimes = function(str){
  // 创建一个用于判重的对象
  let obj = {};
  // 判断字符串是否为空或只有一个元素
  if(str.length <= 1){
    return str.length === 0?&#39;字符串不能为空&#39;:str;
  }
  // 利用String的charAt()方法获取各个字符
  for(let i = 0; i <= str.length; i++){
    if(!obj[str.charAt(i)]){ //如果不存在
      obj[str.charAt(i)] = 1;
    }else{ //如果存在
      obj[str.charAt(i)] += 1;
    }
  }
   
  // 在obj对象中寻找值最大的那个属性
  let maxChar = &#39;&#39;;
  let maxTimes = 0;
  for(var k in obj){
    if(obj[k] > maxTimes){
      maxChar = k;
      maxTimes = obj[k];
    }
  }
  return maxChar;
}

Nach dem Login kopieren

(4) Werte zwischen zwei Variablen austauschen, ohne eine dritte Variable zu verwenden

Prinzip: Es ist gerecht Eine Variable Replacement, die Idee ist sehr clever, sie kann nur für den Austausch von Zahlen verwendet werden.

var swap = function(a,b){
  if(a === b){
    return [a,b];
  }
  b = b - a; // 此处的 b - a中的b和a的值是最初的值
  a = a + b; // a = a + b -a; 实现了将b的值赋给a
  b = a - b; // b = a - (b - a) = 2a - b 相当于 2b = 2a;实现了将a的值赋给b
  return [a,b];
}

Nach dem Login kopieren

(5) Finden Sie die maximale Differenz eines Arrays

Prinzip: Durchlaufen Sie das Array einmal und finden Sie das Maximum Summe Mindestwert, Differenz zurückgeben

var getMaxProfit = function(arr){
  // 定义两个变量，分别存贮最大值和最小值
  let maxNum = arr[0];
  let minNum = arr[0];
  for(let i = 0; i < arr.length; i++){
    if(arr[i] > maxNum){
      maxNum = arr[i];
    }
    if(arr[i] < minNum){
      minNum = arr[i];
    }
  }
  return maxNum - minNum;
}

Nach dem Login kopieren

(6) Erhalten Sie eine zufällige Zeichenfolge beliebiger Länge

Prinzip: Sie Sie können dies manuell tun. Geben Sie die Zeichenbibliothek und die zufällige Zeichenlänge n an und verwenden Sie die Methoden Math.floor() und Math.random(), um zufällige Zeichen zu erhalten.

var getRandomString = function(n){
  // 定义随机字符串的字符库
  let str = &#39;qwertyuiopasdfghjklzxcvbnm1234567890&#39;;
  // 定义一个临时变量tmp存储生成的随机字符串
  let tmp = &#39;&#39;;
  //获取str的长度
  let len = str.length;
  // 生成一个长度为n的随机字符串
  for(let i = 0; i < n; i++){
    tmp += str.charAt(Math.floor(Math.random() * len));
  }
  return tmp;
}

Nach dem Login kopieren