2020秋招笔试/面试编程题小记

自己对秋招过程中的一些算法题、编程题的一些复盘（非网络搜集）

一、图的遍历

1. 求带权图的最大路径

问题描述

图（A、B、C、D、E、F、G）

A B 100
B D 100
D E 50
A C 200
C G 300
A F 100

A->B->D->E 250

A->C->G 500

A->F 100

B->D->E 150

C->G 300

找到权重最大的路径，输出出来（如果有多条一样的，全部都输出）

解题方案

// 路径遍历
let read_line = (function (){
    let i = 0
    data = [
        'A B 100',
        'B D 100',
        'D E 50',
        'A C 200',
        'C G 300',
        'A F 500',
    ]
    return function (){
        return data[i++]
    }
})()

function main(){
    // 定义路径树,最终将会生成如下：
    /*
     { A: { B: 100, C: 200, F: 100 },
       B: { D: 100 },
       D: { E: 50 },
      C: { G: 300 } }*/

    let TREE = {}

    let MaxValue = 0 , MaxRoads = []

    let read  = read_line()

    while(read){
        let p = read.split(' ')
        let begin = p[0],end = p[1],value = parseInt(p[2])
        // 生成路径树
        TREE[begin] = {...TREE[begin],[end]:value}
        read = read_line()
    }
    /**
     * 回溯函数
     * @param {String} begin 起点键值
     * @param {Object} tree 路径树
     * @param {Number} value 当前路径权值 
     * @param {String} road 已走过的路径
     */
    function resolve(begin,tree,value,road){
        if(!tree[begin])return

        for (const end in tree[begin]) {
            if (tree[begin].hasOwnProperty(end)) {
                const element = tree[begin][end];

                let currentValue = value+element,currentRoad = road+'->'+end

                if(!TREE[end] && currentValue > MaxValue){
                    // 抵达终点，当前值比之前的最大值还要大，更新MaxValue和路径数组
                    MaxValue = currentValue
                    MaxRoads = [currentRoad]
                    continue
                }else if(!TREE[end] && currentValue == MaxValue){
                    // 抵达终点，当前值等于之前的最大值，路径数组新增路径
                    MaxRoads.push(currentRoad)
                }else if(TREE[end]){
                    // 还没有抵达终点，继续向下走
                    resolve(end,tree,currentValue,currentRoad)
                }
            }
        }
    }
    for (const begin in TREE) {
        if (TREE.hasOwnProperty(begin)) {
            // 遍历路径树下的各个起点，开始路径计算
            resolve(begin,TREE,0,begin)
        }
    }
    MaxRoads.map(road=>console.log(road,MaxValue))
}

main()

2. 小D去旅游

问题描述

小D要在某个时间点要从A点到B点，A到B有可能有多种不同的路径方案，计算小D走花费时间最小路径到达B点后的时间。

输入第一行 N:节点个数，M:边的个数

输入之后的M行都是 节点begin 节点end 需要花费的时间(小时)

最后一行再输入 小D要出发的点 到达的点 起始时间（起始时间格式：month.day/hour）

输出 小D抵达的时间month.day/hour

样例1：

输入：
4 4
1 2 5
1 3 6
2 4 8
3 4 6
1 4 7.9/8

输出：
7.9/20 
注：1->3->4 = 12小时

样例2：

输入：
4 4
1 2 25
1 3 18
2 4 28
3 4 22
1 4 7.9/8

输出：
7.11/0
注：1->3->4 = 40小时

解决方案

let read_line = (function (){
    let i = 0
    let data = [
        '4 4',
        '1 2 25',
        '1 3 18',
        '2 4 28',
        '3 4 22',
        '1 4 7.9/8',
        ]
    // let data = [
    //     '4 4',
    //     '1 2 5',
    //     '1 3 6',
    //     '2 4 8',
    //     '3 4 6',
    //     '1 4 7.9/8',
    //     ]
    return function (){
        return data[i++]
    }
})()

function main(){
    let args = read_line().split(' ')
    let N = args[0]
    let M = args[1]

    // 默认为最大time
    let result = 1000000000000000
    let TREE = {}
    for(let i=0;i<M;i++){
        let p = read_line().split(' ').map(e=>parseInt(e))
        let begin = p[0],end = p[1],time = p[2]
        if(TREE[begin])TREE[begin][end] = time
        else{
            TREE[begin] = {
                [end]:time
            }
        }
    }

    // 获取起点、终点和时间
    let p = read_line().split(' ')
    let Begin = p[0],End = p[1],BeginTime = p[2]
    // 构建回溯函数
    function resolve(begin,end,tree,price){
        if(!tree[begin])return 
        for (const key in tree[begin]) {
            if (tree[begin].hasOwnProperty(key)) {
                const element = tree[begin][key];
                // 找到终点
                if(key == end && price+element<result){
                    result = price+element
                    continue
                }
                if(key != end && price+element < result){
                    resolve(key,end,tree,price+element)
                }
            }
        }
    }
    // 获取最小需要花费的时间 => result
    resolve(Begin,End,TREE,0)

    // 返回值为加了result时间后的时间字符串
    function addHour(time,hours){
        let [month,day,hour] = time.split(/[\.\/]/)
        let resHour = parseInt(hour)+parseInt(hours)
        let a = new Date(2020,month-1,parseInt(day)+parseInt(resHour/24),resHour%24)
        return `${a.getMonth()+1}.${a.getDate()}/${a.getHours()}`

    }
    console.log(addHour(BeginTime,result))

}
main()

