剑指Offer

BT Agency by Mohamed Chahin

引言

《剑指 Offer（第 2 版）》通行全球的程序员经典面试秘籍。剖析典型的编程面试题，系统整理基础知识、代码质量、解题思路、优化效率和综合能力这 5 个面试要点。

栈与队列

用两个栈实现队列[09]

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

示例 1

输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]

示例 2

输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]

提示

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

模板

class CQueue {
public:
    CQueue() {

    }
    
    void appendTail(int value) {

    }
    
    int deleteHead() {

    }
};

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

题解

思路和算法

维护两个栈，第一个栈支持插入操作，第二个栈支持删除操作。

根据栈先进后出的特性，我们每次往第一个栈里插入元素后，第一个栈的底部元素是最后插入的元素，第一个栈的顶部元素是下一个待删除的元素。为了维护队列先进先出的特性，我们引入第二个栈，用第二个栈维护待删除的元素，在执行删除操作的时候我们首先看下第二个栈是否为空。如果为空，我们将第一个栈里的元素一个个弹出插入到第二个栈里，这样第二个栈里元素的顺序就是待删除的元素的顺序，要执行删除操作的时候我们直接弹出第二个栈的元素返回即可。

成员变量

维护两个栈 stack1 和 stack2，其中 stack1 支持插入操作，stack2 支持删除操作

构造方法

初始化 stack1 和 stack2 为空

插入元素

插入元素对应方法 appendTail()，stack1 直接插入元素

删除元素

删除元素对应方法 deleteHead()

• 如果 stack2 为空，则将 stack1 里的所有元素弹出插入到 stack2 里
• 如果 stack2 仍为空，则返回 -1，否则从 stack2 弹出一个元素并返回

class CQueue {
    stack<int> stack1, stack2;
public:
    CQueue() {
        while(!stack1.empty())
            stack1.pop();
        while(!stack2.empty())    
            stack2.pop();
    }
    
    void appendTail(int value) {
        stack1.push(value);
    }
    
    int deleteHead() {
        if(stack2.empty()) {
            while(!stack1.empty()) {
                stack2.push(stack1.top());
                stack1.pop();
            }
        }

        if(stack2.empty())
            return -1;
        else {
            int deleteHead = stack2.top();
            stack2.pop();
            return deleteHead;
        }
    }
};

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

包含min函数的栈[30]

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

示例

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 次

模板

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {

    }
    
    void push(int x) {

    }
    
    void pop() {

    }
    
    int top() {

    }
    
    int min() {

    }
};

/**
 * 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();
 */

题解

此题要求写一个栈，与普通栈不同的是多出了一个获取最小值的方法。由于栈比较简单，这里就不多说了，主要还是说说怎么以 O(1) 的时间复杂度查找栈中的最小值。

1. 使用一个变量 min 记录每次栈中的最小值，每次有元素进栈都对 min 进行更新。
   这个方法存在一个问题，没有考虑出栈时，怎么对 min 进行更新。
2. 为了解决出栈对最小值的更新，可以设定一个辅助栈，栈顶表示当前数据栈中的最小值，每次有元素入栈，就将当前最小值入辅助栈。出栈时，辅助栈也要将栈顶元素出栈，这就解决了出栈时的最小值更新问题。

push：将数据入栈的同时，更新最小值。如果入栈元素大于辅助栈顶元素（也就是元素入栈前，数据栈中的最小值），则最小值依旧是数据栈原来的最小值，否则将元素入辅助栈。


pop：将数据栈和辅助栈的栈顶元素同时出栈，保持辅助栈的栈顶元素是数据栈中的最小值。


class MinStack {
    stack<int> minStack;
    stack<int> dataStack;
public:
    /** initialize your data structure here. */
    MinStack() {
        while(!dataStack.empty())
            dataStack.pop();
        while(!minStack.empty())
            minStack.pop();
        minStack.push(INT_MAX);
    }
    
    void push(int x) {
        dataStack.push(x);
        minStack.push(std::min(x, minStack.top()));
    }
    
    void pop() {
        dataStack.pop();
        minStack.pop();
    }
    
    int top() {
        return dataStack.top();
    }
    
    int min() {
        return minStack.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();
 */

链表

从尾到头打印链表[06]

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例

输入：head = [1,3,2]
输出：[2,3,1]

限制

• 0 <= 链表长度 <= 10000

模板

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {

    }
};

题解

反转链表[24]

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

限制

• 0 <= 节点个数 <= 5000

模板

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {

    }
};

题解

考虑使用递归法遍历链表，当越过尾节点后终止递归，在回溯时修改各节点的 next 引用指向。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head || !head->next)
            return head;
        else {
            ListNode* res = reverseList(head->next);
            ListNode* tmp = head->next->next;
            head->next->next = head;
            head->next = nullptr;
            return res;
        }    
    }
};

复杂链表的复制[35]

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

示例1

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例2

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

示例 3

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

示例 4

输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。

提示

• -10000 <= Node.val <= 10000
• Node.random 为空（null）或指向链表中的节点
• 节点数目不超过 1000

模板

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        
    }
};

题解

栈的特点是后进先出，即最后压入栈的元素最先弹出。考虑到栈的这一特点，使用栈将链表元素顺序倒置。从链表的头节点开始，依次将每个节点压入栈内，然后依次弹出栈内的元素并存储到数组中。

注意不要随意改变 head，要另设一个 ListNode。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        ListNode* pre = head;
        stack<int> s;
        vector<int> res;

        while(pre) {
            s.push(pre->val);
            pre = pre->next;
        }

        while(!s.empty()) {
            res.push_back(s.top());
            s.pop();
        }

        return res;
    }
};

字符串

替换空格[05]

请实现一个函数，把字符串 s 中的每个空格替换成”%20”。

示例

输入：s = "We are happy."
输出："We%20are%20happy."

限制

• 0 <= s 的长度 <= 10000

模板

class Solution {
public:
    string replaceSpace(string s) {

    }
};

题解

class Solution {
public:
    string replaceSpace(string s) {
        string res;
        for(auto& c : s) {
            if(c == ' ') {
                res.push_back('%');
                res.push_back('2');
                res.push_back('0');
            } else
                res.push_back(c);
        }

        return res;
    }
};

左旋转字符串[58]

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串”abcdefg”和数字2，该函数将返回左旋转两位得到的结果”cdefgab”。

示例1

输入: s = "abcdefg", k = 2
输出: "cdefgab"

示例 2

输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"

限制

• 1 <= k < s.length <= 1000`

模板

class Solution {
public:
    string reverseLeftWords(string s, int n) {

    }
};

题解

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        auto it = s.begin();
        for(int i = 0; i < n; i++){
            it++;
        }
        rotate(s.begin(), it, s.end());
        return s;
    }
};