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;
}
};