跳转至

力扣杯2021年秋季赛个人赛

题一 LCP 39. 无人机方阵

描述

在 「力扣挑战赛」 开幕式的压轴节目 「无人机方阵」中，每一架无人机展示一种灯光颜色。 无人机方阵通过两种操作进行颜色图案变换：

调整无人机的位置布局 切换无人机展示的灯光颜色 给定两个大小均为 N*M 的二维数组 source 和 target 表示无人机方阵表演的两种颜色图案，由于无人机切换灯光颜色的耗能很大，请返回从 source 到 target 最少需要多少架无人机切换灯光颜色。

注意： 调整无人机的位置布局时无人机的位置可以随意变动。

示例 1：

输入：source = [[1,3],[5,4]], target = [[3,1],[6,5]]

输出：1

解释： 最佳方案为 将 [0,1] 处的无人机移动至 [0,0] 处； 将 [0,0] 处的无人机移动至 [0,1] 处； 将 [1,0] 处的无人机移动至 [1,1] 处； 将 [1,1] 处的无人机移动至 [1,0] 处，其灯光颜色切换为颜色编号为 6 的灯光； 因此从source 到 target 所需要的最少灯光切换次数为 1。

示例 2：

输入：source = [[1,2,3],[3,4,5]], target = [[1,3,5],[2,3,4]]

输出：0 解释： 仅需调整无人机的位置布局，便可完成图案切换。因此不需要无人机切换颜色

提示： n == source.length == target.length m == source[i].length == target[i].length 1 <= n, m <=100 1 <= source[i][j], target[i][j] <=10^4

思路

存储源每个灯光的次数。遍历目标，当次数不够时，就需要切换颜色。

代码

/**
 * @author mikusugar
 */
public class N1 {

    public int minimumSwitchingTimes(int[][] source, int[][] target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int[] s : source) {
            for (int k : s) {
                map.put(k, map.getOrDefault(k, 0) + 1);
            }
        }
        int res = 0;
        for (int[] t : target) {
            for (int k : t) {
                if (map.containsKey(k)) {
                    final Integer cnt = map.get(k);
                    if (cnt == 1) map.remove(k);
                    else map.put(k, cnt - 1);
                } else res++;
            }
        }
        return res;
    }
}

题二 LCP 40. 心算挑战

描述

「力扣挑战赛」心算项目的挑战比赛中，要求选手从 N 张卡牌中选出 cnt 张卡牌，若这 cnt 张卡牌数字总和为偶数，则选手成绩「有效」且得分为 cnt 张卡牌数字总和。 给定数组 cards 和 cnt，其中 cards[i] 表示第 i 张卡牌上的数字。 请帮参赛选手计算最大的有效得分。若不存在获取有效得分的卡牌方案，则返回 0。

示例 1：

输入：cards = [1,2,8,9], cnt = 3

输出：18

解释：选择数字为 1、8、9 的这三张卡牌，此时可获得最大的有效得分 1+8+9=18。

示例 2：

输入：cards = [3,3,1], cnt = 1

输出：0

解释：不存在获取有效得分的卡牌方案。

提示：

  • 1 <= cnt <= cards.length <= 10^5
  • 1 <= cards[i] <= 1000

思路

  • 按奇数偶数分类。
  • 各自排序预求出sum。
  • 最后的和要为偶数，奇数的个数必须为偶数。
  • 遍历所有情况。

代码

/**
 * @author mikusugar
 */
public class N2 {

    public int maxmiumScore(int[] cards, int cnt) {

        List<Integer> l1 = new ArrayList<>();
        List<Integer> l2 = new ArrayList<>();
        for (int i : cards) {
            if (i % 2 == 0) l1.add(i);
            else l2.add(i);
        }
        l1.sort((o1, o2) -> Integer.compare(o2, o1));
        l2.sort((o1, o2) -> Integer.compare(o2, o1));

        int[] s1 = getSum(l1);
        int[] s2 = getSum(l2);

        int res = 0;
        for (int i = 0; i <= Math.min(cnt, s2.length-1); i += 2) {
            int j = cnt - i;
            if (j >= s1.length) continue;
            res = Math.max(res, s1[j] + s2[i]);
        }
        return res;
    }

    private int[] getSum(List<Integer> list) {
        int[] res = new int[list.size() + 1];
        for (int i = 0; i < list.size(); i++) {
            res[i + 1] = res[i] + list.get(i);
        }
        return res;
    }
}

题三 LCP 41. 黑白翻转棋

描述

在 n*m 大小的棋盘中，有黑白两种棋子，黑棋记作字母 "X", 白棋记作字母 "O"，空余位置记作 "."。当落下的棋子与其他相同颜色的棋子在行、列或对角线完全包围（中间不存在空白位置）另一种颜色的棋子，则可以翻转这些棋子的颜色。

