iLeft(inorder.begin(), it), iRight(it + 1, inorder.end());// 4、划分前序数组，根据中序数组的左右子树的大小int n = iLeft.size();//通过刚才计算出来的左子树长度，来返回左右子树的前序和中序遍历数组vector pLeft(preorder.begin() + 1, preorder.begin() + 1 + n), pRight(preorder.begin() + 1 + n, preorder.end());// 5、递归处理左右子树root->left = buildTree(pLeft, iLeft);root->right = buildTree(pRight, iRight);// 6、返回该节点return root;}};
构建二叉树，根据前序和中序遍历的结果构建一个二叉树 。
剑指 Offer 09. 用两个栈实现队列
class CQueue {public:stack headStack;stack rearStack;CQueue() {}void appendTail(int value) {headStack.push(value);}int deleteHead() {if (headStack.empty()) {return -1;} else {while (!headStack.empty()) {rearStack.push(headStack.top());headStack.pop();}int value = http://www.kingceram.com/post/rearStack.top();rearStack.pop();while (!rearStack.empty()) {headStack.push(rearStack.top());rearStack.pop();}return value;}}};/*** Your CQueue object will be instantiated and called as such:* CQueue* obj = new CQueue();* obj->appendTail(value);* int param_2 = obj->deleteHead();*/
使用两个栈实现队列，无非就是一个栈用作队列存储（），另一栈用作队列输出（），每次要出队的时候就让存储栈（）将所有数据pop到输出栈（）上，然后输出输出栈的栈顶元素，最后再将剩下的元素pop回存储栈（），每次都如此就完成两个栈实现一个队列了 。
剑指 Offer 10- I. 斐波那契数列
class Solution {public:int fib(int n) {if (n < 2) {return n;}int f1 = 0, f2 = 1;for (int i = 0; i < n - 1; i++) {int t = f1 % 1000000007;f1 = (f1 + f2) % 1000000007;f2 = t;}return (f1 + f2) % 1000000007;}};
用两个存储F(N - 1)和F(N - 2)就行了，注意题上说的答案要取余 。同时递归也可以写，但是递归实在是太慢了，会超时 。
剑指 Offer 10- II. 青蛙跳台阶问题
class Solution {public:int numWays(int n) {if (n == 0 || n == 1) {return 1;}int f1 = 0, f2 = 1;for (int i = 0; i < n; i++) {int t = f1 % 1000000007;f1 = (f1 + f2) % 1000000007;f2 = t;}return (f1 + f2) % 1000000007;}};
这不就是斐波那契的变形嘛，难点就在于你啥时候能理解它的原理，哎嘘，就看这个大哥的讲解吧 。
剑指 Offer 11. 旋转数组的最小数字
class Solution {public:int minArray(vector& numbers) {int left = 0, right = numbers.size() - 1;int mid;while (left < right) {mid = (left + right) / 2;if (numbers[right] > numbers[mid]) {right = mid;} else if (numbers[right] < numbers[mid]) {left = mid + 1;} else { //去重right--;}}return numbers[left];}};
只要右边比中间大，他就是顺序的，所以我们可以只通过右边对其进行判断 。right比mid大说明mid到right都是顺序的就不用看了，令right到mid位置就行 。right比mid小说明mid到right之间经过了旋转，则应该令left到mid位置，right不变继续进行查找 。还有一种最重要的情况就是right和mid是相等的，那么我们就要对其进行去重处理，就得让right– 。
剑指 Offer 12. 矩阵中的路径
class Solution {public:bool exist(vector>& board, string word) {//若二维数组为空，就看word是否为空，是空就能匹配上，返回1，不是空就直接返回0if (!board.size() || !board[0].size()) {return !word.length();}for (int row = 0; row < board.size(); row++) {for (int col = 0; col < board[0].size(); col++) {//利用&&的特性，等该位置字符匹配上了才会调用后边的函数if (board[row][col] == word[0] && backSearchResult(board, row, col, word, 0)) { //直到将word全部找到了条件才成立return 1;}}}return 0;}private:bool backSearchResult(vector