算法编程题

本文总结了很多简单的算法编程：

• 降维
• 排序
• 去重
• 统计一个字符串出现最多的字母
• 不借助临时变量，进行两个整数的交换
• 找出下列正数组的最大差值
• 随机生成指定长度的字符串
• 实现类似getElementsByClassName 的功能
• 判断一个单词是否是回文？
• 找出最长单词
• string 里的每个单词首字母大写
• 判断字符串是否是指定字符结尾
• 重复字符串指定次数
• 找出字符串中出现最多的字符和个数
• 创建一个函数判断给定的表达式中的小括号是否闭合
• 在字符串中找出连续最长的数字串
• 使用canvas 绘制一个有限度的斐波那契数列的曲线？
• 实现阶乘
• 过滤敏感词
• 二分查找
• App版本比较
• 生成菲波那切数列
• 使用JS 实现二叉查找树(Binary Search Tree)
• 密码强度判断
• 修改路由规则
• 字符串大小写转换

跟着我一起学习吧~

js降维

//迭代降维
function jiangwei(arr){
  var newarr = []
  arr.forEach(item=>{
    if(item instanceof Array){
      newarr.push(...jiangwei(item))
    } else{
      newarr.push(item)
    }
  })
  return newarr
}
console.log(jiangwei( [3, ['a', [0,['a',1], 1], null], [4, '4j', [3]], -2]))

//用apply的特性，将数组作为参数展开传入新的空数组[]，再contact
var arr=[[1,2,3],["sy",1,"jh",null],["",9],1]
function jiangwei(arr){
  var newarr=[]
  newarr=newarr.concat.apply(newarr,arr)
  return newarr
}

//使用ES6特性-扩展运算符将数组展开
function jiangwei(arr){
  var newarr=[]
  newarr=[].concat(...arr)
  return newarr
}
console.log(jiangwei(arr))

//多维数组变成一维数组
//es6新增的flat方法
var arr = [3, ['a', [0, 1], null], [4, '4j', [3]], -2]
function jiangwei(arr){
  var newarr=[]
  //数字参数指定降维次数
  newarr=arr.flat(3)
  return newarr
}
console.log(jiangwei(arr))

js排序

//一、冒泡排序，相邻元素比较交换

//基本思路：
//1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
//2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
//3.针对所有的元素重复以上的步骤，除了最后一个。
//4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
var arr=[9,-2,1,30,-59]
function paixu(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]){
                var temp=arr[j]
                arr[j]=arr[j+1]
                arr[j+1]=temp
            }
        }
    }
    return arr
}
console.log(paixu(arr))

//二、快速排序

//基本思路：
//1.以一个数为基准(中间的数)，比基准小的放到左边，比基准大的放到右边
//2.再按此方法对这两部分数据分别进行快速排序（递归进行）
//3.不能再分后退出递归，并重新将数组合并
function quickSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }
    let leftArr = [];
    let rightArr = [];
    let q = arr[0];
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] > q) {
            rightArr.push(arr[i]);
        } else {
            leftArr.push(arr[i]);
        }
    }
    return [].concat(quickSort(leftArr), [q], quickSort(rightArr));
}
console.log(quickSort(arr));//['a','b','c','d']

js去重

var arr = ['1','hello','ree','ke','yi','1','e','1']

//ES6数组去重，无法去{}空对象
function quchong(arr){
    return Array.from(new Set(arr))
}

//splice去重，一个数据和后面所有数据比较，相同的删除
function quchong(arr){
    for (var i=0; i<arr.length; i++){
        for (var j=i+1; j<arr.length; j++){
            if (arr[i]==arr[j]){
                arr.splice(j,1)
                j--
            }
        }
    }
    return arr
}

//使用indexOf去重，新建一个数组，把原数组的数据与新数组里的数据比较newarr.indexOf(arr[i])===-1，不存在就push进去，存在的就跳过
function quchong(arr){
    var newarr=[]
    for (var i=0; i<arr.length; i++){
        if(newarr.indexOf(arr[i])===-1){
            newarr.push(arr[i])
        }
    }
    return newarr
}


//使用sort去重，先将数组排序，然后前后数据相比较，不存在就放入新的数组
function quchong(arr){
    var newarr=[]
    arr= arr.sort()
    for (var i=0; i<arr.length; i++){
        if(arr[i]!==arr[i+1]){
            newarr.push(arr[i])
        }
    }
    return newarr
}

console.log(quchong(arr))

统计一个字符串出现最多的字母

