LeetCode 281. 锯齿迭代器

Categories:

题目描述
思路分析
1. 解法一：队列存储索引（推荐）
2. 解法二：多指针轮转
相似题目

题目描述

✅ 281. 锯齿迭代器

思路分析

解法一：队列存储索引（推荐）

核心思路：

使用一个队列，存储 (listIndex, elementIndex) 的配对，按锯齿顺序初始化

初始化时将各列表的第一个元素对应的位置入队：list0[0], list1[0], list0[1], list1[1]…

next() 时从队列头取出位置，返回对应元素

hasNext() 直接判断队列是否非空

这种方式将迭代逻辑提前计算，调用时 O(1)

复杂度分析：

时间复杂度：初始化 O(n+m)，next() O(1)，hasNext() O(1)

空间复杂度：O(n+m)，n、m 分别为两个列表的长度

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;

public class ZigzagIterator {

  // 队列中存储 [列表索引, 元素索引]
  private Deque<int[]> queue;
  private List<List<Integer>> lists;

  public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
    lists = new java.util.ArrayList<>();
    lists.add(v1);
    lists.add(v2);

    queue = new ArrayDeque<>();

    int maxLen = Math.max(v1.size(), v2.size());

    // 按锯齿顺序将各位置加入队列
    for (int i = 0; i < maxLen; i++) {
      for (int j = 0; j < lists.size(); j++) {
        if (i < lists.get(j).size()) {
          queue.offer(new int[]{j, i});
        }
      }
    }
  }

  public int next() {
    int[] pos = queue.poll();
    return lists.get(pos[0]).get(pos[1]);
  }

  public boolean hasNext() {
    return !queue.isEmpty();
  }
}

type ZigzagIterator struct {
    // 存储 (列表索引, 元素索引) 的队列
    queue [][2]int
    lists [][]int
}

func Constructor(v1, v2 []int) *ZigzagIterator {
    lists := [][]int{v1, v2}
    queue := [][2]int{}

    maxLen := len(v1)
    if len(v2) > maxLen {
        maxLen = len(v2)
    }

    // 按锯齿顺序将各位置加入队列
    for i := 0; i < maxLen; i++ {
        for j, list := range lists {
            if i < len(list) {
                queue = append(queue, [2]int{j, i})
            }
        }
    }

    return &ZigzagIterator{queue: queue, lists: lists}
}

func (z *ZigzagIterator) next() int {
    pos := z.queue[0]
    z.queue = z.queue[1:]
    return z.lists[pos[0]][pos[1]]
}

func (z *ZigzagIterator) hasNext() bool {
    return len(z.queue) > 0
}

解法二：多指针轮转

核心思路：

使用双指针分别指向 v1 和 v2 的当前位置，用 turn 标记当前轮到哪个列表

next() 时根据 turn 取对应列表元素，指针前进，切换 turn

若某个列表已耗尽，则跳过只取另一个列表

适合 k 路扩展时改用指针数组

复杂度分析：

时间复杂度：初始化 O(1)，next() O(1)，hasNext() O(1)

空间复杂度：O(1)，不计输入存储

import java.util.List;

public class ZigzagIterator {

  private List<Integer> v1;
  private List<Integer> v2;
  private int i1;
  private int i2;
  private int turn;

  public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
    this.v1 = v1;
    this.v2 = v2;
    this.i1 = 0;
    this.i2 = 0;
    this.turn = 0;
  }

  public int next() {
    int val;

    // 当前轮到 v1 且 v1 未耗尽，或 v2 已耗尽
    if ((turn == 0 && i1 < v1.size()) || i2 >= v2.size()) {
      val = v1.get(i1++);
      turn = 1;
    } else {
      val = v2.get(i2++);
      turn = 0;
    }

    return val;
  }

  public boolean hasNext() {
    return i1 < v1.size() || i2 < v2.size();
  }
}

type ZigzagIterator struct {
    v1, v2 []int
    i1, i2 int
    turn   int
}

func Constructor(v1, v2 []int) *ZigzagIterator {
    return &ZigzagIterator{v1: v1, v2: v2}
}

func (z *ZigzagIterator) next() int {
    var val int

    // 当前轮到 v1 且 v1 未耗尽，或 v2 已耗尽
    if (z.turn == 0 && z.i1 < len(z.v1)) || z.i2 >= len(z.v2) {
        val = z.v1[z.i1]
        z.i1++
        z.turn = 1
    } else {
        val = z.v2[z.i2]
        z.i2++
        z.turn = 0
    }

    return val
}

func (z *ZigzagIterator) hasNext() bool {
    return z.i1 < len(z.v1) || z.i2 < len(z.v2)
}

相似题目

题目	难度	考察点
284. 窥探迭代器	中等	设计、迭代器
341. 扁平化嵌套列表迭代器	中等	设计、栈
251. 展开二维向量	中等	设计、双指针
173. 二叉搜索树迭代器	中等	设计、栈
604. 迭代压缩字符串	简单	设计

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/67243410