LeetCode 面试题 03.01. 三合一

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

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 回帖
  • 算法
    437 引用 • 254 回帖 • 24 关注
  • Java

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

    3201 引用 • 8216 回帖
  • Stack
    11 引用 • 3 回帖

相关帖子

欢迎来到这里!

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

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