给出一段英文连续的英文字符窜，找出重复出现次数最多的字母比如：
输入：afjghdfraaaasdenas ;输出 ： a
前面出现过去重的算法，这里需要是统计重复次数。
利用Object中key的唯一性，利用key来进行筛选，然后计数。

var string = 'afjghdfraaaasdenas'
function findMaxDuplicateChar(str) {  
  if(str.length == 1) {
    return str;
  }
  let charObj = {};
  for(let i=0;i<str.length;i++) {
    if(!charObj[str.charAt(i)]) {
      charObj[str.charAt(i)] = 1;
    }else{
      charObj[str.charAt(i)] += 1;
    }
  }
  let maxChar = '',
      maxValue = 1;
  for(var k in charObj) {
    if(charObj[k] >= maxValue) {
      maxChar = k;
      maxValue = charObj[k];
    }
  }
  return maxChar;
}
console.log(findMaxDuplicateChar(string))

不借助临时变量，进行两个整数的交换　　

举例：输入 a = 2, b = 4 输出 a = 4, b =2　　
这种问题非常巧妙，需要大家跳出惯有的思维，利用 a , b进行置换。　　
主要是利用 + - 去进行运算，类似 a = a + ( b - a) 实际上等同于最后 的 a = b;

var a = 2
var b = 4
function swap(a , b) {  
  b = b - a;
  a = a + b;
  b = a - b;
  return [a,b];
}
console.log(swap(a,b))

找出下列正数组的最大差值

比如：输入 [10,5,11,7,8,9] ;输出 6
这是通过一道题目去测试对于基本的数组的最大值的查找，很明显我们知道，最大差值肯定是一个数组中最大值与最小值的差。

function getMaxProfit(arr) { 
    var minPrice = arr[0]; 
    var maxProfit = 0; 
    for (var i = 0; i < arr.length; i++) { 
        var currentPrice = arr[i]; 
        minPrice = Math.min(minPrice, currentPrice); 
        var potentialProfit = currentPrice - minPrice; 
        maxProfit = Math.max(maxProfit, potentialProfit); 
    } 
    return maxProfit; 
}

function getMaxProfit(arr){
  var min = arr[0]
  var max = arr[0]
  var value = 0
  arr.map(item=>{
    if(item < min){
      min = item
    } else if (item > max){
      max = item
    }
    value = Math.max(value, max-min)
  })
  return value
}
console.log(getMaxProfit([8,10,1,3,6,2,9]))

随机生成指定长度的字符串

实现一个算法，随机生成指指定长度的字符窜。
比如：给定 长度 8 输出 4ldkfg9j

function randomString(n) {  
  let str = 'abcdefghijklmnopqrstuvwxyz9876543210';
  let tmp = '',
      i = 0,
      l = str.length;
  for (i = 0; i < n; i++) {
    tmp += str.charAt(Math.floor(Math.random() * l));
  }
  return tmp;
}
console.log(randomString(8))

实现类似getElementsByClassName 的功能　　

自己实现一个函数，查找某个DOM节点下面的包含某个class的所有DOM节点？
不允许使用原生提供的 getElementsByClassName querySelectorAll 等原生提供DOM查找函数。

function queryClassName(node, name) {  
  var starts = '(^|[ \n\r\t\f])',
      ends = '([ \n\r\t\f]|$)';
  var array = [],
        regex = new RegExp(starts + name + ends),
        elements = node.getElementsByTagName("*"),
        length = elements.length,
        i = 0,
        element;

    while (i < length) {
        element = elements[i];
        if (regex.test(element.className)) {
            array.push(element);
        }

        i += 1;
    }

    return array;
}

判断一个单词是否是回文？

回文是指把相同的词汇或句子，在下文中调换位置或颠倒过来，产生首尾回环的情趣，叫做回文，也叫回环。比如 mamam redivider
很多人拿到这样的题目非常容易想到用for 将字符串颠倒字母顺序然后匹配就行了。其实重要的考察的就是对于reverse的实现。其实我们可以利用现成的函数，将字符串转换成数组，这个思路很重要，我们可以拥有更多的自由度去进行字符串的一些操作。

// 简易好理解的方法
var str = 'helloolleh';
function checkPalindrom(str) {  
    return str == str.split('').reverse().join('');
}
console.log(checkPalindrom(str));//true


// 复杂方法
function isPalindrome(str){
    if (typeof str !== 'string' || str.constructor !== String) {
  return false;
    }
    var len = parseInt((str.length+1)/2);
    for(var i=0; i<len; i++){
  if (str[i] !== str[str.length-i-1]) {
      return false;
  }
    }
    return true;
}
console.log(isPalindrome('adddddda'));//true
console.log(isPalindrome('addddda'));//true
console.log(isPalindrome('adddasd'));//false

