题解 | #神奇的数字#

题目描述
将字符串数字中为偶数位的数字进行翻转，将翻转后的结果进行输出。

方法一：暴力求解

求解思路
对于本题目要求翻转偶数位的数字，我们直接遍历字符串，用一个辅助数组记录偶数位的数字，再次遍历字符串，对偶数位的数字进行替换，按照上述思路我们即可得到题目所要的答案。

图片说明

解题代码

class Solution {
public:
    string change(string number) {
        string myres = ""; // 声明变量，记录结果
        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) // 若为偶数将后面的替换上来
                myres += temp[m--];
            else
                myres += number[i];
        }
        return myres; // 返回结果
    }
};

复杂度分析
时间复杂度：一层循环，因此时间复杂度为 $O(N)$
空间复杂度：使用辅助数组temp[n]，因此空间复杂度为 $O(N)$

方法二：双指针思想求解

求解思路
对于本题我们也可以使用双指针来对问题进行解决，我们使用头指针和尾指针，让它们从字符串的两边开始往中间进行迭代，遇到偶数位的数字进行交换，根据上述操作即可得到本题的答案。

图片说明

解题代码

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(1)$