「天池 X LeetCode」在线编程专场选拔赛

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

菜菜

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

思路：模拟

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int numberEvenListNode(ListNode head) {
        int c = 0;
        while (head != null) {
            if (head.val % 2 == 1)
                c++;
            head = head.next;
        }
        return c;
    }
}

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’ 和 ‘.’

思路：模拟

class Solution {
    public int getLength(String[] grid) {
        return dfs(grid, 0, 0, 0);
    }
    // 0, 1, 2, 3
    int[] dx = {1, 0, -1, 0}, dy = {0, -1, 0, 1};
    int[] dr = {1, 0, 3, 2}, dl = {3, 2, 1, 0};
    int dfs(String[] grid, int from, int x, int y) {
        if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length())
            return 0;
        int res = 1;
        char c = grid[x].charAt(y);
        if (c == '.') {
            res += dfs(grid, from, x + dx[from], y + dy[from]);
        } else if (c == 'R') {
            from = dr[from];
            res += dfs(grid, from, x + dx[from], y + dy[from]);
        } else {
            from = dl[from];
            res += dfs(grid, from, x + dx[from], y + dy[from]);
        }
        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

思路：贪心 + 单调栈

class Solution {
    public int[] arrangeBookshelf(int[] a, int limit) {
        int n = a.length;
        int[] stk = new int[n];
        int p = -1;
        Map<Integer, Integer> map = new HashMap<>();
        Map<Integer, Integer> cnt = new HashMap<>();
        Map<Integer, Integer> used = new HashMap<>();
        for (int x : a) map.merge(x, 1, Integer::sum);
        for (int i = 0; i < n; i++) {
            if (cnt.getOrDefault(a[i], 0) >= limit) {
                used.merge(a[i], 1, Integer::sum);
                continue;
            }
            while (p > -1 && a[i] < a[stk[p]] && cnt.get(a[stk[p]]) - 1 + map.get(a[stk[p]]) - used.get(a[stk[p]]) >= limit) {
                int idx = stk[p--];
                cnt.merge(a[idx], -1, Integer::sum);
            }
            used.merge(a[i], 1, Integer::sum);
            stk[++p] = i;
            cnt.merge(a[i], 1, Integer::sum);
        }
        int[] res = new int[p + 1];
        for (int i = 0; i <= p; i++)
            res[i] = a[stk[i]];
        return res;
    }
}

类似的题目：
2434. 使用机器人打印字典序最小的字符串
2030. 含特定字母的最小子序列

class Solution {
    public String smallestSubsequence(String s, int k, char letter, int repetition) {
        int n = s.length();
        char[] c = s.toCharArray();
        int[] rt = new int[n], r = new int[n];
        for (int i = n - 1, a = 0, b = 0; i >= 0; i--) {
            rt[i] = a;
            r[i] = b;
            if (c[i] == letter) a++;
            else b++;
        }
        char[] stk = new char[n];
        int p = -1;
        for (int i = 0, cnt = 0; i < n; i++) {
            while (p > -1 && stk[p] > c[i]) {
                if (stk[p] == letter) {
                    if (cnt + rt[i] - 1 >= repetition && p + r[i] + rt[i] + 1 >= k) {
                        p--;
                        cnt--;
                    } else break;
                } else if (p + r[i] + rt[i] + 1 >= k)
                    p--;
                else break;
            }
            stk[++p] = c[i];
            if (c[i] == letter) cnt++;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0, cnt = 0; i <= p && sb.length() != k; i++) {
            int need = repetition - cnt;
            if (stk[i] == letter) {
                sb.append(stk[i]);
                cnt++;
            } else {
                if (need < k - sb.length())
                    sb.append(stk[i]);
            }
        }
        return sb.toString();
    }
}

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

思路：背包 + 分治 + 贪心
CF原题https://codeforces.com/problemset/problem/1442/D