文远知行 9.8 笔试

记录体验最好的一次笔试， 代码可以下载

第一题：单调队列

package main

import (
	"fmt"
)
func finMaxMin(n int, k int, arr []int) ([]int, []int) {
	minQ, maxQ := make([]int, 0), make([]int, 0)
	var ansMin []int
	var ansMax []int
	// 初始化窗口
	for i := 0; i < k; i++ {
		// 维护队列头部为最大值
		for len(maxQ) > 0 && arr[maxQ[len(maxQ)-1]] <= arr[i] {
			maxQ = maxQ[:len(maxQ)-1]
		}
		maxQ = append(maxQ, i)
		// 维护队列头部为最小值
		for len(minQ) > 0 && arr[minQ[len(minQ)-1]] >= arr[i] {
			minQ = minQ[:len(minQ)-1]
		}
		minQ = append(minQ, i)
	}
	ansMax = append(ansMax, arr[maxQ[0]])
	ansMin = append(ansMin, arr[minQ[0]])
	for i := k; i < n; i++ {
		if maxQ[0] <= i-k {
			maxQ = maxQ[1:]
		}
		if minQ[0] <= i-k {
			minQ = minQ[1:]
		}
		// 维护队列头部为最大值
		for len(maxQ) > 0 && arr[maxQ[len(maxQ)-1]] <= arr[i] {
			maxQ = maxQ[:len(maxQ)-1]
		}
		maxQ = append(maxQ, i)
		// 维护队列头部为最小值
		for len(minQ) > 0 && arr[minQ[len(minQ)-1]] >= arr[i] {
			minQ = minQ[:len(minQ)-1]
		}
		minQ = append(minQ, i)
	ansMax = append(ansMax, arr[maxQ[0]])
	ansMin = append(ansMin, arr[minQ[0]])
	}
	return ansMin, ansMax
}
func main() {
	var n, k int
	fmt.Scan(&n, &k)
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&arr[i])
	}
	arrMin, arrMax := finMaxMin(n, k, arr)
    for _,v := range arrMin {
        fmt.Printf("%d ",v)
    }
    fmt.Println()
    for _,v := range arrMax {
        fmt.Printf("%d ",v)
    }
}

第二题：拓扑排序

package main

import (
    "container/list"
    "fmt"
)
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 找到最小执行时间
 * @param n int整型 算法模块的个数
 * @param dependences int整型二维数组 算法模块的依赖关系，[i, j] 表示算法模块j依赖算法模块i
 * @param latencies int整型一维数组 每个算法模块的延迟
 * @param critical_modules int整型一维数组 必须执行的算法模块
 * @return int整型
*/

func dfs (node int,graph map[int][]int, visited map[int]bool) {
    if visited[node] {
        return 
    }
    visited[node] = true 
    for _,neighbor := range graph[node] {
        dfs(neighbor, graph, visited)
    }
}
func max(a,b int) int {
    if a>b{
        return a 
    }
    return b 
}
func minimumCriticalTime( n int ,  dependences [][]int ,  latencies []int ,  critical_modules []int ) int {
    // write code here
    // 构建图
    graph := make(map[int][]int)
    graph2 := make(map[int][]int)
    inDegree := make(map[int]int) 
    for _,dep := range dependences {
        pre,next := dep[0],dep[1]
        graph[next] = append(graph[next], pre)
        graph2[pre] = append(graph2[pre], next)
        inDegree[next] ++ 
    }
    reachable := make(map[int]bool)
    for _,mod := range critical_modules {
        dfs(mod,graph,reachable)
    }
    // reachable 是必须执行的节点
    fmt.Println(reachable)
    queue := list.New() 
    for i:= 0;i<n;i++{
        if _,ok:=reachable[i]; ok&& inDegree[i]==0 {
            queue.PushBack(i)
        }
    }
    dp:=make(map[int]int)
    for i := 0;i<n;i++ {
        dp[i] = latencies[i]
    }
    for queue.Len() > 0 {
        node := queue.Remove(queue.Front()).(int)
        for  _ , neighbor := range graph2[node] {
            if _,ok := reachable[neighbor]; !ok{
                continue
            }
            inDegree[neighbor] -- 
            if inDegree[neighbor] == 0 {
                queue.PushBack(neighbor)
            }
            dp[neighbor] = max(dp[neighbor],dp[node]+latencies[neighbor])
        }
    }
    maxTime := 0 
    for _,mod := range critical_modules {
        if val,ok:=dp[mod];ok {
            maxTime = max(maxTime,val)
        }
    }
    return maxTime
}

第三题：拓扑排序+背包问题

package main

import (
	"container/heap"
	"fmt"
)

type Task struct {
	id int
	dep   []int
	r     int
	s     int
	ready bool
}

type TaskQueue []*Task

func (q TaskQueue) Len() int { return len(q) }
func (q TaskQueue) Less(i, j int) bool {
	return q[i].s > q[j].s
}
func (q TaskQueue) Swap(i, j int) {
	q[i], q[j] = q[j], q[i]
}
func (q *TaskQueue) Push(x interface{}) {
	*q = append(*q, x.(*Task))
}
func (q *TaskQueue) Pop() interface{} {
	old := *q
	n := len(old)
	task := old[n-1]
	*q = old[:n-1]
	return task
}

func maxScore(N int, R int, dep [][]int, r []int, s []int) int {
	tasks := make([]*Task,N)
    for i :=0; i<N;i++ {
        tasks[i] = &Task{
            id: i,
            dep: dep[i],
            r: r[i],
            s: s[i],
        }
    }

    inDegree := make([]int,N)
    for _,task := range tasks {
        for _,id := range task.dep{
            if id != -1 {
                inDegree[id] ++ 
            }
        }
    }

    readyQueue := make(TaskQueue,0)
    for i,task := range tasks {
        if inDegree[i] == 0 {
            task.ready = true 
            heap.Push(&readyQueue,task)
        }
    }
    // 背包问题
    dp := make([][]int,N+1)
    for i:= range dp {
        dp[i] = make([]int, R+1)
    }
    // 动态规划，先物品，再weight
    i:=1
    for readyQueue.Len() > 0 {
        cur := heap.Pop(&readyQueue).(*Task)
        for j:= R;j>=cur.r ;j--{
            if dp[i][j] < dp[i][j-cur.r]+cur.s {
                 dp[i][j] = dp[i-1][j-cur.r]+cur.s 
            }
        }
        i++
        for _,nextID := range cur.dep {
            if nextID!=-1 && inDegree[nextID] >0 {
                inDegree[nextID] --
                if inDegree[nextID] == 0{
                    tasks[nextID].ready = true 
                    heap.Push(&readyQueue, tasks[nextID])
                }
            }
        }
    }
	return dp[N][R]
}

func main() {
	var N, R int
	fmt.Scan(&N, &R)
    dep := make( [][]int,N)
	for i := 0; i < N; i++ {
        dep[i] = make([]int, 1) 
		
	}
    r := make([]int,N)
    s := make([]int,N)
	for i := 0; i < N; i++ {
		fmt.Scan(&dep[i][0],&r[i],&s[i])
	}
	fmt.Print(maxScore(N, R, dep, r, s))
}