2525.根据规则将箱子分类/并查集/动态规划

2023-10-22 22:52
文章标签 动态 规划 分类 规则 箱子 查集 2525

本文主要是介绍2525.根据规则将箱子分类/并查集/动态规划，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2525. 根据规则将箱子分类 - 力扣（LeetCode）

给你四个整数 length ，width ，height 和 mass ，分别表示一个箱子的三个维度和质量，请你返回一个表示箱子 类别 的字符串。

  • 如果满足以下条件，那么箱子是 "Bulky" 的：
    • 箱子 至少有一个 维度大于等于 104 。
    • 或者箱子的 体积 大于等于 109 。
  • 如果箱子的质量大于等于 100 ，那么箱子是 "Heavy" 的。
  • 如果箱子同时是 "Bulky" 和 "Heavy" ，那么返回类别为 "Both" 。
  • 如果箱子既不是 "Bulky" ，也不是 "Heavy" ，那么返回类别为 "Neither" 。
  • 如果箱子是 "Bulky" 但不是 "Heavy" ，那么返回类别为 "Bulky" 。
  • 如果箱子是 "Heavy" 但不是 "Bulky" ，那么返回类别为 "Heavy" 。

注意，箱子的体积等于箱子的长度、宽度和高度的乘积。

示例 1：

输入：length = 1000, width = 35, height = 700, mass = 300
输出："Heavy"
解释：
箱子没有任何维度大于等于 104 。
体积为 24500000 <= 109 。所以不能归类为 "Bulky" 。
但是质量 >= 100 ，所以箱子是 "Heavy" 的。
由于箱子不是 "Bulky" 但是是 "Heavy" ，所以我们返回 "Heavy" 。

示例 2：

输入：length = 200, width = 50, height = 800, mass = 50
输出："Neither"
解释：
箱子没有任何维度大于等于 104 。
体积为 8 * 106 <= 109 。所以不能归类为 "Bulky" 。
质量小于 100 ，所以不能归类为 "Heavy" 。
由于不属于上述两者任何一类，所以我们返回 "Neither" 。

提示：

  • 1 <= length, width, height <= 105
  • 1 <= mass <= 103

思路

用数学公式，然后进行判断，返回值

完整代码

class Solution {public String categorizeBox(int length, int width, int height, int mass) {long maxd = Math.max(length, Math.max(width, height)), vol = 1L * length * width * height;boolean isBulky = maxd >= 10000 || vol >= 1000000000, isHeavy = mass >= 100;if (isBulky && isHeavy) {return "Both";} else if (isBulky) {return "Bulky";} else if (isHeavy) {return "Heavy";} else {return "Neither";}}
}

 题目来源：【模板】并查集 - 洛谷

就是将要合并的数做成一个集合，然后再查找；

其实我觉得并查集好像最关键的就是找根节点，只要跟根节点扯上关系就能证明属于一个集合；

所以首先我先做了一个查找根节点的函数

public static int find(int x,int p[])
{int x_root=x;while(p[x_root]!=-1)x_root = p[x_root];return x_root;}

 首先我会让所有数都指向自己，也就是我先都把他们的节点设为-1（因为题目中有说集合中的元素都是大于0的，就不用担心出现漏洞；然后就是用循环一步步往上找，知道找到根节点，然后返回根节点的值；

public static void op(int x,int y,int p[])
{int x_root = x;int y_root = y;int find(int x,int p[]);x_root = find(x,p);y_root = find(y,p);if(x_root != y_root)p[x_root] = y_root ;
}

然后我又做了一个合并的函数，就是把有关系的集合合并起来，也是利用的根节点，先找到我要合并的集合的根节点，然后合并；

class Text(){public static void main(Sting[]args)
{int m,n;int x,y,z,v;int find(int x,int p[]);scanf("%d %d",&m,&n);int p[m+1];for(int i=1;i<=m;i++)p[i]=-1;
}

然后在主函数中，将数据都输入，特别是将父节点数组全部初始化为-1。

  for(int i=0;i<n;i++){scanf("%d %d %d",&x,&y,&z);if(x==1)op(y,z,p);if(x==2){int y_root,z_root;y_root = find(y,p);z_root = find(z,p);if(y_root == z_root)printf("Y\n");elseprintf("N\n");}}return 0;
}

然后就是，判断是做集合还是找集合，如果是1就是做集合，如果是2就是找集合，然后按条件输出Y或者N；

 （最后交上去出来的结果也不是很好，发现时间有点超限，应该是数据类型不对，或者说我要用路径压缩）

改错：

我知道为什么时间超限了，因为我没有按照把小的树往大的树上面凑，而是随便凑，那么这样就会导致树的深度变大，也就是说时间会变长，那么我只需要在我将集合合并的函数上加上一组判断的语句；