3. 省钱造桥术

问题描述

城市管理者要把若干岛屿造桥连接起来，并限定造每条桥的最大成本，设计程序查看是否能在这种情况下把所有岛屿连接起来。

第一行输入T 代表组数

第二行输入第一组的 N节点数 M边数 最大成本K

接下来的M行 ： 小岛begin 小岛end 需要的花费

再输入第二组 ...

输出Yes或者No代表是否将所有岛屿连接起来

样例：

2
4 3 400
1 2 200
1 3 400
3 4 300
3 3 400
1 2 500
1 3 600
2 3 700

Yes
No

解决方案

let read_line = (function (){
    let i = 0
    let data = [
        '2',
        '4 3 400',
        '1 2 200',
        '1 3 400',
        '3 4 300',
        '3 3 400',
        '1 2 500',
        '1 3 600',
        '2 3 700',
        ]
    return function (){
        return data[i++]
    }
})()
main()
function main(args){
    let T = read_line()
    for(let i=0;i<T;i++){
        console.log(resolve())
    }
}

function resolve(){
    let args = read_line().split(' ').map(e=>parseInt(e))
    let N = args[0] // 小岛数目
    let M = args[1] // 边数
    let maxPrice = args[2] //最大成本

    // 定义数据树 { '1': { '2': 500, '3': 600 }, '2': { '3': 700 } }
    let TREE = {}
    for (let index = 0; index < M; index++) {
        let p = read_line().split(' ').map(e=>parseInt(e))
        let begin = p[0],end = p[1],price = p[2]
        if(TREE[begin]) TREE[begin][end] = price
        else{
            TREE[begin] = {
                [end]:price
            }
        }
    }
    // 结果状态树，存放满足最大成本的小岛为key
    let result = {}
    // 存放当前的已构建的桥数
    let sideCount = 0
    // 根据数据树 遍历小岛起点
    for (const begin in TREE) {
        if (TREE.hasOwnProperty(begin)) {
            const ends = TREE[begin]
            // 遍历小岛终点
            for (const end in ends) {
                if (ends.hasOwnProperty(end)) {
                    const element = ends[end]

                    if(element <= maxPrice){ //小于等于最大成本
                        // 将两个小岛都存放到结果树中
                        result[begin] = result[end] = true
                        // 增加桥数
                        sideCount++
                        // 如果当前结果树中，节点个数正好与N要求一致，并且边数正好是节点个数减一（防止1->2,3->4出现的错误） 则返回"Yes"
                        if(Object.keys(result).length === N && sideCount == N-1) return "Yes"
                    }
                }
            }
        }
    }
    return "No"
}

二、其他

1. 字符串全排列

题目描述

*全排列 'abc' -> ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

解题方案

function permutation(str) {
    let ans = []
    function Search(str = '',result = ''){
        if(str.length === 0)return ans.push(result)
        let arr = str.split('')
        for(let i = 0;i < arr.length;i++){
            let t = arr[i]
            arr[i] = ''
            Search(arr.join(''),result+t)
            arr[i] = t
        }
    }
    Search(str,"")
    return ans
}

2. 异步控制

题1

题目描述

function asyncAdd(a, b, callback) {

setTimeout(() => callbacl(null, a + b), 0);

}

asyncAdd(1, 2, function (err, result) {

if (err) throw err;

console.log(result); // 3

});

-- 题目

有一个数列：[1, 2, 3, ...., N]

基于 asyncAdd 完成数列的求和操作。

function sum(list) {

// TODO

}

sum([1, 2, 3, 4]).then(v => console.log(v)); // 10

解题方案

function asyncAdd(a, b, callback) {
    setTimeout(() => callback(null, a + b), 0);
}

function sum(list = []){
    return new Promise((resolve,reject)=>{
        if(list.length > 2){
            sum(list.slice(1)).then(data=>{
                asyncAdd(list[0],data,(err,data)=>{
                    resolve(data)
                })
            })
        }else{
            asyncAdd(list[0],list[1],(err,data)=>{
                resolve(data)
            })
        }
    })
}

sum([1,2,3,4]).then(console.log)

题2

题目描述

let tasks = [task1, task2, ..., taskN];

function seq(tasks) {

}

promise.then()

task1().then(() => task2()).then(() => task3())

模拟tasks

function asyncPrint(str){
    return function(){
        return new Promise((resolve,reject)=>{
            setTimeout(()=>{
                console.log(str)
                resolve()
            },Math.random()*1000)
        })
    }
} 

let tasks = [ asyncPrint("task1"), asyncPrint("task2"), asyncPrint("task3")]

解题步骤

解1：

function seq(tasks) {
    return tasks.reduce((pre,cur)=>{
        return pre.then(cur)
    },Promise.resolve())
}

解2：

function seq(tasks) {
    if(tasks.length == 0)return
    tasks[0]().then(()=>{
        seq(tasks.slice(1))
    })
}