JavaScript算法题整理（一）

算法
字数统计: 3.2k字   |   阅读时长≈ 14分钟

好几年没碰算法题，头次打开一脸懵逼。为了面试刷起来，以下为整理：

JavaScript算法题

dom 节点查找

描述

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

输入描述

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

获取node父节点，可以使用node.parentNode

分析

若oNode1节点的父节点包含oNode2，则此父节点为共同父节点。以此类推。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function commonParentNode(oNode1, oNode2) {
    let parent1 = oNode1.parentNode;
    let parent2 = oNode2.parentNode;
    while(true){
        if(parent1.contains(oNode2)){
            return parent2;
        }
        if(parent2.containw(oNode1)){
            return parent1;
        }
        parent1 = parent1.parentNode;
        parent2 = parent2.parentNode;
    }
}

斐波那契数列

描述
用 JavaScript 实现斐波那契数列函数,返回第n个斐波那契数。 f(1) = 1, f(2) = 1 等

斐波那契数列，f(0)=0,f(1)=1,f(2)=f(0)+(1)=1,...,f(n)=f(n-1)+f(n-2)

1
2
3
function fibonacci(n) {
    return n<=2 ? 1 : fibonacci(n-1) + fibonacci(n-2);
}

字符串统计

描述
统计字符串中每个字符的出现频率，返回一个 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. 字符串分离字符可以使用split方法，也可以使用正则表达式str.replace(/\s/,'');去除字符串中的空格。

  2. 判断对象中是否已含有指定对象x可以直接object[x]!==undefined，也可以使用对象的hasOwnProperty()方法，如object.hasOwnProperty(x)判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function count(str) {
    let count = {};
    let arr = str.split("");//将字符串分离为字符数组，也可以使用正则表达式分离
    for(let i = 0;i<arr.length;i++){
        if(arr[i]!==""|| arr[i]!== " "){//用split("")分离的数组会带空格，故需要排除空格的情况
            if(count[arr[i]] !== undefined){//此处可以使用对象的hasOwnProperty()方法看对象中是否已包含此字符
                count[arr[i]]++;
            }else{
                count[arr[i]] = 1;
            }
        }
    }
    return count;
}

删除数组元素

描述

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

示例1

输入：

[1, 2, 3, 4]

输出：

[1, 2, 3]

分析

不修改原数组arr，则需要将原数组copy一份到新数组。

1
2
3
4
5
function truncate(arr) {
    var newArr = JSON.parse(JSON.stringify(arr));
    newArr.pop();
    return newArr;
}

可能涉及的知识点

  1. 数组的深拷贝和浅拷贝
  • 浅拷贝：如果数组元素是基本类型，就会拷贝一份，互不影响，而如果是对象或者数组，就会只拷贝对象和数组的引用，无论对新旧数组的哪一个进行了修改，两者都会发生变化。
1
2
3
4
5
6
//使用=直接赋值
let newArr = arr;
//使用slice()
let newArr = arr.slice();
//使用concat()
let newArr =  arr.concat();
  • 深拷贝：完全的拷贝一个对象，即使嵌套了对象，两者也相互分离，修改一个对象的属性，也不会影响另一个。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//使用JSON.stringify和JSON.parse
var newArr = JSON.parse(JSON.stringify(arr));//该方法可以拷贝数组和对象，但不能拷贝函数。对于RegExp类型和Function类型无法完全满足，且不支持有循环引用的对象。
//拷贝时判断属性类型
var deepCopy = function(obj) {
    // 只拷贝对象
    if (typeof obj !== 'object') return;
    // 根据obj的类型判断是新建一个数组还是一个对象
    var newObj = obj instanceof Array ? [] : {};
        for (var key in obj) {
            // 遍历obj,并且判断是obj的属性才拷贝
            if (obj.hasOwnProperty(key)) {
                // 判断属性值的类型，如果是对象递归调用深拷贝
                newObj[key] = typeof obj[key] === 'object' ? deepCopy(obj[key]) : obj[key];
            }
        }
  return newObj;
}
  1. 数组的常用方法
方法名 描述
concat(arrayX,arrayX,…,arrayX) 连接两个或更多的数组，并返回结果。
join(&separator) 把数组的所有元素放入一个字符串。元素通过指定的分隔符进行分隔。
pop() 删除并返回数组的最后一个元素
push(newelement1,…,newelementX) 向数组的末尾添加一个或更多元素，并返回新的长度。
reverse() 颠倒数组中元素的顺序。
shift() 删除并返回数组的第一个元素
slice(start,&end) 从某个已有的数组返回选定的元素
sort(&sortby-fn) 对数组的元素进行排序
splice(index,howmany,item1,…,itemX) 删除元素，并向数组添加新元素。
toSource() 返回该对象的源代码。
toString() 把数组转换为字符串，并返回结果。
toLocaleString() 把数组转换为本地数组，并返回结果。
unshift(newelement1,…,newelementX) 向数组的开头添加一个或更多元素，并返回新的长度。
valueOf() 返回数组对象的原始值

