• 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

    思路

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

    完整代码

    1. class Solution {
    2.     public String categorizeBox(int length, int width, int height, int mass) {
    3.         long maxd = Math.max(length, Math.max(width, height)), vol = 1L * length * width * height;
    4.         boolean isBulky = maxd >= 10000 || vol >= 1000000000, isHeavy = mass >= 100;
    5.         if (isBulky && isHeavy) {
    6.              return "Both";
    7.         } else if (isBulky) {
    8.             return "Bulky";
    9.         } else if (isHeavy) {
    10.             return "Heavy";
    11.         } else {
    12.             return "Neither";
    13.         }
    14.     }
    15. }

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

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

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

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

    1.  
    2.  
    3. public static int find(int x,int p[])
    4. {
    5.     int x_root=x;
    6.     while(p[x_root]!=-1)
    7.     x_root = p[x_root];
    8.     return x_root;
    9.  
    10. }

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

    1. public static void op(int x,int y,int p[])
    2. {
    3.     int x_root = x;
    4.     int y_root = y;
    5.     int find(int x,int p[]);
    6.     x_root = find(x,p);
    7.     y_root = find(y,p);
    8.     if(x_root != y_root)
    9.         p[x_root] = y_root ;
    10. }

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

    1. class Text(){
    2.      public static void main(Sting[]args)
    3. {
    4.     int m,n;
    5.     int x,y,z,v;
    6.     int find(int x,int p[]);
    7.     scanf("%d %d",&m,&n);
    8.     int p[m+1];
    9.     for(int i=1;i<=m;i++)
    10.         p[i]=-1;
    11. }

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

    1.   for(int i=0;i
    2.     {
    3.         scanf("%d %d %d",&x,&y,&z);
    4.         if(x==1)
    5.             op(y,z,p);
    6.             if(x==2)
    7.             {
    8.                 int y_root,z_root;
    9.                 y_root = find(y,p);
    10.                 z_root = find(z,p);
    11.                 if(y_root == z_root)
    12.                     printf("Y\n");
    13.                 else
    14.                     printf("N\n");
    15.             }
    16.  
    17.     }
    18.     return 0;
    19. }

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

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

    改错：

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

    1. public static void op(int x,int y,int p[],int rank[])
    2. {
    3.     int x_root = x;
    4.     int y_root = y;
    5.     int find(int x,int p[]);
    6.     x_root = find(x,p);
    7.     y_root = find(y,p);
    8.     if(x_root != y_root)
    9.         {
    10.             if(rank[x_root] > rank[y_root])
    11.                p[y_root]=x_root;
    12.             else if(rank[x_root] < rank[y_root])
    13.                 p[x_root] = y_root;
    14.             else
    15.             {
    16.                 p[x_root] = y_root;
    17.                 rank[y_root]++;
    18.             }
    19.         }
    20. }

    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（参考文章），以一个串为模板串，然后判断另一个串在这个串里面的排列顺序；

    代码

    1. class Text{
    2.  
    3. int inf = 100010l;
    4.  
    5. public static int min(int x,int y)
    6. {
    7.     return x
    8. }
    9.  
    10. public static void main(String[]args)
    11. {
    12.     
    13.     Scanner sc = new Scanner(System.in);
    14.     int n = sc.nextInt();
    15.     int []p1 = new int[num];
    16.     int []p2 = new int[num];
    17.     int []dp = new int[num];
    18.     int []map = new int[map];     //dp表示的是合乎题意的子串，map下标表示的是数值，而其对应的数字是该数值的位置；
    19.     for(int i=1; i<=n; i++)
    20.     {
    21.         p1[i] = sc.nextInt();
    22.         dp[i]=inf;            //初始化
    23.         map[p1[i]]=i;         //明确一个串里面数字的顺序，以便之后另一个串的数字在这个串里面找位置
    24.     }
    25.     for(int i=1; i<=n; i++)
    26.         scanf("%d",&p2[i]);
    27.  
    28.     int len=0;               //找到的合乎题目意思的子串长度
    29.     dp[0]=0;                 
    30.     for(int i=1; i<=n; i++)
    31.     {
    32.         int xx=0,r=len,mid;  
    33.         
    34.         if(map[p2[i]]>dp[len])  //如果说p2第i个数字在p1中的位置大于已有的子串的最后一个数字
    35.  
    36.             dp[++len]=map[p2[i]];  //那么就把这个数字加入子串中
    37.         else
    38.         {
    39.             while(xx//二分查找（就是更加方便查找，节省时间）
    40.             {
    41.                 mid=(xx+r)/2;
    42.                 if(map[p2[i]]
    43.                     r=mid;
    44.                 else
    45.                     xx=mid+1;
    46.             }
    47.             dp[xx]=min(map[p2[i]],dp[xx]);
    48.         }
    49.     }
    50.  
    51.     printf("%d",len);  //len就是子串的长度
    52.   
    53. }

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

    # 编辑距离

    ## 题目描述

    设 $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 ]表示替换；

    代码

    1. #include<stdio.h>
    2. #include<string.h>
    3. #define num 3010
    4.  
    5. int min(int x,int y)
    6. {
    7.     return x<y?x:y;
    8. }
    9.  
    10. int main()
    11. {
    12.     char A[num],B[num];
    13.     int arr[num][num];
    14.     int a,b;
    15.     scanf("%s%s",A,B);
    16.     a=strlen(A);
    17.     b=strlen(B);
    18.     int c=a>b?a:b;
    19.     for(int i=1;i<=c;i++)
    20.     {
    21.         arr[i][0]=i;
    22.         arr[0][i]=i;
    23.     }
    24.     for(int i=1; i<=a; i++)
    25.         for(int j=1; j<=b; j++)
    26.         {
    27.             if(A[i-1]==B[j-1])
    28.             {
    29.                 arr[i][j]=arr[i-1][j-1];
    30.                 
    31.             }
    32.                else
    33.             arr[i][j]=min(min(arr[i-1][j],arr[i][j-1]),arr[i-1][j-1])+1;
    34.         }
    35.     printf("%d",arr[a][b]);
    36.     return 0;
    37. }

  • 相关阅读:
    揭示语言大模型的采样过程
    短视频矩阵系统，抖音矩阵系统，抖音SEO源码。
    RabbitMQ介绍及下载安装详解
    打卡系统有什么用？如何通过日常管理系统提高企业员工的效率？
    记一次生产中使用CompletableFuture遇到的坑
    Transformer，浅析归纳偏置对模型缩放的影响
    交叉熵函数和KL散度函数
    Flutter基础入门-环境搭建并Helloworld
    从李佳琦到背后的商业逻辑再到游戏行业
    网络面试-0x03http有哪些常见的请求头以及作用
  • 原文地址：https://blog.csdn.net/qq_74455082/article/details/133979008