找出最长单词

这个有很多种解决办法 我只是用了个蠢一点最早想到的方法
Find the Longest Word in a String

function findLongestWord(str) {
  // 请把你的代码写在这里
  var new_str = str.split(" ");
  var arr = [];
  for(var i = 0;i<new_str.length;i++){
    arr.push(new_str[i].length);
  }
  return arr.sort(function(a,b){
        return b-a;
    })[0];
}
findLongestWord("The quick brown fox jumped over the lazy dog");

string 里的每个单词首字母大写

Title Case a Sentence

function titleCase(str) {
  return str.toLowerCase().split(" ").map((item)=>{
    return item.replace(item.charAt(0),item[0].toUpperCase())
}).join(" ")
}
titleCase("I'm a little tea pot");

判断字符串是否是指定字符结尾

这只是一种思路 我这个有点过去简单粗暴了 小伙伴们如果有更多答案 可以留言 探讨下

function confirmEnding(str, target) { 
    return (str.substr(-target.length)==target) ? true:false;
}
confirmEnding("He has to give me a new name", "name");

重复字符串指定次数

这个折腾了一会儿 刚开始得保存一次 没想到Repeat a string repeat a string

function repeat(str, num) {
  if(num<=0)
      return "";
  var save_ = str
  for(var i=1;i<num;i++)
    str+=save_ ;
  return str;
}
repeat("abc", 3);

找出字符串中出现最多的字符和个数

var string="sssfgtdfssddfsssfssss";
function max(str){
  var json={};
  var num=0;
  var value=null;
  for(var i=0;i<str.length;i++){
    var k=str[i];
    if(!json[k]){
      json[k]=[];
    }
    json[k].push(k); //这里不需要else，否则只有存在这个字符时才添加。次数会少一次
  }
  for(var attr in json){
    if(num<json[attr].length){
      num=json[attr].length;
      value=json[attr][0];
    }
  }
  return value+' '+num;
};
console.log(max(string))

创建一个函数判断给定的表达式中的小括号是否闭合

var expression = "(())()()"
var expressionFalse = "()(()"
function isBalanced(expression) {
  var checkString = expression;
  var stack = [];
  if (checkString.length <= 0) return true;
  for (var i = 0; i < checkString.length; i++) {
    if(checkString[i] === '(') {
      stack.push(checkString[i]);
    } else if (checkString[i] === ')') {
      // Pop on an empty array is undefined
      if (stack.length > 0) {
        stack.pop();
      } else {
        return false;
      }
    }
  }
  // If the array is not empty, it is not balanced
  if (stack.pop()) return false;
  return true;
}
console.log(isBalanced(expression))

在字符串中找出连续最长的数字串

var lines = 'abc360360xyz#123you'

function findTheNumString(str) {
    var reg = /\d+/g     
    var array = str.match(reg)
    var max = 0
    for (var i = 0; i < array.length; i++) {
        if (array[i].length >= max) {
            max = array[i].length
            var j = i
        }
    }
    return array[j].length + '/' + array[j]
}
console.log(findTheNumString(lines))

使用canvas 绘制一个有限度的斐波那契数列的曲线？

数列长度限定在9.斐波那契数列，又称黄金分割数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列主要考察递归的调用。我们一般都知道定义fibo[i] = fibo[i-1]+fibo[i-2]; 生成斐波那契数组的方法

function getFibonacci(n) {  
  var fibarr = [];
  var i = 0;
  while(i<n) {
    if(i<=1) {
      fibarr.push(i);
    }else{
      fibarr.push(fibarr[i-1] + fibarr[i-2])
    }
    i++;
  }
  return fibarr;
}

实现阶乘

1. 非递归实现?

function factorialize(num) {
 var result = 1;
 if(num < 0) return -1;
 if(num == 0 || num == 1) return 1;
 while(num>1)
  result *= num--;
 return result;
}

2. 递归实现

function factorialize(num) {
  if (num < 0) { 
        return -1; 
    } else if (num === 0 || num === 1) { 
        return 1; 
    } else { 
        return (num * factorialize(num - 1)); 
    } 
}
factorialize(5);

过滤敏感词

