《剑指offerDAY1_3,6,9,10》

说明：本题太过简单，不多bb，主要是使用C++解答，熟悉一下，C++的操作
首先就是定义一个栈容器，利用栈的后入先出的特点，使得数据在栈中待过一轮后放到容器类中达到一个逆序的效果。

class Solution {
public:vector<int> reversePrint(ListNode* head) {stack<int> stackOne;ListNode* temp = head;while (temp != NULL) {stackOne.push(temp->val);temp = temp->next;}// 创建一个vector 返回逆序结果vector<int> vec;while (!stackOne.empty()) {vec.push_back(stackOne.top());stackOne.pop();}return vec;}
};

主要提到c++的使用
vector的作用
vector是最常用的容器之一，功能十分强大，可以储存、管理各种类型的数据。在很多情况下可以用来代替功能比较局限的普通数组，因为我们知道，普通数组只能实现一对一的映射而不能实现一对多的映射，vector就是专门为了解决这个问题而诞生的。vector也可以称为动态数组，因为其大小是根据实时更新而变化的，正因为如此vector显得更加灵活易用。
vector<储存的类型> 容器名
如：
储存int型的值 vector v;
储存double型的值 vector v;
储存string型的值 vector v;
储存结构体或者类的值的值 vector<结构体名> v;

当然也可以定义vector数组：
储存int型的值 vector v[n];
储存double型的值 vector v[n];
等等，n为数组的大小

//这些都是必会的成员函数
size()//返回返回容器中元素个数
begin()//返回头部迭代器
end()//返回尾部+1迭代器
rbegin()//返回逆首部迭代器
rend()//返回逆尾部-1迭代器
front()//返回首个元素
back()//返回尾部元素
push_back()//在末尾添加一个函数
emplace_back()//和push_back()是一样的作用
pop_back()//弹出最后一个元素
empty()//判断是否为空
insert()//在指定位置插入元素
erase()//在指定位置删除元素
clear()//清空容器
详细解析：
（1）size()
size()是最常用的成员函数了，常用于vector的遍历和元素个数的查询（2）push_back()
出了初始化以外，push_back()是vector最重要的修改函数了，复杂度为O(1)，而insert()的复杂度为O(n)，差距明显（3）front()、back()
查询首元素和未元素，其实通过随机访问，v[0]、v[v.size()-1]是可以达到相同效果的，用front()和back()显得专业点（4）begin()、end()
通常用来方便排序的，也可以用来遍历，但没必要，通过下标遍历更简单快捷，rbegin()、rend()则可以用来逆序排序（5）insert()
insert (position, x );
insert (position, n, x );
insert (position, first, last );
插入新的元素，
第一个函数，在迭代器指定的位置前插入值为x的元素
第二个函数，在迭代器指定的位置前插入n个值为x的元素
第三个函数，在迭代器指定的位置前插入另外一个容器的一段序列迭代器first到last
复杂度很高，迫不得已不使用（6）erase()
erase ( position );
erase (first, last );
删除元素或一段序列
同样地，复杂度很高，迫不得已不使用

说明：刚开始随便找的练手题没难度，还是熟悉c++语法

class Solution {
public:int findRepeatNumber(vector<int>& nums) {int i = 0;while(i < nums.size()) {if(nums[i] == i) {i++;continue;}if(nums[nums[i]] == nums[i])return nums[i];swap(nums[i],nums[nums[i]]);}return -1;}
};

说明：斐波那契数列数列的一般思想是递归的方法做，但是这个题不太一样，里面有一个取模的运算，所以就会导致如果使用递归的方法写的话会，超出时间限制。
所以还是看看远处的迭代吧，家人们。ps：有一个递归的思路可以不超出时间限制，不过说到底也只是做了一些手脚罢了

迭代：

class Solution {
public:int fib(int n) {int MOD = 1000000007;if (n < 2) {return n;}int p = 0, q = 0, r = 1;for (int i = 2; i <= n; ++i) {p = q; q = r; r = (p + q)%MOD;}return r;}
};

递归：

class Solution {const int mod = 1000000007;int dp[101] = {0};
public:int fib(int n){if(dp[n]) return dp[n];if(n < 2) return n;dp[n] = (fib(n-1)+fib(n-2)) % mod;return dp[n];}
};

说明：经典题目之一，用两个栈来构造一个队列
题目中的CQueue不用实现，主要就是看怎么用栈的操作来模拟队列的操作，队列：先进后出，从队尾添加，从队首删除,那么可以用两个栈来实现队列的操作，设置一个入栈，一个出栈，出栈的栈顶弹出可以模拟队列的队首删除，入栈的压栈操作则可以模拟队列的队尾添加，由于我们是要在队尾添加，队首删除，则必须要保证进行删除操作的时候是在出栈操作的，当出栈完全为空的时候将入栈所有的元素压入出栈，再进行出栈操作，如果出栈为空，入栈为空，则证明该模拟队列没有任何元素，所以不能进行删除操作。

class CQueue {stack<int> inStack;stack<int> outStack;
public:CQueue() {}void appendTail(int value) {inStack.push(value);}int deleteHead() {if(outStack.empty()) {if(inStack.empty()) {return -1;}while(!inStack.empty()) {outStack.push(inStack.top());inStack.pop();}}int val = outStack.top();outStack.pop();return val;}
};/* Your CQueue object will be instantiated and called as such:* CQueue* obj = new CQueue();* obj->appendTail(value);* int param_2 = obj->deleteHead();*/