leetcode 阿里天池专场

第三题与第四题确实比较难，前两题都是常规题目

221021天池-01. 统计链表奇数节点

题目

给你一个链表的头节点 head，请统计链表中值为奇数的节点个数

示例 1：

输入：head = [2,1,8]
输出：1
解释：链表中存在 1 个奇数值的节点，值为 1

示例 2：

输入：head = [1,2,3,4]
输出：2
解释：链表中存在 2 个奇数值的节点，值分别为 1、3

提示：

链表中节点的数目在 [1, 5000] 范围内。
1 <= Node.val <= 10000

地址

https://leetcode.cn/contest/tianchi2022/problems/yGdjWb/

题意

直接模拟

思路

我们直接遍历整个链表即可。
复杂度分析：

时间复杂度：$O(n)$。
空间复杂度：$O(1)$。

代码

class Solution {
public:
    int numberEvenListNode(ListNode* head) {
        int res = 0;
        while(head) {
            if (head->val % 2 == 1) {
                res++;
            }
            head = head->next;
        }
        return res;
    }
};

221021天池-02. 光线反射

题目

工程师正在研究一个 N*M 大小的光线反射装置，装置内部的构造记录于 grid 中，其中

'.' 表示空白区域，不改变光的传播方向
'R' 表示向右倾斜的双面均可反射光线的镜子，改变光的传播方向
'L' 表示向左倾斜的双面均可反射光线的镜子，改变光的传播方向
假如光线从装置的左上方垂直向下进入装置，请问在离开装置前，光线在装置内部经过多长的路线。

示例 1：

输入：grid = ["...","L.L","RR.","L.R"]
输出：12
解释：如图所示，光线经过路线长度为 12

示例 2：

输入：grid = ["R.",".."]
输出：1
解释：如图所示，光线经过路线长度为 1

提示：

1 <= grid.length, grid[i].length <= 100
grid[i][j] 仅为 'L'、'R' 和 '.'

地址

https://leetcode.cn/problems/find-the-original-array-of-prefix-xor/

题意

遍历

思路

题目比较简单，只是一个简单的转换，我们设有四个方向：左上右下，沿着四个方向射入某个单元格。

遇到右倾斜，则变换为:下右上左
遇到左倾斜，则变换为:上左下右
根据当前的变换即可得到最终的结果。

复杂度分析：

时间复杂度：时间复杂度为 $O(m \times n)$，其中 $m$ 表示矩阵的行数，$n$ 表示矩阵的列数。
空间复杂度：空间复杂度为 $O(1)$。

代码

