LeetCode 面试题 03.01. 三合一

Espada 最近想系统地学声乐! 本文由博客端 https://blog.yuanmo.xyz 主动推送

0301.png

Problem Description

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

你应该实现:

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

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

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

e.g.

Solution

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

0301flow.png

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!

    197 引用 • 74 回帖 • 1 关注
  • 算法
    350 引用 • 242 回帖 • 17 关注
  • Java

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

    2812 引用 • 8043 回帖 • 749 关注
  • Stack
    11 引用 • 3 回帖

赞助商 我要投放

欢迎来到这里!

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

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