1.5 小米2024校招笔试真题

1.5.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");

}

}

1.5.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;

import java.util.ArrayList;

public class Main {

private static boolean[][] visited;

private static int index = 0;

public static void main(String[] args) {

String line = in.nextLine();

if (!