JS 常见的算法实现题

👁 2021-03-06

一些有关JS常见的算法实现题

1 排序算法

2 封装函数实现驼峰命名

function toCamString(sName) {
    let arr = sName.split('-')
    if(arr[0] == ""){  //判断数组第一个元数是否为空，是就截取之后的元素
        arr = arr.slice(1,arr.length)
    }
    for(let i = 1; i < arr.length; i++){
        arr[i] = arr[i].charAt(0).toUpperCase()+arr[i].substr(1,arr[i].length - 1)
    }
    return arr.join("")
}
console.log(toCamString('-webkit-background-composite'))

3 实现数组翻转

function reverseArr(arr){
    for(let i = 0;i<arr.length/2;i++){
        let temp=arr[i]
        arr[i]=arr[arr.length-1-i]
        arr[arr.length-1-i]=temp
    }
    return arr
}

console.log(reverseArr([2,6,5,3,8,9,0,1]))

4 实现字符串翻转

function reverseString(str){
        let arr = str.split('')
        return arr.reverse().join("")
    }
    console.log(reverseString('ffgudrew'))

5 判断字符串是否回文

function strHui(str){
        return str == str.split('').reverse().join('')
    }
    console.log(strHui('hellooleh'))

6 数组扁平化

7 数组去重

8 斐波那锲数列

function fib(n){
    if(n == 0 || n == 1){
        return 1
    }
    return fib(n-1)+fib(n-2)
}
console.log(fib(4))

9 JS实现继承

10 统计字符串中出现频率最高的十个单词以及次数

function maxFrequency(str){
    let arr = [],obj = {}
    //将字符串以空格分割成数组
    let arrstr = str.split(" ")
    console.log(arrstr)
    //查找所有的单词以及单词数量
    for(let i = 0; i< arrstr.length; i++){
        if(obj.hasOwnProperty(arrstr[i])){
            obj[arrstr[i]]++
        }else {
            obj[arrstr[i]] = 1
        }
    }

    console.log(obj)
    //将每个单词对象push进一个数组中
    for(let key in obj){
        let temp = {}
        temp.name = key
        temp.count = obj[key] 
        arr.push(temp)
    }
    //给数组进行排序
    for(let i = 0; i<arr.length - 1; i++){
        for(let j = 0; j< arr.length - i - 1; j++){
            if(arr[j].count<arr[j+1].count){
                let temp = arr[j]
                arr[j] = arr[j+1]
                arr[j+1] = temp
            }

        }
    }
    console.log(arr)
    //截取前十个高频单词
    return arr.slice(0,10)
}
let str = "world hello go boy world hi lll my i you him you me world go boy you i me to lo hi gr de y u i ovds swq dcr aqw hi go fp back vh back wo mi me you"

console.log(maxFrequency(str))

11 时间格式化

function formatDate(time){
    console.log(time)
    let datetime = new Date(time)
    console.log(datetime)
    var year = datetime.getFullYear()
    var month = (datetime.getMonth() + 1) < 10 ? '0'+ (datetime.getMonth() + 1) : (datetime.getMonth() + 1)
    var day = datetime.getDate() < 10 ? '0' + datetime.getDate() : datetime.getDate()
    var hours = datetime.getHours()
    var minutes = datetime.getMinutes() < 10 ? '0'+ datetime.getMinutes() : datetime.getMinutes()
    var seconds = datetime.getSeconds()
    let arr = ['星期天','星期一','星期二','星期三','星期四','星期五','星期六']
    var zhou = datetime.getDay()
    return `${year}-${month}-${day} ${hours}:${minutes}:${seconds} ${arr[zhou]}`

}
console.log(formatDate(Date.now()))

12 统计每个字符出现的频率

function count(str) {
    let obj = {}
    str = str.replace(/\s/g,'')
    for(let i = 0;i < str.length; i++){
        console.log(str[i])
        if(obj.hasOwnProperty(str[i])){
                obj[str[i]]++
            }else{
                obj[str[i]] = 1
            }
    }
    return obj
}
console.log(count('hello world'))

13 字符串大小写转换

14 深克隆和浅克隆

15 实现千位分隔符

将数字12345673456.78分割成12,345,673,456.78

function toThousands(num) {
    num = (num || 0).toString()  //先将数字转换成字符串
    let first = num,result = '',last = ''

    if(num.indexOf('.')){   //判断是否存在小数点
        first = num.split(".")[0]
        last = '.'+num.split(".")[1]  //存在就进行分割
        result = last
    }
    while (first.length > 3) {
        result = ',' + first.slice(-3) + result;  //对整数字符串从后向前进行截取三位
        first = first.slice(0, first.length - 3);   //对剩余整数字符串截取
    }
    if(first){ 
        result = first + result; 
    }
    return result;
}