class Solution {
public:
    int getLength(vector<string>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int res = 0;
        int dir[4][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
        int cr[4] = {3, 2, 1, 0};
        int cl[4] = {1, 0, 3, 2};
        queue<tuple<int,int,int>> qu;
        int x = 0, y = 0, d = 3;
        while(x >= 0 && y >= 0 && x < m && y < n) {
            res++;
            if (grid[x][y] == '.') {
                x = x + dir[d][0];
                y = y + dir[d][1];
            } else if (grid[x][y] == 'L') {
                d = cl[d];
                x = x + dir[d][0];
                y = y + dir[d][1];
            } else if (grid[x][y] == 'R') {
                d = cr[d];
                x = x + dir[d][0];
                y = y + dir[d][1];
            }
        }
        return res;
    }
};

221021天池-03. 整理书架

题目

书架上有若干本书，从左至右的书籍编号记于整型数组 order 中。为保证书籍多样性，管理员想取走一些重复编号的书籍，要求满足以下条件：

剩余书本中相同编号的书本数量均不大于 limit
取走的书籍数量尽可能少
由于存在多种整理方案，请返回剩余书本编号的排列为「最小排列」的方案。

注意：

「最小排列」：若干数组中第一位数字最小的数组；若第一位数字相同，则为第二位数字最小的数组，以此类推。
示例 1：

输入：order = [5,5,6,5], limit = 2
输出：[5,5,6]
解释：order 中出现了 3 次 5 号书：
方案 1：去掉 order[0] 或 order[1]，所得排列为 [5,6,5]；
方案 2：去掉 order[3]，所得排列为 [5,5,6]；
经比较，最终返回排列最小的方案 2：[5,5,6]。

示例 2：

输入：order = [5,5,6,5], limit = 3
输出：[5,5,6,5]
解释：order 中所有相同编号的书本数目均未超过 limit，不需要去除，返回 [5,5,6,5]

示例 3：

输入：order = [3,3,9,8,9,2,8], limit = 1
输出：[3,8,9,2]
解释：列表中 3、8、9 号数字都出现了 2 次，去掉编号相同的书后的排列结果中 [3,8,9,2] 为排列最小的结果。

示例 4：

输入：order = [2,1,2,2,1,3,3,1,3,3], limit = 2
输出：[1,2,2,1,3,3]

提示：

1 <= order.length <= 10^5
1 <= limit <= 10
1 <= order[i] <= 10^6

地址

https://leetcode.cn/contest/tianchi2022/problems/ev2bru/

题意

贪心 + 栈

思路

题目本身有些难，比较难想到，最后看了解答用的贪心的栈，关键是在于剔除的操作，比如当前候选队列分别为 $[2,3,2],[2,1,2]$，由于我们现在需要剔除一个 $2$，则：

对于第一种情况由于由于 $3$ 比 $2$ 大，此时我们需要检测 $3$ 之前存储的

复杂度分析

时间复杂度：时间复杂度为 $O(n)$，$n$ 为数组的长度。
空间复杂度：时间复杂度为 $O(1)$。

代码

class Solution {
public:
    vector<int> arrangeBookshelf(vector<int>& order, int limit) {
        unordered_map<int,int> cnt, st_cnt;
        vector<int> res;
        for (auto v : order) {
            cnt[v]++;
        }
        res.emplace_back(0);
        for (auto x : order) {
            /* skip the current val */
            if (st_cnt[x] == limit) {
                cnt[x]--;
                continue;
            }
            while (x < res.back() && cnt[res.back()] > limit) {
                cnt[res.back()]--;
                st_cnt[res.back()]--;
                res.pop_back();
            }
            res.emplace_back(x);
            st_cnt[x]++;
        }
        vector<int> ans;
        for (int i = 1; i < res.size(); i++) {
            ans.emplace_back(res[i]);
        }
        return ans;
    }
};

221021天池-04. 意外惊喜

题目

某电商平台举办了一个用户抽奖活动，奖池中共有若干个礼包，每个礼包中包含一些礼物。 present[i][j] 表示第 i 个礼包第 j 件礼（下标从 0 开始）物的价值。抽奖规则如下：

每个礼包中的礼物摆放是有顺序的，你必须从第 0 件礼物开始打开；
对于同一个礼包中的礼物，必须在打开该礼包的第 i 个礼物之后，才能打开第 i+1 个礼物；
每个礼物包中的礼物价值非严格递增。
参加活动的用户总共可以打开礼物 limit 次，请返回用户能够获得的最大礼物价值总和。

示例 1：

输入: present = [[1,2],[2,3],[3,4]], limit = 3
输出: 9
解释：最佳的方案为：
第 1 次拿走第 3 个礼包中的第 1 个礼物，得到价值 3；
第 2 次拿走第 3 个礼包中的第 2 个礼物，得到价值 4；
第 3 次拿走第 2 个礼物包的第 1 个礼物，得到价值 2；
返回打开的礼物价值总和 3 + 4 + 2 = 9

示例 2：

输入: present = [[1,2,100],[4,5],[3,4]], limit = 4
输出: 107
解释：最佳的方案为：
第 1 次拿走第 1 个礼包中的第 1 个礼物，得到价值 1；
第 2 次拿走第 1 个礼包中的第 2 个礼物，得到价值 2；
第 3 次拿走第 1 个礼物包的第 3 个礼物，得到价值 100；
第 4 次拿走第 2 个礼物包的第 1 个礼物，得到价值 4；
返回打开的礼物价值总和 107

提示：

1 <= present.length <= 2000
1 <= present[i].length <= 1000
1 <= present[i][j] <= present[i][j+1] <= 10^5
1 <= limit <= 1000

地址

https://leetcode.cn/contest/tianchi2022/problems/tRZfIV/

题意

归并+ 01背包

思路

题目难度太大，还是参考题解，很少会出这么难的题目。
复杂度分析

时间复杂度：时间复杂度为 $O(limit \times n \times \log n)$，$n$ 为数组的长度。
空间复杂度：时间复杂度为 $O(n \times m)$。

代码

class Solution {
public:
    int brilliantSurprise(vector<vector<int>>& present, int limit) {
        int ans = 0;
        int n = present.size();
        vector<vector<int>> s(n);
        for (int i = 0; i < present.size(); i += 1) {
            s[i].resize(present[i].size() + 1);
            for (int j = 0; j < present[i].size(); j += 1)
                s[i][j + 1] = s[i][j] + present[i][j];
        }
        vector<int> dp(limit + 1);
        function<void(int, int)> DFS = [&](int L, int R) {
            int M = (L + R) / 2;
            if (L == R) {
                for (int i = 0, pre = 0; i <= limit; i += 1) {
                    pre = max(pre, dp[i]);
                    ans = max(ans, pre + s[M][min((int)s[M].size() - 1, limit - i)]);
                }
                return;
            }
            {
                auto f = dp;
                for (int i = M + 1; i <= R; i += 1) {
                    auto g = dp;
                    int x = (int)s[i].size() - 1, y = s[i].back();
                    for (int j = x; j <= limit; j += 1)
                        g[j] = max(g[j], dp[j - x] + y);
                    dp.swap(g);
                }
                DFS(L, M);
                dp = f;
            }
            {
                auto f = dp;
                for (int i = L; i <= M; i += 1) {
                    auto g = dp;
                    int x = (int)s[i].size() - 1, y = s[i].back();
                    for (int j = x; j <= limit; j += 1)
                        g[j] = max(g[j], dp[j - x] + y);
                    dp.swap(g);
                }
                DFS(M + 1, R);
                dp = f;
            }
        };
        DFS(0, n - 1);
        return ans;
    }
};

欢迎关注和打赏，感谢支持！

关注我的博客: http://mikemeng.org/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 公务程序猿

Tags: 力扣周赛

← leetcode biweekly contest 90 树状数组 →

扫描二维码，分享此文章