【JAVA】小米集团-2021校招-算法方向在线考试(矩阵相乘+盒子包裹问题)

深碍√TFBOYSˉ_ 2022-12-05 01:38 120阅读 0赞

# 前言 #

楼主参加笔试之前去字节面试了，又是被虐的一次，所以笔试迟到40分钟，而且被字节虐的脑子转不动了，今天笔试很简单，但是我做得不是很理想，希望大家多多说一下自己的思路。祝大家都有心仪的offer。  
![在这里插入图片描述][20200908193908824.png_pic_center]

# 一、矩阵相乘（A0.88，超时了） #

时间限制： 3000MS  
内存限制： 589824KB  
**题目描述：**  
实现矩阵相乘函数void matrix\_multiply(int\* A, int\* B, int\* C, int M, int K, int N)

暂不考虑整型溢出，请尽可能优化运行速度。

参数说明：0 < M,K,N < 1000

C\[M\]\[N\] = A\[M\]\[K\] \* B\[K\]\[N\]

**输入描述**  
输入矩阵A和矩阵B的值:  
M=2, K=3,N=2  
A\[2\]\[3\]=\{ \{1,2,3\},\{1,2,3\}\}  
B\[3\]\[2\]=\{ \{1,1\},\{1,1\},\{1,1\}\}

**输出描述**  
输出矩阵C的值：  
C\[2\]\[2\]=\{ \{6,6\},\{6,6\}\}

**样例输入**  
2 3 2  
1 2 3  
1 2 3  
1 1  
1 1  
1 1

**样例输出**  
6 6  
6 6

## 代码 ##

import java.util.Scanner;
    
    /** * Created by IntelliJ IDEA. * * @Author: * @Email: * @Date: 2020/9/8 * @Time: 18:51 * @Version: 1.0 * @Description: Description */
    public class First { 
        public static void main(String[] args) { 
            Scanner sc = new Scanner(System.in);
            int M = sc.nextInt();
            int K = sc.nextInt();
            int N = sc.nextInt();
            int[][] matrix1 = new int[M][K];
            int[][] matrix2 = new int[K][N];
            for (int i = 0; i < M; i++)
                for (int j = 0; j < K; j++)
                    matrix1[i][j] = sc.nextInt();
            for (int i = 0; i < K; i++)
                for (int j = 0; j < N; j++)
                    matrix2[i][j] = sc.nextInt();
            for (int i = 0; i < M; i++) { 
                for (int k = 0; k < N; k++) { 
                    int temp = 0;
                    for (int j = 0; j < K; j++) { 
                        temp += matrix1[i][j] * matrix2[j][k];
                    }
                    System.out.print(temp + " ");
                }
                System.out.println();
            }
            sc.close();
        }
    }

# 二、盒子包裹问题（A50%，就是考虑最简单的情况，没有考虑 2 2 4 4 5这种（这个输出为2）） #

时间限制： 3000MS  
内存限制： 786432KB

**题目描述：**  
假设，小米商城有卖空盒子，各种大小的正方形空盒子。对于i (1<=i<=n)，ai是正方形盒子的边长。

如果有顾客采购多个空盒子，快递打包的时候可以将它们嵌套打包以节约成本。

如果满足以下三个条件，盒子i可以放到j中：

1，盒子i没有放在另一个盒子里

2，盒子j不包含任何其它盒子

3，ai<aj

现在有顾客采购了n个空盒子。工作人员想知道，如何装箱，能使得包裹数量最少。

**输入描述**  
第一行包含一个整数n(1<=n<=5000) 顾客购买箱子的数量。  
第二行包含了n个整数, a1, a2 … an(1<=ai<=109) , ai是盒子的边长。

**输出描述**  
打印包裹的最小数量。

**样例输入**  
4  
4 2 4 3

**样例输出**  
2

**提示**  
在这个示例中，可以将盒子2放入盒子3中，将盒子4 放入盒子1中。

## 代码： ##

package xiaomi;
    
    import java.util.Arrays;
    import java.util.Scanner;
    
    /** * Created by IntelliJ IDEA. * * @Author: * @Email: * @Date: 2020/9/8 * @Time: 19:15 * @Version: 1.0 * @Description: Description */
    
    
    public class Second2 { 
        public static void main(String[] args) { 
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) { 
                arr[i] = sc.nextInt();
            }
            Arrays.sort(arr);
    // System.out.println(Arrays.toString(arr));
            int count = 1;
            /*int i=0,j=n/2; while (i<n/2&&j<n){ if (arr[i]<arr[j]){ i++;j++;count++; } }*/
            for (int i = 1; i < n-1; i++) { 
                int p = arr[i], q = arr[i - 1],k=arr[i+1];
                if (p == q && p==k) { 
                    count++;
                }
            }
            System.out.println(count);
        }
    }

[20200908193908824.png_pic_center]: /images/20221123/f5f73ffa5ed74d7eb7dc794a1fffec3a.png