36.日常算法

1.最小栈

题目来源
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

示例 1:
输入：
[“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”]
[[],[-2],[0],[-3],[],[],[],[]]

class MinStack {
public:MinStack() {}void push(int val) {putstack.push(val);if (minstack.size() == 0 || (putstack.top() <= minstack.top())) minstack.push(val);}void pop() {if (putstack.top() == minstack.top())minstack.pop();putstack.pop();}int top() {return putstack.top();}int getMin() {return minstack.top();}stack<int> putstack;stack<int> minstack;
};/*** Your MinStack object will be instantiated and called as such:* MinStack* obj = new MinStack();* obj->push(val);* obj->pop();* int param_3 = obj->top();* int param_4 = obj->getMin();*/

2.丢失的数字

题目来源
给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

示例 1：
输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。

class Solution {
public:int missingNumber(vector<int>& nums) {int val = 0;for (int i = 0; i <= nums.size(); ++i) val ^= i;for (int i = 0; i < nums.size(); ++i) val ^= nums[i];return val;}
};