leetcode第52场双周赛:对答案的贡献的不同拆解方式

  |  

摘要: 本文是 leetcode 第 52 双周赛的记录。主要涉及的算法包括字符串、模拟、双指针、前缀和、二分。

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


总览

这是 leetcode 第 52 场双周赛,本场比赛的赞助公司是 Datayes 通联数据,前 500 名可获得简历内推机会,奖品比较亮眼,是股市相关的课,如下:

通联数据是由中国万向控股有限公司于2013年投资成立,致力于打造引领全球资管行业的智能投资平台。

公司总部设立于中国金融中心上海,在多个全球十大金融中心城市设有分支机构,其中包括中国北京、深圳、香港、新加坡、美国纽约、硅谷等。目前公司规模约600余人,核心团队由国际顶尖金融专家和海内外顶尖院校互联网精英组成,其中,技术研发人员占80%,近6成硕/博学历、超半数985/211和海归人员。

主要业务是运用大数据和人工智能技术采集、分析、挖掘数据,实现数据智能,为投资加速,将专业知识与人工智能技术相融合,构建投研知识图谱,打造下一代金融服务平台。

更多信息参考官网:

1
https://www.datayes.com/#/about/

本场比赛发挥算是正常,D 题比赛时没写出来,但这道题确实也难,最终成绩如下:

本场前三题考察了模拟和双指针,比较简单。亮点是第四题,需要将答案拆解为不同部分的贡献,然后对这些部分分别处理。但是这个拆解过程并不简单,需要对问题进行正确分析。最后可行的拆解方法有两种,分别对应了两种算法。

各题的算法点以及参考文章如下:


A题

一个 句子 指的是一个序列的单词用单个空格连接起来,且开头和结尾没有任何空格。每个单词都只包含小写或大写英文字母。

我们可以给一个句子添加 从 1 开始的单词位置索引 ,并且将句子中所有单词 打乱顺序 。

比方说,句子 “This is a sentence” 可以被打乱顺序得到 “sentence4 a3 is2 This1” 或者 “is2 sentence4 This1 a3” 。
给你一个 打乱顺序 的句子 s ,它包含的单词不超过 9 个,请你重新构造并得到原本顺序的句子。

示例 1:
输入:s = “is2 sentence4 This1 a3”
输出:”This is a sentence”
解释:将 s 中的单词按照初始位置排序,得到 “This1 is2 a3 sentence4” ,然后删除数字。

示例 2:
输入:s = “Myself2 Me1 I4 and3”
输出:”Me Myself and I”
解释:将 s 中的单词按照初始位置排序,得到 “Me1 Myself2 and3 I4” ,然后删除数字。

1
2
3
4
5
6
7
提示:

2 <= s.length <= 200
s 只包含小写和大写英文字母、空格以及从 1 到 9 的数字。
s 中单词数目为 1 到 9 个。
s 中的单词由单个空格分隔。
s 不包含任何前导或者后缀空格。

算法: 字符串, 模拟

首先将句子转换为带有位置索引的单词的列表 words,长度为 n,由于句子字符串中单词用单个空格连接起来,且开头和结尾没有任何空格这一步,这一步可以直接用 Python 的 split

创建长为 n 的结果单词列表 result,其中 result[i] 表示原句子中的第 i 个不带位置索引的单词。

枚举所得列表 words 中的每个词 word,以及其索引 i = word[-1],将 result[i] 赋值为 word[:-1]

最后将 result 拼成最终返回的字符串。

代码(Python3)

1
2
3
4
5
6
7
8
9
10
class Solution:
def sortSentence(self, s: str) -> str:
words = s.split(" ")
n = len(words)
strs = [""] * n
for word in words:
x = word[:-1]
idx = int(word[-1])
strs[idx - 1] = x
return " ".join(strs)

B题

给你两个整数 memory1 和 memory2 分别表示两个内存条剩余可用内存的位数。现在有一个程序每秒递增的速度消耗着内存。

在第 i 秒(秒数从 1 开始),有 i 位内存被分配到 剩余内存较多 的内存条(如果两者一样多,则分配到第一个内存条)。如果两者剩余内存都不足 i 位,那么程序将 意外退出 。

