算法leetcode

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

字数统计: 3.9k字   |   阅读时长: 16分
,

摘要: 本文是 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