阅读 5350

前端算法题目解析(一)

前言

前几天逛 github 的时候看到一些前端的算法题,自己做了一遍发现还挺有意思的,因此整理了一下收录 daily-question 的 algorithm 文件夹中,后续会继续增加,本文分享我整理的十个算法题目。

题外话:其实给这篇文章起名字的时候不知道起什么名字,看了下掘金命名的文章,整理了几个模板

  1. 你不知道系列 ——《你不知道的前端算法》
  2. 满足系列 —— 《前端算法看这篇就足够了》
  3. 灵魂系列 —— 《前端算法之灵魂拷问》
  4. 你真的懂吗系列 —— 《你真的懂前端算法吗?》
  5. 万字长文建议收藏系列 —— 《(万字长文,强烈建议收藏,错过没有)之前端算法》

最后想想还是朴素一点,不做标题党吧哈哈哈😜

01-把数字转换成中文


题目描述:

完成将 toChineseNum, 可以将数字转换成中文大写的表示,处理到万级别,例如 toChineseNum(12345),返回 一万二千三百四十五


思路:

对八位以上和一下进行分类讨论:

  1. 定义 getResult 方法处理八位数
  2. 处理八位数,切割成两部分,以五位进行分析,如果超出五位,则后五位为一体,除下后五位的为一体。 如果没有超出五位,则按照和后五位一样的方式,转换。最后处理特殊情况零。
  3. 处理八位数以上的,同样切割成两部分,后八位同 2 处理,剩下的用 getResult 处理后在后面补'亿'

参考答案:

function toChineseNum(num) {
  num += ''
  let numLength = num.length
  let numStr = '零一二三四五六七八九十'
  let unitArr = ['', '十', '百', '千', '万']
  function getResult(str) {
    let res = '';
    if (str.length > 5) {
      let first = str.slice(-5);
      let second = str.slice(0, str.length - 5);
      for (let i in second) {
        res = res + numStr[second[i]] + unitArr[second.length - i];
      }
      for (let i in first) {
        res = res + numStr[first[i]] + unitArr[first.length - i - 1];
      }
    } else {
      let first = str.slice(-5);
      for (let i in first) {
        res = res + numStr[first[i]] + unitArr[first.length - i - 1];
      }
    }
    res = res.replace(/零[零十百千]+/g, '零').replace(/零+$/g, '').replace(/零万/g, '万')
    return res;
  }
  
  if (numLength > 8) {
    return getResult(num.slice(0, numLength - 8)) + '亿' + getResult(num.slice(-8))
  } 
  return getResult(num)
}

console.log(toChineseNum(1000005600454456))

复制代码

02-数字添加逗号


题目描述:

完成函数 commafy,它接受一个数字作为参数,返回一个字符串,可以把整数部分从右到左每三位数添加一个逗号,如:12000000.11 转化为 12,000,000.11


思路:

  1. 此题主要考察思路是否严谨,分为正数与负数,整数与非整数
  2. 加逗号主要是处理整数部分,每隔3位插入一个逗号,可以使用数组的 splice() 插入逗号

参考答案:


function commafy (num) {
    let numStr = num + '';
    let arr = num < 0 ? numStr.slice(1).split('.') : numStr.split('.');
    let a = arr[0].split(''); // 整数部分切割成数组
    for(let i = a.length - 3; i > 0; i=i-3) {
      a.splice(i, 0, ',')  
    }
    let res = arr[1] ? a.join('') + '.' + arr[1] : a.join('')
    return num < 0 ? '-' + res : res;
}

console.log(commafy(12564654.456456)) // 12,564,654.456456
复制代码

03-16进制颜色值转RGB值


题目描述:

完成函数 hexToRGB,它的作用将 16 进制颜色值转换成 RGB 值:

hexToRGB('#F0F0F0') // => rgb(240, 240, 240)
hexToRGB('#9fc') // => rgb(153, 255, 204)
hexToRGB('无效颜色') // => null
复制代码

思路:

16 进制转十进制如何计算。A,B,C,D,E,F,不区分大小写这六个字母分别表示10,11,12,13,14,15 首先判断是否是16进制的颜色,特点以#号开头,其余是字母和数字,6位或者3位。 正则匹配如何只匹配3位数字或字母,或只匹配 6 位数字或字母


参考答案:

