每日算法刷题Day15-0到n-1中缺失的数字、调整数组顺序、从尾到头打印链表、用两个栈实现队列

⭐每日算法题解系列文章旨在精选重点与易错的算法题，总结常见的算法思路与可能出现的错误，与笔者另一系列文章有所区别，并不是以知识点的形式提升算法能力，而是以实战习题的形式理解算法，使用算法。

🔥本文已收录于算法刷题系列专栏： 每日算法题解 欢迎订阅，持续更新。

45.0到n-1中缺失的数字

一个长度为 n−1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围 0 到 n−1之内。

在范围 0 到 n−1的 n 个数字中有且只有一个数字不在该数组中，请找出这个数字。

数据范围

1≤n≤1000

样例

输入：[0,1,2,4]

输出：3

思路

此题思路比较简单，主要考察的是对于STL的应用

本次采用的思路是：采用哈希表，先插入0~n-1这n个数字，然后再删除其中nums含有的数字，最后剩下的一个数字即是所需的。

代码

class Solution {
public:
    int getMissingNumber(vector<int>& nums) {
    unordered_set<int> S;
    for(int i = 0; i <= nums.size();i++)S.insert(i);
    
    for(auto x : nums)S.erase(x);
    
    return *S.begin();
    
    }
};

46.调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序。

使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分。

数据范围

数组长度 [0,100]。

样例

输入：[1,2,3,4,5]

输出: [1,3,5,2,4]

思路

这道题可以采用双指针的方法实现。

首先第一个指针指向第一个地方。

• 判断第一个指针，如果是奇数就跳过，直到停到偶数为止
• 判断第二个指针，如果是偶数就跳过，直到奇数为止。
• 最后交换两个数即可。

当i > j时退出循环。

class Solution {
public:
    void reOrderArray(vector<int> &array) {
         int i = 0, j = array.size() - 1;
         while( i < j)
         {
             while(array[i]%2)i++;
             while(array[j]%2 == 0)j--;
             if( i < j)swap(array[i] , array[j]);
         }
    }
};

47.从尾到头打印链表

输入一个链表的头结点，按照 从尾到头 的顺序返回节点的值。

返回的结果用数组存储。

数据范围

0≤ 链表长度 ≤1000。

样例

输入：[2, 3, 5]
返回：[5, 3, 2]

思路

注意这里函数是vector<int> 型的，因此return的变量也应该是vector<int> 型。首先定义vector，然后用push_back压入，再经过reverse，输出即可。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> printListReversingly(ListNode* head) {
        vector<int> res;
        for(auto p = head; p ; p = p -> next)res.push_back(p -> val);
        reverse(res.begin() , res.end());
        return res;
    }
};

48.用两个栈实现队列

请用栈实现一个队列，支持如下四种操作：

• push(x) – 将元素x插到队尾；
• pop() – 将队首的元素弹出，并返回该元素；
• peek() – 返回队首元素；
• empty() – 返回队列是否为空；

注意：

• 你只能使用栈的标准操作：push to top，peek/pop from top, size 和 is empty；
• 如果你选择的编程语言没有栈的标准库，你可以使用list或者deque等模拟栈的操作；
• 输入数据保证合法，例如，在队列为空时，不会进行pop或者peek等操作；

数据范围

每组数据操作命令数量 [0,100]。

样例

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);
queue.peek();  // returns 1
queue.pop();   // returns 1
queue.empty(); // returns false

思路

此题的思路类似于汉诺塔，如果想要通过两个栈实现队列的操作，即先进后出。pop的是队首的元素，这里采用类似的方式如下图所示：

class MyQueue {
public:
    /** Initialize your data structure here. */
    stack<int> s1,s2;
    MyQueue() {
        
    }
    
    /** Push element x to the back of queue. */
    void push(int x) {
        s1.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        while(s1.size() > 1)s2.push(s1.top()),s1.pop();
        int t = s1.top();
        s1.pop();
        while(s2.size()) s1.push(s2.top()),s2.pop();
        return t;
    }
    
    /** Get the front element. */
    int peek() {
        while(s1.size() > 1)s2.push(s1.top()),s1.pop();
        int t = s1.top();
        while(s2.size()) s1.push(s2.top()),s2.pop();
        return t;
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        s1.empty();
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * bool param_4 = obj.empty();
 */