console.log(toThousands(12345673456.78))

16 比较版本号

/**
* @param {string} version1
* @param {string} version2
* @return {number}
*/
var compareVersion = function(version1, version2) {
    let v1 = version1.split('.');
    let v2 = version2.split('.');
    let l1 = v1.length;
    let l2 = v2.length;
    let n = Math.max(l1, l2);
    let n1 = 0, n2 = 0;
    for (let i = 0; i < n; i++) {
        if (i < l1) {
            n1 = parseInt(v1[i])
        } else {
            n1 = 0;
        }
        if (i < l2) {
            n2 = parseInt(v2[i]);
        } else {
            n2 = 0;
        }
        if (n1 > n2) {
            return 1;
        } else if (n1 < n2) {
            return -1;
        }
    }
    return 0;
};

17 找出数组元素中和为0的所有元素，并且使用过一次的元素不能够再次使用

function findZero(arr){
    let resArr = []
    for(let i = 0; i < arr.length; i++){
        for(let j = i+1; j < arr.length; j++){
            if(arr[i] + arr[j] == 0){
                resArr.push(arr[i])
                resArr.push(arr[j])
                arr.splice(i,1)
                arr.splice(j,1)
            }
        }
    }
    return resArr
}
console.log(findZero([-1,0,1,-2,2,3,2,-2]))

18 当a等于何值时，条件为真

1.第一种，重写toString()方法

var a = {
    i:0,
    //重写toString()
    toString(){
        return ++this.i
    }
    /*也可以使用
    valueOf(){
        return ++this.i
    }*/
}
if(a == 1 && a == 2 && a == 3){
    console.log(1)
}

2.利用Object.defineProperty进行数据劫持

var i = 0 
Object.defineProperty(window,'a',{//全局var a，相当于在window声明了属性a
    get(){
        return ++i  //getter拦截器中不能够再次调用当前值，否则会无法进行下去
    }
})
if(a == 1 && a == 2 && a == 3){
    console.log(1)
}

3.利用数组方法

var a = [1,2,3]
a.toString = a.shift
if(a == 1 && a == 2 && a == 3){
    console.log(1)
}

19 找到字符串中最长无重复子串

给定一个数组arr，返回arr的最长无的重复子串的长度(无重复指的是所有数字都不相同)。

示例1：输入[2,3,4,5]，返回值4

示例2：输入[2,2,3,4,3]，返回值3

function maxLength( arr ) {
    let max = 0;
    let res = [];
    for(let i=0;i<arr.length;i++){
        let pos = res.indexOf(arr[i]);
        if(pos == -1){   // 判断该元素是否存在新数组中
            res.push(arr[i]);   // 不存在就push

        }else{
            res = res.slice(pos+1);   // 存在就截取之后的数组，将元素push
            res.push(arr[i]);
        }
        max = Math.max(max,res.length);
    }
    return max;
}

20 二分查找

实现有重复数字的升序数组的二分查找，给定一个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例1
输入[1,2,4,4,5],4
返回值2
说明
从左到右，查找到第1个为4的，下标为2，返回2 

function search( nums ,  target ) {

    let low = 0,high = nums.length - 1
    let res = -1,mid = 0
    while(low <= high){
        mid = Math.floor((low + high) / 2)
        if(target < nums[mid]){
            high = mid - 1
        }else if(target > nums[mid]){
            low = mid + 1
        }else {
            while(mid > 0 && nums[mid] == nums[mid - 1]){
                mid--
            }
            res = mid
            return res
        }
    }
    return res
}
console.log(search([1,2,4,3,2],2))

21 剑指 Offer 50. 第一个只出现一次的字符

/**
* @param {string} s
* @return {character}
*/
var firstUniqChar = function(s) {
    let res = ' '
    let obj = {}
    for (let i = 0; i < s.length; i++) {
        if (obj.hasOwnProperty(s[i])) {
            obj[s[i]]++
        }else {
            obj[s[i]] = 1
        }
    }
    for(let key in obj) {
        if (obj[key] === 1) {
            res = key
            return res
        }
    }
    return res
};

22 买股票的好时机（一次交易）

题目描述：
假设你有一个数组，其中第i个元素是股票在第i天的价格。
你有一次买入和卖出的机会。（只有买入了股票以后才能卖出）。请你设计一个算法来计算可以获得的最大收益。

示例
输入[1,4,2]
返回值3

function maxProfit( prices ) {
    if(!prices) return 0;
    let temp = prices[0];
    let sub = 0;
    for (let i=1; i<prices.length; i++){
        if(prices[i] < temp) {
            temp = prices[i];
        }else if(prices[i] - temp > sub){
            sub = prices[i] - temp;
        }
    }
    return sub
}

