1.数组中重复的数字
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
思路：可以采用哈希表的方式，最简洁的办法是采用原地交换。

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        /*如果没有重复数字，那么正常排序后，数字i应该在下标为i的位置，所以思路是重头扫描数组，遇到下标为i的数字如果不是i的话，（假设为m),那么我们就拿与下标m的数字交换。在交换过程中，如果有重复的数字发生，那么终止返回ture*/
        int len=nums.size();
        for(int i=0;i<len;i++)
        {
            //位置正确，先不用管
            if (i == nums[i])
                continue;
            //出现了重复，直接返回
            if (nums[i] == nums[nums[i]]) {
                return nums[i];
            }
            //交换
            int temp = nums[nums[i]];
            nums[nums[i]] = nums[i];
            nums[i] = temp;
            //这里的i--是为了抵消掉上面的i++，
            //交换之后需要原地再比较
            i--;
        }
        return -1;
    }
};

2.二维数组中的查找

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        if(matrix.size()==0) return false;
        int row=matrix.size();
        int col=matrix[0].size();
        int i=row-1;
        int j=0;
        while(i>=0&&i<row&&j>=0&&j<col)
        {
            if(matrix[i][j]<target)
                j++;
            else if(matrix[i][j]>target)
                i--;
            else
                return true;
        }
        return false;
    }
};

3.替换空格
思路：从后往前替换，string类也具有push_back()的功能。也可以不使用额外的字符串，每当出现一个空格，就把s扩展两个长度，然后从后往前替换。

class Solution {
public:
    string replaceSpace(string s) {
        string res="";
        for(int i=0;i<s.length();i++)
        {
            if(s[i]==' ')
            {
                res.push_back('%');
                res.push_back('2');
                res.push_back('0');
            }
            else
            {
                res.push_back(s[i]);
            }
        }
        return res;
    }
};
class Solution {
public:
    string replaceSpace(string s) {
        int l1 = s.length() - 1;
        for (int i = 0; i <= l1; i++) {
            if (s[i] == ' ') {
                s += "00";
            }
        }//出现空格，提出两个占位符
        int l2 = s.length() - 1;
        if (l2 <= l1) {
            return s;
        }//没有空格的情况
        for (int i = l1; i >= 0; i--) {
            char c = s[i];
            if (c == ' ') {
                s[l2--] = '0';
                s[l2--] = '2';
                s[l2--] = '%';
            } else {
                s[l2--] = c;
            }
        }//从后往前替换
        return s;
    }
};

4.从尾到头打印链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        vector<int> res;
        stack<int> s1;
        if(head==nullptr) return res;
        ListNode* p=head;
        while(p)
        {
            s1.push(p->val);
            p=p->next;
        }
        while(!s1.empty())
        {
            res.push_back(s1.top());
            s1.pop();
        }
        return res;
    }
};

5.重建二叉树

/**
 * 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<int>& preorder, vector<int>& inorder) {
        int len=preorder.size();
        if(len==0) return nullptr;
        TreeNode* root=new TreeNode(preorder[0]);
        int gen=0;
        for(int i=0;i<len;i++)
        {
            if(inorder[i]==preorder[0])
            {
                gen=i;
                break;
            }
        }//找出根节点
        vector<int> preLeft,preRight,inLeft,inRight;
        for(int i=0;i<gen;i++)
        {
            preLeft.push_back(preorder[i+1]);
            inLeft.push_back(inorder[i]);
        }//左子树的数组
        for(int i=gen+1;i<len;i++)
        {
            preRight.push_back(preorder[i]);
            inRight.push_back(inorder[i]);

        }//右字数的数组
        root->left=buildTree(preLeft,inLeft);
        root->right=buildTree(preRight,inRight);//递归
        return root;
    }
};