正确的使用 parseInt

描述

修改 js 代码中 parseInt 的调用方式，使之通过全部测试用例

示例1

输入：

‘12’

输出：

12

示例2

输入：

‘12px’

输出：

12

示例3

输入：

‘0x12’

输出：

0

分析

方法parseInt()若前面以0x开头，parseInt()会把它的其余部分解析为十六进制的整数。

方法parseInt(string, radix)的radix参数表示要解析的数字的基数。该值介于 2 ~ 36 之间。故可以设置radix为10将所有传入的字符串都以十进制方式解析。

1
2
3
function parse2Int(num) {
    return parseInt(num,10);
}

使用arguments

描述

函数 useArguments 可以接收 1 个及以上的参数。请实现函数 useArguments，返回所有调用参数相加后的结果。本题的测试参数全部为 Number 类型，不需考虑参数转换。

示例1

输入：

1, 2, 3, 4

输出：

10

1
2
3
4
5
6
7
function useArguments() {
    let sum = 0;
    for(let i = 0;i<arguments.length;i++){
        sum += arguments[i];
    }
    return sum;
}

涉及知识点

JavaScript函数传参

  1. 显式参数Parameters
1
function fn(parameter1,...,parameterx){}

JS定义显式参数时不需要指定数据类型。

  1. 隐式参数Arguments

JS函数有内置的对象arguments，包含了函数调用的参数数组。

JS函数对隐式参数没有类型和个数检测。若函数在调用时没有提供隐式参数，则参数默认值均为undefined

  1. ES6函数可以自带默认参数
1
2
3
4
5
6
7
function myFunction(x, y = 10) {
    // y is 10 if not passed or undefined
    return x + y;
}
 
myFunction(0, 2) // 输出 2
myFunction(5); // 输出 15, y 参数的默认值
  1. 传递参数
  • 通过值传参

函数中调用的参数是隐式参数，其通过值来传递，函数仅是获得值。若函数修改参数的值，不会修改显式参数的初始值（在函数外定义），隐式参数的改变在函数外不可见

  • 通过对象传参

JS中可以引用对象的值，在函数内部修改对象的属性会修改其初始的值，即修改对象属性可作用于函数外部。

函数传参

描述

将数组 arr 中的元素作为调用函数 fn 的参数

示例1

输入：

function (greeting, name, punctuation) {return greeting + ‘, ‘ + name + (punctuation || ‘!’);}, [‘Hello’, ‘Ellie’, ‘!’]

输出：

Hello, Ellie!

1
2
3
function argsAsArray(fn, arr) {
    return fn.apply(this,arr)
}

涉及到的知识点

  1. JS函数调用

JS函数有4中调用方式，不同点在于this的初始化

  • 作为函数调用
1
2
3
4
function myFunction(a, b) {
    return a * b;
}
myFunction(10, 2);

此种方式默认的全局对象是什么，函数就属于什么对象的函数，即this指向全局对象

  • 作为方法调用
1
2
3
4
5
6
7
8
var myObject = {
    firstName:"John",
    lastName: "Doe",
    fullName: function () {
        return this.firstName + " " + this.lastName;
    }
}
myObject.fullName();

此种方式的this为myObject对象。

  • 使用构造函数调用
1
2
3
4
5
6
7
8
9
// 构造函数:
function myFunction(arg1, arg2) {
    this.firstName = arg1;
    this.lastName  = arg2;
}
 
// This    creates a new object
var x = new myFunction("John","Doe");
x.firstName;

构造函数的调用会创建一个新的对象，新对象继承构造函数的属性和方法，故this的值在函数调用实例话对象时创建，即在构造函数调用时被创建

  • 作为函数方法调用函数

JS函数有其自己的属性和方法，call()和apply()是预定义的函数方法，可用于调用函数，其第一个参数必须为对象本身。

1
2
3
4
5
6
7
8
function myFunction(a, b) {
    return a * b;
}
//call方法
myObject = myFunction.call(myObject,10,2);
//apply方法
myArray = [10,2];
myObject = myFunction.apply(myObject,myArray);

由此可看出，apply()方法传入的第二个参数为参数数组，而call()方法直接传入所有的参数。这为二者的区别。

在JavaScript严格模式(strict mode)下, 在调用函数时第一个参数会成为this的值， 即使该参数不是一个对象。
在JavaScript非严格模式(non-strict mode)下, 如果第一个参数的值是null或undefined, 它将使用全局对象替代。