「力扣挑战赛」黑白翻转棋项目中，将提供给选手一个未形成可翻转棋子的棋盘残局，其状态记作 chessboard。若下一步可放置一枚黑棋，请问选手最多能翻转多少枚白棋。

注意：

若翻转白棋成黑棋后，棋盘上仍存在可以翻转的白棋，将可以 继续 翻转白棋 输入数据保证初始棋盘状态无可以翻转的棋子且存在空余位置 示例 1：

输入：chessboard = ["....X.","....X.","XOOO..","......","......"]

输出：3

解释： 可以选择下在 [2,4] 处，能够翻转白方三枚棋子。

示例 2：

输入：chessboard = [".X.",".O.","XO."]

输出：2

解释： 可以选择下在 [2,2] 处，能够翻转白方两枚棋子。

示例 3：

输入：chessboard = [".......",".......",".......","X......",".O.....","..O....","....OOX"]

输出：4

解释： 可以选择下在 [6,3] 处，能够翻转白方四枚棋子。

提示：

1 <= chessboard.length, chessboard[i].length <= 8 chessboard[i] 仅包含 "."、"O" 和 "X"

思路

模拟，遍历所有情况。

一些细节在注释里

代码

/**
 * @author mikusugar
 */
public class N3 {

    public int flipChess(String[] chessboard) {

        int[][] g = new int[chessboard.length][chessboard[0].length()];
        for (int i = 0; i < chessboard.length; i++) {
            for (int j = 0; j < chessboard[i].length(); j++) {
                if (chessboard[i].charAt(j) == 'X') g[i][j] = 1;
                else if (chessboard[i].charAt(j) == '.') g[i][j] = -1;
            }
        }
        //存储当前白子可以从哪些方向来
        int[][] tag = new int[chessboard.length][chessboard[0].length()];

        for (int i = 0; i < g.length; i++) {
            for (int j = 0; j < g[i].length; j++) {
                if (g[i][j] == 1) {
                    for (int k = 1; k <= 8; k++) {
                        int ii = i + NEXTS[k - 1][0];
                        int jj = j + NEXTS[k - 1][1];
                        if (isOk(g, ii, jj)) continue;
                        dfs1(ii, jj, k, tag, g);
                    }
                }
            }
        }
        int res = 0;

        //按之前存储的方向反着回去，看可以变多少个颜色
        for (int i = 0; i < g.length; i++) {
            for (int j = 0; j < g[0].length; j++) {
                if (g[i][j] != -1) continue;
                res = Math.max(res, slove(i, j, g, tag));
            }
        }

        return res;


    }

    //检查是否越界
    private boolean isOk(int[][] g, int ii, int jj) {
        return ii < 0 || jj < 0 || ii >= g.length || jj >= g[0].length || g[ii][jj] != 0;
    }

    private int slove(int i, int j, int[][] g, int[][] tag) {
        final boolean[][] visit = new boolean[g.length][g[0].length];
        return next(i, j, g, tag, 0, visit);
    }

    private int next(int i, int j, int[][] g, int[][] tag, int res, boolean[][] visit) {
        for (int k = 1; k <= 8; k++) {
            int ii = i + NEXTS[k - 1][0];
            int jj = j + NEXTS[k - 1][1];
            if (isOk(g, ii, jj)) continue;
            res += dfs2(ii, jj, k, tag, g, visit);
        }
        return res;
    }

    private int dfs2(int i, int j, int kk, int[][] tag, int[][] g, boolean[][] visit) {
        if ((tag[i][j] & (1 << kk)) == 0 || visit[i][j]) return 0;
        visit[i][j] = true;
        return next(i, j, g, tag, 1, visit);
    }

    private void dfs1(int i, int j, int k, int[][] tag, int[][] g) {
        tag[i][j] |= 1 << BOOK[k - 1];
        int ii = i + NEXTS[k - 1][0];
        int jj = j + NEXTS[k - 1][1];
        if (isOk(g, ii, jj)) return;
        dfs1(ii, jj, k, tag, g);
    }


    //                                      1        2         3       4       5        6       7      8
    private final static int[][] NEXTS = {{0, -1}, {-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}};
    //对应的反方向
    private final static int[] BOOK = {5, 6, 7, 8, 1, 2, 3, 4};
}

题四 LCP 42. 玩具套圈

描述

力扣挑战赛」场地外，小力组织了一个套玩具的游戏。所有的玩具摆在平地上，toys[i] 以 [xi,yi,ri] 的形式记录了第 i 个玩具的坐标 (xi,yi) 和半径 ri。小扣试玩了一下，他扔了若干个半径均为 r 的圈，circles[j] 记录了第 j 个圈的坐标 (xj,yj)。套圈的规则如下：

