前言

我出生时的情形？嗯，稍微有点印象。
我在昏暗的森林里独自哇哇大哭。
虽然寂寞也是我哭的原因，但不知道为什么，内心很悲伤。
如果就这样一直没被前辈们发现，我想，我大概会哭成一滩水洼吧……
不，我们的体质还满匪夷所思，这番话有一半是认真的。
现在？现在已经没问题了。
生活又没有平稳到可以让我因为寂寞难过而哭哭啼啼的。
……欸，做什么。
你那是什么温柔的眼神？
感觉好像被你当成小孩，真令人火大。

整体评价

t1感觉是超级签名题，t2和秋季赛的t3有点渊源，t3带限制的单调栈应用，t4好难。

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

更多解题报告详见：珂朵莉MM的解题报告汇总

1. 统计链表奇数节点

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

直接贴代码，好像真没啥好讲的。

Java

class Solution {
    public int numberEvenListNode(ListNode head) {
        if (head == null) return 0;
        ListNode cur = head;
        int ans = 0;
        while (cur != null) {
            if (cur.val % 2 == 1) {
                ans++;
            }
            cur = cur.next;
        }
        return ans;
    }
}

2. 光线反射

221021天池-02. 光线反射

这种带反射，肯定没有环，所以直接模拟就行。

模拟就行, 不过这代码，写的有些丑陋，T_T.

Java

class Solution {

    static final int[][] dirs = new int[][] {
            {0, 1},
            {1, 0},
            {0, -1},
            {-1, 0},
    };

    int solve(char[][] board, int y, int x, int d) {
        int r = board.length, c = board[0].length;
        int ans = 0;
        while (y >= 0 && y < r && x >= 0 && x < c) {
            ans++;
            char ch = board[y][x];
            if (ch == '.') {
            } else if (ch == 'L') {
                if (d == 0) {
                    d = 1;
                } else if (d == 1) {
                    d = 0;
                } else if (d == 2) {
                    d = 3;
                } else {
                    d = 2;
                }
            } else if (ch == 'R') {
                if (d == 0) {
                    d = 3;
                } else if (d == 3) {
                    d = 0;
                } else if (d == 1) {
                    d = 2;
                } else {
                    d = 1;
                }
            }

            y = y + dirs[d][0];
            x = x + dirs[d][1];
        }

        return ans;
    }

    public int getLength(String[] grid) {
        int n = grid.length;
        char[][] board = new char[n][];
        for (int i = 0; i < n; i++) {
            board[i] = grid[i].toCharArray();
        }


        return solve(board, 0, 0, 1);
    }

}

3. 整理书架

221021天池-03. 整理书架

带限制条件的单调栈，核心还是贪心。

总觉得哪里做过类似题的感觉....

Java

class Solution {

    // *)
    public int[] arrangeBookshelf(int[] order, int limit) {
        // 感觉和单调栈有关

        Map<Integer, Integer> hash = new HashMap<>();
        for (int v: order) {
            hash.put(v, hash.getOrDefault(v, 0) + 1);
        }

        Stack<Integer> stack = new Stack<>();

        Map<Integer, Integer> prev = new HashMap<>();
        for (int i = 0; i < order.length; i++) {
            int v = order[i];
            hash.put(v, hash.getOrDefault(v, 0) - 1);

            if (prev.getOrDefault(v, 0) < limit) {
                while (!stack.isEmpty() && v < stack.peek()) {
                    int tv = stack.peek();

                    int cnt = prev.getOrDefault(tv, 0) - 1 + hash.getOrDefault(tv, 0);

                    if (cnt >= limit) {
                        stack.pop();
                        prev.put(tv, prev.getOrDefault(tv, 0) - 1);
                    } else {
                        break;
                    }
                }

                stack.push(v);
                prev.put(v, prev.getOrDefault(v, 0) + 1);
            }
        }

        List<Integer> arr = new ArrayList<>();
        while (!stack.isEmpty()) {
            arr.add(stack.pop());
        }
        Collections.reverse(arr);

        return arr.stream().mapToInt(Integer::valueOf).toArray();

    }

}

4. 意外惊喜

221021天池-04. 意外惊喜

惭愧，完全不会，连0-1背包都没想到。