⭐每日算法题解系列文章旨在精选重点与易错的算法题，总结常见的算法思路与可能出现的错误，与笔者另一系列文章有所区别，并不是以知识点的形式提升算法能力，而是以实战习题的形式理解算法，使用算法。
🔥本文已收录于算法刷题系列专栏： 每日算法题解 欢迎订阅，持续更新。
45.0 到 n-1 中缺失的数字
一个长度为 n−1 的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围 0 到 n−1 之内。
在范围 0 到 n−1 的 n 个数字中有且只有一个数字不在该数组中，请找出这个数字。
数据范围
1≤n≤1000
样例
思路
此题思路比较简单，主要考察的是对于 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。
样例
思路
注意这里函数是 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 1queue.pop(); // returns 1queue.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(); */
复制代码
评论