数据结构 算法 leetcode

力扣杯秋季编程大赛 2021 战队赛

lose together, win together, slay together.

Posted by MatthewHan on 2021-10-18

0x00

第一次和小伙伴一起参加战队赛，根据以往经验以为只能做出来一题，结果还真就一题。但是第一题实在是太白给了，都不能算题，所以说相当于一题都没做出来。

坐牢 3 小时，不过我对第二题的印象很深刻，之前对于图中判环、跳环的问题一直处理不好，经此一役，不再害怕。

0x01

第 0 题：开幕式焰火

沾点白给了，一开始觉得应该没这么简单，还反复检查确认，多少沾点懦弱哥了，递归一套就完事了。

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
public class Lcp44 {

    Set<Integer> set;

    /**
     * 开幕式火焰
     *
     * @param root
     * @return
     */
    public int numColor(TreeNode root) {
        set = new HashSet<>();
        dfs(root);
        return set.size();
    }

    public void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        set.add(root.val);
        dfs(root.left);
        dfs(root.right);
    }
}

第 1 题：自行车炫技赛场

这题 byd 是真难读题啊，和小伙伴解题过程中碰到了一个小问题，解决了又来一个。不是 Wrong Answer 、Time Limit Exceeded 就是 Runtime Error 到比赛结束了都一致认为只要存在高度差速度就肯定会一直下降。其实，速度不一定会一直降的。可能会出现速度 +1、-1 一直重复走的情况。所以难点就是如何不走重复路，如果每次递归都开一个 vis 对象去判重的话，内存直接爆了，所以需要一个三维数组，三个向量分别是 x、 y、 v ，其中 x、y 是场地坐标，v 是速度。三个向量确定一个唯一值，重复跳出。我这里用的是 HashSet，比三维数组快一点。

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
48
49
50
51
52
53
54
class Solution {
    
    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, -1, 1};
    List<int[]> ans;
    Set<String> mem;
    boolean[][] global;
    int[] p;

    public int[][] bicycleYard(int[] position, int[][] terrain, int[][] obstacle) {
        ans = new ArrayList<>();
        mem = new HashSet<>();
        global = new boolean[terrain.length][terrain[0].length];
        p = position;
        bfs(1, position[0], position[1], terrain, obstacle);
        int[][] res = new int[ans.size()][2];
        for (int i = 0; i < ans.size(); i++) {
            res[i] = ans.get(i);
        }
        Arrays.sort(res, (o1, o2) -> {
            if (o1[0] == o2[0]) {
                return Integer.compare(o1[1], o2[1]);
            } else {
                return Integer.compare(o1[0], o2[0]);
            }
        });
        return res;
    }

    public void bfs(int curr, int x, int y, int[][] terrain, int[][] obstacle) {
        if (x >= 0 && y >= 0 && x < terrain.length && y < terrain[0].length) {
            for (int i = 0; i < 4; i++) {
                int newX = x + dx[i];
                int newY = y + dy[i];
                if (newX >= 0 && newY >= 0 && newX < terrain.length && newY < terrain[0].length) {
                    int next = curr + terrain[x][y] - terrain[newX][newY] - obstacle[newX][newY];
                    // i, j, v 作为唯一 key
                    String k = newX + "-" + newY + "-" + next;
                    if (mem.contains(k)) {
                        continue;
                    }
                    mem.add(k);
                    if (next >= 1) {
                        if (next == 1 && (newX != p[0] || newY != p[1]) && !global[newX][newY]) {
                            global[newX][newY] = true;
                            ans.add(new int[]{newX, newY});
                        }
                        bfs(next, newX, newY, terrain, obstacle);
                    }
                }
            }
        }
    }
}

第一次组队参加战队赛，虽然结果不太理想，但是和小伙伴一起思考，一起交流的过程还是非常美妙的。想起了 OG 战队的 ceb 在 Ti8 Grand Finals 最后一场开始前的一句话：

Lose together, win together, slay together, slay together, slay together.

CATALOG
    FEATURED TAGS
    数据结构 算法 leetcode
    FRIENDS