2020.0319美团笔试-前端(node.js)+讨论求解

😢感觉赛马🐴网的 OJ 对前端js太不友好了吧，5道题4道超时，js在OJ上本来速度就不如其他语言。

🧐淦！突然发现了赛🐴网的OJ注意事项：Web编程题：javascript不支持ES6及以上。不支持ES6，哦那没事了😁。

😊推荐大家去看一下leetcode300最长上升子序列-今晚两道题和 LIS有关。

一、扎银花-签到题（秒A）

AC-100%

数组从大到小排序，取前三之和，比较大小😃

const readline = require('readline')
const rl = readline.createInterface({
    input: process.stdin,
    ouput: process.stdout
})
let inArr = []
rl.on('line', line=>{
    if(!line) return
    inArr.push(line.trim())
    if(inArr.length === 3){
        let n = +inArr[0]
        let arr1 = inArr[1].split(' ').map(e=>+e)
        let arr2 = inArr[2].split(' ').map(e=>+e)
        let max1 = getMax(arr1)
        let max2 = getMax(arr2)
        let max = (max1 == max2) ? max1: Math.max(max1, max2)
        console.log(max)
    }
})

function getMax(arr) {
    let res = arr.sort((a,b)=>b-a)
    let max = res[0]+res[1]+res[2]
    return max
}

二、最长上升子序列-删除一个数

超时-18%

dp/贪心 + 二分查找，写了两种，试了两种，杠了至少半个小时🥺

两种都超时，时间复杂度dp是O(n^2),贪心 + 二分查找是O(nlogn)

const readline = require('readline')
const rl = readline.createInterface({
    input: process.stdin,
    ouput: process.stdout
})
let inArr = []
rl.on('line', line=>{
    if(!line) return
    inArr.push(line.trim())
    if(inArr.length === 2){
        let n = +inArr[0]
        let arr = inArr[1].split(' ').map(e=>+e)
        let tmp = []
        let res = []
        for (let i = 0; i < n; i++) {
            tmp = [...arr].del(i)
            res.push(lengthOfLIS(tmp))
        }
        let max = Math.max(...res)
        console.log(max)
    }
})

var lengthOfLIS = function(nums) {
    const len = nums.length
    if (len == 0) return 0
    if (len == 1) return 1
    let dp = new Array(len).fill(1)
    for (let i = 1; i < len; i++) {
        for (let j = 0; j < i; j++) {
            dp[i] = Math.max(dp[i], nums[i] > nums[j] ? dp[j] + 1 : 1)
        }
    }
    return Math.max(...dp)
};

Array.prototype.del=function(n) {　
    if(n<0)　return this
    else return this.slice(0,n).concat(this.slice(n+1,this.length))
}

三、任务-dp

超时-18%

本来感觉比较简单能拿分的，最后十分钟才开始做，没做完😂

四、跑步-bfs

超时-18%

自闭了😶

五、最长上升子序列-翻转查询

超时-64%

这道题感觉思路，算法都没问题。用贪心 + 二分查找比dp的ac率还低。😶

const readline = require('readline')
const rl = readline.createInterface({
    input: process.stdin,
    ouput: process.stdout
})
let inArr = []
let n
rl.on('line',line=>{
    if(!line) return
    inArr.push(line.trim())
    n = inArr[0].split(' ').map(e=>+e)[1]
    if(inArr.length === n+2){  
        let arr = inArr[1].split('').map(e=>+e) 
        let qc = []
        for (let i = 0; i < n; i++) {
            qc[i] = inArr[i+2].split(' ')
            if(qc[i][0]=='c'){
                let [c,a,b]=qc[i]
                for (let i = a-1; i < b; i++) {
                    if(arr[i]==0){
                        arr[i]=1
                    }else {
                        arr[i]=0 
                    }
                }
            }
            if(qc[i][0]=='q'){
                console.log(lengthOfLIS(arr))
            }
        }
    }
})

var lengthOfLIS = function(nums) {
    const len = nums.length
    if (len == 0) return 0
    if (len == 1) return 1
    let dp = new Array(len).fill(1)
    for (let i = 1; i < len; i++) {
        for (let j = 0; j < i; j++) {
            dp[i] = Math.max(dp[i], nums[i] >= nums[j] ? dp[j] + 1 : 1)
        }
    }
    return Math.max(...dp)
};