lc-第234场单周赛

2021年3月28日，星期日

　　前一天刚刚完成和实验室同学一起参加的华为软挑，虽然无缘决赛，但是还是收获了比赛的快乐，接着今天就迎来了力扣单周赛，又是望着大佬们流口水的一天......

这次的全国排名是

值得高兴的是我把四道题都做出来了！虽然是“手速场”，但我还是要夸夸自己。

第一题是

5713. 字符串中不同整数的数目

给你一个字符串，让你把字符串中的数字挑出来，看看有多少个不同的数字。

诶，我一拍脑袋，这不就是遍历的过程中把int存在一个集合里就可以了嘛，注意到题目里面说前导0不算，我还在暗自庆幸转化成数字前导0根本不受影响，考虑到大数int没法存，我还抖机灵的换成了long，然后下面的代码就没法应对 "035985750011523523129774573439111590559325" 这种离谱的数字

class Solution {
public:
    bool isnum(char c){
        return c >= '0' && c <= '9';
    }
    int numDifferentIntegers(string word) {
        word += 'y';
        set<long> ss;
        long sum = 0;
        for(int i = 0; i < word.length(); i++){
            if(!isnum(word[i])){
                if(i > 0 && isnum(word[i - 1]))ss.insert(sum);
                sum = 0;
                continue;
            }
            sum = sum * 10 + word[i] - '0';
        }
        return ss.size();
    }
};

我都做到这份上了，干脆换成string存不好吗，于是换成下面的代码通过了

class Solution {
public:
    bool isnum(char c){
        return c >= '0' && c <= '9';
    }
    int numDifferentIntegers(string word) {
        word += 'y';
        set<string> ss;
        string sum = "";
        for(int i = 0; i < word.length(); i++){
            if(!isnum(word[i])){
                if(i > 0 && isnum(word[i - 1])){
                    int j = 0;
                    while(j < sum.length() - 1 && sum[j] == '0')++j;  
                    ss.insert(sum.substr(j, (sum.length() - j)));
                    
                }
                sum = "";
                continue;
            }
            sum += word[i];
        }
        return ss.size();
    }
};

第二题

5715. 还原排列的最少操作步数

听我同学们说按照规律只用判断1什么时候回原位值就可以了，我当时直接暴力模拟做的，因为它数据量实在太小了 n < 1000

如果 i % 2 == 0 ，那么 arr[i] = perm[i / 2]
如果 i % 2 == 1 ，那么 arr[i] = perm[n / 2 + (i - 1) / 2]

按照这个规律，当 n = 6的时候,
[0, 1, 2, 3, 4, 5]

[0, 3, 1, 4, 2, 5]

[0, 4, 3, 2, 1, 5]

[0, 2, 4, 1, 3, 5]

[0, 1, 2, 3, 4, 5]

方法一：暴力模拟

class Solution {
public:
    bool isEqual(vector<int>& a, int n){
        for(int i = 0; i < n; i++){
            if(a[i] != i) return false;
        }
        return true;
    }
    int reinitializePermutation(int n) {
        vector<int> a(n, 0);
        vector<int> b(n, 0);
        for(int i = 0; i < n; i++){
            a[i] = i;
        }
        int ans = 0;
        do{
            for(int i = 0; i < n; i++){
                if(i % 2 == 1){
                    b[i] = a[n / 2 + (i - 1) / 2];
                }else{
                    b[i] = a[i / 2];
                }
            }
            a = b;
            ans++;
        }while(!isEqual(a, n));
        return ans;
    }
};

方法二：因为每个数字最周都会回到原来的位置，所以每个数字都有它的循环路径，我们以下标 pos = 1 为追踪位置，当数字1重新回到位置1时，数组恢复原样

class Solution {
public:
    int reinitializePermutation(int n) {
        int pos = 1, ans = 0;
        do{
            //pos = pos & 1 ? n / 2 + (pos - 1) / 2 : pos / 2;
            if(pos % 2 == 1){
                pos = n / 2 + (pos - 1) / 2;
            }else{
                pos = pos / 2;
            }
            ++ans;
        }while(pos != 1);
        return ans++;
    }
};

第三题

5714. 替换字符串中的括号内容

我觉得这个题目没有什么技巧也没有什么坑，用一个map保存一下映射就好了

class Solution {
public:
    string evaluate(string s, vector<vector<string>>& k) {
        unordered_map<string, string> mp;
        for(auto& v : k){
            mp[v[0]] = v[1];
        }
        string ans = "";
        int i = 0;
        while(i < s.length()){
            if(s[i] == '('){
                string cur = "";i++;
                while(i < s.length() && s[i] != ')'){
                    cur += s[i];
                    i++;
                }
                i++;
                if(mp.find(cur) != mp.end()){
                    ans += mp[cur];
                }else{
                    ans += '?';
                }
                continue;
            }
            if(i < s.length())
                ans += s[i];
            i++;
        }
        return ans;
    }
};

第四题

5716. 好因子的最大数目

很高兴这次的hard是一道数学题，和leetcode上剪绳子是类似的题目

其实是看primFactors分解成若干个数的和之后，这些数的最大乘积是多少，理论上，能分解成3尽量分解成3，变成3的幂次和2的幂次

这道题如果用pow(x, n)会大数溢出，并且会超时，选择用快速幂解决就好啦

class Solution {
public:
    int mm = 1e9 + 7;
    long powt(int t, int n){
        if(n == 0)return 1;
        if(n == 1){
            return t;
        }
        long tmp = powt(t, n / 2) % mm;
        if(n & 1) return tmp * tmp % mm * t % mm;
        return tmp * tmp % mm;
    }
    int maxNiceDivisors(int p) {
        long ans = 1;
        int two = 0, three = 0;
        if(p == 1)return 1;
        if(p % 3 == 2){
            three = p / 3;
            two = 1;
        }else if(p % 3 == 1){
            three = p / 3 - 1;
            two = 2;
        }else{
            three = p / 3;
        }
        ans = powt(2, two) * powt(3, three) % mm;
        return (ans + mm) % mm;
    }
};