题解 | #神奇的数字#

一.题目描述
NC532神奇的数字
将字符串数字中为偶数位的数字进行翻转，将翻转后的结果进行输出。
图片说明
二.算法(双指针)
根据题目的意思将字符串中为偶数位的数字进行翻转，既然是翻转那么就可以利用双指针。对于左边采用左指针l遍历，对于右指针采用r遍历，当两边的指针都找到偶数位的时候对两个指针所指位置进行交换，返回最后的字符串既为所求字符串。下面是完整代码：

class Solution {
public:
    string change(string number) {
        //分别表示左右指针
        int l=0,r=number.size()-1;
        while(l<r){
            while(l<r&&(number[l]-'0')%2==1){
                l++;
            }
            while(l<r&&(number[r]-'0')%2==1){
                r--;
            }
            //左右指针进行交换
            if(l<r) swap(number[l],number[r]);
            l++;
            r--;
        }
        return number;
    }
};

时间复杂度： $O(n)$ 只需要对字符串进行一次遍历
空间复杂度： $O(1)$ 不需要额外空间
优缺点：实现简单而且便于理解
三.算法(模拟)
图片说明
我们直接遍历字符串，用一个新的字符数组记录偶数位的数字，再次遍历字符串，然后对偶数位的数字进行替换，按照上述思路我们即可得到题目所要的答案。下面是完整代码：

class Solution {
public:
    string change(string number) {
        string s=""; 
        vector<char>ans;
        if(number.size()<=1) return number;//对于单个字符串进行特判
        for(int i = 0; i < number.size(); i++){
            if((number[i]-'0')%2==0) {
                ans.push_back(number[i]);//偶数位进行记录
            }
        }
        int n=ans.size()-1;
        //利用额外开辟的数字进行处理
        for(int i=0;i<number.size();i++){
            if((number[i]-'0')%2==0){
                s+=ans[n];// 若为偶数将后面的替换上来,所以是从后往前遍历
                n--;
            } else {
                s+=number[i];//不需要处理，加上原字符
            }

        }
        return s; // 返回结果
    }
};

时间复杂度： $O(n)$ 只需要对数组进行两次遍历
空间复杂度： $O(n)$ 需要额外开辟数组对偶数位的字符串进行存储
优缺点：思路简单，但是实现复杂