题解 | #神奇的数字#

思路

题目分析

题目给出一个数字字符串
我们需要将这个字符串中所有的偶数数字进行翻转，奇数数字位置不变，返回这个新的字符串

第一种思路可以根据题目描述的方法，通过数据结构按照顺序存储偶数数字和偶数数字的索引，将偶数数字反转后按照原来的顺序和索引下标重新填到number中
第二种思路可以利用双指针的方法，对number字符串进行前后遍历，遇到偶数则将两个指针指向的数字交换，最终返回number数组

图片说明

方法一：按照要求反转偶数序列重新填回

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param number string字符串 
     * @return string字符串
     */
    string change(string number) {
        // write code here
        int n = number.size();
        vector<int> idx;                        // 保存所有偶数所在number字符串的下标
        string even = "";                       // 保存所有偶数数值
        for(int i = 0; i < n; i++){             // 遍历number找到所有的偶数和下标并存储在我们上述的两个变量中
            char c = number[i];
            if((c-'0') % 2 == 0) {              // 判断是否为偶数
                idx.push_back(i);
                even.push_back(c);
            }
        }
        reverse(even.begin(), even.end());      // 将even字符串整个倒置
        for(int i = 0; i < idx.size(); i++){    // 遍历下标数组并重新填回到number字符串中
            int pos = idx[i];
            number[pos] = even[i];              // 将翻转后的even字符串根据idx的下标逐个填到number字符串的所有偶数位置上
        }
        return number;
    }
};

复杂度分析

时间复杂度： $O(n)$ ，循环和翻转都只需要 $O(n)$ 数量级的时间开销
空间复杂度： $O(n)$ ，借助了辅助数组idx，even

方法二：双指针

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param number string字符串 
     * @return string字符串
     */
    bool isEven(char c) {
        return (c - '0') % 2 == 0;
    }

    string change(string number) {
        // write code here
        int n = number.size();
        int i = 0;                // 定义左指针
        int j = n-1;              // 定义右指针
        while(i < j) {
            while(i < j && !isEven(number[i])) i++;    // 从前往后找一个偶数
            while(i < j && !isEven(number[j])) j--;    // 从后往前找一个偶数
            swap(number[i++], number[j--]);            // 交换这两个偶数，并更新前后指针指向下一个位置
        }
        return number;
    }
};

复杂度分析

时间复杂度： $O(n)$ ，while循环的时间开销
空间复杂度： $O(1)$ ，只有常量空间的开销