const hexToRGB = (hex) => {
  if (!/(^\#([a-fA-F0-9]{3})$)|(^\#([a-fA-F0-9]{6})$)/g.test(hex)) return null
  let allNumberStr = '0123456789abcdef' // 十六进制的所有数字
  let len = hex.slice(1).length;
  let str = len === 6 ? hex.slice(1) : hex.slice(1)[0].repeat(2) + hex.slice(1)[1].repeat(2) + hex.slice(1)[2].repeat(2);
  let arrStr = str.split('');
  let newArrStr = arrStr.map((item, index) => {
    return allNumberStr.indexOf((item + '').toLowerCase())
  })
  let num1 = newArrStr[0] * 16 + newArrStr[1];
  let num2 = newArrStr[2] * 16 + newArrStr[3];
  let num3 = newArrStr[4] * 16 + newArrStr[5];
  return `rgb(${num1}, ${num2}, ${num3})`
}

console.log(hexToRGB('#fffaaa'))
复制代码

04-转换驼峰命名


题目描述:

小科去了一家新的公司做前端主管,发现里面的前端代码有一部分是 C/C++ 程序员写的,他们喜欢用下划线命名,例如: is_good。小科决定写个脚本来全部替换掉这些变量名。

完成 toCamelCaseVar 函数,它可以接受一个字符串作为参数,可以把类似于 is_good 这样的变量名替换成 isGood。


思路:

  • 可以利用正则及字符串方法 replace() 实现

参考答案:

const toCamelCaseVar = (variable) => {
  variable = variable.replace(/[\_|-](\w)/g, function (all, letter) {
    return letter.toUpperCase();
  });
  return variable.slice(0, 1).toLowerCase() + variable.slice(1)
 }

console.log(toCamelCaseVar('Foo_style_css')) // fooStyleCss
console.log(toCamelCaseVar('Foo-style-css')) // fooStyleCss
复制代码

05-监听数组变化


题目描述:

在前端的 MVVM 框架当中,我们经常需要监听数据的变化,而数组是需要监听的重要对象。请你完成 ObserverableArray,它的实例和普通的数组实例功能相同,但是当调用:push,pop,shift,unshift,splice,sort,reverse 这些方法的时候,除了执行相同的操作,还会把方法名打印出来。 例如:

const arr = new ObserverableArray()

arr.push('Good') // => 打印 'push',a 变成了 ['Good']
复制代码

注意,你不能修改 Array 的 prototype。还有函数 return 的值和原生的操作保持一致。


思路:

  • 可以利用 es6的 Proxy 监听实现实现

参考答案:


function ObserverableArray() {
  return new Proxy([], {
    get(target, propKey) {
      const matArr = ['push', 'pop', 'shift', 'unshift', 'splice', 'sort', 'reverse'];
      matArr.indexOf(propKey) > -1 && console.log(propKey);
      return target[propKey]
    }
  })
}
const arr = new ObserverableArray()

arr.push('Good') // => 打印 'push',a 变成了 ['Good']
arr.push('Good2') // => 打印 'push',a 变成了 ['Good', 'Good2']
arr.unshift('Good2') // => 打印 'unshift',a 变成了 ['Good2','Good', 'Good2']
console.log(arr) // ['Good2','Good', 'Good2']

复制代码

06-验证一个数是否是素数


思路:

素数也称为质数,质数是指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数。有一下几种情况:

  1. 如果这个数是 2 或 3,一定是素数;

  2. 如果是偶数,一定不是素数

  3. 如果这个数不能被 3 至它的平方根中的任一数整除,m 必定是素数。而且除数可以每次递增2(排除偶数)


参考答案:

function isPrime(num){
  if (typeof num !== 'number') {
    throw new TypeError('num should be number')
  }
	if (num === 2 || num === 3) {
		return true;
	};
	if (num % 2 === 0) {
		return false;
	};
	let divisor = 3, limit = Math.sqrt(num);
	while(limit >= divisor){
		if (num % divisor === 0) {
			return false;
		}
		else {
			divisor += 2;
		}
	}
	return true;
}
console.log(isPrime(30));  // false
console.log(isPrime(31));  // true
复制代码

07-斐波那契数列


什么是斐波那契数列:

斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上,斐波那契数列以如下被以递推的方法定义:F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2)(n>=3,n∈N*)在现代物理、准晶体结构、化学等领域,斐波纳契数列都有直接的应用,为此,美国数学会从 1963 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志,用于专门刊载这方面的研究成果。


思路:

从上面的定义得出,斐波那契数列的三种情况:

  1. F(1)=1
  2. F(2)=1
  3. F(n)=F(n-1)+F(n-2)(n>=3,n∈N\*)

试用递归实现

function fibonacci(n) {
  if (n <= 0) {
    return 0;
  }
  if (n == 1) {
    return 1;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}
console.time('fibonacci');
console.log(fibonacci(40)); // 102334155
console.timeEnd('fibonacci'); // 1106.791ms
复制代码

仔细分析该递归,你会发现 f(40) = f(39) + f(38) , f(39) = f(38) + f(37) , f(38) = f(37) + f(36) , 算 f(40) 和 f(39) 都会计算 f(38),多算了一遍 f(38),会有明显的效率问题。这种是从上至下计算(40-1),我们换种思路,从下至上试试(1-40),首先根据 f(0)和 f(1)计算出 f(2),再根据 f(1)和 f(2)计算出 f(3)……以此类推就可以计算出第 n 项。时间复杂度 O(n)。:

function fibonacci(n) {
  if (n <= 0) {
    return 0;
  }
  if (n == 1) {
    return 1;
  }
  let fiboOne = 1,
    fiboTwo = 0,
    fiboSum = 0;
  for (let i = 2; i <= n; i++) {
    fiboSum = fiboOne + fiboTwo;
    fiboTwo = fiboOne;
    fiboOne = fiboSum;
  }
  return fiboSum;
}
console.time('fibonacci');
console.log(fibonacci(40)); //102334155
console.timeEnd('fibonacci'); // 4.376ms
复制代码

可以看出,时间上少了将近 1000ms,数字越大,耗时差越大


参考答案:

function fibonacci(n) {
  if (n <= 0) {
    return 0;
  }
  if (n == 1) {
    return 1;
  }
  let fiboOne = 1,
    fiboTwo = 0,
    fiboSum = 0;
  for (let i = 2; i <= n; i++) {
    fiboSum = fiboOne + fiboTwo;
    fiboTwo = fiboOne;
    fiboOne = fiboSum;
  }
  return fiboSum;
}
复制代码

08-两数相加


题目描述:

请你用 javascript 实现两个字符串数字相加(大数相加)?


思路:

  • 这道题考查两个超过 js 最大数值的数相加,可运用小学数学加法规律实现. 个十百千万...位相加,满十进一。

参考答案:

function add(a, b) {
  // 看看两个字符串长度相差多少,小的在前面补0, 如 10000 和 1, 补0后为 10000 和 00001
  let leng = Math.abs(a.length - b.length);
  if (a.length > b.length) {
    b = Array(leng).join('0') + '0' + b;
  } else if (a.length < b.length) {
    a = Array(leng).join('0') + '0' + a;
  }
  // 将字符串转化为数组并且倒装,如同小学加法从个位开始算起
  let textArrA = a.split('').reverse(),
    textArrB = b.split('').reverse(),
    resultArr = [];

  // 对数组进行循环
  for (let i = 0; i < a.length; i++) {
    // 求和,和小于10,则将和放进目标数组,若大于10,将除以10将余数放进目标数组,然后textArrA数组的下一位 + 1(textArrB数组也可以,选一个即可)
    let sum = parseInt(textArrA[i]) + parseInt(textArrB[i]);

    // 这里判断是否是最高位数值相加,即i === a.length - 1, 如果是不用取余直接放进去
    if (parseInt(sum / 10) === 0 || i === a.length - 1) {
      resultArr.push(sum);
    } else {
      resultArr.push(sum % 10);
      textArrA[i + 1] = parseInt(textArrA[i + 1]) + 1;
    }
  }
  // 最后将目标数组倒装一下,再转成字符串
  return resultArr.reverse().join('');
}

console.log(add('1045747', '10')); // 1045757
复制代码

09-最大公约数&最小公倍数


最大公约数:能同时被两数整除的最大数字

最小公倍数:能同时整除两数的最小数字


思路:

  • 获取两数孰大孰小,若是最大公约数,则从小值逐一递减,找到第一个能被两数同时整除的数即为最大公约数;若是最小公倍数,则从大值逐一递乘,找到第一个能同时整除两数的的数即为最小公倍数

参考答案:

// 最大公约数
function maxDivisor(num1, num2) {
  let max = num1 > num2 ? num1 : num2,
    min = num1 > num2 ? num2 : num1;
  for (var i = min; i >= 1; i--) {
    if (max % i == 0 && min % i == 0) {
      return i;
    }
  }
}

console.log(maxDivisor(60, 30)); // 30

// 最小公倍数
function minDivisor(num1, num2) {
  let max = num1 > num2 ? num1 : num2,
    min = num1 > num2 ? num2 : num1,
    result = 0;
  // 这个循环,当两数同为质数时,终止的最大条件值为 i = min
  for (var i = 1; i <= min; i++) {
    result = i * max;
    if (result % max == 0 && result % min == 0) {
      return result;
    }
  }
}
console.log(minDivisor(6, 8)); // 24
复制代码

10-验证是否为回文


什么是回文?

回文指从左往右和从右往左读到相同内容的文字。比如: aba,abba,level。


思路:

  1. 使用数组方法生成倒装的新字符串与原字符串对比
function isPalindrome(str) {
  str = '' + str;
  if (!str || str.length < 2) {
    return false;
  }
  return (
    Array.from(str)
      .reverse()
      .join('') === str
  );
}
复制代码
  1. 通过倒序循环生成新字符串与原字符串对比
function isPalindrome(str) {
  str = '' + str;
  if (!str || str.length < 2) {
    return false;
  }
  var newStr = '';
  for (var i = str.length - 1; i >= 0; i--) {
    newStr += str[i];
  }
  return str1 === str;
}
复制代码
  1. 以中间点为基点,从头至中与从尾至中逐一字符串进行对比,若有一个不同,则 return false. 这种方法循环次数最少,效率最高
function isPalindrome(str) {
  str = '' + str;
  if (!str || str.length < 2) {
    return false;
  }
  for (let i = 0; i < str.length / 2; i++) {
    if (str[i] !== str[str.length - 1 - i]) {
      return false;
    }
  }
  return true;
}
复制代码