LeetCode 剑指Offer

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

题目描述

​ 用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，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 次

解题思路

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

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

  • 解题思路：

    分为栈A与栈B两个栈：

    ​ 其中栈A进行正常的pop与push操作，而栈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, 其中Hashmap的key为值item，value为下标index，存入Hashmap。

​ 若遍历时Hashmap存在值为target - 当前遍历的item的key，则返回[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