LeetCode 面试题 03.01. 三合一

Three in One LCCI

Posted by MatthewHan on 2020-07-24

Problem Description

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

你应该实现:

  1. push(stackNum, value)

  2. pop(stackNum)

  3. isEmpty(stackNum)

  4. peek(stackNum)

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

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

e.g.

  • 示例 1:

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

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

  • 示例 2:

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

Solution

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

单个数组

  • pop方法只要操作head指针的size即可:大于0,自减;小于等于0,return -1
  • peek方法类似pop方法;
  • push方法,判断head指针的size,有空余,则移动指针去塞入新数据;
  • isEmpty方法,判断head指针的size,为0则为空。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
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 +
'}';
}
}