第83场周赛

用户1145562

发布于 2020-10-23 08:05:59

36400

代码可运行

文章被收录于专栏：LC刷题LC刷题

运行总次数：0

代码可运行

传送门

830. 较大分组的位置

题解：根据描述，只要设置两个指针i，j。初始i指向第一次出现的字母，j指向i的后面一个位置，不断增加j，使得i与j之间的字母相同，当j指向字母与i不同时且ij之间的距离大于等于3保存结果，小于3则更新i至位置j，j向后移动一位。

注意如字符串“aaa”，上述原则失效，可以在“aaa”后增加一个哨兵(一个隐藏的字符)。也可以在最后增加一个判断。当上述循环结束时，ij距离大于2即可。以下是个人code。

vector<vector<int>> largeGroupPositions(string S) {
        vector<vector<int>>ret;
        if(!S.length()) return {};
        int i,j;
        for(i = 0,j = 1;i<S.length()&&j<S.length();){
            if(S[i]==S[j]){
                j++;
            }
            else{
                if((j-i)>=3){
                    ret.emplace_back({i,j-1});
                }
                i = j;
                j = i+1;
            }
        }
        if((j-i)>2){
            ret.emplace_back({i,j-1});}
        return ret;  
    }

831. 隐藏个人信息

题解：根据描述，我们只需要根据是否有@符号，设计两个函数maskMail与maskPhone。

string maskPII(string S) {    	
    transform(S.begin(),S.end(),S.begin(),::tolower);
    //转换所有字符变为小写
        for(auto i:S){
            if(i=='@'){
                //当有@符号，用maskMail
                string ret = maskMail(S);
                return ret;
            }
            
        }
    	//没有@符号，用maskPhone
        string ret = maskPhone(S);
        return ret;
    }
    string maskMail(string S){
        int j;
        for(j=1;j<S.length();j++){
            if(S[j]=='@') break;
        }
        string star = "*****";
        star.insert(star.begin(),S[0]);
        star.insert(star.end(),S[j-1]);
        string ret=star+S.substr(j,S.length()-j);
        return ret;   
    }
    string maskPhone(string &S){
        vector<char>tmp;
        for(auto i:S){
            if(i>='0'&&i<='9') tmp.emplace_back(i);
        }
        string ret = "";
        /*
        由于电话号码的数字只有10-13位，根据数字长度，
        加上不同的前缀即可。
        */
        if(tmp.size()==10){
            ret+="***-***-";
            for(int i=6;i<10;i++) ret+=tmp[i];
        }
        if(tmp.size()==11){
            ret+="+*-***-***-";
            for(int i=7;i<11;i++) ret+=tmp[i];
        }
        if(tmp.size()==12){
            ret+="+**-***-***-";
            for(int i=8;i<12;i++) ret+=tmp[i];
        }
        if(tmp.size()==13){
            ret+="+***-***-***-";
            for(int i=9;i<13;i++) ret+=tmp[i];
        }  
        return ret;
    }

829. 连续整数求和

题解：根据题意，

个数参与求和，那么有

N = (x+1)+(x+2)+…+(x+k)=\frac{(2x+k+1)k}{2}

解得

x = \frac{1}{2}(\frac{2N}{k} - k - 1)

，至此，只要枚举

int consecutiveNumbersSum(int N) {
        // 2N = k(2x + k + 1)
        int ret = 0;
        for (int k = 1; k <= 2*N; ++k)
            if (2 * N % k == 0) {
                int y = 2 * N / k - k - 1;
                if (y % 2 == 0 && y >= 0)
                    ret++;
            }
        return ret;
}

的枚举范围。

N = (x+1)+(x+2)+…+(x+k)=\frac{(2x+k+1)k}{2}

在该式中，明显可观察到

第四反应:

int consecutiveNumbersSum(int N) {
    int ans = 0;
    for (int i = 1; N > 0; N-=i, i++)
        ans += (N % i == 0);
    return ans;
}
//第四种解法可以看作另一种形式的枚举吧，优美且简洁。
作者：pris_bupt
链接：https://leetcode-cn.com/problems/consecutive-numbers-sum/solution/c-ji-jian-by-pris_bupt/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。