请你返回一个数组,包含 [crashTime, memory1crash, memory2crash] ,其中 crashTime是程序意外退出的时间(单位为秒), memory1crash 和 memory2crash 分别是两个内存条最后剩余内存的位数。

示例 1:
输入:memory1 = 2, memory2 = 2
输出:[3,1,0]
解释:内存分配如下:

  • 第 1 秒,内存条 1 被占用 1 位内存。内存条 1 现在有 1 位剩余可用内存。
  • 第 2 秒,内存条 2 被占用 2 位内存。内存条 2 现在有 0 位剩余可用内存。
  • 第 3 秒,程序意外退出,两个内存条分别有 1 位和 0 位剩余可用内存。

示例 2:
输入:memory1 = 8, memory2 = 11
输出:[6,0,4]
解释:内存分配如下:

  • 第 1 秒,内存条 2 被占用 1 位内存,内存条 2 现在有 10 位剩余可用内存。
  • 第 2 秒,内存条 2 被占用 2 位内存,内存条 2 现在有 8 位剩余可用内存。
  • 第 3 秒,内存条 1 被占用 3 位内存,内存条 1 现在有 5 位剩余可用内存。
  • 第 4 秒,内存条 2 被占用 4 位内存,内存条 2 现在有 4 位剩余可用内存。
  • 第 5 秒,内存条 1 被占用 5 位内存,内存条 1 现在有 0 位剩余可用内存。
  • 第 6 秒,程序意外退出,两个内存条分别有 0 位和 4 位剩余可用内存。

提示:

1
0 <= memory1, memory2 <= 2^31 - 1

算法: 模拟

初始内存为 memory1 和 memory2,然后从 1 开始一秒一秒地模拟。第 i 秒要分配 i 位。如果:

  • i > memory1 且 i > memory2,则两个内存跳都无法分配,返回结果 [i, memory1, memory2]
  • i > memory1 且 i <= memory2, 只能将 i 位分派到 memory2, 将 memory2 减 i
  • i <= memory1 且 i > memory2, 只能将 i 位分派到 memory1, 将 memory1 减 i
  • i <= memory1 且 i <= memory2, 将 memory1 和 memory1 中较小的键 i

模拟直到两个内存都无法分配。

假设返回时间点是 t,则第 1 到第 t - 1 秒都是成功分配的,且第 t 秒没有成功分配。根据等差数列求和,第 1 到第 t - 1 秒分配的总量为 $(1 + t - 1) \times (t - 1) / 2 = t(t - 1) / 2$。

由于 $t(t - 1) / 2 <= memory1 + memory2$,因此时间复杂度为 $O(\sqrt{memory1 + memory2})$。

代码(C++)

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 {
public:
vector<int> memLeak(int memory1, int memory2) {
int i = 1;
while(true)
{
if(i > memory1 && i > memory2)
return vector<int>{i, memory1, memory2};
if(i > memory1)
memory2 -= i;
else if(i > memory2)
memory1 -= i;
else
{
if(memory1 >= memory2)
memory1 -= i;
else
memory2 -= i;
}
++i;
}
}
};

C题

给你一个 m x n 的字符矩阵 box ,它表示一个箱子的侧视图。箱子的每一个格子可能为:

  • ‘#’ 表示石头
  • ‘*’ 表示固定的障碍物
  • ‘.’ 表示空位置

这个箱子被 顺时针旋转 90 度 ,由于重力原因,部分石头的位置会发生改变。每个石头会垂直掉落,直到它遇到障碍物,另一个石头或者箱子的底部。重力 不会 影响障碍物的位置,同时箱子旋转不会产生惯性 ,也就是说石头的水平位置不会发生改变。

题目保证初始时 box 中的石头要么在一个障碍物上,要么在另一个石头上,要么在箱子的底部。

请你返回一个 n x m的矩阵,表示按照上述旋转后,箱子内的结果。

