宜春做网站公司怎么样,app安装官方免费下载,如何建立自己推广网站,php网站开发自学2525. 根据规则将箱子分类 - 力扣#xff08;LeetCode#xff09;
给你四个整数 length #xff0c;width #xff0c;height 和 mass #xff0c;分别表示一个箱子的三个维度和质量#xff0c;请你返回一个表示箱子 类别 的字符串。
如果满足以下条件#xff0c;那么…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 1051 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_rootx;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[m1];for(int i1;im;i)p[i]-1;
}
然后在主函数中将数据都输入特别是将父节点数组全部初始化为-1。 for(int i0;in;i){scanf(%d %d %d,x,y,z);if(x1)op(y,z,p);if(x2){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 xy?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 i1; in; i){p1[i] sc.nextInt();dp[i]inf; //初始化map[p1[i]]i; //明确一个串里面数字的顺序以便之后另一个串的数字在这个串里面找位置}for(int i1; in; i)scanf(%d,p2[i]);int len0; //找到的合乎题目意思的子串长度dp[0]0; for(int i1; in; i){int xx0,rlen,mid; if(map[p2[i]]dp[len]) //如果说p2第i个数字在p1中的位置大于已有的子串的最后一个数字dp[len]map[p2[i]]; //那么就把这个数字加入子串中else{while(xxr) //二分查找就是更加方便查找节省时间{mid(xxr)/2;if(map[p2[i]]dp[mid])rmid;elsexxmid1;}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 ]表示替换
代码
#includestdio.h
#includestring.h
#define num 3010int min(int x,int y)
{return xy?x:y;
}int main()
{char A[num],B[num];int arr[num][num];int a,b;scanf(%s%s,A,B);astrlen(A);bstrlen(B);int cab?a:b;for(int i1;ic;i){arr[i][0]i;arr[0][i]i;}for(int i1; ia; i)for(int j1; jb; 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;
}
