Q1 判断一个单词是否是回文？
回文是指把相同的词汇或句子，在下文中调换位置或颠倒过来，产生首尾回环的情趣，叫做回文，也叫回环。比如 mamam redivider .
很多人拿到这样的题目非常容易想到用for 将字符串颠倒字母顺序然后匹配就行了。其实重要的考察的就是对于reverse的实现。其实我们可以利用现成的函数，将字符串转换成数组，这个思路很重要，我们可以拥有更多的自由度去进行字符串的一些操作。
function checkPalindrom(str) {
return str == str.split('').reverse().join('');
}
console.log(checkPalindrom('mamam')); //true
console.log(checkPalindrom('banana')); //false
split() 方法用于把一个字符串分割成字符串数组。
reverse() 方法用于颠倒数组中元素的顺序。
join() 方法用于把数组中的所有元素放入一个字符串。元素是通过指定的分隔符进行分隔的。
Q2 去掉一组整型数组重复的值
比如 输入: [1,13,24,11,11,14,1,2]， 输出: [1,13,24,11,14,2] ，需要去掉重复的11 和 1 这两个元素。
主要考察个人对Object的使用，利用key来进行筛选。
let unique = function(arr) {
let hashTable = {};
let data = [];
for(let i=0,l=arr.length;i<l;i++) {
if(!hashTable[arr[i]]) {
hashTable[arr[i]] = true;
data.push(arr[i]);
}
}
return data
}
var arr=[1,13,24,11,11,14,1,2]
console.log(unique(arr)) //[1, 13, 24, 11, 14, 2]
还有一种方法 利用ES6的Set
var arr=[1,13,24,11,11,14,1,2];
let uniqueES6= function(arr){
return Array.from(new Set(arr))
}
console.log(uniqueES6(arr))//[1, 13, 24, 11, 14, 2]
Q3 统计一个字符串出现最多的字母
给出一段英文连续的英文字符窜，找出重复出现次数最多的字母
比如： 输入：afjghdfraaaasdenas 输出 ： a
前面出现过去重的算法，这里需要是统计重复次数。
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('gffhghjllyesdfffnmfffssssffffjjffff')) //f
Q4 排序算法
如果说到算法题目的话，应该大多都是比较开放的题目，不限定算法的实现，但是一定要求掌握其中的几种。
冒泡排序
插入排序
快速排序
选择排序
let arr = [4,6,32,11,5,667,39,56,78,2,42,7];
/*冒泡排序*/
function bubbleSort(arr){
for(var i=0;i<arr.length-1;i++){
for(var j=0;j<arr.length-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(bubbleSort(arr))
/*插入排序*/
function insertionSort(array) {
console.time('插入排序耗时：');
for (var i = 1; i < array.length; i++) {
var key = array[i];
var j = i - 1;
while ( array[j] > key) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = key;
}
console.timeEnd('插入排序耗时：');
return array;
}
console.log(insertionSort(arr));
/*快速排序*/
function quickSort(arr){
//如果数组<=1,则直接返回
if(arr.length<=1){return arr;}
var pivotIndex=Math.floor(arr.length/2);
//找基准，并把基准从原数组删除
var pivot=arr.splice(pivotIndex,1)[0];
//定义左右数组
var left=[];
var right=[];
//比基准小的放在left，比基准大的放在right
for(var i=0;i<arr.length;i++){
if(arr[i]<=pivot){
left.push(arr[i]);
}
else{
right.push(arr[i]);
}
}
//递归
return quickSort(left).concat([pivot],quickSort(right));
}
console.log(quickSort(arr))
// 选择排序
var arr = [8,3,9,12,45,23,4,89,48,63,27,53,56,98]
function selectSort(arr){
var len = arr.length
for(var i= 0;i<len-1;i++){
for(var j = i+1;j<len;j++){
if(arr[i]>arr[j]){
var temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
}
}
return arr
}
console.log(selectSort(arr))
// 选择排序的思想是：把每一个数都与第一个数比较，如果小于第一个数，就把它们交换位置；这样一轮下来，最小的数就排到了最前面；重复n-1轮，就实现了选择排序
// 选择排序和冒泡排序思想上有些相近
Q5 不借助临时变量，进行两个整数的交换
举例：输入 a = 2, b = 4 输出 a = 4, b =2
这种问题非常巧妙，需要大家跳出惯有的思维，利用 a , b进行置换。
主要是利用 + - 去进行运算，类似 a = a + ( b - a) 实际上等同于最后 的 a = b;
let a=2 ,b=4
function swap(a , b) {
b = b - a;
a = a + b;
b = a - b;
return [a,b];
}
console.log(swap(a , b));
Q6 使用canvas 绘制一个有限度的斐波那契数列的曲线
斐波那契数列曲线
数列长度限定在10.
斐波那契数列，又称黄金分割数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列主要考察递归的调用。我们一般都知道定义
fibo[i] = fibo[i-1]+fibo[i-2];
var canvas = document.querySelector('canvas');
canvas.width = 600;
canvas.height = 480;
var coor = {
x: 300,
y: 240,
};
var ctx = canvas.getContext('2d');
function draw(r, n ,prevR) {
if(n>2) {
switch(n%4) {
case 0 :
coor.y = coor.y - 5 * prevR;
coor.y = coor.y + 5 * r;
break;
case 1 :
coor.x = coor.x + 5 * prevR;
coor.x = coor.x - 5 * r;
break;
case 2 :
coor.y = coor.y + 5 * prevR;
coor.y = coor.y - 5 * r;
break;
case 3 :
coor.x = coor.x - 5 * prevR;
coor.x = coor.x + 5 * r;
break;
}
}
ctx.beginPath();
ctx.arc(coor.x,coor.y,5*r,Math.PI*0.5*(n),Math.PI*0.5*(n-1),true);
if(n>1) {
switch(n%4) {
case 0 :
ctx.moveTo(coor.x - 5*r,coor.y);
break;
case 1 :
ctx.moveTo(coor.x,coor.y + 5*r);
break;
case 2 :
ctx.moveTo(coor.x + 5*r,coor.y);
break;
case 3 :
ctx.moveTo(coor.x,coor.y-5*r);
break;
}
}
ctx.lineWidth = 1;
ctx.strokeStyle = '#fff';
ctx.stroke();
}
/*生成斐波那契数组的方法*/
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;
}
console.log(getFibonacci(10)) //[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
var data = getFibonacci(10);
for(var i = 0,l=data.length;i<l;i++) {
if(data[i]!=0) {
draw(data[i],i,data[i-1]);
}
}
Q7 找出下列正数组的最大差值
比如： 输入 [10,5,11,7,8,9] 输出 6
这是通过一道题目去测试对于基本的数组的最大值的查找，很明显我们知道，最大差值肯定是一个数组中最大值与最小值的差。
var arr = [16,5,111,7,21,9]
function getMaxProfit(arr) {
const item1 = Math.max.apply( null, arr );
const item2 = Math.min.apply( null, arr );
return item1 - item2;
}
console.log(getMaxProfit(arr)) //106
ES6的方法
var arr = [16,5,111,7,21,9]
//ES6
function getMaxProfitES6(arr){
const item1 = Math.max(...arr);
const item2 = Math.min(...arr);
return item1 - item2;
}
console.log(getMaxProfitES6(arr));
Q8 随机生成指定长度的字符串
实现一个算法，随机生成指制定长度的字符窜。
比如：给定 长度 8 输出 4ldkfg9j
function randomString(n) {
let str = 'abcdefghijklmnopqrstuvwxyz9876543210';
let tmp = '',
l = str.length;
for (let i = 0; i < n; i++) {
tmp += str.charAt(Math.floor(Math.random() * l));
}
return tmp;
}
console.log(randomString(8))
Q9 计算一个整数的阶乘
function factorialize(num) {
if(num<1){
return 1;
}else{
return num*factorialize(num-1);
}
}
console.log(factorialize(5)); //120
Q10 找到提供的句子中最长的单词，并计算它的长度
function findLongestWord(str) {
//转化成数组
var astr=str.split( " " );
//对数组中每个元素的字符串长度进行比较，按照字符串长度由大至小排列数组顺序。
var bstr=astr.sort(function(a,b){
return b.length-a.length;
});
//取出数组中第一个元素(也就是最大长度的字符串）
console.log(bstr[0]) //jumped
var lenMax= bstr[0].length;
//返回长度值
return lenMax;
}
console.log(findLongestWord("The quick brown fox jumped over the lazy dog"));//6
array.sort()方法默认是升序排序，如果想按照其他标准进行排序，就需要提供比较函数，该函数要比较两个值，然后返回一个用于说明这两个值的相对顺序的数字。比较函数应该具有两个参数 a 和 b，其返回值如下：
若 a 小于 b，在排序后的数组中 a 应该出现在 b 之前，则返回一个小于 0 的值。
若 a 等于 b，则返回 0。
若 a 大于 b，则返回一个大于 0 的值。
简单点：比较函数两个参数a和b，返回a-b升序，返回b-a降序
Q11 确保字符串的每个单词首字母都大写，其余部分小写。
function titleCase(str) {
var astr=str.toLowerCase().split(" ");
for(var i=0 ; i<astr.length; i++){
astr[i]=astr[i][0].toUpperCase()+astr[i].substring(1,astr[i].length);
}
var string=astr.join(" ");
return string;
}
console.log(titleCase("I'm a little tea pot"));//结果：I'm A Little Tea Pot
Q12 找出4个小数组中最大值，组成一个新数组
function largestOfFour(arr) {
var newArr=[];
for(i=0;i<arr.length;i++){
arr[i].sort(function(a,b){
return b-a;
});
newArr.push(arr[i][0]);
}
return newArr;
}
console.log(largestOfFour([[4, 5, 1, 3], [13, 27, 18, 26], [32, 35, 37, 39], [1000, 1001, 857, 1]])); //[5,27,39,1001]
Q13 比较两个数组，然后返回一个新数组，该数组的元素为两个给定数组中所有独有的数组元素。换言之，返回两个数组的差异。
方法一：
function diff(arr1, arr2) {
var newArr = [];
//过滤数组1中与数组2相等的项
var arr1Filtered=arr1.filter(function(num){
for(var i=0; i<arr2.length; i++){
if(num==arr2[i]){
return false;
}
}
return true;
});
//过滤数组2中与数组1相等的项
var arr2Filtered=arr2.filter(function(num){
for(var i=0; i<arr1.length; i++){
if(num==arr1[i]){
return false;
}
}
return true;
});
//连接两个数组
newArr=arr1Filtered.concat(arr2Filtered);
return newArr;
}
var arr1 = [1, "calf", 3, "piglet"],
arr2 = [1, "calf", 3, 4]
console.log(diff(arr1, arr2)); // ["piglet", 4]
方法二：
var arr1 = [1, "calf", 3, "piglet"],
arr2 = [1, "calf", 3, 4]
function fn(arr1,arr2){
var newArr = []
var arr1Filtered = arr1.filter(function(num){
if(arr2.indexOf(num)!=-1){
return false
}
return true
})
var arr2Filtered = arr2.filter(function(num){
if(arr1.indexOf(num)!=-1){
return false
}
return true
})
return arr1Filtered.concat(arr2Filtered)
}
console.log(fn(arr1,arr2))
Q14 写一个 function，传入两个或两个以上的数组，返回一个以给定的原始数组排序的不包含重复值的新数组。
说明：所有数组中的所有值都应该以原始顺序被包含在内，但是在最终的数组中不包含重复值。
如：unite([1, 3, 2], [5, 2, 1, 4], [2, 1]) 应该返回 [1, 3, 2, 5, 4]。
unite([1, 2, 3], [5, 2, 1, 4], [2, 1], [6, 7, 8]) 应该返回 [1, 2, 3, 5, 4, 6, 7, 8]。
方法一：
function unite(arr1, arr2, arr3) {
for(var j=1; j<arguments.length; j++){
//过滤掉第j个数组中已经在前面出现过的值
var filteredArr=arguments[j].filter(function(num){
for(var i=0; i<arr1.length; i++){
if(arr1[i]==num){
return false;
}
}
return true;
});
arr1=arr1.concat(filteredArr);
}
return arr1;
}
console.log(unite([1, 2, 3], [5, 2, 1, 4], [2, 1], [6, 7, 8])); //[1,2,3,5,4,6,7,8]
方法二：
function unite(){
var arr = arguments[0]
for(let i = 0;i<arguments.length;i++){
var filterArr = arguments[i].filter(function(num){
if(arr.indexOf(num)!=-1){
return false
}
return true
})
arr= arr.concat(filterArr)
}
return arr
}
console.log(unite([1, 2, 3], [5, 2, 1, 4], [2, 1], [6, 7, 8]));
Q15 求小于等于给定数值的质数（素数）之和。
说明：只有 1 和它本身两个约数的数叫质数。例如，2 是质数，因为它只能被 1 和 2 整除。1 不是质数，因为它只能被自身整除。给定的数不一定是质数。
如：sumPrimes(10) 应该返回 17。
function sumPrimes(num) {
//将所有小于等于num的质数放进一个数组
var arr=[];
//1不是质数，从2开始循环，需算上num
for(var i=2; i<=num; i++){
var j=2;
//判断i能否被从2开始的数整除
while(i%j!==0){
j++;
}
//判断这个数是不是自身，是则加进数组
if(i==j){
arr.push(i);
}
}
//对数组求和
var result=arr.reduce(function (a,b){return a+b;});
return result;
}
console.log(sumPrimes(10)) ///17
reduce() 方法接收一个函数作为累加器，数组中的每个值（从左到右）开始缩减，最终计算为一个值。
reduce() 可以作为一个高阶函数，用于函数的 compose。
注意: reduce() 对于空数组是不会执行回调函数的。
另外一种写法
function sumFun(num){
let sum=0
for(let i=2;i<=num;i++){
var j= 2
while(i%j !==0){
j++
}
if(j==i){
sum+=j
}
}
return sum
}
console.log(sumFun(11)) //18
方法三
function getPrimes(n){
var arr = []
for(var i=2;i<=n;i++){
var flag = true
for(var j = 2;j<=Math.sqrt(i);j++){
if(i%j==0){
flag = false
break
}
}
if(flag){
arr.push(i)
}
}
//对数组求和
var result=arr.reduce(function (a,b){return a+b;});
return result
}
方法四
function getPrimes(n){
var prime = []
var arr = []
for(var i = 2;i<=n;i++){
if(!prime[i]){
arr.push(i)
for (var j = i; j*i <=n; j++) {
prime[j*i]=true;
}
}
}
//对数组求和
var result=arr.reduce(function (a,b){return a+b;});
return result
}
Q16 写一个 function，它浏览数组（第一个参数）并返回数组中第一个通过某种方法（第二个参数）验证的元素。
如：find([1, 3, 5, 8, 9, 10], function(num) { return num % 2 === 0; }) 应该返回 8。
find([1, 3, 5, 9], function(num) { return num % 2 === 0; }) 应该返回 undefined。
function find(arr, func) {
var newArr=arr.filter(func);
return newArr[0];
}
console.log(find([1, 3, 5, 8, 9, 10], function(num) { return num % 2 === 0; })) //8
Q17 对嵌套的数组进行扁平化处理。你必须考虑到不同层级的嵌套。
如：steamroller([1, [2], [3, [[4]]]]) 应该返回 [1, 2, 3, 4]。
steamroller([1, [], [3, [[4]]]]) 应该返回 [1, 3, 4]。
steamroller([1, {}, [3, [[4]]]]) 应该返回 [1, {}, 3, 4]。
1、
function steamroller(arr) {
var newArr=[];
for(var i=0; i<arr.length; i++){
if(!Array.isArray(arr[i])){
newArr.push(arr[i]);
}else{
newArr=newArr.concat(steamroller(arr[i]));
}
}
return newArr;
}
console.log(steamroller([1, {}, [3, [[4]]]])) //[1, {}, 3, 4]
此题的解法是在一个for循环中使用了递归，在for循环中使用递归时，不会影响for循环的进程。
2、另外一种方法：
function flatten(arr){
while(arr.some(item=>Array.isArray(item))){
arr = [].concat(...arr)
}
return arr;
}
console.log(flatten([1, {}, [3, [[4]]]]));//[1, 2, 3]
some() 方法用于检测数组中的元素是否满足指定条件（函数提供）。
some() 方法会依次执行数组的每个元素：
如果有一个元素满足条件，则表达式返回true , 剩余的元素不会再执行检测。
如果没有满足条件的元素，则返回false。
注意：some() 不会对空数组进行检测。
注意：some() 不会改变原始数组。
3、es6新增的数组实例方法flat()
[1, 2, [3, 4]].flat()
// [1, 2, 3, 4]
flat()默认只会“拉平”一层，如果想要“拉平”多层的嵌套数组，可以将flat()方法的参数写成一个整数，表示想要拉平的层数，默认为1。
[1, 2, [3, [4, 5]]].flat()
// [1, 2, 3, [4, 5]]
[1, 2, [3, [4, 5]]].flat(2)
// [1, 2, 3, 4, 5]
如果不管有多少层嵌套，都要转成一维数组，可以用Infinity关键字作为参数。
[1, [2, [3]]].flat(Infinity)
// [1, 2, 3]
如果原数组有空位，flat()方法会跳过空位。
[1, 2, , 4, 5].flat()
// [1, 2, 4, 5]
4、如果数组中元素都是字符串，可以利用数组toString()方法
例如：['a',[b],c,[[d],e,[f,[g,h]]]]
var arr= ['a',[`b`],`c`,[[`d`],`e`,[`f`,[`g`,`h`]]]]
console.log(arr.toString().split(','))
Q18 二分查找
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;
};
var arr=[2,4,6,9,11,25,28,36,44,47,67,76,79],
key=36;
console.log(binary_search(arr,key)) //7
因为二分查找每次排除掉一半的不适合值，所以对于n个元素的情况：
一次二分剩下：n/2
两次二分剩下：n/2/2 = n/4
……
m次二分剩下：n/(2^m)
在最坏情况下是在排除到只剩下最后一个值之后得到结果，所以为
n/(2^m)=1;
2^m=n;
所以时间复杂度为：log2(n)
作者：指尖跳动
链接：https://www.jianshu.com/p/2f38ac50c63a
来源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