23 买股票（无限次交易）

题目描述：
假定你知道某只股票每一天价格的变动。你最多可以同时持有一只股票。但你可以无限次的交易（买进和卖出均无手续费）。请设计一个函数，计算你所能获得的最大收益。

function maxProfit( prices ) {
    let res = 0
    for(let i = 1; i < prices.length; i++){
        res += Math.max(0,prices[i] - prices[i-1])
    }
    return res
}
console.log(maxProfit([1,2,3,4,5]))

24 剑指 Offer 09. 用两个栈实现队列

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

var CQueue = function() {
    this.inStack = []
    this.outStack = []
};

/** 
* @param {number} value
* @return {void}
*/
CQueue.prototype.appendTail = function(value) {
    this.inStack.push(value)
};

/**
* @return {number}
*/
CQueue.prototype.deleteHead = function() {
    if (this.outStack.length === 0) {
        while (this.inStack.length !== 0) {
            this.outStack.push(this.inStack.pop())
        }
    }
    if (this.outStack.length === 0){
        return -1
    }
    else {
        return this.outStack.pop()
    }
};

/**
* Your CQueue object will be instantiated and called as such:
* var obj = new CQueue()
* obj.appendTail(value)
* var param_2 = obj.deleteHead()
*/

25 求平方根

function sqrt( x ) {
    let left = 0,right = x,res = -1
    while(left <= right) {
        let mid = Math.floor(left + (right - left) / 2);
        if (mid * mid <= x) {   
            res = mid            
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return res;
}
console.log(sqrt(5))

26 最长公共子串

function LCS( str1 ,  str2 ) {
    if(str1.length>str2.length) {
        let temp = str1
        str1 = str2   //让str1是小字符串，str2是大字符串
        str2 = temp
    }

    let len = 0,res = ''
    for(let i=0; i<str1.length; i++){
        //遍历长度小的字符串，因为找的是最大字串，所以len不会减少，像一个框从左向右移动搜寻即可
        let str=str1.slice(i-len, i+1)
        if(str2.indexOf(str) !== -1){
            res=str; //更新结果
            len++; //更新结果长度
        }
    }
    if(res) {
        return res
    }else {
        return -1
    }
}
console.log(LCS("1AB2345CD","12345EF"))

27 发布订阅模式

class EventBus{
    constructor(){
        this.events = this.events || new Map()   
        /*
        {key:[fn,fn,fn]}
        */
    }
    //监听事件
    on(key,fn){
        //获取对应的事件名称事件清单
        let handle = this.events.get(key)
        if(!handle){
            this.events.set(key,fn)
        }else if (handl && typeof handle == 'function'){
            // 如果handle类型为函数，说明目前只有一个事件，则以数组形式进行存储fn和handle
            thi.events.set(key,[handle,fn])
        }else {
          //直接push
          handle.push(fn)
        }
    }
    //触发事件
    emit(key,...arg){
        //获取对应的事件名称事件清单
        let handle = this.events.get(key)
        if(!handle){
            return false
        }
        if(Array.isArray(handle)){
            //如果是数组，则一次触发事件
            for(let i = 0; i < handle.length; i++){
                handle[i].call(this,...arg)
            }
        }else {
            handle.call(this,...arg)
        }
        return true
    }
    //移除事件
    remove(key,fn){
        //获取对应的事件名称事件清单
        let handle = this.events.get(key)

        if(Array.isArray(handle)){
            //如果是数组，判断事件是否和fn相等，相等就进行删除
            for(let i = 0; i < handle.length; i++ ){
                if(handle[i] == fn){
                    handle.splice(i,1)
                }
            }
        }else{
            //只有一个事件
            this.events.delete(key,fn)
        }

    }
}
let event = new EventBus()
event.on('click',function(){
    console.log('click 1')
})
event.on('keyup',function(){
    console.log('keyup 1')
})
event.emit('click')
event.emit('keyup')
event.remove('click')
console.log(event.events)
event.remove('keyup')
console.log(event.events)

28 缺失数字

从0,1,2,…,n这n+1个数中选择n个数，组成有序数组，请找出缺失的那个数，要求O(n)尽可能小。

function solve( a ) {
    let index = 0
    while(a[index] + 1 === a[index + 1]) {
        index++
    }
    return a[index] + 1
}
console.log(solve([0,1,2,3,5,6]))

29 剑指 Offer 15. 二进制中1的个数

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量).）。

/**
* @param {number} n - a positive integer
* @return {number}
*/
var hammingWeight = function(n) {
    let res = 0
    while(n) {
        n = n & (n - 1)
        res++
    }
    return res
};