LeetCode 面试题 03.01. 三合一

本贴最后更新于 1323 天前,其中的信息可能已经时过境迁

0301.png

Problem Description

三合一。描述如何只用一个数组来实现三个栈。

你应该实现:

  1. push(stackNum, value)
  2. pop(stackNum)
  3. isEmpty(stackNum)
  4. peek(stackNum)

stackNum 表示栈下标,value 表示压入的值。

构造函数会传入一个 stackSize 参数,代表每个栈的大小。

e.g.

  • 示例 1:

    • 输入:
      ["TripleInOne", "push", "push", "pop", "pop", "pop", "isEmpty"]
      [[1], [0, 1], [0, 2], [0], [0], [0], [0]]
      
    • 输出:
      [null, null, null, 1, -1, -1, true]
      

    说明:当栈为空时 pop, peek 返回-1,当栈满时 push 不压入元素。

  • 示例 2:

    • 输入:
      ["TripleInOne", "push", "push", "push", "pop", "pop", "pop", "peek"]
      [[2], [0, 1], [0, 2], [0, 3], [0], [0], [0], [0]]
      
    • 输出:
      [null, null, null, null, 2, 1, -1, -1]
      

Solution

用数组来实现栈是非常简单的,不过这里需要实现 3 个栈且只能用一个数组。那肯定是需要将这个数组分段利用指针去管理了。

0301flow.png

  • pop 方法只要操作 head 指针的 size 即可:大于 0,自减;小于等于 0,return -1
  • peek 方法类似 pop 方法;
  • push 方法,判断 head 指针的 size,有空余,则移动指针去塞入新数据;
  • isEmpty 方法,判断 head 指针的 size,为 0 则为空。
public class ThreeInOne {

    private final int[] data;
    private final int size;
    private final int capacity;

    /**
     * 执行用时: 13 ms , 在所有 Java 提交中击败了 56.62% 的用户
     * 内存消耗: 49.1 MB , 在所有 Java 提交中击败了 100.00% 的用户
     *
     * @param stackSize
     */
    public ThreeInOne(int stackSize) {
        capacity = stackSize * 3;
        size = capacity + 3;
        data = new int[size];
    }

    public void push(int stackNum, int value) {
        int index = headIndex(stackNum);
        System.out.println("index = " + index);

        // 头指针,容量计数功能,如果超过容量,就塞不了
        if (data[index] < capacity / 3) {
            data[index]++;
            // 剩余位置塞入数据
            data[index + data[index]] = value;
        }
    }

    public int pop(int stackNum) {
        int index = headIndex(stackNum);
        // stack为空
        if (data[index] == 0) {
            return -1;
        } else {
            int temp = data[index + data[index]];
            data[index]--;
            // 这里并不需要真的删除这个元素
            return temp;
        }
    }

    public int peek(int stackNum) {
        int index = headIndex(stackNum);
        if (data[index] == 0) {
            return -1;
        } else {
            return data[index + data[index]];
        }
    }

    public boolean isEmpty(int stackNum) {
        return data[headIndex(stackNum)] == 0;
    }

    /**
     * 根据stack下标取头指针
     * @param stackNum
     * @return
     */
    public int headIndex(int stackNum) {
        int index = 0;
        switch (stackNum) {
            case 1:
                index = capacity / 3 + 1;
                break;
            case 2:
                index = size - 1 - capacity / 3;
                break;
            default:
        }
        return index;
    }

    @Override
    public String toString() {
        return "ThreeInOne{" +
                "data=" + Arrays.toString(data) +
                ", size=" + size +
                ", capacity=" + capacity +
                '}';
    }
}
  • LeetCode

    LeetCode(力扣)是一个全球极客挚爱的高质量技术成长平台,想要学习和提升专业能力从这里开始,充足技术干货等你来啃,轻松拿下 Dream Offer!

    209 引用 • 72 回帖
  • 算法
    388 引用 • 254 回帖 • 22 关注
  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3165 引用 • 8206 回帖
  • Stack
    11 引用 • 3 回帖

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...