头部背景图片
小畅童鞋的学习笔记 |
小畅童鞋的学习笔记 |

算法编程题

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

  • 降维
  • 排序
  • 去重
  • 统计一个字符串出现最多的字母
  • 不借助临时变量,进行两个整数的交换
  • 找出下列正数组的最大差值
  • 随机生成指定长度的字符串
  • 实现类似getElementsByClassName 的功能
  • 判断一个单词是否是回文?
  • 找出最长单词
  • string 里的每个单词首字母大写
  • 判断字符串是否是指定字符结尾
  • 重复字符串指定次数
  • 使用canvas 绘制一个有限度的斐波那契数列的曲线?
  • 实现阶乘
  • 过滤敏感词
  • 二分查找
  • App版本比较
  • 生成菲波那切数列
  • 使用JS 实现二叉查找树(Binary Search Tree)

跟着我一起学习吧~

js降维

//二维数组变一维数组
//遍历数组两遍,放入新数组
var arr=[[1,2,3],["sy",1,"jh",null],["",9],1]
function jiangwei(arr){
  var newarr=[]
  arr.forEach(item => {
  //判断是不是数组,是进入下一个判断,不是直接push
    item.forEach?item.forEach(val => {
      newarr.push(val)
    }):newarr.push(item)
  });
  return newarr
}

//用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排序

//js数组排序,冒泡,相邻元素比较交换
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))

//快速排序
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; 
}

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

实现一个算法,随机生成指指定长度的字符窜。
比如:给定 长度 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);

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

Image1.png
数列长度限定在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;
}
  1. 递归实现
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;
};
  1. 递归实现
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;
}
  1. 简约非递归版
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、关联数组等。
    Image2.png
    在写的时候需要足够理解二叉搜素树的特点,需要先设定好每个节点的数据结构
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();
}
Lililich's Blog