登录
原创

JS基础算法(数据结构之队列篇)

专栏JS算法基础篇
发布于 2020-12-14 阅读 4615
  • 前端
  • 面试
  • 算法
原创

数据结构之队列

特殊的线性表,只允许在表的前端删除,表的后端插入(先进先出)

设计循环队列

设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。
你的实现应该支持如下操作:

  • MyCircularQueue(k): 构造器,设置队列长度为 k 。
  • Front: 从队首获取元素。如果队列为空,返回 -1 。
  • Rear: 获取队尾元素。如果队列为空,返回 -1 。
  • enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
  • deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
  • isEmpty(): 检查循环队列是否为空。
  • isFull(): 检查循环队列是否已满。

示例:

MyCircularQueue circularQueue = new MycircularQueue(3); // 设置长度为 3

circularQueue.enQueue(1); // 返回 true

circularQueue.enQueue(2); // 返回 true

circularQueue.enQueue(3); // 返回 true

circularQueue.enQueue(4); // 返回 false,队列已满

circularQueue.Rear(); // 返回 3

circularQueue.isFull(); // 返回 true

circularQueue.deQueue(); // 返回 true

circularQueue.enQueue(4); // 返回 true

circularQueue.Rear(); // 返回 4

提示:
所有的值都在 0 至 1000 的范围内;
操作数将在 1 至 1000 的范围内;
请不要使用内置的队列库。

queue1.512391dd.png

注意添加数据时队尾指针要求余this.max,获取队尾数据时要队尾指针减一,并且如果指针减一小于0,即为数组最后一位

export default class MyCircularQueue {
    constructor (k) {
        // 保存数据长度为k的数据结构
        this.list=Array(k)
        // 队首的指针
        this.front=0
        // 队尾的指针
        this.rear=0
        // 队列的长度
        this.max=k
    }
    enQueue (num) {
        if(this.isFull()){
            return false
        }else{
            this.list[this.rear]=num
            this.rear=(this.rear+1)%this.max
            return true
        }
    }
    deQueue () {
        let v=this.list[this.front]
        this.list[this.front]=''
        this.front=(this.front+1)%this.max
        return v
    }
    isEmpty () {
        return this.front===this.rear&&!this.list[this.front]
    }
    isFull () {
        return this.front===this.rear&&!!this.list[this.front]
    }
    Front () {
        return this.list[this.front]
    }
    Rear () {
        let rear=this.rear-1

        return this.list[rear<0?this.max-1:rear]
    }
}
class MycircularQueue{
    constructor(len){
        this.list=new Array(len);
        this.front=0;
        this.rear=0;
        this.max=len;
    }
    Front(){
        return this.list.length?this.list(this.front):-1;
    }
    Rear(){
        let rear=this.rear-1;
        return this.list[rear<0?this.max-1:rear]
    }
    enQueue(value){
        if(this.isFull()){
            return false;
        }else{
            this.list[this.rear]=value;
            this.rear=(this.rear+1)%this.max;
            return true;
        }
    }
    deQueue(){
        if(this.list.length>0){
            this.list[this.front]="";
            this.front++;
            return true;
        }else{
            return false;
        }
    }
    isEmpty(){
        return this.front===this.rear&&!this.list[this.front]
    }
    isFull(){
        return this.front===this.rear&&this.list[this.front]
    }
}

任务调度器

给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的26 种不同种类的任务。任务可以以任意顺序执行,并且每个任务都可以在 1 个单位时间内执行完。CPU 在任何一个单位时间内都可以执行一个任务,或者在待命状态。
然而,两个相同种类的任务之间必须有长度为 n 的冷却时间,因此至少有连续 n 个单位时间内 CPU 在执行不同的任务,或者在待命状态。
你需要计算完成所有任务所需要的最短时间。

示例 1:

输入: tasks = [“A”,“A”,“A”,“B”,“B”,“B”], n = 2
输出: 8
执行顺序: A -> B -> (待命) -> A -> B -> (待命) -> A -> B.
注:

任务的总个数为 [1, 10000]。
n 的取值范围为 [0, 100]。

das.png

任务多的优先执行即可

export default (tasks, n) => {
    let q = ''
    let Q = {}
    // 每种任务的数量
    tasks.forEach(item => {
        if (Q[item]) {
            Q[item]++
        } else {
            Q[item] = 1
        }
    })
    while (1) {
        let keys = Object.keys(Q)
        if (!keys[0]) {
            break
        }
        // n+1为一组
        let tmp = []
        for (let i = 0; i <= n; i++) {
            let max = 0
            let key
            let pos
            // 从所有的任务中找到未处理数最大的,优先安排
            keys.forEach((item, idx) => {
                if (Q[item] > max) {
                    max = Q[item]
                    key = item
                    pos = idx
                }
            })
            if (key) {
                tmp.push(key)
                keys.splice(pos, 1)
                Q[key]--;
                if (Q[key] < 1) {
                    delete Q[key]
                }
            } else {
                break
            }
        }
        q += tmp.join('').padEnd(n + 1, '-')
    }
    // A--A--A--
    q = q.replace(/-+$/g, '')
    return q.length
}

评论区

timing
4粉丝

励志做一条安静的咸鱼,从此走上人生巅峰。

0

0

0

举报