掘金 后端 ( ) • 2022-08-04 08:22

theme: devui-blue highlight: a11y-dark

携手创作,共同成长!这是我参与「掘金日新计划 · 8 月更文挑战」的第9天,点击查看活动详情

一、前言

队列(queue): 简单的数据结构,先进先出的逻辑顺序。

  1. 进队操作:

队列-2022-08-0216-31-35.png

  1. 出队操作:

队列-2022-08-0216-31-52.png

队列常用于跟树的层序遍历(BFS):

void traverse(TreeNode root) {
    if (null == root) return;
    
    // 初始化队列,将 root 加入队列
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    
    while (!q.isEmpty()) {
        TreeNode cur = q.poll();
        
        // 层级遍历代码
        System.out.println(root.val);
        
        if (cur.left != null) q.offer(cur.left);
        if (cur.right != null) q.offer(cur.right);
    }
}

刷题必知操作:

// 创建队列
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(e); // 入队
queue.add(e);   // 入队
queue.poll();   // 出队

// 优先队列:最小堆(默认)
Queue<Integer> q = new PriorityQueue<>((a, b) -> a - b);
// 优先队列:最大堆
Queue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());
// 自定义排序:最小堆
Queue<ListNode> q = new PriorityQueue<>((a, b) -> a.val - b.val);



二、题目

(1)二叉树的 Z 字形遍历(中)

LeetCode 103

题干分析

这个题目说的是,给你一棵二叉树,要求你从根节点到叶子节点一层一层地进行 Z 字形遍历,也就是先从左向右访问一层节点,然后从右向左访问下一层节点。以这样的方式交替去访问二叉树上每一层节点,并且将访问的结果以二维数组的形式返回。

比如说,给你的二叉树是:

  1
 / \
2   4
   / \
  8  16

它的 Z 字形遍历结果是:

[
 [1],
 [4, 2],
 [8, 16]
]

思路解法

思路:BFS + 变量(判断层次遍历方向)

AC 代码:

// Time: O(n), Space: O(n), Faster: 76.84%
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {

    if (null == root) return Collections.emptyList();
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    List<List<Integer>> result = new ArrayList<>();
    boolean right2Left = false;  // 判断是否变换方向
    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> subResult = new ArrayList<>(size);
        for (int i = 0; i < size; ++i) {
            TreeNode node = queue.poll();
            subResult.add(node.val);
            if (null != node.left) queue.add(node.left);
            if (null != node.right) queue.add(node.right);
        }
        if (right2Left) Collections.reverse(subResult);
        right2Left = !right2Left;
        result.add(subResult);
    }
    return result;
}

(2)任务调度(中)

LeetCode 621

题干分析

这个题目说的是,给你一个字符数组和一个非负整数 n。字符数组表示等待 CPU 处理的任务,每个任务用 A 到 Z 中的一个字符表示,并且每个任务都可以在一个时间单位内完成;n 表示冷却时间,即相同任务之间需要间隔至少 n 个时间单位才能再次执行,冷却时间内的每个时间单位,可以选择执行不同的任务或是让 CPU 处于闲置状态。

现在你要重新组织任务的执行顺序,并计算出最少需要多少个时间单位才能完成所有任务。

# 比如说,给你的任务数组是:
A, A, A, B, B, B, D

# 给你的冷却时间是:
n = 2

# 完成所有任务最少需要 8 个时间单位,一种执行序列是:
A, B, D, A, B, _, A, B

序列中的 '_' 表示 CPU 处于闲置状态。

因此,对于这个例子,你要返回 8。

按上面栗子,题意是:某任务执行完,要等待 n 时间才能继续执行,但这期间可以执行别的任务。

  • 比如 A 执行完,那么后面可以执行 B 、D(或者不执行,空着)

思路解法

思路方法有 二: 最大堆数学方法

方法一:最大堆

  1. **统计每个任务数量:**可以存在一个数组里 int[] freqs = new int[26]; (26个字母)。
  2. **构建最大堆:**将统计完的数据放入堆中。
  3. 计算结果两个变量: ans = result - idle
    • result:每次加分组值(n + 1
    • idle:最后一个分组有几个空闲
  4. **遍历最大堆:**每次取 n + 1 个数,并 -1

队列-2022-08-0316-46-13.png

时间复杂度计算:O(m) × log(26) => O(m)

  • 假设:要处理任务个数 m

  • 有 26 种字母,最大堆每次操作时间复杂度 log(26)

    log(26) < 5 可以忽略。

AC 代码:

// 方法一:最大堆
// Time: O(m), Space: O(1), Faster: 35.62%
public int leastIntervalMaxHeap(char[] tasks, int n) {
    if (tasks == null || tasks.length == 0) return 0;

    // 1. 统计每个任务数量
    int[] freqs = new int[26];
    for (char t : tasks) ++freqs[t - 'A'];

    // 2. 构建最大堆
    Queue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());
    for (int freq : freqs) {
        if (freq != 0) q.add(freq);
    }

    // 3. 遍历最大堆
    int result = 0, idle = 0; // idle:最后一个分组有几个空闲
    while (!q.isEmpty()) {
        result += (n + 1);
        idle = n + 1 - q.size();
        int size = Math.min(n + 1, q.size());
        for (int i = 0; i < size; ++i) {
            freqs[i] = q.poll() - 1;
        }
        for (int i = 0; i < size; ++i) {
            if (freqs[i] != 0) q.add(freqs[i]);
        }
    }
    return result - idle;
}

方法二:数学方法

  1. **统计每个任务数量:**可以存在一个数组里 int[] freqs = new int[26]; (26个字母)。
  2. 任务出现次数最多:maxFreq
  3. 有多少个maxFreqcnt
  4. 计算公式:MAX((maxFreq - 1) * (n + 1) + cnt, tasks.len)

队列-2022-08-0317-47-31.png

AC 代码:

// 方法二:数学方法
// Time: O(m), Space: O(1), Faster: 100.00%
public int leastIntervalMath(char[] tasks, int n) {
    if (tasks == null || tasks.length == 0) return 0;

    // 1. 统计每个任务数量
    int[] freqs = new int[26];
    for (char t : tasks) ++freqs[t - 'A'];

    // 2. 求 maxFreq 和 cnt
    // maxFreq: 任务出现次数最多
    // cnt: 有多少个 maxFreq
    int maxFreq = 0, cnt = 0;
    for (int freq : freqs) {
        if (freq > maxFreq) {
            maxFreq = freq;
            cnt = 1;
        } else if (freq == maxFreq) {
            ++cnt;
        }
    }

    // 3. 计算
    int result = (n + 1) * (maxFreq - 1) + cnt;
    // 取最大值
    return Math.max(result, tasks.length);
}