示例 1:
输入:box = [[“#”,”.”,”#”]]
输出:[[“.”],
[“#”],
[“#”]]
示例 2:
输入:box = [[“#”,”.”,”“,”.”],
[“#”,”#”,”
“,”.”]]
输出:[[“#”,”.”],
[“#”,”#”],
[““,”“],
[“.”,”.”]]
示例 3:
输入:box = [[“#”,”#”,”“,”.”,”“,”.”],
[“#”,”#”,”#”,”“,”.”,”.”],
[“#”,”#”,”#”,”.”,”#”,”.”]]
输出:[[“.”,”#”,”#”],
[“.”,”#”,”#”],
[“#”,”#”,”
“],
[“#”,”“,”.”],
[“#”,”.”,”
“],
[“#”,”.”,”.”]]

提示:

1
2
3
4
m == box.length
n == box[i].length
1 <= m, n <= 500
box[i][j] 只可能是 '#' ,'*' 或者 '.' 。

算法: 单串单向双指针

首先模拟球的下落,在原矩阵中对应地是向右移动,这一步一行一行地做就可以,对应到代码中的 process_col 函数。

对于每一行,我们做一轮单串单向双指针,双指针的端点为 [l, r]。

1
2
3
4
5
step1: 首先初始化 l 为 0,只要当前 l 位置为障碍物,就往右推进 l。
step2: 然后初始化 r 等于 l,石头计数初始化 cnt 为 0。只要当前 r 位置不为障碍物,就向右推进 r,过程中如果 r 遇到石头,则计数 cnt 加 1。
step3: r 遇到障碍物或者到达结尾后,将 cnt 个石头依次放在 r-1, r-2, ..., r-cnt 位置。并且将 r-cnt-1, ..., l 中的所有石头变为空位置
step4: 更新 l 位置,首先将 l 设为 r,只要当前 l 为障碍物,则向右推进 l。
step5: 返回 step2

移动完成后,模拟矩阵的旋转,将原矩阵 box 旋转后得到新矩阵 rotated

代码(C++)

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
class Solution {
public:
vector<vector<char>> rotateTheBox(vector<vector<char>>& box) {
int n = box.size(), m = box[0].size();
for(int i = 0; i < n; ++i)
{
process_col(box[i]);
}
vector<vector<char>> rotated(m, vector<char>(n));
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
rotated[j][n - 1 - i] = box[i][j];
return rotated;
}

private:
void process_col(vector<char>& row)
{
int n = row.size();
int l = 0;
while(l < n && row[l] == '*')
++l;
while(l < n)
{
// row[l] != '*'
int r = l;
int cnt = 0;
while(r < n && row[r] != '*')
{
if(row[r] == '#')
++cnt;
++r;
}
for(int i = 0; i < cnt; ++i)
row[r - 1 - i] = '#';
for(int i = r - 1 - cnt; i >= l; --i)
row[i] = '.';
l = r;
while(l < n && row[l] == '*')
++l;
}
}
};

D题

给你一个整数数组 nums ,请你返回所有下标对 0 <= i, j < nums.length 的 floor(nums[i] / nums[j]) 结果之和。由于答案可能会很大,请你返回答案对1e9 + 7 取余 的结果。

函数 floor() 返回输入数字的整数部分。

示例 1:
输入:nums = [2,5,9]
输出:10
解释:
floor(2 / 5) = floor(2 / 9) = floor(5 / 9) = 0
floor(2 / 2) = floor(5 / 5) = floor(9 / 9) = 1
floor(5 / 2) = 2
floor(9 / 2) = 4
floor(9 / 5) = 1
我们计算每一个数对商向下取整的结果并求和得到 10 。

示例 2:
输入:nums = [7,7,7,7,7,7,7]
输出:49

提示:

1
2
1 <= nums.length <= 1e5
1 <= nums[i] <= 1e5

算法1: 排序 + 单串单向双指针

将 nums 排序。

然后用单串单向双指针去得到各个区间(外层),每个区间包含相同的一个数。例如 nums 排序后为 [1, 2, 2, 4, 5, 5, 5, 7],那么双指针的过程得到的各个区间为 nums[0] = [1], nums[1..2] = [2, 2], nums[3] = [4], nums[4, 5, 6] = [5, 5, 5], nums[7] = [7]

对于每个区间(记为 [li, ri),再用单串单向双指针走一遍(内层),得到各个包含相同数的区间(记为 [lj, rj),内层这一层对答案的贡献就是 floor(nums[lj] / nums[li]) * (rj - lj),将所有的这些贡献相加,得到最终答案。

下面的问题是两个单串单向双指针的过程中,固定 l 之后,如何找到 r。如果是通过一个一个地判断,那么两层双指针的时间复杂度为 $O(N^{2})$

在外层,固定 li 后,我们要找 [li..n-1] 中的最小的 ri,使得 nums[ri] > nums[li],直接线性地推进 ri 即可。

在内层,固定 lj 后,我们就已经知道内层每个单位长度可以贡献的答案了,也就是 floor(nums[lj] / nums[li]),古国内层所得区间为 [lj, rj),则当前内外层组合贡献答案: floor(nums[lj] / nums[li]) * (rj - lj)

假设 t = floor(nums[lj] / nums[li]) 那么当前内层选中的区间 [lj, rj] 应该满足 t <= nums[rj] / nums[li] < t + 1,其中 t 和 nums[li] 已知,于是可以得到 nums[rj] 的范围: t * nums[i] <= nums[j] < (t + 1) * nums[i]

于是我们用二分的方式找到大于等于 (t + 1) * nums[li] 的最小的数的位置 rj

1
int rj = lower_bound(nums.begin() + lj, nums.end(), (t + 1) * nums[li]) - nums.begin();

向最终答案里累加当前内外侧组合贡献答案 floor(nums[lj] / nums[li]) * (rj - lj) * (ri - li)。枚举完内外层区间组合即可得到最终答案。

这个算法可以跑过,但是时间复杂度我不会推导。

代码(C++)

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:
int sumOfFlooredPairs(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
using ll = long long;
const int MOD = 1e9 + 7;
int ans = 0;
int li = 0;
while(li < n)
{
// 按范围枚举分母 nums[i]
int ri = upper_bound(nums.begin() + li, nums.end(), nums[li]) - nums.begin();
int lj = 0;
while(lj < n)
{
int t = nums[lj] / nums[li];
int rj = lower_bound(nums.begin() + lj, nums.end(), (t + 1) * nums[li]) - nums.begin();
ans = (ans + (((t * (ll)(rj - lj)) % MOD) * (ll)(ri - li)) % MOD) % MOD;
lj = rj;
}
li = ri;
}
return ans;
}
};

算法2: 频数前缀和

算法2我不会,以下为学习了官方题解之后写出来的。

由于 nums[i] 的范围是 [1, 1e5],可以直接开一个频率数组 cnt,cnt[x] = nums 中 x 的个数

正常的枚举过程: 枚举所有数字 x,再所有数字 y,(x, y) 这对组合对答案贡献 cnt[x] * cnt[y] * floor(x/y)

转换枚举过程,不是枚举 (x, y) 而是枚举 (y, floor(x/y))

枚举到 (y, t=floor(x/y)) 时,如果知道有 k 个 x 对应的 floor(x/y) 恰好为 t,那么 (y, t) 组合对答案的贡献为 cnt[y] * k * t

由于 t <= x / y < t + 1,于是可以得到 x 的范围: t * y <= x < (t + 1) * y,现在问题就变成了 nums 中有多少数的范围在 [t * y, (t + 1) * y) 之间,这个值就是前面定义的 k。

如果提前预处理了 cnt 的前缀和 sums, 那么 k = sums[min(y * (t + 1) - 1, U) + 1] - sums[t * y]

时间复杂度:

两层枚举的时间复杂度为 $O(C\sum\limits_{t=1}\limits^{\lfloor C/y\rfloor}1) = O(\sum\limits_{y=1}\limits^{C}\frac{C}{y})$,这是调和级数,趋近于 $O(ClogC)$

代码(C++)

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
class Solution {
public:
int sumOfFlooredPairs(vector<int>& nums) {
using ll = long long;
const int MOD = 1e9 + 7;
const int U = 1e5;

vector<int> cnt(U + 1);
for(int x: nums) ++cnt[x];
vector<int> sums(U + 2);
for(int x = 1; x <= U + 1; ++x)
sums[x] = sums[x - 1] + cnt[x - 1];

ll ans = 0;
for(int y = 1; y <= U; ++y)
{
for(int t = 1; t * y <= U; ++t)
{
int k = sums[min((t + 1) * y - 1, U) + 1] - sums[t * y];
ans += cnt[y] * (ll)k * t;
}
}
return ans % MOD;
}
};

Share