2023 年力扣杯春季编程大赛（个人赛）题解 - 刷题题解

2023 年力扣杯春季编程大赛题解

题目集合：

2 分 - 补给马车
4 分 - 探险营地
6 分 - 最强祝福力场
8 分 - 传送卷轴
10 分 - 魔法棋盘

# T1. 补给马车

# 思路

模拟

# 代码

	class Solution {
	public int[] supplyWagon(int[] supplies) {
	int n = supplies.length;
	int newLen = n / 2;
	for (int i = n; i > newLen; --i) {

	int k = 0;
	int mv = Integer.MAX_VALUE;
	for (int j = 0; j < i - 1; ++j) {
	if (supplies[j] + supplies[j + 1] < mv) {
	mv = supplies[j] + supplies[j + 1];
	k = j;
	}
	}

	supplies[k] += supplies[k + 1];

	for (int j = k + 1; j < i - 1; ++j) {
	supplies[j] = supplies[j + 1];
	}
	}

	int[] ans = new int[newLen];

	System.arraycopy(supplies, 0, ans, 0, newLen);

	return ans;
	}
	}

# T2. 探险营地

# 思路

模拟

# 代码

	class Solution {
	public int adventureCamp(String[] es) {
	Set<String> old = new HashSet<>();

	String[] ss = es[0].split("->");

	for (String s : ss) old.add(s);

	int cnt = 0;
	int idx = -1;
	for (int i = 1; i < es.length; ++i) {
	ss = es[i].split("->");
	int c = 0;
	for (String s : ss) {
	if (s.length() > 0 && !old.contains(s)) {
	old.add(s);
	++c;
	}
	}

	if (c > cnt) {
	cnt = c;
	idx = i;
	}
	}
	return idx;
	}
	}

# T3. 最强祝福力场

# 解题思路

坐标离散化
坐标点整数化
建图进行二维差分（矩阵）
求矩阵的前缀和

具体看代码注释

# 代码

	class Solution {
	public int fieldOfGreatestBlessing(int[][] forceField) {
	// 1. 坐标点离散化
	// 有序集合：唯一 + 有序
	Set<Long> xs = new TreeSet<>();
	Set<Long> ys = new TreeSet<>();

	for (int[] fo : forceField) {
	// x - side / 2：
	// 考虑到可能为小数，故将坐标转成整数：2 * x - side

	// 左上角坐标
	long x = 2L * fo[0] - fo[2];
	long y = 2L * fo[1] - fo[2];
	xs.add(x);
	ys.add(y);

	// 右下角坐标
	x = 2L * fo[0] + fo[2];
	y = 2L * fo[1] + fo[2];
	xs.add(x);
	ys.add(y);
	}
	int xn = xs.size();
	int yn = ys.size();
	long[] xAxis = new long[xn];
	long[] yAxis = new long[yn];
	int k = 0;
	for (long x : xs) xAxis[k++] = x;
	k = 0;
	for (long y : ys) yAxis[k++] = y;

	// 2. 二维差分
	int[][] m = new int[xn][yn];
	for (int[] f : forceField) {
	long lx = 2L * f[0] - f[2];
	long rx = 2L * f[0] + f[2];
	long ty = 2L * f[1] - f[2];
	long by = 2L * f[1] + f[2];
	// 通过二分找到当前坐标的离散化后的下标
	int lxi = Arrays.binarySearch(xAxis, lx);
	int rxi = Arrays.binarySearch(xAxis, rx);
	int tyi = Arrays.binarySearch(yAxis, ty);
	int byi = Arrays.binarySearch(yAxis, by);

	if (lxi >= 0 && tyi >= 0 && rxi >= 0 && byi >= 0) {
	// 左上 +1
	++m[lxi][tyi];
	// 左下 -1
	if (byi + 1 < yn) --m[lxi][byi + 1];
	// 右上 -1
	if (rxi + 1 < xn) --m[rxi + 1][tyi];
	// 右下 +1
	if (byi + 1 < yn && rxi + 1 < xn) ++m[rxi + 1][byi + 1];
	}
	}

	// 二维前缀和计算答案
	int max = 0;
	for (int i = 0; i < xn; ++i) {
	for (int j = 0; j < yn; ++j) {
	if (j > 0) m[i][j] += m[i][j - 1];
	if (i > 0) m[i][j] += m[i - 1][j];
	if (i > 0 && j > 0) m[i][j] -= m[i - 1][j - 1];
	max = Math.max(m[i][j], max);
	}
	}

	return max;
	}
	}

