Yuan Blog

Appearance

本篇基本算法针对常用方法，无论在任何地方都有可能使用到。在这里做下笔记，偶尔拿来看看。^-^

数组去重 ​

  • 利用对象属性不可重复特征
function sort(arr) {
  var obj = {};
  var newArr = [];
  for(var i=0; i<arr.length; i++) {
    if(!obj[arr[i]]) {
      newArr.push(arr[i]);
      obj[arr[i]] = 1; // 随意赋值
    }
  }
  return newArr;
}
function sort(arr) {
  var obj = {};
  var newArr = [];
  for(var i=0; i<arr.length; i++) {
    if(!obj[arr[i]]) {
      newArr.push(arr[i]);
      obj[arr[i]] = 1; // 随意赋值
    }
  }
  return newArr;
}
  • 利用数组splice方法
function sort(arr) {
  for(var i=0; i<arr.length; i++) {
    for(var j=i+1; j<arr.length; j++) {
      if(arrr[i] == arr[j]) {
        arr.splice(j, 1)
        j--;
      }
    }
  }
  return arr;
}
function sort(arr) {
  for(var i=0; i<arr.length; i++) {
    for(var j=i+1; j<arr.length; j++) {
      if(arrr[i] == arr[j]) {
        arr.splice(j, 1)
        j--;
      }
    }
  }
  return arr;
}
  • 利用数组indexOf方法
function sort(arr) {
  var newArr = [];
  for(var i=0; i<arr.length; i++) {
    if(newArr.indexOf(arr[i]) == -1) {
      newArr.push(arr[i])
    }
  }
  return newArr;
}
function sort(arr) {
  var newArr = [];
  for(var i=0; i<arr.length; i++) {
    if(newArr.indexOf(arr[i]) == -1) {
      newArr.push(arr[i])
    }
  }
  return newArr;
}
function sort(arr) {
  var newArr = [];
  for(var i=0; i<arr.length; i++) {
    if(arr.indexOf(arr[i]) == i) {
      newArr.push(arr[i])
    }
  }
  return newArr;
}
function sort(arr) {
  var newArr = [];
  for(var i=0; i<arr.length; i++) {
    if(arr.indexOf(arr[i]) == i) {
      newArr.push(arr[i])
    }
  }
  return newArr;
}
  • 使用ES6特征
[... new Set([1, 1, 2, 2])]
// or
Array.from(new Set([1, 1, 2, 2]))
[... new Set([1, 1, 2, 2])]
// or
Array.from(new Set([1, 1, 2, 2]))

闭包运用 ​

输入sum(1)(2)与sum(1, 2)值相等

function sum() {
  var x = arguments[0];
  if(arguments.length == 1) {
    return function(y) {
      return x + y;
    }
  }else{
    var x = 0;
    for(var i=0; i<arguments.length; i++) {
      x = x + arguments[i];
    }
    return x;
  }
}
function sum() {
  var x = arguments[0];
  if(arguments.length == 1) {
    return function(y) {
      return x + y;
    }
  }else{
    var x = 0;
    for(var i=0; i<arguments.length; i++) {
      x = x + arguments[i];
    }
    return x;
  }
}

冒泡排序 ​

冒泡排序是最简单的排序算法。它重复走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，即该数列已经排序完成。 思路：

  • 比较相邻的元素，如果第一个比第二个大，就交换它们。
  • 对每一个相邻元素做同样的工作，从开始第一对到结尾的最后一对，这一轮结束在最后的元素应该会是最大的数。
  • 对所有的元素重复以上步骤，除了最后一个。
  • 重复以上步骤，直到排序完成。
function sort(arr) {
  var temp = '';
  if(arr.length <= 1) return arr;
  for(var i=0; i<arr.length-1; i++) {
    for(var j=0; j<arr.length-1-i; j++) {
      if(arr[j] > arr[j+1]) {
        temp = arr[j+1];
        arr[j+1] = arr[j];
        arr[j] = temp;
      }
    }
  }
  return arr;
}
function sort(arr) {
  var temp = '';
  if(arr.length <= 1) return arr;
  for(var i=0; i<arr.length-1; i++) {
    for(var j=0; j<arr.length-1-i; j++) {
      if(arr[j] > arr[j+1]) {
        temp = arr[j+1];
        arr[j+1] = arr[j];
        arr[j] = temp;
      }
    }
  }
  return arr;
}

冒泡排序特征：如果数据足够大运行效率低，也比较耗时。

