【Leetcode】第335场周赛题解_bfsla

简介

Leetcode第335场周赛，一共4道题，时间1.5h
比赛链接

第一题：2582. 递枕头

2582. 递枕头

思路：写简单的公式

步骤：

1. 判断当前是处于1-n还是n-1的趟数
2. 根据times%(n-1)来确定处于当前趟的位置

代码

int passThePillow(int n, int time)
{
    int mod = time % (n - 1);
    int sindou = time / (n - 1);
    return sindou % 2 ? n - mod : 1 + mod;
}
1
2
3
4
5
6

第二题：2583. 二叉树中的第 K 大层和

2583. 二叉树中的第 K 大层和

思路1：bfs

• 一看到处理的是树的“层”信息，就想到用bfs
• 类似层序遍历，求每一层的和即可
• 弊端：代码量大

代码1：bfs

int getDepth(TreeNode *root)
{
    if (root == NULL)
        return 0;
    else
    {
        return max(getDepth(root->left), getDepth(root->right)) + 1;
    }
}

vector<long long> getLevelSum(TreeNode *root, int total)
{
    queue<pti> qt;
    vector<long long> levelSum(total + 1, 0);

    qt.push(make_pair(root, 1));
    while (!qt.empty())
    {
        pti tp = qt.front();
        levelSum[tp.second] += tp.first->val;
        qt.pop();
        if (tp.first->left != NULL)
        {
            qt.push(make_pair(tp.first->left, tp.second + 1));
        }
        if (tp.first->right != NULL)
        {
            qt.push(make_pair(tp.first->right, tp.second + 1));
        }
    }
    return levelSum;
}

long long kthLargestLevelSum(TreeNode *root, int k)
{
    vector<long long> ans;
    int total = getDepth(root);
    if (total < k)
    {
        return -1;
    }
    else
        ans = getLevelSum(root, total);

    sort(ans.rbegin(), ans.rend());
    return ans[k - 1];
}
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
46
47

思路2：dfs

• 通过dfs，将“层”作为参数，进行递归之间的传递
• 全局变量保存每一层的和
• 代码简洁

代码2：dfs

vector<long long> sum;
void dfs(TreeNode *root, int dep)
{
    if (root == nullptr)
        return;
    if (sum.size() == dep)
        sum.push_back(0);
    sum[dep] += root->val;
    dfs(root->left, dep + 1);
    dfs(root->right, dep + 1);
}

long long kthLargestLevelSum(TreeNode *root, int k)
{
    dfs(root, 0);
    if (sum.size() < k)
        return -1;
    sort(sum.begin(), sum.end());
    return sum[sum.size() - k];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

第三题：2584. 分割数组使乘积互质

2584. 分割数组使乘积互质

思路：分解质因数 + 合并区间

本次周赛最难的题（比最后一题难），思考过程如下：

1. 反向思考，题目要求在nums范围找最小的i满足要求，那么 “哪些地方的i不能取” ？
2. 如下图所示，当左侧有质因数，右侧也出现了的时候，该位置不能取，即对每个质因数找到nums出现的最左、右的下标i，j，那么答案不能在[i,j)里面

于是有了具体步骤：

1. 分解质因子
2. 设置left每个质数最左边出现的位置,right[i]=j 表示每个位置最右边到的位置,则right就已经记录了[i,j)的信息，也就是所有不能取得区间
3. 最后合并区间找第一个空的位置（不被任何区间覆盖）

代码

int findValidSplit(vector<int> &nums)
{
    unordered_map<int, int> left;

    vector<int> right(nums.size(), 0);
    auto f = [&](int p, int i)
    {
        auto it = left.find(p);
        if (it == left.end())
            left[p] = i; // 第一次遇到质数 p
        else
        {
            right[it->second] = i; // 记录左端点 l 对应的右端点的最大值
        }
    };

    // 分解质因数
    for (int n = 0; n < nums.size(); n++)
    {
        int tp = nums[n], d = 2;
        while (d * d <= tp)
        {
            if (tp % d == 0)
            {
                f(d, n);
                while (tp % d == 0)
                {
                    tp /= d;
                }
            }
            d++;
        }
        if (tp > 1)
            f(tp, n);
    }
    // 开始找区间,若到了空位（不在任何区间内）
    int ans = 0;
    for (int i = 0; i <= nums.size() - 1; i++)
    {
        if (i > ans)
            return ans;
        ans = max(ans, right[i]);
    }
    return -1;
}
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

第四题：2585. 获得分数的方法数

2585. 获得分数的方法数

思路：DP，背包问题

• 设dp[i][j]表示前i类型获得j体积的拿法
• dp[i][j] = dp[i][j]+ dp[i - 1][j - n * types[i - 1][1]]
• (其中n属于1，2，，，，,j / types[i-1][1])

代码

int waysToReachTarget(int target, vector<vector<int>> &types)
{
    vector<vector<int>> dp(types.size() + 1, vector<int>(1001, 0));
    for (int i = 0; i <= types.size(); i++)
    {
        for (int j = 0; j <= target; j++)
        {
            if (i == 0 && j == 0)
                dp[i][j] = 1;
            else if (i == 0 && j != 0)
                dp[i][j] = 0;
            else if (j == 0)
            {
                dp[i][j] = 1;
            }
            else
            {
                int tp = 0;
                while (tp <= types[i - 1][0])
                {
                    if (j - tp * types[i - 1][1] >= 0)
                    {
                        dp[i][j] = (dp[i][j] % 1000000007 + dp[i - 1][j - tp * types[i - 1][1]] % (1000000007)) % (1000000007);
                    }
                    else
                        break;
                    tp++;
                }
            }
        }
    }
    cout << dp[types.size()][target] << endl;
    return dp[types.size()][target];
}
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