剑指 Offer（普通版）
剑指 Offer 03. 数组中重复的数字
//方法一：class Solution {public:int findRepeatNumber(vector& nums) {unordered_map map;for (int i = 0; i < nums.size(); i++) {if (map.find(nums[i]) != map.end()) { //没找到才会返回end的迭代器return nums[i];} else {map[nums[i]] ++;}}return -1;}};//方法二：class Solution {public:int findRepeatNumber(vector& nums) {sort(nums.begin(), nums.end());for (int i = 0; i < nums.size() - 1; i++) {if (nums[i] == nums[i + 1]) {return nums[i];}}return -1;}};//方法三：class Solution {public:int findRepeatNumber(vector& nums) {for (int i = 0; i < nums.size(); i++) {while (nums[i] != i) {if (nums[nums[i]] == nums[i]) { //即该值索引位已经为该值了return nums[i];}int t = nums[i];nums[i] = nums[t];nums[t] = t;}}return -1;}};
方法一：利用C++中自带的哈希表，通过键值访问，若已经有了则表示这个数字重复了 。
方法二：直接进行排序，看相邻两个元素是否相同 。
方法三：鸽巢原理，也就是相当于把原表当作哈希表，如果其相应数值索引位置存储的值等于这个索引值，那么就表示该值已经出现一次了，下次再出现就是重复值了 。
剑指 Offer 04. 二维数组中的查找
class Solution {public:bool findNumberIn2DArray(vector>& matrix, int target) {if (matrix.size() == 0) {return false;}int row = 0, col = matrix[0].size() - 1;while (row < matrix.size() && col >= 0) {if (matrix[row][col] == target) {return true;} else if (matrix[row][col] > target) {col--;} else if (matrix[row][col] < target) {row++;}}return false;}};
因为每行的最后一个都是该行最大的，所以先从最后判断，若大于就表示这一行都比小，就到下一行重新判断，若小于就表示这一行存在比它大的数和比它小的数，就在这行找就行了，找不到就返回false，注意没有东西的特殊情况 。
剑指 Offer 05. 替换空格
//方法一：class Solution {public:string replaceSpace(string s) {for (int i = 0; i < s.size(); i++) {if (s[i] == ' ') {s = s.replace(i, 1, "%20");}}return s;}};//方法二：class Solution {public:string replaceSpace(string s) {while (s.find(" ") + 1) {s = s.replace(s.find(' '), 1, "%20");}return s;}};//find函数没找到就会返回-1.
没啥说的，找到后替换就行 。
剑指 Offer 06. 从尾到头打印链表
class Solution {public:vector reversePrint(ListNode* head) {vector num;stack myStack;ListNode *temp = head;while (temp) {myStack.push(temp->val);temp = temp->next;}while (!myStack.empty()) {num.push_back(myStack.top());myStack.pop();}return num;}};
很简单的先用栈存储，然后再pop进数组就行了 。
剑指 Offer 07. 重建二叉树
/*** Definition for a binary tree node.* struct TreeNode {*int val;*TreeNode *left;*TreeNode *right;*TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/class Solution {public:// 递归解决：前序遍历是根左右，中序遍历是左根右，我们可以根据根来分别划分 前序数组和中序数组，然后递归处理划分的数组即可TreeNode* buildTree(vector& preorder, vector& inorder) {//传递的数组位空说明就没有该节点if (preorder.empty() || inorder.empty()) {return nullptr;}// 1、建立根节点，然后根据根节点来划分 前序数组 和 中序数组，前序数组的第一个元素就是该根节点的值TreeNode *root = new TreeNode(*preorder.begin());// 2、来找到 中序数组 中该根节点的位置auto it = find(inorder.begin(), inorder.end(), *preorder.begin());// 3、划分中序数组，根据根节点的位置，因为中序数组根节点的左边为左子树，右边为右子树vector