剑指offer——C++打卡

最近开始用c++写算法，浅浅的记录一下打卡题。
之后写的题会持续在里面更新！

栈与队列（简单）4.25 剑指 Offer 09. 用两个栈实现队列

思路：题目需要利用两个栈实现队列，队列是一端进一端出，我们可以将两个栈拼接起来，一个栈作为队尾进元素，将这个栈的元素d出到另一个栈，另一个栈作为队头输出，就可以实现了。
代码：

class CQueue {
public:
    stack <int> headStack;
    stack <int> frontStack;
    CQueue() {
        
    }
    
    void appendTail(int value) {
        headStack.push(value);
    }
    
    int deleteHead() {
        if (headStack.empty()) {
            return -1;
        } else {
            while (!headStack.empty()) {
                frontStack.push(headStack.top());
                headStack.pop();
            }
            int val = frontStack.top();
            frontStack.pop();
             while (!frontStack.empty()) {
                headStack.push(frontStack.top());
                frontStack.pop();
            }
            return val;
        }
    }
};

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

思路：首先设置两个栈，第一个栈用来记录输入的元素，第二个栈用于保存数据最小值，这个题的关键在于如何对最小栈进行压入，当栈空时，直接压入第一个元素，并默认此时这个元素为最小值，在压入后续元素时，进行比对，如果小了，就压入栈中，作为新的最小值，如果不是，那么就继续压入一个当前最小值元素，这样做对目的是，在后续两个栈d出元素时，可以保证最小栈栈顶永远是最小的。

class MinStack {
public:
    /** initialize your data structure here. */
    stack <int> myStack;
    stack <int> minStack;
    MinStack() {

    }
    
    void push(int x) {
        myStack.push(x);
        if (minStack.empty()) {
            minStack.push(x);
        } else {
            if (x < minStack.top()) {
                minStack.push(x);
            } else {
                minStack.push(minStack.top());
            }
        }
    }
    
    void pop() {
        myStack.pop();
        minStack.pop();
    }
    
    int top() {
       return (int)myStack.top();
    }
    
    int min() {
        return minStack.top();
    }
};

链表（简单）4.26 剑指 Offer 06. 从尾到头打印链表

很简单可以用个栈记录输入元素，然后给到容器里就行，这里直接调用的数组的函数，让元素一直插入在头部位置。
这里直接调库，循环一遍就行了。

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        ListNode *temp = head;
         vector <int> ans;
        while (temp) {
            
            ans.insert(ans.begin(), temp->val);
            temp = temp->next;
        }

        return ans;
    }
};

剑指 Offer 24. 反转链表

利用三指针原地反转

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *temp;
        ListNode *nextTemp;
        ListNode *p;
        temp = head;
        p = NULL;
        nextTemp = NULL;
        while (temp) {
            nextTemp = temp->next;
            temp->next = p;
            p = temp;
            temp = nextTemp;
        }
        return p;
    }
    
};

剑指 Offer 35. 复杂链表的复制

思路：这题的难点就在于增加指针是随机的，要做到深拷贝就需要指向新生成的随机结点，这里我的做法是在原来的结点后新生成一个结点，第一遍仅初始化next指针和值，第二遍遍历时，因为新的结点已经生成，根据旧结点的指向给新结点的random赋值，最后将链表新结点取出即可。

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == NULL) {
            return head;
        }
        Node* temp = head;
        while(temp) {
            Node *newNode = new Node(temp->val);
            newNode->next = temp->next;
            temp->next = newNode;
            temp = newNode->next;
            
        }
        temp = head;
        while(temp) {
            if (temp->random != NULL) {
                temp->next->random = temp->random->next;
            }
            temp = temp->next->next;
        }
        Node *ans = head->next;
        temp = head;
        Node *copyNode = head->next;
        while(temp) {
            temp->next = temp->next->next;
            temp = temp->next;
            if (copyNode->next) {
                copyNode->next = copyNode->next->next;
                copyNode = copyNode->next;
            }
        }
        return ans;
    }
};