前端知识编程题整理

常见排序算法的JS实现

排序算法图片总结(图片来源于网络):

排序对比:
image

排序分类:
image

冒泡排序

每一趟结束都能确定一个元素的最终位置

1
2
3
4
5
6
7
8
9
10
11
12
13
var bubbleSort = function(arr){
for(var i=0;i<arr.length;i++){
for(var j=0;j<arr.length-1-i;j++){
if(arr[j] > arr[j+1]){
temp = arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
return arr;
}

快速排序实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var quickSort = function(arr){
if(arr.length <= 1)
return arr;
var pivotIndex = Math.flood(arr.length/2);
var pivot = arr.splice(pivotIndex)[0]; //通过数组的splice方法删除该基准数
var left =[];
var 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)); //递归形式不断重复划分基准左右两边的数组,直到剩下一个元素;
}

前端技能编程

根据包名,在指定空间中创建对象

输入描述:

namespace({a: {test: 1, b: 2}}, ‘a.b.c.d’)

输出描述:

{a: {test: 1, b: {c: {d: {}}}}}

通过代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function namespace(oNamespace, sPackage) {
var arr = sPackage.split("."); //拆分输入字符串
var oName = oNamespace; //引用类型的赋值,使得oName相当于指针,方便操作;
for(var i=0;i<arr.length;i++){
//判断对象是否已包含该属性,可以使用in操作符或者hasOwnProperty方法,区别在于in判断有无该属性,而hasOwnProperty()方法判断该属性是否来自对象实例,是的话true;
if(oName.hasOwnProperty(arr[i]) ){
if(typeof oName[arr[i]] !== 'object'){ //如果该属性不是对象,将此属性设为空对象
oName[arr[i]] = {};
}
}else{
oName[arr[i]] = {}; // 属性不在对象中或者是原型链上属性时,建立此属性设为空对象
}
oName = oName[arr[i]]; //指向下一层
}
return oNamespace; //返回对象
}


字符串字符统计

题目描述

统计字符串中每个字符的出现频率,返回一个 Object,key 为统计字符,value 为出现频率

  1. 不限制 key 的顺序
  2. 输入的字符串参数不会为空
  3. 忽略空白字符

示例1
输入

‘hello world’

输出

{h: 1, e: 1, l: 3, o: 2, w: 1, r: 1, d: 1}

通过代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function count(str) {
var obj = {}; //创建对象,利用对象的属性检测方法方便操作
//字符串去除空格,/S为非空字符,g是全局;也可以使用str.replace(/\s/g,'')
var str1 = str.match(/\S/g);
for(var j =0 ; j<str1.length; j++){
if(obj.hasOwnProperty(str1[j])){ //去重统计操作
obj[str1[j]]++; //此处只能使用方括号表示法,不能使用点表示法?
}else{
obj[str1[j]]=1;
}
}
return obj;
}
`


数组去重

题目描述

为 Array 对象添加一个去除重复项的方法

示例1
输入

[false, true, undefined, null, NaN, 0, 1, {}, {}, ‘a’, ‘a’, NaN]

输出

[false, true, undefined, null, NaN, 0, 1, {}, {}, ‘a’]

通过代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Array.prototype.uniq = function () {
var flag = false;
for(var i=0;i<this.length;i++){
if(this[i] !== this[i] && typeof this[i] != 'object'){ //找出NaN,并做下标记;此处的{}!=={} 值为true
flag = true;
}
for(var j=i+1;j<this.length;){
if(this[i] === this[j] || (flag && this[j] !== this[j])){ //找到相同的项,使用splice方法剔除
this.splice(j,1);
}else{
j++;
}
}
}
return this;
}

或者利用辅助数组的indexOf方法,减少空间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Array.prototype.uniq = function () {
var flag = false;
var arr=[];
for(var i=0;i<this.length;i++){
if(arr.indexOf(this[i]) == -1){ //查找元素在数组中的位置信息,没找到或者不能严格相等(===)的值返回-1
if(this[i] !== this[i]){ //找到NaN的情况
if(!flag){
arr.push(this[i]);
flag = true;
}
}else{
arr.push(this[i]);
}
}
}
return arr;
}

以上都是两层循环,下面利用散列表:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Array.prototype.unique = function () {
var hash = {}, result = [], type = '', item;
for (var i = 0; i < this.length; i++) {
item = this[i];
type = Object.prototype.toString.call(item);
if ( !hash[item + type] ) {
hash[item + type] = true;
result.push(item);
}
}
return result;
}


获取字符串长度

题目描述

如果第二个参数 bUnicode255For1 === true,则所有字符长度为 1
否则如果字符 Unicode 编码 > 255 则长度为 2

示例1
输入

‘hello world, 牛客’, false

输出

17

通过代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
function strLength(s, bUnicode255For1) {
var len =s.length;
if(bUnicode255For1 ){
return s.length;
}else{
for(var i=0;i<s.length;i++){
if(s.charCodeAt(i) > 255){ //charCodeAt()方法可返回指定位置的字符的 Unicode 编码。这个返回值是 0 - 65535 之间的整数
len++;
}
}
return len;
}
}


DOM节点查找

题目描述

查找两个节点的最近的一个共同父节点,可以包括节点自身

输入描述:

oNode1 和 oNode2 在同一文档中,且不会为相同的节点

通过代码:

1
2
3
4
5
6
7
8
9
10
11
function commonParentNode(oNode1, oNode2) {
if(oNode1.parentNode == oNode2){
return oNode2;
}
for(;oNode1;oNode1=oNode1.parentNode){
if(oNode1.contains(oNode2)){ //利用节点的contains()方法,查找有无此后代节点
return oNode1;
}
}
}


修改this指向

题目描述

封装函数 f,使 f 的 this 指向指定的对象

示例1
输入

输出

通过代码:

1
2
3
function bindThis(f, oTarget) {
return f.bind(oTarget); //bind 是返回对应函数,便于稍后调用;apply 、call 则是立即调用
}


1
2
3
4
5
function bindThis(f, oTarget) {
return function(){
return f.apply(oTarget,arguments); //由于参数个数不确定,在此使用apply()比call()方法更合适
};
}


移除数组中的元素(删除特定值,不改原数组)

题目描述

移除数组 arr 中的所有值与 item 相等的元素。不要直接修改数组 arr,结果返回新的数组

示例1
输入

[1, 2, 3, 4, 2], 2

输出

[1, 3, 4]

通过代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
function remove(arr, item) {
if(Object.prototype.toString.call(arr) !== '[object Array]'){ //检测输入参数是否为数组
return false;
}
if(arr.length < 0){
return false;
}
return arr.filter(function(element){ //利用数组的filter()方法过筛选符合回调函数的数组元素,返回一个新数组
return element !== item;
});
}


移除数组中的元素(删除特定值,直接改)

题目描述

移除数组 arr 中的所有值与 item 相等的元素,直接在给定的 arr 数组上进行操作,并将结果返回

示例1
输入

[1, 2, 2, 3, 4, 2, 2], 2

输出

[1, 3, 4]

通过代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function removeWithoutCopy(arr, item) {
if(Object.prototype.toString.call(arr) !== '[object Array]'){
return false;
}
if(arr.length == 0){
return arr;
}
//利用递归实现
if(arr.indexOf(item) == -1){
return arr;
}else{
arr.splice(arr.indexOf(item),1); //利用数组的indexOf检测出存在位置,再利用splice方法(参数一为删除位置,参数二为删除数量)删除
removeWithoutCopy(arr,item); //把改动后的数组递归,继续利用indexOf()方法检测
}
return arr;
}


添加元素(在数组末尾添加,不改原数组)

题目描述

在数组 arr 末尾添加元素 item。不要直接修改数组 arr,结果返回新的数组

示例1
输入

[1, 2, 3, 4], 10

输出

[1, 2, 3, 4, 10]

通过代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function append(arr, item) {
if(Object.prototype.toString.call(arr) !== '[object Array]'){
return false;
}
var a =[];
if(Array.prototype.copyWithin){ //copyWithin()方法检测,部分浏览器不支持
a = arr.copyWithin(); //copyWithin()方法浅拷贝数组对象,生成返回新数组
}else{
for(var i=0;i<arr.length;i++){ //不支持copyWithin()方法时,迭代实现
a.push(arr[i]);
}
}
a.push(item); //在数组尾部插入元素,使用push()方法
return a;
}


删除数组最后一个元素(返回新数组,多种方式实现)

题目描述

删除数组 arr 最后一个元素。不要直接修改数组 arr,结果返回新的数组

示例1
输入

[1, 2, 3, 4]

输出

[1, 2, 3]

通过代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
function truncate(arr) {
if(Object.prototype.toString.call(arr) !== '[object Array]'){
return false;
}
if(arr.length == 0){
return false;
}
//push 简单迭代
var a=[];
for(var i=0; i<arr.length-1;i++){
a.push(arr[i]);
}
return a;
//slice //浅拷贝
return arr.slice(0,-1);
//concat //连接数组,为空时返回新的数组(浅拷贝)
var a=[];
a = arr.concat();
a.pop();
return a;
//filter 返回符合条件的项的新数组
return arr.filter(function(e){
return e!=arr[arr.length-1];
});
//push.apply+pop 利用apply()方法参数传递
var a=[];
a.push.apply(a,arr);
a.pop();
return a;
//join()+split()+pop() 依据join特有的不会改变原数组的特性,但是输出的数组变成字符串数组
var a=arr.join('').split('');
a.pop();
return a;
}


添加元素(返回新数组,多种方式实现)

题目描述

在数组 arr 开头添加元素 item。不要直接修改数组 arr,结果返回新的数组

示例1
输入

[1, 2, 3, 4], 10

输出

[10, 1, 2, 3, 4]

通过代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function prepend(arr, item) {
//数组类型检测
//apply()方法
//var a =[];
//a.push.apply(a,arr);
//a.unshift(item);
//return a;
//slice()方法
//var a = arr.slice();
//a.unshift(item);
//return a;
//filter()方法
//var a = [];
//a = arr.filter(function(e){
// return true;
//});
//a.unshift(item);
//return a;
//concat()方法
var a =arr.concat();
a.unshift(item);
return a;
//或者迭代
}


查找重复元素

题目描述

找出数组 arr 中重复出现过的元素

示例1
输入

[1, 2, 4, 4, 3, 3, 1, 5, 3]

输出

[1, 3, 4]

通过代码:

1
2
3
4
5
6
7
8
9
function duplicates(arr) {
var a =[];
arr.forEach(function(e){ //通过forEach()方法对每项元素检查
if(arr.indexOf(e) != arr.lastIndexOf(e) && a.indexOf(e) == -1){ //巧用indexOf()与lastIndexOf()方法,虽然查找方向不同,但返回的都是从左到右元素所在的位置,不等时说明有重复项;再利用indexOf()判断新数组中是否有该元素;没有则添加
a.push(e);
}
});
return a.sort(); //由于所给示例有排序,此处使用sort()方法
}


查找元素位置

题目描述

在数组 arr 中,查找值与 item 相等的元素出现的所有位置

示例1
输入

‘abcdefabc’

输出

[0, 6]

通过代码:

1
2
3
4
5
6
7
function findAllOccurrences(arr, target) {
var result=[];
arr.filter(function(item,index){
return item===target&&result.push(index); //在对每项元素的检查操作中,将位置信息放进新数组
});
return result;
}


正确的函数定义

题目描述

请修复给定的 js 代码中,函数定义存在的问题

示例1
输入

true

输出

a

原错误代码:

1
2
3
4
5
6
7
8
9
function functions(flag) {
if (flag) {
function getValue() { return 'a'; } //函数声明不能放在if语句中,else内的函数总是覆盖if中的函数
} else {
function getValue() { return 'b'; }
}
return getValue();
}

通过代码:

1
2
3
4
5
6
7
8
9
10
function functions(flag) {
if (flag) {
var getValue = function() { return 'a'; } //利用函数表达式的方式修正错误
} else {
var getValue = function() { return 'b'; }
}
return getValue();
}
}


计时器

题目描述

实现一个打点计时器,要求
1、从 start 到 end(包含 start 和 end),每隔 100 毫秒 console.log 一个数字,每次数字增幅为 1
2、返回的对象中需要包含一个 cancel 方法,用于停止定时操作
3、第一个数需要立即输出

通过代码:

1
2
3
4
5
6
7
8
9
10
11
function count(start, end) {
if(start <= end){
console.log(start++);
t = setTimeout(function(){count(start,end)},100); //通过setTimeout()方法,定时执行函数
}
return {
cancel: function (){
clearTimeout(t);
}
}
}

或者使用setInterval()方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function count(start, end) {
console.log(start++);
var t = setInterval(function (){
if(start <= end){
console.log(start++);
}
},100);
return {
cancel: function (){
clearTimeout(t);
}
}
}

setTimeout()和setInterval()方法的差别:

1
2
3
4
5
6
7
function run(){
// 其他代码
setTimeout(function(){
run();
}, 10000);
}
run();

setTimeout()方法执行时间由“其他代码决定”,实际执行时间是其他代码执行时间 与 10s 的最大值;

1
2
3
setInterval(function(){
run();
}, 10000);

而setInterval, 不会有上面的问题, 但是如果run()的执行时间, 操作大于10s, 那么甚至可能跳过任务;

二次封装函数

题目描述

实现函数 partialUsingArguments,调用之后满足如下条件:
1、返回一个函数 result
2、调用 result 之后,返回的结果与调用函数 fn 的结果一致
3、fn 的调用参数为 partialUsingArguments 的第一个参数之后的全部参数以及 result 的调用参数

示例1
输入

输出

通过代码:

1
2
3
4
5
6
7
8
function partialUsingArguments(fn) {
var arr = Array.prototype.slice.call(arguments); //因为要保留partialUsingArguments函数参数的第一项以后参数,需要使用数组操作方法,故需要转换为数组
arr.shift();
var result = function(){
return fn.apply(this,arr.concat([].slice.call(arguments))); // 合并partialUsingArguments 函数的第一个参数之后的全部参数以及 result 的调用参数
};
return result;
}

柯里化

题目描述

已知 fn 为一个预定义函数,实现函数 curryIt,调用之后满足如下条件:
1、返回一个函数 a,a 的 length 属性值为 1(即显式声明 a 接收一个参数)
2、调用 a 之后,返回一个函数 b, b 的 length 属性值为 1
3、调用 b 之后,返回一个函数 c, c 的 length 属性值为 1
4、调用 c 之后,返回的结果与调用 fn 的返回值一致
5、fn 的参数依次为函数 a, b, c 的调用参数

示例1
输入

var fn = function (a, b, c) {return a + b + c}; curryIt(fn)(1)(2)(3);

输出

6

通过代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//柯里化是把接受多个参数的函数变换成接受一个单一参数(最初函数的第一个参数)的函数,并且返回接受余下的参数且返回结果的新函数的技术。
function curryIt(fn) {
var len = fn.length;
var args = [];
var result = function(arg){
args.push(arg);
len--;
if(len <=0){
return fn.apply(this,args);
}else{
return result;
}
}
return result;
}