题解 | #神奇的数字#

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

示例：
输入："12346"
返回值："16342"
说明：第2、4、5位为偶数，所以将其翻转后，得到 16342

方法一：双指针
设置头指针指向数组头部，尾指针指向数组尾部
当头指针和尾指针未相遇时:

当头指针所指数字不是偶数时，头指针不断向右移动，直到找到第一个偶数，停止移动
当尾指针所指数字不是偶数时，尾指针不断向左移动，直到找到第一个偶数，停止移动
这时，头指针和尾指针所指数字都为偶数，两个数字交换，头指针继续向左移动，尾指针向右移动，继续步骤一二

Java版本

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param number string字符串 
     * @return string字符串
     */
    public String change (String number) {
        // write code here
        //设置头指针和尾指针
        int start=0,end=number.length()-1;
        char[]array=number.toCharArray();
        while(start<end){
            //头指针不是偶数，头指针向右移动
            while(start<end&&(array[start]-'0')%2!=0)start++;
            //尾指针不是偶数，尾指针向左移动
            while(start<end&&(array[end]-'0')%2!=0)end--;
            //如果头指针和尾指针所指数字都是偶数，则交换数字并且头指针向右移动，尾指针向左移动
            if(start<end){
                char temp=array[start];
                array[start]=array[end];
                array[end]=temp;
                start++;end--;
            }

        }
        return String.valueOf(array);
    }
}

C++版本

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param number string字符串 
     * @return string字符串
     */
    string change(string number) {
        // write code here
        int start=0,end=number.length()-1;
        while(start<end){
            //头指针不是偶数，头指针向右移动
            while(start<end&&(number[start]-'0')%2!=0)start++;
            //尾指针不是偶数，尾指针向左移动
            while(start<end&&(number[end]-'0')%2!=0)end--;
            //如果头指针和尾指针所指数字都是偶数，则交换数字并且头指针向右移动，尾指针向左移动
            if(start<end){
                char temp=number[start];
                number[start]=number[end];
                number[end]=temp;
                start++;end--;
            }

        }
        return number;
    }
};

复杂度：
时间复杂度：最坏情况下遍历一次字符串， $O(n)$
空间复杂度：辅助数组array大小为n(n为字符串长度),所以空间复杂度为 $O(n)$

方法二：利用辅助栈
两次遍历字符串，第一次遍历字符串时，用栈保存偶数，第二次遍历字符串时，利用栈“先进后出”的特性，把偶数替换为出栈数字

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param number string字符串 
     * @return string字符串
     */
    public String change (String number) {
        // write code here
        Stack<Character> s=new Stack<>();
        //遇到偶数进栈
        for(int i=0;i<number.length();i++){
            if((number.charAt(i)-'0')%2==0)s.push(number.charAt(i));
        }
        char[]ch=number.toCharArray();
        //再次遍历字符串，遇到偶数则将元素出栈。出栈元素替换偶数
        for(int i=0;i<number.length();i++){
            if((ch[i]-'0')%2==0)ch[i]=s.pop();
        }

        return String.valueOf(ch);
    }
}

复杂度：
时间复杂度：遍历字符串， $O(n)$
空间复杂度：辅助栈的大小不超过n， $O(n)$