LeetCode weekly contest 234

发表于 更新于 分类于 Disqus：
Rank Name Score Finish Time Q1 (3) Q2 (5) Q3 (5) Q4 (6)
672 / 12421 YoungForest 19 1:19:08 0:12:04 2 0:23:51 0:29:26 0:54:08 3

又要打卡了，已经连续5周残酷打卡了。而且确实自己本次做题没觉得多简单，WA5次，心态爆炸，但是排名却不理想。感觉还是LeetCode越来越卷了。

1805. Number of Different Integers in a String

本题其实用Python做会好很多，实现起来更快。Python对字符串和大整数的优势还是无可比拟的。
我还是坚持用C++ 完成，各种字符串不熟悉和不方便的操作。WA了2发。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int numDifferentIntegers(string word) {
        for (char& c : word) {
            if (!isdigit(c)) {
                c = ' ';
            }
        }
        while (!word.empty() && word.back() == ' ') {
            word.pop_back();
        }
        if (word.empty()) return 0;
        std::istringstream is(word);
        unordered_set<string> ans;
        while (is)
        {
            string s;
            is >> s;
            reverse(s.begin(), s.end());
            while (s.size() > 1 && s.back() == '0') {
                s.pop_back();
            }
            // cout << "xx : " << s << endl;
            if (s.empty()) continue;
            ans.insert(s);
        }
        return ans.size();
    }
};

时间复杂度: O(N),
空间复杂度: O(N).

1806. Minimum Number of Operations to Reinitialize a Permutation

本题我是倒着思考的，
操作的拟操作是 技术位置到后半段，偶数位置到前半段。
而且观察变化的过程，只需要关注一个数，如果他回到原位置，剩下所有的数都会回到原位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    // operation: odd to half second, even to half first
    // [0 1 2 3 4 5] 4
    // [0 2 4 1 3 5] 3
    // [0 4 3 2 1 5] 2
    // [0 3 1 4 2 5] 1
    // [0 1 2 3 4 5] 0
    
public:
    int reinitializePermutation(int n) {
        int ans = 0;
        int index1 = 1;
        do {
            if (index1 % 2 == 1) {
                index1 = n / 2 + index1 / 2;
            } else {
                index1 = index1 / 2;
            }
            ++ans;
        } while (index1 != 1);
        return ans;
    }
};

时间复杂度: O(N),
空间复杂度: O(1).

1807. Evaluate the Bracket Pairs of a String

说实话，本题作为第3题，并没有相应的难度。完全可以作为签到题。
直接做即可。
知识点：字符串处理 + 字典/Map.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    string evaluate(string s, vector<vector<string>>& knowledge) {
        unordered_map<string, string> m;
        for (const auto& v : knowledge) {
            m[v[0]] = v[1];
        }
        string word;
        bool left = false;
        string ans;
        for (char c : s) {
            if (c == '(') {
                left = true;
            } else if (c == ')') {
                left = false;
                auto it = m.find(word);
                if (it == m.end()) {
                    ans.push_back('?');
                } else {
                    ans.append(it->second);
                }
                word.clear();
            } else {
                if (left) {
                    word.push_back(c);
                } else {
                    ans.push_back(c);
                }
            }
        }
        return ans;
    }
};

时间复杂度: O(s.size() + knowledge.size() * (knowledge[i][0].size() + knowledge[i][1].size())),
空间复杂度: O(s.size() + knowledge.size() * (knowledge[i][0].size() + knowledge[i][1].size())).

1808. Maximize Number of Nice Divisors

问题可以转换成 确定和，最大化乘积。

sum 确定是primeFactors。然后好因子的数目就是乘积，也就是题目里最大化的目标。
因为你观察好因子其实是每个质因数数目的乘积。

在Google上搜索fix sum max multiplication，第3条就有Geekforgeek的一个类似问题Breaking an Integer to get Maximum Product. 其实LeetCode上也有原题343.
我试图照搬它的代码，然而有2个地方不同：

  • geekforgeek上必须break，不能作为一个整体。而本题是可以不break的。这个涉及到特殊case, 即primeFactors = 2 或 3时，应改为返回 n.
  • geekforgeek上的代码采用一个for loop * 3. 时间复杂度是 O(n / 3). 在本题会超时。我自己写了pow以更快的方式*3，时间复杂度是 O(log n)。其实是LeetCode 50 Pow(x, n).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    using ll = long long;
    const ll MOD = 1e9 + 7;
    // https://www.geeksforgeeks.org/breaking-integer-to-get-maximum-product/
    /* The main function that returns the max possible product */
    ll mypow(ll a, ll b) {
        // a ^ b
        if (b == 0) {
            return 1;
        } else if (b % 2 == 1) {
            return (mypow(a, b - 1) * a) % MOD;
        } else {
            auto x = mypow(a, b/2);
            return (x * x) % MOD;
        }
    }
    int maxProd(ll n)
    {
       // n equals to 2 or 3 must be handled explicitly
       if (n == 2 || n == 3) return n;

       // Keep removing parts of size 3 while n is greater than 4
       ll res = 1;
       // while (n > 4)
       // {
       //     n -= 3;
       //     res = (res * 3) % MOD; // Keep multiplying 3 to res
       // }
        // 4 0
        // 5 1
        // 6 1
        // 7 1
        // 8 2
        if (n >= 5) {
            const int step = ((n - 5) / 3 + 1);
            res = mypow(3, step);
            n -= step * 3;
        }
       return (n * res) % MOD; // The last part multiplied by previous parts
    }
public:
    int maxNiceDivisors(int primeFactors) {
        return maxProd(primeFactors);
    }
};

时间复杂度: O(log n),
空间复杂度: O(1).