题解 | #神奇的数字#

思路：

题目的主要信息：

将字符串中数字为偶数的数字进行翻转，即翻转字符串，但只调换数字为偶数的位置
数字不包含0，字符串长度可能为0

方法一：暴力法
具体做法：
遍历字符串，用一个辅助数组顺序记录所有出现的偶数，再次遍历字符串，遇到偶数时，替换为辅助数组逆序中的字符。

class Solution {
public:
    string change(string number) {
        string res = "";
        vector<char> temp;
        int n = number.size();
        if(n <= 1) //如果只有1位或者空，直接返回原串
            return number;
        for(int i = 0; i < n; i++)
            if((number[i] - '0') % 2 == 0) //若为偶数记录下来
                temp.push_back(number[i]);
        int m = temp.size() - 1;
        for(int i = 0; i < n; i++){
            if((number[i] - '0') % 2 == 0) //若为偶数将后面的替换上来
                res += temp[m--];
            else
                res += number[i];
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，两次遍历，每次都是 $O(n)$
空间复杂度： $O(n)$ ，辅助数组temp长度为 $m$ ，其中 $m$ 最坏情况为 $n$ ，即每个都是偶数

方法二：双指针
具体做法：
设置一个从前往后的指针i和一个从后往前的指针j，两个指针分别找到后续第一个偶数及前序第一个偶数，如果此时两指针未相遇，则交换内容，继续分别向后向前搜索，直到两指针相遇。
图片说明

class Solution {
public:
    string change(string number) {
        int n = number.length();
        if(n <= 1)
            return number;//如果只有1位或者空，直接返回原串
        int i = 0;
        int j = n - 1;
        while(i < j){ //直到两个指针相遇，遍历结束
            while(i < j && (number[i] - '0') % 2 != 0)  //找到后续第一个偶数
                i++;
            while(j > i && (number[j] - '0') % 2 != 0) //找到前续第一个偶数
                j--;
            if(i < j){
                char temp = number[i];
                number[i] = number[j];
                number[j] = temp;
                i++;
                j--;
            }
        }
        return number;
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，遍历半个字符串,即 $O(n/2)=O(n)$
空间复杂度： $O(1)$ ，常数个临时变量