二进制转换

  1. 二进制转十进制
1
2
3
4
5
6
7
8
9
10
11
12
13
//parseInt方法
function base10(str) {
    return parseInt(str,2);
}
//一般方法
function base10(str) {
    var sum = 0;
    var arr = str.split("").reverse();//避免pow()内写一大串
    for(var i= 0;i<arr.length;i++){
        sum += arr[i]* Math.pow(2,i)
    }
    return sum;
}
  1. 十进制转二进制
1
2
let num = 100;
num.toString(2);
  1. 其他
1
2
3
4
5
6
7
8
9
10
parseInt(num,8);   //八进制转十进制
parseInt(num,16);   //十六进制转十进制
parseInt(num).toString(8)  //十进制转八进制
parseInt(num).toString(16)   //十进制转十六进制
parseInt(num,2).toString(8)   //二进制转八进制
parseInt(num,2).toString(16)  //二进制转十六进制
parseInt(num,8).toString(2)   //八进制转二进制
parseInt(num,8).toString(16)  //八进制转十六进制
parseInt(num,16).toString(2)  //十六进制转二进制
parseInt(num,16).toString(8)  //十六进制转八进制

使用 apply 调用函数

描述

实现函数 callIt，调用之后满足如下条件

1、返回的结果为调用 fn 之后的结果

2、fn 的调用参数为 callIt 的第一个参数之后的全部参数

分析

隐式参数arguments不是数组，需要将它先转化为数组。

转化arguments：let args = Array.prototype.slice.call(arguments,0);

1
2
3
4
function callIt(fn) {
    let args = Array.prototype.slice.call(arguments,1);//截取第一个参数之后的参数。
    return fn.apply(this,args);
}

属性

描述

找出对象 obj 不在原型链上的属性(注意这题测试例子的冒号后面也有一个空格~)

1、返回数组，格式为 key: value

2、结果数组不要求顺序

示例1

输入：

1
2
3
var C = function() {this.foo = 'bar'; this.baz = 'bim';}; 
C.prototype.bop = 'bip'; 
iterate(new C());

输出：

[“foo: bar”, “baz: bim”]

分析

对象不属于原型链上的属性，即实例属性，可以通过方法hasOwnProperty()方法找出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function iterate(obj) {
    let arr = [];
    for( let ele in obj){
        if(obj.hasOwnProperty(ele)){
            arr.push(ele+": "+obj[ele]);
        }
    }
    return arr;
}
//更快的解法，使用Object.keys()返回可枚举的实例属性数组
function iterate(obj) {
    return Object.keys(obj).map(function(key) {
        return key + ": " + obj[key];
    });
}

时间格式化

描述

按所给的时间格式输出指定的时间

格式说明–对于 2014.09.05 13:14:20

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
yyyy: 年份，2014
yy: 年份，14
MM: 月份，补满两位，09
M: 月份, 9
dd: 日期，补满两位，05
d: 日期, 5
HH: 24制小时，补满两位，13
H: 24制小时，13
hh: 12制小时，补满两位，01
h: 12制小时，1
mm: 分钟，补满两位，14
m: 分钟，14
ss: 秒，补满两位，20
s: 秒，20
w: 星期，为 ['日', '一', '二', '三', '四', '五', '六'] 中的某一个，本 demo 结果为 五

示例1

输入：

formatDate(new Date(1409894060000), ‘yyyy-MM-dd HH:mm:ss 星期w’)

输出：

2014-09-05 13:14:20 星期五

分析

使用Date对象的各个getXXX()方法获得相应的年月日等值，再通过str.replace()方法替换格式中的内容。

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
function formatDate(date,formate){
    let year = date.getFullYear(),
        month = date.getMonth()+1,
        day = date.getDate(),
        week = date.getDay(),
        weekStr = ["日","一","二","三","四","五","六"],
        hour = date.getHours(),
        minute = date.getMinutes(),
        seconds = date.getSeconds();
    let format0 = function(num){
        if(num < 10){
            return 0 + "" + num;
        }else{
            return num;
        }
    };
    let dateObj = {
        "yyyy": year,
        "yy": year%100,
        "MM": format0(month),
        "M": month,
        "dd": format0(day),
        "d": day,
        "w": weekStr[week],
        "HH": format0(hour),
        "H": hour,
        "hh":format0(hour%12),
        "h": hour%12,
        "mm": format0(minute),
        "m": minute,
        "ss": format0(seconds),
         "s": seconds
    };

    for(let obj in dateObj){
        formate = formate.replace(obj,dateObj[obj]);
    }
    return formate;
    
}
  • 版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！
  • © 2020-2024 Aweso Lynn
  • PV: UV: