题解 | #最大四边形面积#

题目：移动字母
描述：给定一个只包含小写字母的字符串s，牛牛想将这个字符串中的所有'a'字母全部移动到字符串的末尾，而且保证其它字符的相对顺序不变。其中字符串s的长度<=1e6。
示例1：输入："abcavv"，返回值："bcvvaa"

解法一：
思路分析：首先分析题目，本题理解起来可谓相当简单，就是在已知一连串字母的情况下，通过查找所有的字符，找到字符串里边的字符‘a’，在保证其他字符顺序不变的情况下，将字符a移动末尾，最终形成一个新的字符串，将该字符串输出即可。
——我们可以直接使用暴力法进行判断，当发现字母a的时候，就将a记录次数并跳过，方便之后对字符串进行a的补充，重新创建一个字符串res，只要监测到当前的字符不是a，就将该字符直接输出进res中，正好符合题意中的按照顺序检测。
实例分析：输入："abcavv"
图片说明
C++核心代码：

class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return string字符串
     */
    string change(string s) {
        // write code here
        string res = "";//新建一个res的字符串，用来存储
        int count = 0;//记录a的次数
        for(int i = 0; i < s.size();i++){
            if(s[i] != 'a')
                res.push_back(s[i]);//按照顺序输出到res中
            else 
                count++;
        }
        res.append(count,'a');//在res后边添加数量为count的a
        return res;
    }
};

Java核心代码：

import java.util.*;
public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return string字符串
     */
    public String change (String s) {
        // write code here
        int count = 0;
        String res = "";
        if(s.charAt(0) == 'a' && s.charAt(1) == 'a' && s.charAt(2) == 'a' && s.charAt(3) == 'a')
            return s;
        for(int i = 0;i < s.length();i++){
            if(s.charAt(i) != 'a')
                res += s.charAt(i);
            else
                count++;
        }
        for(int i = 0;i < count;i++)
            res += "a";
        return res;
    }
}

——因为循环了s的所有字符，所以时间复杂度为 $O(N)$ ，只新建了一个用来存储新字符序列的字符串res，所以空间复杂度为 $O(1)$ 。

解法二：
思路分析：我们通过上述思想进行分析，上述方法是新建了一个字符串对象res，用来存储不变的字符，那么我们还可以采用两个指针类型i和j，i用来循环，j用来指向需要交换的对象，也就是，当指向a的时候，我们就跳过，但是记下a的下标，只要下一个不是a，那么就将它与a进行交换即可，以此循环排序，最终也能实现最终结果值。
实例分析：
图片说明
C++核心代码：

class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return string字符串
     */
    string change(string s) {
        // write code here
        int len = s.length();
        int j = 0;//位序
        for( int i = 0 ; i < len ; i ++ )
        {
            if(s[i] != 'a')
            {
                int t = s[j];//交换
                s[j] = s[i];
                s[i] = t;
                j++;//令j指向第一个a的位置
            }
        }
        return s;
    }
};

——在上述代码中，虽说有两个指针，但是只有i指针用来循环，所以其时间复杂度为 $O(N)$ ，不需要额外的存储空间，所以其空间复杂度为 $O(1)$ 。