小米2021校招笔试真题

1、矩阵相乘

【题目描述】
实现矩阵相乘函数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

【解题思路】
三层循环实现矩阵相乘操作即可。

【参考代码】
#include <stdio.h> 
#include <stdlib.h> 
#include <assert.h> 
#include <sys/time.h>
void matrix_multiply(int *A, int *B, int *C, int M, int K, int N) {
    int i = 0;
    int j = 0;
    int k = 0;
    for (i = 0; i < M; i++) {
        for (j = 0; j < N; j++) {
            int sum = 0;
            for (k = 0; k < K; k++) {
                sum += A[i * K + k] * B[k * N + j];
            }
            C[i * N + j] = sum;
        }
    }
}
void matrix_multiply_opt(int *A, int *B, int *C, int M, int K, int N) {
    int i = 0;
    int j = 0;
    int k = 0;
    for (k = 0; k < K; k++) {
        for (i = 0; i < M; i++) {
            int r = A[i * K + k];
            for (j = 0; j < N; j++) {
                C[i * N + j] += r * B[k * N + j];
            }
        }
    }
}
int main(int argc, char **argv) {
    int M, N, K;
    scanf("%d%d%d", &M, &K,
          &N); // printf("%d %d %d\n", M, N, K); assert(M>0 && M<=1000);
               // assert(N>0 && N<=1000); assert(K>0 && K<=1000);
    int *A = (int *)malloc(M * K * sizeof(int));
    int *B = (int *)malloc(K * N * sizeof(int));
    int *C = (int *)malloc(M * N * sizeof(int));
    int i = 0;
    while (i < M * K) {
        scanf("%d", &A[i]); // printf("%d ", A[i]); // if ((i+1)%K==0) { //
                            // printf("\n"); // } i++;
    }
    i = 0;
    while (i < K * N) {
        scanf("%d", &B[i]); // printf("%d ", B[i]); // if ((i+1)%N==0) { //
                            // printf("\n"); // } i++;
    }
    matrix_multiply_opt((int *)A, (int *)B, (int *)C, M, K, N);
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            printf("%d ", C[i * N + j]);
        }
        printf("\n");
    }
}

2、单词搜索

【题目描述】
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格,同一个单元格内的字母不允许被重复使用。
二维网格为：
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
输入描述：
需要查询的单词
输出描述：
true 代表单词存在，false表示不存在
输入样例：
SEE
输出样例：
true

【解题思路】
从搜索单词的第一个字母出发，从矩阵中匹配然后开始进行dfs搜索只到完全匹配为止。

【参考代码】
import java.util.Scanner;
import java.util.List;
i