public static void op(int x,int y,int p[],int rank[])
{int x_root = x;int y_root = y;int find(int x,int p[]);x_root = find(x,p);y_root = find(y,p);if(x_root != y_root){if(rank[x_root] > rank[y_root])p[y_root]=x_root;else if(rank[x_root] < rank[y_root])p[x_root] = y_root;else{p[x_root] = y_root;rank[y_root]++;}}
}

rank[]数组就是树的高度，首先判断树的高度，然后将小的树往大的树上面扣，这样找的时候就能有效节省时间复杂度；

 例题一（链接）

# 【模板】最长公共子序列

## 题目描述

给出 $1,2,\ldots,n$ 的两个排列 $P_1$ 和 $P_2$ ，求它们的最长公共子序列。

## 输入格式

第一行是一个数 $n$。

接下来两行，每行为 $n$ 个数，为自然数 $1,2,\ldots,n$ 的一个排列。

## 输出格式

一个数，即最长公共子序列的长度。

## 样例 #1

### 样例输入 #1

```
5 
3 2 1 4 5
1 2 3 4 5
```

### 样例输出 #1

```
3
```

## 提示

- 对于 $50\%$ 的数据， $n \le 10^3$；
- 对于 $100\%$ 的数据， $n \le 10^5$。

思路

本来我用的是滚动数组来做，但是还是时间超限了，我猜测应该不能一组数据一组数据的更新，然后看题目中说是由相同的数字组成，那么就是说只是顺序不同，但元素是相同的，其实这个题就是LIS（参考文章），以一个串为模板串，然后判断另一个串在这个串里面的排列顺序；

代码

