AC了前两道题，推销下自己的博客，陆陆续续会有笔试面试总结，欢迎博客留言：https://bodycoder101.github.io/

第一题（压缩字符串）

解题思路:

1. 只需找到连续字母的下标[i,j)；判断之间的差值是否j-i>=4;
2. 如果差值大于等于4，则按规则进行压缩，否则将子串substr(i,j-i)加入result;
3. 只需遍历一遍字符串即可，时间复杂度为O(n)。

参考代码：

#include<iostream>
#include<string>
using namespace std;
string compressionString(string str)
{
    int len = str.size();
    string result = "";
    for (int i = 0; i <len;)
    {
        if (i< len-1 && str[i] == str[i + 1] - 1)
        {
            int j;
            //连续的区间[i, j-1],共有j-i个元素
            for (j = i + 1; j < len && str[j] - str[j - 1] == 1; j++);
            if (j - i  >= 4)
            {
                result.append(str[i]);
                result.append('-');
                result.append(str[j - 1]);
            }
            else
                result += str.substr(i, j - i);
            i = j;
        }
        else
            result.append(str[i++]);
    }
    return result;
}
int main(int argc, char const *argv[]){
    string str;
    int t;
    cin >> t;
    for (int i = 0; i < t; i++)
    {
        string str;
        cin >> str;
        str = compressionString(str);
        cout << str <<endl;
    }
    return 0;
}

第二题(有关xy进制混合的)

解题思路:

1. 使用对撞指针left,right，分别指向两端,相向扫描，维持两个区间求值va1=[0,left] ,va2=[right,end];
2. if va1<va2 then left++;
3. if va1>va2 then right--;
4. if va1 == va2  && left+1 == right  then return va1; 输出va1即为结果；
5. 时间复杂度为o(n)。

参考代码：

#include <stdio.h>
#include <iostream>
#include <string>;
using namespace std;
    int solutionForTwo(int x, int y, string z){
        int length = z.length();
        int left = 0;
        int right = length-1;
        int* reserve = new int [length];
        for (int i = 0; i < length; i++) {
            if(isdigit(z[i])){
                reserve[i] = z[i] - '0';
            }else{
                reserve[i] = z[i] - 'A' + 10;
            }
        }
        long xbase = reserve[left];
        long ybase = reserve[right];
        long ten = 1;
        while (left < right) {
            if (xbase == ybase) {
                if (left + 1 == right) {
                    delete[] reserve;
                    return xbase;
                }
                left++;
                right--;
                xbase = xbase*x + reserve[left];
                ten *= y;
                ybase = ten*reserve[right] + ybase;
            } else if (xbase < ybase) {
                left++;
                xbase = xbase*x + reserve[left];
            } else {
                right--;
                ten *= y;
                ybase = ten*reserve[right] + ybase;
            }
        }
        delete[] reserve;
        return -1;
    }
int main(int argc, char const *argv[]) {
    int T,X,Y;
    string Z;
    std::cin >> T;
    for (int i = 0; i < T; i++) {
        cin>>X>>Y>>Z;
        std::cout << solutionForTwo(X,Y,Z)<<endl;
    }
    return 0;
}