若一个玩具被某个圈完整覆盖了（即玩具的任意部分均在圈内或者圈上），则该玩具被套中。 若一个玩具被多个圈同时套中，最终仅计算为套中一个玩具 请帮助小扣计算，他成功套中了多少玩具。

注意：

输入数据保证任意两个玩具的圆心不会重合，但玩具之间可能存在重叠。 示例 1：

输入：toys = [[3,3,1],[3,2,1]], circles = [[4,3]], r = 2

输出：1

解释： 如图所示，仅套中一个玩具

eSI86B

示例 2：

输入：toys = [[1,3,2],[4,3,1],[7,1,2]], circles = [[1,0],[3,3]], r = 4

输出：2

解释： 如图所示，套中两个玩具

xvddOK

提示：

1 <= toys.length <= 10^4 0 <= toys[i][0], toys[i][1] <= 10^9 1 <= circles.length <= 10^4 0 <= circles[i][0], circles[i][1] <= 10^9 1 <= toys[i][2], r <= 10

思路

  • Map<Integer, TreeSet<Integer>> map 存储所有圆，key是X,value是Y的集合
  • 对于每一个玩具，遍历从toy[0]-r到toy[0]+r的x。
  • 通过二分找到最近的两个y，用了TreeSet后直接通过floor和ceiling方法获取即可。

代码

/**
 * @author mikusugar
 */
public class N4 {
    public int circleGame(int[][] toys, int[][] circles, int r) {

        Map<Integer, TreeSet<Integer>> map = new HashMap<>();
        for (int[] c : circles) {
            if (!map.containsKey(c[0])) map.put(c[0], new TreeSet<>());
            map.get(c[0]).add(c[1]);
        }

        int res = 0;
        for (int[] toy : toys) {
            if (r < toy[2]) continue;
            for (int x = toy[0] - r; x <= toy[0] + r; x++) {
                if (!map.containsKey(x)) continue;
                final TreeSet<Integer> treeY = map.get(x);
                final Integer floorY = treeY.floor(toy[1]);
                if (floorY != null) {
                    final long dist = getDist(toy, x, floorY);
                    if (check(dist, r, toy[2])) {
                        res++;
                        break;
                    }
                }
                final Integer ceilingY = treeY.ceiling(toy[1]);
                if (ceilingY != null) {
                    final long dist = getDist(toy, x, ceilingY);
                    if (check(dist, r, toy[2])) {
                        res++;
                        break;
                    }
                }
            }

        }
        return res;
    }

    private boolean check(long d, int r1, int r2) {
        return d <= (long) (r1 - r2) * (r1 - r2);
    }

    private long getDist(int[] toy, int x, int y) {
        return (long) (toy[0] - x) * (toy[0] - x) + (long) (toy[1] - y) * (toy[1] - y);
    }
}

题五 LCP 43. 十字路口的交通

描述

前往「力扣挑战赛」场馆的道路上，有一个拥堵的十字路口，该十字路口由两条双向两车道的路交叉构成。由于信号灯故障，交警需要手动指挥拥堵车辆。假定路口没有新的来车且一辆车从一个车道驶入另一个车道所需的时间恰好为一秒钟，长度为 4 的一维字符串数组 directions 中按照 东、南、西、北 顺序记录了四个方向从最靠近路口到最远离路口的车辆计划开往的方向。其中：

"E" 表示向东行驶； "S" 表示向南行驶； "W" 表示向西行驶； "N" 表示向北行驶。 交警每秒钟只能指挥各个车道距离路口最近的一辆车，且每次指挥需要满足如下规则：

同一秒钟内，一个方向的车道只允许驶出一辆车； 同一秒钟内，一个方向的车道只允许驶入一辆车； 同一秒钟内，车辆的行驶路线不可相交。 请返回最少需要几秒钟，该十字路口等候的车辆才能全部走完。

各个车道驶出的车辆可能的行驶路线如图所示：

9WZ8Fv

注意：

测试数据保证不会出现掉头行驶指令，即某一方向的行驶车辆计划开往的方向不会是当前车辆所在的车道的方向; 表示堵塞车辆行驶方向的字符串仅用大写字母 "E"，"N"，"W"，"S" 表示。 示例 1：

输入：directions = ["W","N","ES","W"]

输出：2

解释： 第 1 秒：东西方向排在最前的车先行，剩余车辆状态 ["","N","S","W"]； 第 2 秒：南、西、北方向的车行驶，路口无等待车辆； 因此最少需要 2 秒，返回 2。

示例 2：

输入：directions = ["NS","WE","SE","EW"]

输出：3

解释： 第 1 秒：四个方向排在最前的车均可驶出； 第 2 秒：东南方向的车驶出，剩余车辆状态 ["","","E","W"]； 第 3 秒：西北方向的车驶出。

思路

代码