function sensitive(content){
    var keywords=["暴力", "色情", "fuck", "TMD"];//敏感词词库
      var value = content;//获取需要过滤的内容
      //遍历敏感词数组
      for(var i=0;i<keywords.length;i++){
          var reg = new RegExp(keywords[i],"g");//全局替换
          //判断内容中是否包括敏感词
          if(value.indexOf(keywords[i])!=-1){
              var result = value.replace(reg,"****");
              value = result;
          }
      }
    return value;
  }

二分查找

二分查找又称折半查找，是在有序数组查找中用到的较为频繁的一种算法，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。

1. 非递归实现

function binary_search(arr, key) {
 var low = 0,
  high = arr.length - 1;
 while(low <= high){
  var mid = parseInt((high + low) / 2);
  if(key == arr[mid]){
   return mid;
  }else if(key > arr[mid]){
   low = mid + 1;
  }else if(key < arr[mid]){
   high = mid -1;
  }
 }
 return -1;
};

2. 递归实现

function binary_search2(arr, low, high, key) {
 if(low > high)
  return -1;
 var mid = parseInt((low + high)/2);
 if(key == arr[mid])
  return mid;
 else if(key > arr[mid])
  return binary_search2(arr, mid+1, high, key);
 else if(key < arr[mid])
  return binary_search2(arr, low, mid-1, key);
}

App版本比较

function Version(curV, reqV) {
  var arr1 = curV.toString().split('.');
  var arr2 = reqV.toString().split('.');
  //将两个版本号拆成数字
  var minL = Math.min(arr1.length, arr2.length);
  var pos = 0; //当前比较位
  var diff = 0; //当前为位比较是否相等
  var flag = false;
  //逐个比较如果当前位相等则继续比较下一位
  while(pos < minL) {
    diff = parseInt(arr1[pos]) - parseInt(arr2[pos]);
    if(diff == 0) {
      pos++;
      continue;
    } else if(diff > 0) {
      flag = true;
      break;
    } else {
      flag = false;
      break;
    }
  }
  if(flag){
    return curV + ',' + reqV
  } else {
    return reqV + ',' + curV
  }
}
let test_v = Version('4.1.3','5.0.1')
console.log(test_v )

生成菲波那切数列

斐波那契数列，又称黄金分割数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……
在数学上，斐波纳契数列主要考察递归的调用。通过定义fibo[i] = fibo[i-1]+fibo[i-2];来生成斐波那契数组。

1. 强行递归实现

function getfib(n){
 if(n == 0)
 return 0;
 if(n == 1)
  return 1;
 if(n > 1){
 return getfib(n-1) + getfib(n-2);
 }
}
function fibo(len){
 var fibo = [];
 for(var i=0;i<len;i++)
 fibo.push(getfib(i));
 return fibo;
}

2. 简约非递归版

function getFibonacci(n) {
 var fibarr = [];
 var i = 0;
 while(i < n) {
  if(i <= 1) {
   fibarr.push(i);
  } else {
   fibarr.push(fibarr[i - 1] + fibarr[i - 2])
  }
  i++;
 }
 return fibarr;
}

使用JS 实现二叉查找树(Binary Search Tree)

一般叫全部写完的概率比较少，但是重点考察你对它的理解和一些基本特点的实现。 二叉查找树，也称二叉搜索树、有序二叉树（英语：ordered binary tree）是指一棵空树或者具有下列性质的二叉树：

• 任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 任意节点的左、右子树也分别为二叉查找树；
• 没有键值相等的节点。二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为O(log n)。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合、multiset、关联数组等。
  
  在写的时候需要足够理解二叉搜素树的特点，需要先设定好每个节点的数据结构

class Node {  
  constructor(data, left, right) {
    this.data = data;
    this.left = left;
    this.right = right;
  }
}

树是有节点构成，由根节点逐渐延生到各个子节点，因此它具备基本的结构就是具备一个根节点，具备添加，查找和删除节点的方法.

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  insert(data) {
    let n = new Node(data, null, null);
    if (!this.root) {
      return this.root = n;
    }
    let currentNode = this.root;
    let parent = null;
    while (1) {
      parent = currentNode;
      if (data < currentNode.data) {
        currentNode = currentNode.left;
        if (currentNode === null) {
          parent.left = n;
          break;
        }
      } else {
        currentNode = currentNode.right;
        if (currentNode === null) {
          parent.right = n;
          break;
        }
      }
    }
  }

  remove(data) {
    this.root = this.removeNode(this.root, data)
  }

  removeNode(node, data) {
    if (node == null) {
      return null;
    }

    if (data == node.data) {
      // no children node
      if (node.left == null && node.right == null) {
        return null;
      }
      if (node.left == null) {
        return node.right;
      }
      if (node.right == null) {
        return node.left;
      }

      let getSmallest = function(node) {
        if(node.left === null && node.right == null) {
          return node;
        }
        if(node.left != null) {
          return node.left;
        }
        if(node.right !== null) {
          return getSmallest(node.right);
        }

      }
      let temNode = getSmallest(node.right);
      node.data = temNode.data;
      node.right = this.removeNode(temNode.right,temNode.data);
      return node;

    } else if (data < node.data) {
      node.left = this.removeNode(node.left,data);
      return node;
    } else {
      node.right = this.removeNode(node.right,data);
      return node;
    }
  }

  find(data) {
    var current = this.root;
    while (current != null) {
      if (data == current.data) {
        break;
      }
      if (data < current.data) {
        current = current.left;
      } else {
        current = current.right
      }
    }
    return current.data;
  }

}
module.exports = BinarySearchTree;  