快速排序 ​

基本思想：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分关键字小，则可分别对这两部分记录继续进行排序，达到整个序列有序。

思路：

  • 从数列中找出一个基准元素。
  • 重新排序数列，所有元素比基准元素小的排在基准元素前面，所有元素比基准元素大的排在基准元素后面(相同的数可以到任意一边)，该基准元素就处于数列的中间位置。
  • 递归的把小于基准元素的子数列和大于基准元素的子数列排序。
function sort(arr) {
  if(arr.length <= 1) return arr;
  var minIndex = Math.floor(arr.length/2);
  var minVal = arr.splice(minIndex, 1);
  var left = [];
  var right = [];
  for(var i=0; i<arr.length; i++) {
    if(arr[i] < minVal) {
      left.push(arr[i])
    }else{
      right.push(arr[i])
    }
  }
  return sort(left).concat(minVal, sort(right));
}
function sort(arr) {
  if(arr.length <= 1) return arr;
  var minIndex = Math.floor(arr.length/2);
  var minVal = arr.splice(minIndex, 1);
  var left = [];
  var right = [];
  for(var i=0; i<arr.length; i++) {
    if(arr[i] < minVal) {
      left.push(arr[i])
    }else{
      right.push(arr[i])
    }
  }
  return sort(left).concat(minVal, sort(right));
}

快速排序特征：声明两个数组，占用内存

查找字符串重复数 ​

function filter(str) {
  var obj = {};
  return (function() {
    for(var i=0; i<str.length; i++) {
      var val = str.charAt(i);
      if(obj[val] && obj[val].value == val) {
        obj[val].count = ++obj[val].count;
      }else{
        obj[val] = {};
        obj[val].count = 1;
        obj[val].value = val;
      }
    }
    return obj;
  })()
}
// var str = 'aabccddd';
function filter(str) {
  var obj = {};
  return (function() {
    for(var i=0; i<str.length; i++) {
      var val = str.charAt(i);
      if(obj[val] && obj[val].value == val) {
        obj[val].count = ++obj[val].count;
      }else{
        obj[val] = {};
        obj[val].count = 1;
        obj[val].value = val;
      }
    }
    return obj;
  })()
}
// var str = 'aabccddd';

阶乘 ​

需要计算n的阶乘，最多需要保存n个调用记录，复杂度O(n)。

function factorial(x) {
  if(x === 1) return 1;
   return x * fectorial(x - 1);
}
factorial(3) // 6
function factorial(x) {
  if(x === 1) return 1;
   return x * fectorial(x - 1);
}
factorial(3) // 6

改写成尾递归(ES6函数尾调用优化部分) 只保留一个调用记录，复杂度O(1)。

function factorial(x, total) {
  if(x === 1) return total;
  return factorial(x-1, x * total);
}
factorial(3, 1) // 6
function factorial(x, total) {
  if(x === 1) return total;
  return factorial(x-1, x * total);
}
factorial(3, 1) // 6

斐波那契数列 ​

非递归实现

function fibonacci(x) {
   if(x <= 1) return 1;
    return fibonacci(x - 1) + fibonacci(x - 2);
}
fibonacci(3) // 3
function fibonacci(x) {
   if(x <= 1) return 1;
    return fibonacci(x - 1) + fibonacci(x - 2);
}
fibonacci(3) // 3

改写成尾递归(ES6函数尾调用优化部分)

function fibonacci(x, y=1, z=1) {
  if(x <= 1) return z;
  return fibonacci(x-1, z, y+z);
}
fibonacci(3) // 3
function fibonacci(x, y=1, z=1) {
  if(x <= 1) return z;
  return fibonacci(x-1, z, y+z);
}
fibonacci(3) // 3

字符串可以相减 ​

var start = '2018-07-10 10:30:33';
var end = '2018-07-10 18:50:45';
function testTime(start, end) {
  var now = new Date();
  start = new Date(start.replace(/-/g, '-'));
  end = new Date(end.replace(/-/g, '-'));
  if(start - now > 0 && now - end < 0) {
    return 'before';
  }else{
    return 'after';
  }
}
var start = '2018-07-10 10:30:33';
var end = '2018-07-10 18:50:45';
function testTime(start, end) {
  var now = new Date();
  start = new Date(start.replace(/-/g, '-'));
  end = new Date(end.replace(/-/g, '-'));
  if(start - now > 0 && now - end < 0) {
    return 'before';
  }else{
    return 'after';
  }
}