image-20210516114449615

GG

5742. 将句子排序

简单模拟， 用py实现的，方便点。

1
2
3
4
5
6
class Solution:
    def sortSentence(self, s: str) -> str:
        sl = s.split(' ')
        sl.sort(key=lambda x: x[-1])

        return ' '.join([s[:-1] for s in sl])

5743. 增长的内存泄露

简单模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> memLeak(int memory1, int memory2) {
        int cnt = 0;
        int i=0;
        for(i=1;memory1 >= i || memory2 >= i; i++) {
            if(memory1 >= memory2) {

            memory1 -= i;
            } else {

            memory2 -= i;
            }

        }
        return {i, memory1, memory2};
    }
};

5744. 旋转盒子

模拟题，

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
class Solution {
public:
    vector<vector<char>> rotateTheBox(vector<vector<char>>& box) {
        for(auto &raw: box) {
            for(int i=raw.size()-1,p=raw.size()-1; i>=0;i--) {
                if(raw[i] == '*') {
                    p = i-1;
                    continue;
                } else if (raw[i] == '#') {
                    raw[i] = '.';
                    raw[p--] = '#';
                }
            }
        }
        vector<vector<char>> ans;
        int n=box.size(), m = box[0].size();
        for(int j=0;j<m;j++) {
            vector<char> tmp;
            for(int i=n-1;i>=0;i--) {
                tmp.push_back(box[i][j]);
            }
            ans.push_back(tmp);
        }
        return ans;
    }
};

5212. 向下取整数对和

这题写的比较麻烦，开始写了个分段除法 结果这题居然卡O(N×N)O(N \times \sqrt{N}),

最后改成了类似朴素晒法的过程实现的。

首先将数放入桶中记nums[i]的个数，预处理桶的前缀和， 然后按照晒法的过程途中统计下结果就好了。

这里注意复杂度

∑i=1nni=n×log(n)\sum_{i=1}^n \frac{n}{i} = n \times log(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
class Solution {
public:
    static const int MOD = 1e9+7;
    // static const int N = 1e5;
    int sumOfFlooredPairs(vector<int>& nums) {
        // sort(nums.begin(), nums.end());
        int N = nums[0];
        // printf("%d --\n", N);
        for(auto a: nums) N = max(N, a);
        // printf("%d --\n", N);
        vector<int> h(N+1);

        int ans = 0;
        int sum = 0;
        for(auto a: nums) h[a]++;
        // for(int i=0;i<=N;i++) printf("%d ",h[i]); puts("");

        for(int i=1;i<=N;i++) {
            h[i] += h[i-1];
        }
        // for(int i=0;i<=N;i++) printf("%d ",h[i]); puts("");

        for(int i=1;i<=N;i++) {
            for(int j=i,k=1; j<=N; j+=i,k++) {
                ans += 1LL*k*(h[i]-h[i-1])%MOD*(h[min(N, j+i-1)]-h[j-1])%MOD;
                // printf("%d >>> %d %d (%d, %d] | %d = %d(k) * %d(h[i]) * %d(h[min(N, j+i-1)]-h[j-1])\n", i, j, k, j-1, min(N, j+i-1), 1LL*k*h[i]%MOD*(h[min(N, j+i-1)]-h[j-1])%MOD, k, h[i], (h[min(N, j+i-1)]-h[j-1]));
                ans %= MOD;
            }
        }
        return ans;
    }
};
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
// O(N * Sqrt(N)) 超时的代码
class Solution {
public:
    static const int MOD = 1e9+7;
    // static const int N = 1e5;
    int sumOfFlooredPairs(vector<int>& nums) {
        // sort(nums.begin(), nums.end());
        int N = nums[0];
        // printf("%d --\n", N);
        for(auto a: nums) N = max(N, a);
        // printf("%d --\n", N);
        vector<int> h(N+1);

        int ans = 0;
        int sum = 0;
        for(auto a: nums) h[a]++;
        // for(int i=0;i<=N;i++) printf("%d ",h[i]); puts("");

        for(int i=1;i<=N;i++) {
            ans = (ans + h[i]*h[i]%MOD)%MOD;

            for(int j=1, last; h[i] >0 && j<i; j=last + 1) {
                last = min(i/(i/j), i-1);

                ans += (i/j)*(h[last] - h[j-1])%MOD*h[i]%MOD;
                ans %= MOD;
            }
            h[i] += h[i-1];
            // printf("%d >> %d \n", i, ans);
        }
        // for(int i=0;i<=N;i++) printf("%d ",h[i]); puts("");

        return ans;
    }
};