Leetcode - 周赛414

ops/2025/1/12 5:03:54/

目录

一,3280. 将日期转换为二进制表示

二,3281. 范围内整数的最大得分

三,3282. 到达数组末尾的最大得分

四,3283. 吃掉所有兵需要的最多移动次数


一,3280. 将日期转换为二进制表示

本题就是简单的字符串和整数之间的转换,可以直接调用库函数解决,代码如下:

class Solution {public String convertDateToBinary(String date) {String[] t = date.split("-");int i = 0;for(String x : t){t[i++] = Integer.toBinaryString(Integer.parseInt(x));}return String.join("-", t);}
}

二,3281. 范围内整数的最大得分

本题求数组两两之间最小的绝对差,那么最小值一定会出现在排序后相邻的两数之间,所以我们可以先将数组排序。又因为题目中的数据范围导致我们无法使用O(n^2)的做法,这时就需要至少O(nlogn)的做法,再结合排序和求最大值,自然而然就能想到二分,再分析一下是否具有单调性,答案越小,它越能使满足题目要求,具有单调性,所以该题的做法就是二分答案。

知道二分后,最难的一步就是如何判断二分的答案 k 是否满足条件,要想使得每个start[i]的范围都在[start[i],start[i] + d]之间,那么对于每个值都需要尽可能的小(这样后一个值才更可能处于范围内),所以我们的第一个值一定选择start[0],如果 x1 = start[0] + k 超过了 start[1] + d,那么 r 缩小;如果 x1 <= start[1] + d,此时还需要保证 x1 >= start[1],也就是 x1 = max(start[i],x0 + k),对于所有的 i 都满足 xi <= start[i] + d,那么 l 增大。

代码如下:

class Solution {public int maxPossibleScore(int[] start, int d) {int n = start.length;Arrays.sort(start);long l = 0, r = (start[n-1] - start[0] + d)/(n-1);//最大是均值while(l <= r){long mid = (l + r) / 2;if(check(mid, start, d)){l = mid + 1;}else{r = mid - 1;}}return (int)l-1;}boolean check(long k, int[] start, int d){int n = start.length;long now = start[0];for(int i=1; i<n; i++){now = Math.max(now + k, start[i]);if(now > start[i] + d) return false;}return true;}
}

三,3282. 到达数组末尾的最大得分

本题看到后的第一个想法就是dfs选或不选,记录前一个选择的下标 j,看是否选择nums[i]。但是对于本题来说,dfs的做法的时间复杂度是O(n^2),它一定会超时,所以需要其他做法。

"dp的尽头是贪心",所以我们可以试着使用贪心的思路去做,下面画个图理解一下:

我们将数组转换成矩形,那么计算最大总得分就变成了计算矩形的最大面积,那么要想面积大,那么对于每个下标 i 来说,当前能得到的面积一定是max(nums[0:i])。注意:题目中的终点是n-1!!

代码如下:

class Solution {public long findMaximumScore(List<Integer> nums) {int n = nums.size();long ans = 0, mx = nums.get(0);for(int i=1; i<n; i++){ans += mx;mx = Math.max(mx, nums.get(i));}return ans;}
}

四,3283. 吃掉所有兵需要的最多移动次数

本题是一道综合题,我们需要先通过 bfs 计算出(kx,ky) 与 (xi,yi) 任意两点之间的距离(指🐎从a -> b最小的移动距离),预处理之后,问题就变成了从 0 开始,将所有点联通所需的最大移动次数。

假设有 n 个兵,考虑下面两种情况:

  • Alice 吃 1 号兵,Bob 吃 2 号兵,Alice 吃 3 号兵,轮到 Bob 操作
  • Bob 吃 1 号兵,Alice 吃 2 号兵,Alice 吃 3 号兵,轮到 Bob 操作

可以发现上述两种做法都是 Alice 吃 3 号兵,轮到 Bob 操作,具有重复子问题,可以使用dfs来做。根据上述情况,我们需要两个参数:

  • i:表示前一个被吃掉的兵
  • mask:表示所有已经被吃掉的兵的集合

还有一点需要注意:Alice 和 Bob 所进行的操作不相同,所以需要分别讨论:

  • 当 mask 中 1 的个数为奇数时,说明轮到 Alice 操作,假设当前选 j(不在mask集合中),dfs(i,mask) = max(dfs(j,maskUk) + dis[i][j])
  • 当 mask 中 1 的个数为偶数时,说明轮到 Bob 操作,假设当前选 j(不在mask集合中),dfs(i,mask) = min(dfs(j,maskUk) + dis[i][j])

代码如下:

class Solution {int[][] dirct = new int[][]{{1,2},{-1,-2},{-1,2},{1,-2},{2,1},{-2,-1},{-2,1},{2,-1}};public int maxMoves(int kx, int ky, int[][] positions) {int n = positions.length;//(kx,ky)->(i,j)的最短距离//将(kx, ky) 和 (xi, yi) 依次当成 0 1 2 3 ..... nint[][] dis = new int[n+1][n+1];int[][] f = bfs(kx, ky);for(int i=0; i<n; i++){dis[0][i+1] = dis[i+1][0] = f[positions[i][0]][positions[i][1]];}for(int i=0; i<n; i++){f = bfs(positions[i][0], positions[i][1]);for(int j=i+1; j<n; j++)dis[i+1][j+1] = dis[j+1][i+1] = f[positions[j][0]][positions[j][1]];}//点到点的最短距离//从0开始互相联通的最多移动次数memo = new int[n+1][1<<(n+1)];for(int i=0; i<=n; i++)Arrays.fill(memo[i], -1);return dfs(0, 1, dis);}int[][] memo;int dfs(int i, int mask, int[][] dis){int cnt = Integer.bitCount(mask);if(cnt == dis.length) return 0;if(memo[i][mask] != -1) return memo[i][mask];int res = cnt%2==1?Integer.MIN_VALUE:Integer.MAX_VALUE;for(int j=1; j<dis.length; j++){if((mask>>j&1)==1) continue;if(cnt%2 == 1) res = Math.max(res, dfs(j, mask|1<<j, dis) + dis[i][j]);//Alice要求最大路径if(cnt%2 == 0) res = Math.min(res, dfs(j, mask|1<<j, dis) + dis[i][j]);//Bob要求最短路劲}return memo[i][mask] = res;}int[][] bfs(int kx, int ky){//计算从 (kx, ky) -> (x, y) 的最小移动次数int[][] f = new int[50][50];Queue<int[]> que = new LinkedList<>();que.add(new int[]{kx, ky});while(!que.isEmpty()){int size = que.size();while(size-- > 0){int[] t = que.poll();for(int[] d : dirct){int x = t[0] + d[0], y = t[1] + d[1];if(x>=0 && x<50 && y>=0 && y<50 && f[x][y]==0){f[x][y] = f[t[0]][t[1]] + 1;que.add(new int[]{x, y});}}}}return f;}
}


http://www.ppmy.cn/ops/108860.html

相关文章

分布式技术概览

文章目录 分布式技术1. 分布式数据库&#xff08;Distributed Databases&#xff09;2. 分布式文件系统&#xff08;Distributed File Systems&#xff09;3. 分布式哈希表&#xff08;Distributed Hash Tables, DHTs&#xff09;4. 分布式缓存&#xff08;Distributed Caching…

大数据-120 - Flink Window 窗口机制-滑动时间窗口、会话窗口-基于时间驱动基于事件驱动

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; 目前已经更新到了&#xff1a; Hadoop&#xff08;已更完&#xff09;HDFS&#xff08;已更完&#xff09;MapReduce&#xff08;已更完&am…

linux————根据端口查找运行目录的三种方法

先查询端口找到进程 netstat -anlpt | grep 16443 | grep -v grep tcp 0 0 0.0.0.0:16443 0.0.0.0:* LISTEN 3710563/nginx: mast tcp 0 0 192.168.110.253:16443 192.168.110.22:64430 ESTABLISHED 3710580/n…

Ansible Tower与AWX:构建可视化的运维自动化解决方案

Ansible Tower与AWX&#xff1a;构建可视化的运维自动化解决方案 引言 随着企业数字化转型的深入&#xff0c;运维自动化逐渐成为IT管理的重要组成部分。Ansible作为一种简单、灵活且功能强大的自动化工具&#xff0c;广泛应用于配置管理、应用部署和任务自动化中。然而&…

EmguCV学习笔记 VB.Net 10.1 人脸检测 CascadeClassifier类

版权声明&#xff1a;本文为博主原创文章&#xff0c;转载请在显著位置标明本文出处以及作者网名&#xff0c;未经作者允许不得用于商业目的。 EmguCV是一个基于OpenCV的开源免费的跨平台计算机视觉库,它向C#和VB.NET开发者提供了OpenCV库的大部分功能。 教程VB.net版本请访问…

http网络请求与下载进度

Http_request 目录 一、XMLHttpRequest 在使用 Fetch API 进行网络请求时&#xff0c;原生的 Fetch API 并不直接支持获取下载进度的功能&#xff0c;因为 Fetch API 主要是基于 Promise 的&#xff0c;它主要关注于请求的成功或失败&#xff0c;以及响应数据的处理&#xff…

备份还原 本地所有的Docker 镜像并且在另一台机器上还原

备份命令 并且显示进度 backup_docker_images.sh sudo yum install jq chmod x backup_docker_images.shsudo ./backup_docker_images.sh#!/bin/bash# 指定备份目录 backup_dir"/app/dockerImageBackup/Images"# 创建备份目录&#xff0c;如果不存在的话 mkdir -p …

MIT6.824 课程-GFS

GFS 原文&#xff1a;https://zhuanlan.zhihu.com/p/113161014 搬运用于参考学习 概述 存储&#xff08;Storage&#xff09;是一个非常关键的抽象&#xff0c;用途广泛。 GFS 论文还提到了很多关于容错、备份和一致性的问题。 GFS 本身是 Google 内部一个很成功的实用系统&…