class Text{int inf = 100010l;public static int min(int x,int y)
{return x<y?x:y;
}public static void main(String[]args)
{Scanner sc = new Scanner(System.in);int n = sc.nextInt();int []p1 = new int[num];int []p2 = new int[num];int []dp = new int[num];int []map = new int[map];     //dp表示的是合乎题意的子串，map下标表示的是数值，而其对应的数字是该数值的位置；for(int i=1; i<=n; i++){p1[i] = sc.nextInt();dp[i]=inf;            //初始化map[p1[i]]=i;         //明确一个串里面数字的顺序，以便之后另一个串的数字在这个串里面找位置}for(int i=1; i<=n; i++)scanf("%d",&p2[i]);int len=0;               //找到的合乎题目意思的子串长度dp[0]=0;                 for(int i=1; i<=n; i++){int xx=0,r=len,mid;  if(map[p2[i]]>dp[len])  //如果说p2第i个数字在p1中的位置大于已有的子串的最后一个数字dp[++len]=map[p2[i]];  //那么就把这个数字加入子串中else{while(xx<r)   //二分查找（就是更加方便查找，节省时间）{mid=(xx+r)/2;if(map[p2[i]]<dp[mid])r=mid;elsexx=mid+1;}dp[xx]=min(map[p2[i]],dp[xx]);}}printf("%d",len);  //len就是子串的长度}

例题二（编辑距离 - 洛谷）

# 编辑距离

## 题目描述

设 $A$ 和 $B$ 是两个字符串。我们要用最少的字符操作次数，将字符串 $A$ 转换为字符串 $B$。这里所说的字符操作共有三种：

1. 删除一个字符；
2. 插入一个字符；
3. 将一个字符改为另一个字符。

$A, B$ 均只包含小写字母。

## 输入格式

第一行为字符串 $A$；第二行为字符串 $B$；字符串 $A, B$ 的长度均小于 $2000$。

## 输出格式

只有一个正整数，为最少字符操作次数。

## 样例 #1

### 样例输入 #1

```
sfdqxbw
gfdgw
```

### 样例输出 #1

```
4
```

## 提示

对于 $100 \%$ 的数据，$1 \le |A|, |B| \le 2000$。

思路

首先知道有俩个字符串，那么可以建一个二维数组arr[ i ][ j ]，分别用于俩个字符串的遍历；

然后根据题目可以知道，对于每一个字符，具有四种操作，删除，插入，替换，不变；那么就可以判断在不同情况下，该怎么更新arr里面的值；

当新遍历的俩个字符相等时，就不要增加步骤，那么此时这个点的步骤就和没新遍历的那俩个字符时相等，即 ：

arr[ i ][ j ] = arr[ i - 1 ][ j - 1 ];

当不满足这个条件的时候，就考虑此时该进行什么操作，arr[ i ][ j - 1 ]表示的是增加一个字符的操作， arr[ i - 1 ][ j ]表示的是删除一个字符的操作，arr[ i - 1 ][ j - 1 ]表示替换；

代码

#include<stdio.h>
#include<string.h>
#define num 3010int min(int x,int y)
{return x<y?x:y;
}int main()
{char A[num],B[num];int arr[num][num];int a,b;scanf("%s%s",A,B);a=strlen(A);b=strlen(B);int c=a>b?a:b;for(int i=1;i<=c;i++){arr[i][0]=i;arr[0][i]=i;}for(int i=1; i<=a; i++)for(int j=1; j<=b; j++){if(A[i-1]==B[j-1]){arr[i][j]=arr[i-1][j-1];}elsearr[i][j]=min(min(arr[i-1][j],arr[i][j-1]),arr[i-1][j-1])+1;}printf("%d",arr[a][b]);return 0;
}

这篇关于2525.根据规则将箱子分类/并查集/动态规划的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/264103。

相关文章

基于人工智能的图像分类系统

基于人工智能的图像分类系统

目录 引言项目背景环境准备 硬件要求软件安装与配置系统设计 系统架构关键技术代码示例 数据预处理模型训练模型预测应用场景结论 1. 引言 图像分类是计算机视觉中的一个重要任务，目标是自动识别图像中的对象类别。通过卷积神经网络（CNN）等深度学习技术，我们可以构建高效的图像分类系统，广泛应用于自动驾驶、医疗影像诊断、监控分析等领域。本文将介绍如何构建一个基于人工智能的图像分类系统，包括环境
阅读更多...
认识、理解、分类——acm之搜索

认识、理解、分类——acm之搜索

普通搜索方法有两种：1、广度优先搜索；2、深度优先搜索； 更多搜索方法： 3、双向广度优先搜索； 4、启发式搜索（包括A*算法等）； 搜索通常会用到的知识点：状态压缩（位压缩，利用hash思想压缩）。
阅读更多...
第10章 中断和动态时钟显示

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始，按照书籍的划分，第10章开始就进入保护模式（Protected Mode）部分了，感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断（Interrupt）的设计，中断的几种方式：外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用： 为了更好的利用处理器的性能。协同快速和慢速设备一起工作
阅读更多...
动态规划---打家劫舍

动态规划---打家劫舍

题目： 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 思路： 动态规划五部曲： 1.确定dp数组及含义 dp数组是一维数组，dp[i]代表
阅读更多...
软考系统规划与管理师考试证书含金量高吗？

软考系统规划与管理师考试证书含金量高吗？

2024年软考系统规划与管理师考试报名时间节点： 报名时间：2024年上半年软考将于3月中旬陆续开始报名 考试时间：上半年5月25日到28日，下半年11月9日到12日 分数线：所有科目成绩均须达到45分以上（包括45分）方可通过考试 成绩查询：可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间：预计在11月左右 证书领取时间：一般在考试成绩公布后3~4个月，各地领取时间有所不同
阅读更多...
poj 1182 并查集 食物链类

poj 1182 并查集 食物链类

题意： 有n只动物，分别编号1....n。所有动物都属于A，B，C中的一种，已知A吃B，B吃C，C吃A。 按顺序给出下面两种共K条信息： 1. x 和 y 属于同一类。 2. x 吃 y 。 然而这些信息可能会出错，有可能有的信息和之前给出的信息矛盾，也有的信息可能给出的 x 和 y 不在n的范围内。 求k条信息中有多少条是不正确的。 解析： 对于每只动物，创建3个元素 i
阅读更多...
poj 2976 分数规划二分贪心（部分对总体的贡献度） poj 3111

poj 2976 分数规划二分贪心（部分对总体的贡献度） poj 3111

poj 2976： 题意： 在n场考试中，每场考试共有b题，答对的题目有a题。 允许去掉k场考试，求能达到的最高正确率是多少。 解析： 假设已知准确率为x，则每场考试对于准确率的贡献值为： a - b * x，将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码： #include <iostream>#include <cstdio>#incl
阅读更多...
代码随想录冲冲冲 Day39 动态规划Part7

代码随想录冲冲冲 Day39 动态规划Part7

198. 打家劫舍 dp数组的意义是在第i位的时候偷的最大钱数是多少 如果nums的size为0 总价值当然就是0 如果nums的size为1 总价值是nums[0] 遍历顺序就是从小到大遍历 之后是递推公式 对于dp[i]的最大价值来说有两种可能 1.偷第i个 那么最大价值就是dp[i-2]+nums[i] 2.不偷第i个 那么价值就是dp[i-1] 之后取这两个的最大值就是d
阅读更多...
POJ1988带权并查集

POJ1988带权并查集

M u v 将u所在的堆移动到v所在的堆的上面 C u 求u的下面有多少块 带权并查集 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;i
阅读更多...
POJ1703带权并查集

POJ1703带权并查集

D： u v  u与v在不同的集合 A： u v  查询u与v的关系 1)压缩路径过程        fu->root   0  1  u-fu 0                 0  1   1                 1  0 2)合并过程 fu->fv      u->fu   0 1   v->fv 0            1 0 1            0
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2