LeetCode 剑指Offer

剑指 Offer 09. 用两个栈实现队列

题目描述

​ 用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTaildeleteHead,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回-1 )

  • 实例:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    # 实例1:
    # 输入:
    ["CQueue","appendTail","deleteHead","deleteHead","deleteHead"]
    [[],[3],[],[],[]]
    # 输出:
    [null,null,3,-1,-1]

    # 实例2:
    # 输入:
    ["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
    [[],[],[5],[2],[],[]]
    # 输出:
    [null,-1,null,null,5,2]
  • 提示

    • 1 <= values <= 10000
    • 最多会对appendTail、deleteHead进行10000 次调用

解题思路

  • 对于输入输出样例的解释:

    ​ 输入上半对应的是操作函数名,下半指的是对应的参数。

    比如:

    1. ["CQueue","appendTail","deleteHead","deleteHead","deleteHead"]
      [[],[3],[],[],[]]

    ​ 则是 CQueue()->appendTai(3)->deleteHead()->deleteHead()->deleteHead()

    1. ["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]

      [[],[],[5],[2],[],[]]

      则是CQueue()->deleteHead()->appendTail(5)->appendTail(2)->deleteHead()->deleteHead()

  • 解题思路:

    即通过两个栈实现一个队列的操作,由于单独一个栈无法实现出队,因此设栈A负责入队,栈B辅助出队。

    • 入队:直接push入栈A即可。
    • 出队:将栈A栈顶元素依次push入栈B,最后将栈B的顶部元素pop出来,最后将栈B栈顶元素依次push回栈A即可。

实现代码

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
class CQueue {
public:
stack<int> stackA;
stack<int> stackB;
CQueue() {}

void appendTail(int value) {
stackA.push(value);
}

int deleteHead() {
if(stackA.empty())
return -1;
while(!stackA.empty()){
int temp = stackA.top();
stackA.pop();
stackB.push(temp);
}
int res = stackB.top();
stackB.pop();
while(!stackB.empty()){
int temp = stackB.top();
stackB.pop();
stackA.push(temp);
}
return res;
}
};

/**
* Your CQueue object will be instantiated and called as such:
* CQueue* obj = new CQueue();
* obj->appendTail(value);
* int param_2 = obj->deleteHead();
*/

剑指 Offer 30. 包含min函数的栈

题目描述

​ 定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。

  • 实例:

    1
    2
    3
    4
    5
    6
    7
    8
    MinStack minStack = new MinStack();
    minStack.push(-2);
    minStack.push(0);
    minStack.push(-3);
    minStack.min(); --> 返回 -3.
    minStack.pop();
    minStack.top(); --> 返回 0.
    minStack.min(); --> 返回 -2.
  • 提示

    • 各函数的调用总次数不超过 20000 次

解题思路

​ 实际上和直接手写一个栈的数据结构类似,一般的栈poppush的时间复杂度是O(1),而min由于要遍历栈(数组),因此时间复杂度为O(n)

​ 由于本题要求min的时间复杂度也要为O(1),因此本题可用双栈的方法解决,使其时间复杂度最终也为O(1)

  • 解题思路:

    分为栈A与栈B两个栈:

    ​ 其中栈A进行正常的poppush操作,而栈B则push栈A每次进行入栈操作时的最小的数,并且当某个元素从栈Apop后,栈B也要同步进行pop的操作。

    ∴ 栈Bpush的逻辑为: 栈B空的时候,push栈Apush的元素x,栈B非空时, push的value需要<=栈B的栈顶元素;

    pop的逻辑为: 若栈Apop的元素为栈B的栈顶元素时,栈B进行pop操作。

    因次栈minstack与栈A栈B的关系为:

    1. `minstack.push/pop => A.push/pop => 根据条件再决定是否B.push/pop`
     2. `minstack.top() == A.top()`
     3. `minstack.min() == B.top()`
    

实现代码

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
class MinStack:

def __init__(self):
"""
initialize your data structure here.
"""
self.stackA, self.stackB = [],[]


def push(self, x: int) -> None:
self.stackA.append(x)
if not self.stackB or self.stackB[-1] >= x:
self.stackB.append(x)

def pop(self) -> None:
if self.stackA.pop() == self.stackB[-1]:
self.stackB.pop()

def top(self) -> int:
return self.stackA[-1]

def min(self) -> int:
return self.stackB[-1]


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.min()

2023.2.2 今日收获

今天的题目属于 栈与队列 的基础数据结构。

​ 第一道题是用栈实现队列的操作,第二道题是用空间换取时间。双栈的结合使用既可以模拟队列,又可以优化单栈操作的时间复杂度。第二道题没有用C++转为使用Python是因为C++定义链表的知识忘了很多…

​ 回头第二题需要用C++链表重新写一遍栈的数据结构定义。

==补充==

​ …额,突然记起来C++内部其实有Stack的数据结构,这题并不需要用链表再定义Stack这么麻烦,补充C++写法如下:

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
class MinStack {
public:
/** initialize your data structure here. */
stack<int> stackA,stackB;
MinStack() {
}

void push(int x) {
stackA.push(x);
if(stackB.empty() || stackB.top() >= x)
stackB.push(x);
}

void pop() {
if(stackA.top()==stackB.top()){
stackA.pop();
stackB.pop();
}
else {
stackA.pop();
}
}

int top() {
return stackA.top();
}

int min() {
return stackB.top();
}
};

/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(x);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->min();
*/

LeetCode 精选面试题

1. 两数之和

题目描述

​ 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。

​ 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

​ 你可以按任意顺序返回答案。

  • 实例:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    # 实例1
    # 输入:
    nums = [2,7,11,15], target = 9
    # 输出:
    [0,1]

    # 实例2
    # 输入:
    nums = [3,2,4], target = 6
    # 输出:
    [1,2]

    # 实例3
    # 输入:
    nums = [3,3], target = 6
    # 输出:
    [0,1]
  • 提示

    • 2 <= nums.length <= 10^4
    • -10^9 <= nums[i] <= 10^9
    • -10^9 <= target <= 10^9
    • 只会存在一个有效答案

解题思路

​ 利用Python Dict数据类型模拟Hashmap, 其中Hashmapkey为值itemvalue为下标index,存入Hashmap

​ 若遍历时Hashmap存在值为target - 当前遍历的itemkey,则返回[index, Hashmap[target-item]]

实现代码

1
2
3
4
5
6
7
class Solution(object):
def addTwo(self, nums, target):
Hashmap = {}
for index, item in enumerate(nums):
if target - item in Hashmap:
return [index, Hashmap[target-item]]
Hashmap[item] = index