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

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

?本文已收录于算法刷题系列专栏: ​​每日算法题解​​ 欢迎订阅,持续更新。

每日算法刷题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 型。首先定义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的是队首的元素,这里采用类似的方式如下图所示:

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

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

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();
*/
发表评论

相关文章