# T4. 传送卷轴

# 解题思路

BFS + 二分枚举

# 代码

	class Solution {
	final int[] dx = new int[] {0, 0, -1, 1};
	final int[] dy = new int[] {1, -1, 0, 0};
	char[][] mat;
	public int challengeOfTheKeeper(String[] maze) {
	/**
	* 1. 找到【初始位置】和【魔法水晶】位置
	* 2. bfs 计算【魔法水晶】位置到每个可达点的最短距离 dis [i][j]
	* 3. 二分答案
	*/
	int n = maze.length;
	mat = new char[n][];
	// 【初始位置】的坐标
	int startX = -1, startY = -1;
	// 【魔法水晶】的位置坐标
	int endX = -1, endY = -1;
	for (int i = 0; i < n; ++i) {
	mat[i] = maze[i].toCharArray();
	if (startX + startY < 0 \|\| endX + endY < 0) {
	for (int j = 0; j < n; ++j) {
	if (mat[i][j] == 'S') {
	startX = j;
	startY = i;
	} else if (mat[i][j] == 'T') {
	endX = j;
	endY = i;
	}
	}
	}
	}

	// 2. 计算【魔法水晶】到各个点的最短距离
	int[][] dis = new int[n][n];
	Queue<int[]> que = new ArrayDeque<>();

	for (int i = 0; i < n; ++i) Arrays.fill(dis[i], Integer.MAX_VALUE);
	que.offer(new int[]{endX, endY});
	dis[endY][endX] = 0;

	while (!que.isEmpty()) {
	for (int i = que.size(); i > 0; --i) {
	int[] cur = que.poll();
	int curX = cur[0];
	int curY = cur[1];
	for (int j = 0; j < dx.length; ++j) {
	int nxtX = curX + dx[j];
	int nxtY = curY + dy[j];
	if (0 <= nxtX && nxtX < n && 0 <= nxtY && nxtY < n
	// 不是墙壁
	&& mat[nxtY][nxtX] != '#'
	// 还未访问过
	&& dis[nxtY][nxtX] == Integer.MAX_VALUE) {
	que.offer(new int[] {nxtX, nxtY});
	dis[nxtY][nxtX] = dis[curY][curX] + 1;
	}
	}
	}
	}

	// 初始位置本身就无法达到【魔法水晶】
	if (dis[startY][startX] == Integer.MAX_VALUE) return -1;

	// 3. 二分枚举答案
	int l = -1, r = n * n + 1;
	int [][] vis = new int[n][n];
	while (l + 1 < r) {
	int step = (l + r) / 2;
	if (dfs(startX, startY, step, vis, dis)) r = step;
	else l = step;
	}

	return r > n * n ? -1 : r;
	}

	// 判断是否能在 maxStep 步数内能否到达【魔法水晶】
	private boolean dfs(int x, int y, int maxStep, int[][] vis, int[][] dis) {
	int n = mat.length;
	if (x < 0 \|\| x >= n \|\| y < 0 \|\| y >= n // 越界
	\|\| mat[y][x] == '#' // 走到墙壁
	\|\| vis[y][x] == maxStep + 1) // 没有走过
	return false;
	// 到达终点
	if (mat[y][x] == 'T') return true;

	vis[y][x] = maxStep + 1;

	// 守护者使用卷轴，如果无法在 maxDis 内到达，则返回 false
	if (mat[y][x] == '.'
	&& (mat[y][n - 1 - x] != '#' && dis[y][n - 1 - x] > maxStep
	\|\| mat[n - 1 - y][x] != '#' && dis[n - 1 - y][x] > maxStep))
	return false;

	for (int i = 0; i < dx.length; ++i) {
	if (dfs(x + dx[i], y + dy[i], maxStep, vis, dis))
	return true;
	}

	return false;
	}
	}

leetcode 题解力扣杯

# T1. 补给马车

# 思路

# 代码

# T2. 探险营地

# 思路

# 代码

# T3. 最强祝福力场

# 解题思路

# 代码

# T4. 传送卷轴

# 解题思路

# 代码

力扣第 342 场周赛题解

每日一题：按身高排序