【每日挠头算法题（2）】压缩字符串|仅执行一次字符串交换能否使两个字符串相等-Toy模板网

这篇具有很好参考价值的文章主要介绍了【每日挠头算法题（2）】压缩字符串|仅执行一次字符串交换能否使两个字符串相等。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、压缩字符串

点我直达~

【每日挠头算法题（2）】压缩字符串|仅执行一次字符串交换能否使两个字符串相等

思路

使用双指针法

大致过程如下：

使用双指针，分别读（read），写（write）指针，读指针不断向后走，当read指针走到最后位置处时，或read和read的下一个位置与当前位置不相等时，说明该read指针走到了某一串相同子串的最后位置处。
此时write指针开始记录具体的字符，给定一个left指针记录当前位置，此时每一个子串的长度都是 read - left +1
使用短除法将子串的长度记录下来，再进行逆置即可。

具体操作如下：

1.给定两个指针write 和 left（left指针记录每一个子串的开始位置），分别指向第一个元素的位置。
2.使用read指针，遍历字符串，当read遇到其后面一个字符与当前字符不等，或者read走到末尾时，此时将write指针记录当前子串的字符，以及长度，那就让write一边记录一边往后走。
3.当write指针开始记录子串的长度时，给一个下标begin，这个begin就是记录子串的长度的起始位置，比如一个串的长度为：123，需要记录到chars数组的是[“1”,“2”,“3”]，begin记录着"1"下标的位置。
4.使用短除法将某一个串的长度的每一位记录下来，然后逆置，逆置的开始是begin，结尾是write。
5.因为write总是向后走，知道走到记录完所有的字符以及每一个相同的字符串的长度，则最终返回write的长度即可

具体代码如下：

class Solution {
public:
    int compress(vector<char>& chars) 
    {
        int write = 0,left = 0;
        for(int read = 0;read<chars.size();++read)
        {
            if(read == chars.size()-1 ||
             chars[read]!=chars[read+1])
            {   
                chars[write++] = chars[read];//存储字符
                int begin = write; // 逆置的左下标
                
                int n = read - left + 1 ; 
                if(n>1)
                {
                    while(n)
                    {
                        chars[write++] = (n%10) + '0';
                        n/=10;
                    }
                    //逆置的右下标是write
                    reverse(&chars[begin],&chars[write]);
                }
                left = read+1;
            }
        }
        return write;
    }
};

时间复杂度：O（n），空间复杂度O（1）

二、仅执行一次字符串交换能否使两个字符串相等

点我直达~

【每日挠头算法题（2）】压缩字符串|仅执行一次字符串交换能否使两个字符串相等

思路1：计数法

情况1：如果两个字符串的长度不同，那么不管怎么交换一定不等，返回false
情况2：如果两个字符串的长度相同：
- 情况1：如果不相同的字符超过两个，或者不相同的字符只有一个，那么两个字符串不管怎么交换字符一定不等，返回false
- 情况2：如果不相同的字符恰好为两个，此时有两种方法解决：
- - 1.交换这两个不相同的字符的位置，如果交换后s1 == s2，返回true，否则false。
- - 2.判断 s1[i] == s2[j] ,s1[j] == s2[i]是否满足即可。

具体请看下面代码：

class Solution {
public:
    bool areAlmostEqual(string s1, string s2)
    {
        //1.相等，true
        if(s1 == s2)
            return true;
        //2.长度不等，false
        if(s1.size() != s2.size())
            return false;
        
        //3.遍历s1和s2,如果发现有两个以上字母不同，不管怎么交换都不等       
        vector<int> v1; // 两个下标
        int count = 0;//计算s1和s2有几个不等的字母
        for(int i = 0;i<s1.size();++i)
        {
            if(s1[i]!=s2[i])
            {
                ++count;
                v1.push_back(i);
            }
        }

        //如果不是只有两个字母不同，不管怎么交换一定不等。
        if(count !=2)
            return false;

        return s1[v1[0]] == s2[v1[1]] && 
        s1[v1[1]] == s2[v1[0]] ;

        //下面的操作也可
         //swap(s2[v1[0]],s2[v1[1]]);
        // if(s1 == s2)
        //     return true;

        // return false;
    }
};

思路2：模拟法

模拟法整体思路与计数法大致相同
给定两个初始值pos1 ，pos2均为 -1，记录两个字符串不同的字符的下标。

如果不同位置超过两个或者只有一个，返回false
如果不同位置为两个或者没有不同位置，返回true

具体请看下面代码：

class Solution {
public:
    bool areAlmostEqual(string s1, string s2)
    {
        int n = s1.size(),pos1 = -1,pos2 = -1;
        for(int i = 0;i<n;++i)
        {
            if(s1[i] == s2[i])
                continue;

            if(pos1 == -1)
                pos1 = i;
            else if(pos2 == -1)
                pos2 = i;
            
            //该情况是超过两个不同的字符
            else
                return false;
        }

            //该情况是没有不同的字符
        if(pos1 == -1)
            return true;
            //该情况是只有一个不同的字符
        if(pos2 == -1)
            return false;
        
            //该情况是正常情况
        return s1[pos1] == s2[pos2] && s1[pos2] == s2[pos1];
    }
};