2525. 根據規(guī)則將箱子分類 - 力扣（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";
}
}
}
?題目來源：【模板】并查集 - 洛谷
就是將要合并的數做成一個集合，然后再查找；
其實我覺得并查集好像最關鍵的就是找根節(jié)點，只要跟根節(jié)點扯上關系就能證明屬于一個集合；
所以首先我先做了一個查找根節(jié)點的函數
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;
}?首先我會讓所有數都指向自己，也就是我先都把他們的節(jié)點設為-1（因為題目中有說集合中的元素都是大于0的，就不用擔心出現漏洞；然后就是用循環(huán)一步步往上找，知道找到根節(jié)點，然后返回根節(jié)點的值；
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 ;
}然后我又做了一個合并的函數，就是把有關系的集合合并起來，也是利用的根節(jié)點，先找到我要合并的集合的根節(jié)點，然后合并；
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;
}然后在主函數中，將數據都輸入，特別是將父節(jié)點數組全部初始化為-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");
else
printf("N\n");
}
}
return 0;
}然后就是，判斷是做集合還是找集合，如果是1就是做集合，如果是2就是找集合，然后按條件輸出Y或者N；
?（最后交上去出來的結果也不是很好，發(fā)現時間有點超限，應該是數據類型不對，或者說我要用路徑壓縮）
改錯：
我知道為什么時間超限了，因為我沒有按照把小的樹往大的樹上面湊，而是隨便湊，那么這樣就會導致樹的深度變大，也就是說時間會變長，那么我只需要在我將集合合并的函數上加上一組判斷的語句；
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[]數組就是樹的高度，首先判斷樹的高度，然后將小的樹往大的樹上面扣，這樣找的時候就能有效節(jié)省時間復雜度；
?例題一（鏈接）
# 【模板】最長公共子序列
## 題目描述
給出 $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) //二分查找（就是更加方便查找，節(jié)省時間）
{
mid=(xx+r)/2;
if(map[p2[i]]<dp[mid])
r=mid;
else
xx=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 ];文章來源：http://www.zghlxwxcb.cn/news/detail-721989.html
當不滿足這個條件的時候，就考慮此時該進行什么操作，arr[ i ][ j - 1 ]表示的是增加一個字符的操作， arr[ i - 1 ][ j ]表示的是刪除一個字符的操作，arr[ i - 1 ][ j - 1 ]表示替換；文章來源地址http://www.zghlxwxcb.cn/news/detail-721989.html
代碼
#include<stdio.h>
#include<string.h>
#define num 3010
int 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];
}
else
arr[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.根據規(guī)則將箱子分類/并查集/動態(tài)規(guī)劃的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
