🔥本文已收录于算法刷题系列专栏： 每日算法题解 欢迎订阅，持续更新。
@[TOC]
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();
*/