前端算法题目

[XJIANBIN]

1 统计一个字符串出现最多的字母
给出一段英文连续的英文字符窜，找出重复出现次数最多的字母
输入 ： afjghdfraaaasdenas

  var str = "afjghdfraaaasdenas";
function findMaxTimeNumber(str) {
  if (str.length == 1) return str;
  var formatArr = str.split("").sort((a, b) => {
    return a.charCodeAt() - b.charCodeAt();
  });
  var maxNum = 0,
    currentNum = 0;
  formatArr.map((el, index) => {
    currentNum++;
    if (el != formatArr[index + 1]) {
      if (maxNum < currentNum) {
        maxNum = currentNum;
      }
      currentNum = 0;
    }
  });
  console.log(maxNum);
  return maxNum;
}
findMaxTimeNumber(str);

2 去掉一组整型数组重复的值
输入：[1,13,24,11,11,14,1,2]
输出：[1,13,24,11,14,2]
需要去掉重复的11 和 1 这两个元素。

// 第一种
var arr = [1,13,24,11,11,14,1,2];
Array.from(new Set(arr))
// the two
var newArr = [];
arr.map((el,index) => {
 if(newArr.indexOf(el)< 0) {
console.log(newArr.indexOf(el)< 0)
  newArr.push(el);
}
})
// the three
arr.sort().filter(function(item, pos, ary) {
  return item != ary[pos + 1];
});

冒泡排序
依次比较相邻的两个元素，如果后一个小于前一个，则交换，这样从头到尾一次，就将最大的放到了末尾。

var arr =  [1, 13, 24, 11, 14, 2]
function bubbleSort(arr) {
    for(var i = 0 ,l = arr.length ; i < l ; i++){
       for(var j =  0 ; j < l-1 -i; j ++ ) {
			 if(arr[j]>arr[j+1]) {
                [arr[j],arr[j+1]] = [arr[j+1],arr[j]]
            }
		}
	}
	return arr;
}
bubbleSort(arr)