.ajax

https://www.runoob.com/ajax/ajax-examples.html

function ajaxtest(){
    var xmlhttp;
    if (window.XMLHttpRequest)
    {
        //  IE7+, Firefox, Chrome, Opera, Safari 浏览器执行代码
        xmlhttp=new XMLHttpRequest();
    }
    else
    {
        // IE6, IE5 浏览器执行代码
        xmlhttp=new ActiveXObject("Microsoft.XMLHTTP");
    }
    xmlhttp.onreadystatechange=function()
    {
        if (xmlhttp.readyState==4 && xmlhttp.status==200)//0-4和200，404
        {
            // responseText 获得字符串形式的响应数据。
            // responseXML  获得 XML 形式的响应数据。
            document.getElementById("myDiv").innerHTML=xmlhttp.responseText;
        }
    }
    /* 规定请求的类型、URL 以及是否异步处理请求。
    method：请求的类型；GET 或 POST
    url：文件在服务器上的位置
    async：true（异步）或 false（同步）*/
    xmlhttp.open("GET","/try/ajax/ajax_info.txt",true);
    /*
    将请求发送到服务器。
    string：仅用于 POST 请求
    */
    xmlhttp.send();
}

密码强度判断

function checkPassWord(value){
    var modes = 0;
    if(/\d/.test(value)){//如果用户输入的密码 包含了数字
        modes++;
    }
    if(/[a-z]/.test(value)){//如果用户输入的密码 包含了小写的a到z
        modes++;
    }
    if(/[A-Z]/.test(value)){//如果用户输入的密码 包含了大写的A到Z
        modes++;
    }
    if(/\W/.test(value)){//如果是非数字 字母 下划线
        modes++;
    }
    if(value.length < 8 || modes == 1){//最初级别
        return 0;
    } else {
        if(modes == 2){
            if(/\d/.test(value)&&/[a-z]/.test(value)){
                return 1;
            } else if(/\d/.test(value)&&/[A-Z]/.test(value)){
                return 1;
            } else {
                return 2;
            }
        } else if(modes == 3){
            return 3;
        } else if(modes == 4){
            return 3;
        }
    }
}
console.log(checkPassWord('ssqk!!!!!!hk'))

修改路由规则

var routes = [
    {
        path:"/home",
        content:"home",
        children:[
            {
                path:"/hello",
                content:"hello"
            },
            {
                path:"/hello1",
                content:"hello1"
            }
        ]
    },
    {
        path:"/about",
        content:"about",
        children:[{
            path:"/hello",
            content:"hello"
        }]
    }
]
function getRoute(routes){
    var obj=[];
    routes.map(element => {
        var itempath1 = element.path;
        var itemcontent1 = element.content;
        var itemobj1 = {
            path: itempath1,
            content: itemcontent1
        }
        obj.push(itemobj1);
        if(element.children){
            element.children.map(item => {
                var itemcontent2 = [];
                var itempath2;
                itemcontent2.push(itemcontent1);
                itempath2 = element.path+item.path;
                itemcontent2.push(item.content)
                var itemobj2 = {
                    path: itempath2,
                    content: itemcontent2
                }
                obj.push(itemobj2);
            })
        }
    });
    return obj
}
console.log(getRoute(routes));

字符串大小写转换

function change(str){
  var arr = str.split('')
  var newarr = []
  arr.map(item=>{
    if(/[a-z]/.test(item)){
      newarr.push(item.toUpperCase())
    } else if(/[A-Z]/.test(item)){
      newarr.push(item.toLowerCase())
    }
  })
  return newarr.join('')
}
console.log(change('sSuFHJwil'))