//双向遍历
//传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,
//我们可以 在每趟排序中进行正向和反向两遍冒泡 ，
//一次可以得到两个最终值（最大和最小） , 从而使外排序趟数几乎减少了一半
function bubbleSort3(arr) {
  var start = 0,
    end = arr.length - 1,
    flag = true;
  while (start < end && flag) {
    flag = false;
    for (var i = 0; i < end; i++) {
      if (arr[i] > arr[i + 1]) {
        [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
        flag = true;
      }
    }
    end--;
    for (var j = end; j > start; j--) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
    start++;
  }
  return arr;
}

选择排序
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。

var arr = [1, 13, 24, 11, 14, 2];
function selectionSort(arr) {
  var minIndex = 0;
  for (var i = 0, len = arr.length; i < len - 1; i++) {
    minIndex = i;
    for (var j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    if(i != minIndex) [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
  }
  return arr;
}
selectionSort(arr);

插入排序
1 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
2.从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。

var arr =  [1, 13, 24, 11, 14, 2]
function insertSort(arr) {
  var len = arr.length;
  for (var i = 1; i < len; i++) {
    var j = i;
    while (j > 0 && arr[j] < arr[j - 1]) {
      [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
      j--;
    }
  }
	return arr
}
insertSort(arr);

希尔排序（插入排序的改进）
参考资料1
代码参考
原理：希尔排序（shell sort）这个排序方法又称为缩小增量排序，是1959年D·L·Shell提出来的。该方法的基本思想是：设待排序元素序列有n个元素，首先取一个整数increment（小于n）作为间隔将全部元素分为increment个子序列，所有距离为increment的元素放在同一个子序列中，在每一个子序列中分别实行直接插入排序。然后缩小间隔increment，重复上述子序列划分和排序工作。直到最后取increment=1，将所有元素放在同一个子序列中排序为止。

function shellSort(arr){
	var len = arr.length,
		gap = Math.floor(len / 2);
		while(gap > 0){
			for(var i = gap; i < len; i++){
				var preIndex = i - gap;
				while(arr[preIndex] > arr[i]){
					[arr[preIndex],arr[i]] = [arr[i],arr[preIndex]]
					preIndex -= gap;
				}
			}
			gap = Math.floor(gap / 2);
		}
		return arr;
}
var arr = [91, 60, 96, 7, 35, 65, 10, 65, 9, 30, 20, 31, 77, 81, 24];
console.log(shellSort(arr));

归并排序

function mergeSort(arr) {
  var len = arr.length;
  if (len === 1) {
    return arr;
  }
  var mid = Math.floor(len / 2),
    left = arr.slice(0, mid),
    right = arr.slice(mid, len);
  return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
  var result = [],
    al = 0,
    ar = 0;
  while (al < left.length && ar < right.length) {
    if (left[al] < right[ar]) {
      result.push(left[al++]);
    } else {
      result.push(right[ar++]);
    }
  }
  while (al < left.length) {
    result.push(left[al++]);
  }
  while (ar < right.length) {
    result.push(right[ar++]);
  }
  return result
}
function merge(left, right) {
  const result = [];

  while (left.length > 0 && right.length > 0) {
    result.push(left[0] <= right[0] ? left.shift() : right.shift());
  }

  return result.concat(left, right);
}

快速排序
(1)首先，从数组中选择中间一项作为主元。
(2) 创建两个指针，左边一个指向数组第一个项，右边一个指向数组最后一个项。移动左指 针直到我们找到一个比主元大的元素，接着，移动右指针直到找到一个比主元小的元素，然后交 换它们，重复这个过程，直到左指针超过了右指针。这个过程将使得比主元小的值都排在主元之 前，而比主元大的值都排在主元之后。这一步叫作划分操作。
(3) 接着，算法对划分后的小数组(较主元小的值组成的子数组，以及较主元大的值组成的 子数组)重复之前的两个步骤，直至数组已完全排序。

function quick(arr, left, right) {
  var index;
  if (arr.length > 1) {
    index = sort2Index(arr, left, right);
    if (left < index - 1) {
      quick(arr, left, index - 1);
    }
    if (right > index) {
      quick(arr, index, right);
    }
  }
}
function sort2Index(arr, left, right) {
  var mid = arr[Math.floor((left + right) / 2)],
    l = left,
    r = right;
  while (l <= r) {
    while (arr[l] < mid) {
      l++;
    }
    while (arr[r] > mid) {
      r--;
    }
    if (l <= r) {
      [arr[l], arr[r]] = [arr[r], arr[l]];
      l++;
      r--;
    }
  }
  return l;
}
// -------- other
function quick(arr) {
	var len = arr.length;
  if (len <= 1) {
    return arr;
  }
  
   var init = arr[0],
    left = [],
    right = [];

  for (var i = 1; i < len; i++) {
    if (arr[i] < init) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return [].concat(quick(left), [init], quick(right));
}

排序对比

数据量大，要求最好的平均效率？

性能大小：快速排序 > 堆排序 > 归并排序

数据量大，要求效率高，而且要稳定？

归并排序

数据量大，要求稳定的效率（不会像快速排序一样有 O(n²) 的情况）（如数据库中）？

堆排序

数据量小，对效率要求不高，代码简单时？

希尔排序 > 插入排序 > 冒泡排序 > 选择排序
参考资料

二叉搜索树(BST)

二叉搜索树(BST)是二叉树的一种，但是它只允许你在左侧节点存储(比父节点)小的值， 在右侧节点存储(比父节点)大(或者等于)的值。

function BinarySearchTree() {
  var Node = function(key) {
    this, (key = key);
    this.left = null;
    this.right = null;
  };
  this.root = null;
}
// 插入一个节点
this.insert = function(key) {
  var newNode = new Node(key);
  if (root == null) {
    root = newNode;
  } else {
    insertNode(root, newNode);
  }
};
function insertNode(node, newNode) {
  // 比 中间节点大的值放在右边，比中间节点小的值在左边
  if (node.key > newNode.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);
    }
  }
}

中序遍历

可以理解为中间的 value 值为第二个访问，先访问二叉树左边的值，然后中间的值，然后右边的值

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

先序遍历

先序遍历和中序遍历的不同点是，先序遍历会先访问节点本身，然后再访问它的 左侧子节点，最后是右侧子节点

function preOrderTravere(callback) {
  preOrderTravereNode(root, callback);
}
function preOrderTravereNode(node, callback) {
  if (node !== null) {
    callback(node.key);
    preOrderTravereNode(node.left, callback);
    preOrderTravereNode(node.right, callback);
  }
}

后序遍历

后序遍历则是先访问节点的后代节点，再访问节点本身

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

BST 搜索

最大值最小值

function min() {
  minNode(root);
}
function minNode(node) {
  if (node) {
    while (node && node.left != null) {
      node = node.left;
    }
    return node.key;
  }
  return null;
}
function max() {
  maxNode(root);
}
function maxNode() {
  if (node) {
    while (node && node.right != null) {
      node = node.right;
    }
    return node.key;
  }
  return null;
}

搜索特定的值

function find(key) {
  findNode(root, key);
}
function findNode(node, key) {
  if (node === null) {
    return false;
  }
  if (key > node.key) {
    return findNode(node.right, key);
  } else if (key < node.key) {
    return findNode(node.left, key);
  } else {
    return true;
  }
}